Abstract
RSA is a significant cryptographic technique depending on public key cryptography. In fact, if this technique does not have any vulnerabilities, it is considered as a robust algorithm. Nevertheless, if the system contains vulnerabilities, it can be compromised through the utilization of algorithms that target those weaknesses. Currently, RSA is vulnerable to multiple potential weaknesses. This research identifies a novel vulnerability in RSA and presents a technique to exploit this vulnerability. The proposed method, known as Common Prime Attack (CPA), aims to exploit this vulnerability to recover the original message. The vulnerability arises when at least two key producers generate their modulus that inadvertently have at least one prime factor in common. It is divided into three cases. Case 1 relates to two moduli created from two prime numbers, with one prime being common. Case 2 involves the two moduli generated from at least three primes, with one prime common to both values. Case 3 concerns two moduli produced from at least three primes, with a minimum of two primes in common. The evidence and examples show that all situations can effectively retrieve the original message. The datasets have been generated to support three cases in which each modulus shares a common prime factor. Therefore, the experimental results demonstrate that all situations can rapidly compromise RSA with modulus lengths of 1024, 2048 and 4096 bits. CPA can successfully recover plaintexts in all cases, with a 100% success rate under simulated conditions. Moreover, the average computation time is extremely low, ranging from 1.6 ms to 17.2 ms. Because of the large bit length of the modulus, other methods are not suitable for comparison with the proposed method in terms of computational time. In addition, they require a significant amount of time to execute. However, CPA will instead be compared to other algorithms with respect to security aspects. In conclusion, all generated moduli must be mutually coprime to avoid vulnerabilities associated with CPA.
References
M. Hellman, An extension of the Shannon theory approach to cryptography. IEEE Transactions on Information Theory, 23(3) (1977), 289–294, https://doi.org/10.1109/TIT.1977.1055709.
G.J. Simmons, Symmetric and Asymmetric Encryption. ACM Computing Surveys, 11(4) (1979), 305–330, https://doi.org/10.1145/356789.356793.
D. Coppersmith, D.B. Johnson, S.M. Matyas, A proposed mode for triple-DES encryption. IBM Journal of Research and Development, 40(2) (1996), 253–262, https://doi.org/10.1147/rd.402.0253.
C. Sanchez-Avila, R. Sanchez-Reillol, The Rijndael block cipher (AES proposal): a comparison with DES, In Proceedings of IEEE 35th Annual 2001 international carnahan conference on security technology, October 16–19, 2001, United Kingdom: IEEE, pp. 229–234, https://doi.org/10.1109/CCST.2001.962837.
S. Mangard, M. Aigner, S. Dominikus, A highly regular and scalable AES hardware architecture. IEEE Transactions on Computers, 52(4) (2003), 483–491, https://doi.org/10.1109/TC.2003.1190589.
W. Diffie, M. Hellman, New directions in cryptography. IEEE Transactions on Information Theory, 22(6) (1976), 644–654, https://doi.org/10.1109/TIT.1976.1055638.
R. L. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2) (1978), 120–126, https://doi.org/10.1145/359340.359342.
K. Somsuk, M. Thakong, Authentication system for e-certificate by using RSA’s digital signature. TELKOMNIKA Telecommunication, Computing, Electronics and Control, 18(6) (2020), 2948–2955, https://doi.org/10.12928/TELKOMNIKA.v18i6.17278.
K. Somsuk, S. Atsawaraungsuk, C. Suwannapong, S. Khummanee, C. Sanemueang, The Variant of Digital Signature Algorithm for Constant Message. Journal of Internet Services and Information Security, 13(2) (2023), 81–95, https://doi.org/10.58346/JISIS.2023.I2.005.
M.E. Wu, R. Tso, H.M. Sun, On the improvement of Fermat factorization using a continued fraction technique, Future Generation Computer Systems, 30(1) (2014), 162–168, https://doi.org/10.1016/j.future.2013.06.008.
R.R.M. Tahir, M.A. Asbullah, M.R.K. Ariffin, Z. Mahad, Determination of a Good Indicator for Estimated Prime Factor and Its Modification in Fermat’s Factoring Algorithm. Symmetry, 13(5) (2021), 1–22, https://doi.org/10.3390/sym13050735.
J.M. Pollard, Theorems of factorization and primality testing. Math. Proc. Camb. Philos. Soc., 76 (1974), 521–528, https://doi.org/10.1017/S0305004100049252.
K. Somsuk, An efficient variant of Pollard’s p −
for the case that all prime factors of the p −
in B-Smooth. Symmetry, 14(2) (2022), 312, https://doi.org/10.3390/sym14020312.
F.O. Mojisola, S. Misra, C.F. Febisola, O. Abayomi-Alli, G. Sengul, An improved random bit-stuffing technique with a modified RSA algorithm for resisting attacks in information security (RBMRSA). Egyptian Informatics Journal, 23(2) (2022), 291–301, https://doi.org/10.1016/j.eij.2022.02.001.
G.C. Kim, S.C. Li, H.C. Hwang, Fast rebalanced RSA signature scheme with typical prime generation. Theoretical Computer Science, 830–831 (2020), 1–19, https://doi.org/10.1016/j.tcs.2020.04.024.
A. Abubakar, S. Jabaka, B. I. Tijjani, A. Zeki, H. Chiroma, M. J. Usman, S. Raji, M. Mahmud, Cryptanalytic Attacks on Rivest, Shamir, and Adleman (RSA) Cryptosystem: Issues and Challenges. Journal of Theoretical and Applied Information Technology, 61(1) (2014), 1–7.
I. K. Salah, A. Darwish, S. Oqeili, Mathematical Attacks on RSA Cryptosystem. Journal of Computer Science, 2(8) (2006), 665–671, https://doi.org/10.3844/jcssp.2006.665.671.
D. Boneh, Twenty Years of Attacks on the RSA Cryptosystem. Notices of the AMS, 46(2) (2006), 203–213.
N. Lal, A. P. Singh and S. Kumar, Modified trial division algorithm using KNJ-factorization method to factorize RSA public key encryption, In Proceedings of International Conference on Contemporary Computing and Informatics, November 27–29, 2014, India: IEEE, pp. 992–995, https://doi.org/10.1109/IC3I.2014.7019588.
K. Somsuk, T. Chiawchanwattana and C. Sanemueang, Estimating the new Initial Value of Trial Division Algorithm for Balanced Modulus to Decrease Computation Loops, In Proceedings of International Joint Conference on Computer Science and Software Engineering, July 10–12, 2019, Thailand: IEEE, pp. 143–147, https://doi.org/10.1109/JCSSE.2019.8864218.
K. Somsuk, The new integer factorization algorithm based on fermat’s factorization algorithm and euler’s theorem. Int J Electr Comput Eng, 10(2) (2020), 1469–1476, https://doi.org/10.11591/ijece.v10i2.
K. Somsuk, K. Tientanopajai, An Improvement of Fermat’s Factorization by Considering the Last m Digits of Modulus to Decrease Computation Time. Int. J. Netw. Secur., 19(1) (2017), 99–111, https://doi.org/10.6633/IJNS.201701.19(1).11.
J.M. Pollard, Monte Carlo methods for index computation (modp
). Mathematics of computation, 32(143) (1978), 918–924, https://doi.org/10.2307/2006496.
M. Wiener, Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory, 36 (1990), 553–558, https://doi.org/10.1109/18.54902.
P. Sharma, A.K. Gupta, A.Vijay, Modified Integer Factorization Algorithm using V-Factor Method, In Proceedings of International Conference on Advanced Computing & Communication Technologies, January 7–8, 2012, India: IEEE, pp. 423–425, https://doi.org/10.1109/ACCT.2012.73.
H. W. Lenstra Jr., Factoring integers with elliptic curves. Annals of Mathematics, 126(3) (1987), 649–673, https://doi.org/10.2307/1971363.
N. Koblitz, Elliptic Curve Cryptosystems. Mathematics of Computation, 48 (1987), 203–209, http://dx.doi.org/10.1090/S0025-5718-1987-0866109-5.
V.S. Miller, Uses of elliptic curves in cryptography. Lecture Notes in Computer Science, 218 (1986), 417–428, https://doi.org/10.1007/3-540-39799-X_31.
R. D. Silverman, The multiple polynomial quadratic sieve. Mathematics of Computation, 48(1777) (1987), 329–339, https://doi.org/10.1090/s0025-5718-1987-0866119-8.
T. Kleinjung, On polynomial selection for the general number field sieve. Mathematics of Computation, 75(256) (2006), 2037–2047, https://doi.org/10.1090/S0025-5718-06-01870-9.
S.M. Yen, S. Kim, S. Lim, S.J. Moon, RSA speedup with Chinese remainder theorem immune against hardware fault cryptanalysis. IEEE Transactions on computers, 52(4) (2003), 461–472, https://doi.org/10.1109/TC.2003.1190587.
L. Harn, M. Fuyou, C.C. Chang, Verifiable secret sharing based on the Chinese remainder theorem. Security and Communication Networks, 7(6) (2014), 950–957, https://doi.org/10.1002/sec.807.
K. Somsuk, A New Methodology to Find Private Key of RSA Based on Euler Totient Function. Symmetry, 18(2) (2021), 338–348, http://dx.doi.org/10.21123/bsj.2021.18.2.0338.
K. Somsuk, The Improved Estimation of the Least Upper Bound to Search for RSA’s Private key. KSII Transactions on Internet and Information Systems, 16(6) (2022), 2074–2093, http://doi.org/10.3837/tiis.2022.06.016.
D. Poulakis, An application of Euclidean algorithm in cryptanalysis of RSA. Elemente der Mathematik, 75(3) (2020), 114–120, https://doi.org/10.4171/EM/411.
M. Prybylo, S. Haghighi, S.T. Peddinti and S. Ghanavati, Evaluating privacy perceptions, experience, and behavior of software development teams, In Proceedings of the Twentieth USENIX Conference on Usable Privacy and Security, August 11–13, 2024, Philadelphia, PA, USA: pp. 101–120, https://dl.acm.org/doi/10.5555/3696899.3696905.
H.M. Arjomandi, M. Khalooei and M. Amirmazlaghani, Low-epsilon adversarial attack against a neural network online image stream classifier. Applied Soft Computing, 147 (2023), 110760, https://doi.org/10.1016/j.asoc.2023.110760.
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Copyright (c) 2025 Journal of Cyber Security and Mobility