The Rivest–Shamir–Adleman (RSA) cryptosystem remains one of the most widely used public-key mechanisms, with its security depending on the computational difficulty of factoring a large composite modulus $ N $ generated from two primes. Previous studies have shown that RSA becomes vulnerable when its prime factors follow special algebraic structures or when partial information about their least significant bits (LSBs) is exposed. Earlier work demonstrated that primes close to perfect powers allow efficient reconstruction of the modulus when several LSBs of both primes are known. In this paper, we extended this line of research by examining three additional near-square prime structures in which the primes are slightly different, either positively or negatively shifted from their base-power forms. For each structure, we obtained analytical bounds that relate the difference to the square-root proximity of the modulus, and we presented polynomial-time algorithms that recover the prime factors when only a small number of their LSBs are leaked. Numerical experiments confirmed the practicality of the proposed methods. Our results broaden the class of RSA moduli susceptible to LSB-based partial key-exposure attacks and highlight the importance of strengthened key-generation strategies to avoid such structured primes.
Citation: Priscilla Kyle Payne, Wan Nur Aqlili Ruzai, Amir Hamzah Abd Ghafar, Muhammad Asyraf Asbullah, Muhammad Rezal Kamel Ariffin. Extending LSB-based partial key exposure to RSA with special-structured primes[J]. AIMS Mathematics, 2026, 11(2): 4902-4934. doi: 10.3934/math.2026201
The Rivest–Shamir–Adleman (RSA) cryptosystem remains one of the most widely used public-key mechanisms, with its security depending on the computational difficulty of factoring a large composite modulus $ N $ generated from two primes. Previous studies have shown that RSA becomes vulnerable when its prime factors follow special algebraic structures or when partial information about their least significant bits (LSBs) is exposed. Earlier work demonstrated that primes close to perfect powers allow efficient reconstruction of the modulus when several LSBs of both primes are known. In this paper, we extended this line of research by examining three additional near-square prime structures in which the primes are slightly different, either positively or negatively shifted from their base-power forms. For each structure, we obtained analytical bounds that relate the difference to the square-root proximity of the modulus, and we presented polynomial-time algorithms that recover the prime factors when only a small number of their LSBs are leaked. Numerical experiments confirmed the practicality of the proposed methods. Our results broaden the class of RSA moduli susceptible to LSB-based partial key-exposure attacks and highlight the importance of strengthened key-generation strategies to avoid such structured primes.
| [1] |
R. L. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, 21 (1978), 120–126. https://doi.org/10.1145/359340.359342 doi: 10.1145/359340.359342
|
| [2] | R. Crandall, R. Pomerance, Prime numbers: a computational perspective, 2 Eds., Springer, 2006. https://doi.org/10.1007/0-387-28979-8 |
| [3] |
J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc., 76 (1974), 521–528. https://doi.org/10.1017/S0305004100049252 doi: 10.1017/S0305004100049252
|
| [4] |
H. W. Lenstra, Factoring integers with elliptic curves, Ann. Math., 126 (1987), 649–673. https://doi.org/10.2307/1971363 doi: 10.2307/1971363
|
| [5] | D. Coppersmith, Finding a small root of a bivariate integer equation; factoring with high bits known, In: U. Maurer, Advances in cryptology—EUROCRYPT '96, Springer, 1996,178–189. https://doi.org/10.1007/3-540-68339-9_16 |
| [6] | A. H. A. Ghafar, M. R. K. Ariffin, M. A. Asbullah, A new attack on special-structured RSA primes, Malays. J. Math. Sci., 13 (2019), 111–125. |
| [7] |
A. H. A. Ghafar, M. R. K. Ariffin, M. A. Asbullah, A new LSB attack on special-structured RSA primes, Symmetry, 12 (2020), 838. https://doi.org/10.3390/sym12050838 doi: 10.3390/sym12050838
|
| [8] |
W. N. A. Ruzai, A. H. A. Ghafar, N. R. Salim, M. R. K. Ariffin, On (unknowingly) using near-square RSA primes, Symmetry, 14 (2022), 1898. https://doi.org/10.3390/sym14091898 doi: 10.3390/sym14091898
|
| [9] | R. L. Rivest, A. Shamir, Efficient factoring based on partial information, In: H. C. Williams, Advances in cryptology—CRYPTO'85, Springer, 1985, 31–34. https://doi.org/10.1007/3-540-39805-8_3 |
| [10] |
D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology, 10 (1997), 233–260. https://doi.org/10.1007/s001459900030 doi: 10.1007/s001459900030
|
| [11] | M. Herrmann, A. May, Solving linear equations modulo divisors: on factoring given any bits, In: J. Pieprzyk, Advances in cryptology-ASIACRYPT 2008, Springer, 2008,406–424. https://doi.org/10.1007/978-3-540-89255-7_25 |
| [12] | N. Heninger, H. Shacham, Reconstructing RSA private keys from random key bits, In: S. Halevi, Advances in cryptology-CRYPTO 2009, Springer, 2009, 1–17. https://doi.org/10.1007/978-3-642-03356-8_1 |
| [13] | J. Blömer, A. May, New partial key exposure attacks on RSA, In: D. Boneh, Advances in cryptology-CRYPTO 2003, Springer, 2003, 27–43. https://doi.org/10.1007/978-3-540-45146-4_2 |
| [14] | M. Ernst, E. Jochemsz, A. May, B. de Weger, Partial key exposure attacks on RSA up to full size exponents, In: R. Cramer, Advances in cryptology—EUROCRYPT 2005, Springer, 2005,371–386. https://doi.org/10.1007/11426639_22 |
| [15] | C. Patsakis, Recovering RSA private keys on implementations with tampered LSBs, Proceedings of the 10th International Conference on Security and Cryptography (SECRYPT 2013), 2013,453–460. https://doi.org/10.5220/0004534904530460 |
| [16] |
A. Takayasu, N. Kunihiro, Partial key exposure attacks on RSA: achieving the Boneh–Durfee bound, Theor. Comput. Sci., 761 (2018), 51–77. https://doi.org/10.1016/j.tcs.2018.08.021 doi: 10.1016/j.tcs.2018.08.021
|
| [17] |
K. Suzuki, A. Takayasu, N. Kunihiro, Extended partial key exposure attacks on RSA: improvement up to full size decryption exponents, Theor. Comput. Sci., 841 (2020), 62–83. https://doi.org/10.1016/j.tcs.2020.07.004 doi: 10.1016/j.tcs.2020.07.004
|
| [18] |
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
|
Priscilla Kyle Payne, Wan Nur Aqlili Ruzai, Amir Hamzah Abd Ghafar, Muhammad Asyraf Asbullah, Muhammad Rezal Kamel Ariffin. Extending LSB-based partial key exposure to RSA with special-structured primes[J]. AIMS Mathematics, 2026, 11(2): 4902-4934. doi: 10.3934/math.2026201
DownLoad: