The invention of the Rivest–Shamir–Adleman (RSA) cryptosystem was a groundbreaking advancement in cryptography. While the RSA remains relevant in securing global communications and digital transactions, with widespread use in public parameter infrastructure (PKI) and secure online exchanges, its vulnerability to algebraic attacks must be addressed. In this paper, we propose an equation, thereby revealing its potential application in the factorization of the modulus $ N $. By introducing this equation, we demonstrate a method in the first attack named the continued fraction for recovering the primes $ p $ and $ q $ without necessitating the original $ \phi(N) $ used in the RSA encryption. The results were extended to the case where a condition exists such that multiple sets of public parameters were used against a constant private parameter. We retrieved the primes $ p_i's $ and $ q_i's $ of the moduli $ N_i $ via the lattice reduction technique. This breakthrough could potentially expose the prime factors while circumventing standard cryptographic barriers. Our findings open new possibilities for cryptographic analysis and challenge the presumed security of widely used RSA systems.
Citation: Nurul Nur Hanisah Adenan, Muhammad Rezal Kamel Ariffin, Wan Nur Aqlili Ruzai, Muhammad Asyraf Asbullah, Sook-Chin Yip, Terry Shue Chien Lau. New approach of factoring the RSA cryptosystem[J]. AIMS Mathematics, 2025, 10(7): 15512-15538. doi: 10.3934/math.2025696
The invention of the Rivest–Shamir–Adleman (RSA) cryptosystem was a groundbreaking advancement in cryptography. While the RSA remains relevant in securing global communications and digital transactions, with widespread use in public parameter infrastructure (PKI) and secure online exchanges, its vulnerability to algebraic attacks must be addressed. In this paper, we propose an equation, thereby revealing its potential application in the factorization of the modulus $ N $. By introducing this equation, we demonstrate a method in the first attack named the continued fraction for recovering the primes $ p $ and $ q $ without necessitating the original $ \phi(N) $ used in the RSA encryption. The results were extended to the case where a condition exists such that multiple sets of public parameters were used against a constant private parameter. We retrieved the primes $ p_i's $ and $ q_i's $ of the moduli $ N_i $ via the lattice reduction technique. This breakthrough could potentially expose the prime factors while circumventing standard cryptographic barriers. Our findings open new possibilities for cryptographic analysis and challenge the presumed security of widely used RSA systems.
| [1] |
R. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM., 21 (1978), 17–28. https://doi.org/10.1145/359340.359342 doi: 10.1145/359340.359342
|
| [2] |
M. J. Wiener, Cryptanalysis of short RSA secret exponents, IEEE Trans. Inf. Theory, 36 (1990), 553–558. https://doi.org/10.1109/18.54902 doi: 10.1109/18.54902
|
| [3] | D. Boneh, Twenty years of attacks on the RSA cryptosystem, Notices Amer. Math. Soc. 46 (1999), 203–213. |
| [4] |
H. M. Bahig, D. I. Nassr, M. A. Mahdi, H. M. Bahig Small private exponent attacks on RSA using continued fractions and multicore systems, Symmetry, 14 (2022), 1897. https://doi.org/10.3390/sym14091897 doi: 10.3390/sym14091897
|
| [5] | M. J. Hinek, On the security of some variants of RSA, Ph. D. thesis, Waterloo, 2007 |
| [6] |
S. Sarkar, Small secret exponent attack on RSA varian with modulus $N = p^rq$, Des. Codes Cryptogr., 73 (2014), 383–392. https://doi.org/10.1007/s10623-014-9928-6 doi: 10.1007/s10623-014-9928-6
|
| [7] | H. Kuwakado, K. Koyama, Y. Tsuruoka, A new RSA-type scheme based on singular cubic curves $y^2 = x^3+bx^2\mod{n}$, IEICE Trans. Fundam., E78–A (1995), 27–33. |
| [8] | N. Murru, F. M. Saettone, A novel RSA-like cryptosystem based on a generalization of the R'edei rational functions, In: J. Kaczorowski, J. Pieprzyk, J. Pomykała, Number-theoretic methods in cryptology, Springer, 2018. https://doi.org/10.1007/978-3-319-76620-1_6 |
| [9] | M. W. Bunder, A. Nitaj, W. Susilo, J. Tonien, A new attack on three variants of the RSA cryptosystem, In: J. K. Liu, R. Steinfeld, Information security and privacy, Springer, 2016,258–268. https://doi.org/10.1007/978-3-319-40367-0_16 |
| [10] |
M. W. Bunder, A. Nitaj, W. Susilo, J. Tonien, A generalized attack on RSA type cryptosystems, Theor. Comput. Sci., 704 (2017), 74–81. https://doi.org/10.1016/j.tcs.2017.09.009 doi: 10.1016/j.tcs.2017.09.009
|
| [11] | A. Nitaj, M. R. K. Ariffin, N. N. H. Adenan, N. A. Abu, Classical attacks on a variant of the RSA cryptosystem, In: P. Longa, C. Ràfols, Progress in Cryptology – LATINCRYPT 2021, 2021,151–167. https://doi.org/10.1007/978-3-030-88238-9_8 |
| [12] |
D. I. Nassr, M. Anwar, H. M. Bahig Improving small private exponent attack on the Murru-Saettone cryptosystem, Theor. Comput. Sci., 923 (2022), 222–234. https://doi.org/10.1016/j.tcs.2022.05.010 doi: 10.1016/j.tcs.2022.05.010
|
| [13] |
Y. Feng, A. Nitaj, Y. Pan, Partial prime factor exposure attacks on some RSA variants, Theor. Comput. Sci., 999 (2024), 114549. https://doi.org/10.1016/j.tcs.2024.114549 doi: 10.1016/j.tcs.2024.114549
|
| [14] | G. H. Hardy, E. M. Wright, An introduction to theory of numbers, Oxford University Press, 1979. https://doi.org/10.1093/oso/9780199219858.001.0001 |
| [15] | A. Nitaj, M. R. K. Ariffin, D. I. Nassr, H. M. Bahig, New Attacks on the RSA Cryptosystem, In: D. Pointcheval, D. Vergnaud, Progress in Cryptology – AFRICACRYPT 2014 2014,178–198. https://doi.org/10.1007/978-3-319-06734-6_12 |
| [16] |
W. N. A. Ruzai, A. Nitaj, M. R. K. Ariffin, Z. Mahad, M. A. Asbullah, Increment of insecure RSA private exponent bound through perfect square RSA diophantine parameters cryptanalysis, Comput. Stand. Interfaces, 80 (2022), 103584. https://doi.org/10.1016/j.csi.2021.103584 doi: 10.1016/j.csi.2021.103584
|
| [17] |
A. K. Lenstra, H. W. Lenstra, L. Lov'asz, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), 515–534. https://doi.org/10.1007/BF01457454 doi: 10.1007/BF01457454
|
| [18] | A. May, New RSA vulnerabilities using lattice reduction methods, Ph. D. thesis, University of Paderborn, North Rhine-Westphalia, Germany, 2003. |
| [19] | A. Nitaj, New weak RSA keys, JP J. Algebra Number Theory Appl. 23 (2011), 131–148. |
Nurul Nur Hanisah Adenan, Muhammad Rezal Kamel Ariffin, Wan Nur Aqlili Ruzai, Muhammad Asyraf Asbullah, Sook-Chin Yip, Terry Shue Chien Lau. New approach of factoring the RSA cryptosystem[J]. AIMS Mathematics, 2025, 10(7): 15512-15538. doi: 10.3934/math.2025696
DownLoad: