Volume 16 β’ Issue 1 β’ PP: 38-52 β’ 2025
A Constraint Satisfaction Approach for Estimating the RSA Prime Factors towards Known Bits Factorization Attacks
View PDF Abstract
The Rivest–Shamir–Adleman (RSA) cryptosystem is one of the most prevalently utilized public-key cryptographic systems in current practice. Prior investigations into vulnerabilities of this cryptosystem have concentrated on diminishing the complexity associated with the integer factorization challenge, which is integral to the RSA modulus, expressed as π=ππ. Possessing partial knowledge about the least significant digits (LSDs) of both p and q is a common assumption attacker’s advantage to enable the polynomial-time factorization of N, ultimately undermining the security of RSA. This paper presents a novel heuristic algorithm predicated on the Constraint Satisfaction Problem (CSP) principles, which estimates k-LSD pairs of the RSA prime factors, and . The proposed Generate and Test (GT) and Backtracking with Heuristic Variable Ordering (BHVO) solver guarantees polynomial-time factorization of known bits by iteratively refining candidate pairs and eliminating invalid combinations through effective constraint propagation. The proposed approach obviates the requirement for specialized hardware for side-channel attacks to reveal a portion of and . In our results, we have successfully estimated up to 5-LSDs of and with a reduced number of iterations and factored 2048 bits, N based on the known 4-LSDs of the prime in polynomial time. Our research lays the groundwork for factorization algorithms that require partial knowledge of the prime factors. We have highlighted the possible vulnerabilities linked to existing RSA key generation techniques. These may make RSA moduli susceptible to the attacks discussed in this study and proposed countermeasures to ensure secure prime generation.
Keywords
References
[1] R. Ranasinghe, M. Chathurangi, and P. Athukorala, “A novel improvement in RSA algorithm,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 27, no. 1, pp. 143–150, 2024, doi: 10.47974/JDMSC-1628.
[2] P. Cotan and G. TeΕeleanu, “A security analysis of two classes of RSA-like cryptosystems,” Journal of Mathematical Cryptology, vol. 18, no. 1, Jan. 2024, doi: 10.1515/jmc-2024-0013.
[3] D. Ramakrishna and M. A. Shaik, “A comprehensive analysis of cryptographic algorithms: Evaluating security, efficiency, and future challenges,” IEEE Access, pp. 1–1, 2024, doi: 10.1109/ACCESS.2024.3518533.
[4] E. A. Adeniyi, P. B. Falola, M. S. Maashi, M. Aljebreen, and S. Bharany, “Secure sensitive data sharing using RSA and ElGamal cryptographic algorithms with hash functions,” Information (Switzerland), vol. 13, no. 10, Oct. 2022, doi: 10.3390/info13100442.
[5] A. Overmars and S. Venkatraman, “Continued fractions applied to the one line factoring algorithm for breaking RSA,” Journal of Cybersecurity and Privacy, vol. 4, no. 1, pp. 41–54, Mar. 2024, doi: 10.3390/jcp4010003.
[6] S. Pochu, S. Rama, and K. Nersu, “Cybersecurity in the era of quantum computing: Challenges and solutions,” 2022.
[7] A. Montina and S. Wolf, “An algebraic-geometry approach to prime factorization,” Sep. 2022, [Online]. Available: http://arxiv.org/abs/2209.11650
[8] M. Zheng, Z. Chen, and Y. Wu, “Solving generalized bivariate integer equations and its application to factoring with known bits,” IEEE Access, vol. 11, pp. 34674–34684, 2023, doi: 10.1109/ACCESS.2023.3264590.
[9] B. Harjito, H. N. Tyas, E. Suryani, and D. W. Wardani, “Comparative analysis of RSA and NTRU algorithms and implementation in the cloud,” International Journal of Advanced Computer Science and Applications, vol. 13, no. 3, p. 2022, 2022, doi: 10.14569/IJACSA.2022.0130321.
[10] Y. Yarom, D. Genkin, and N. Heninger, “CacheBleed: A timing attack on OpenSSL constant-time RSA,” J. Cryptogr. Eng., vol. 7, no. 2, pp. 99–112, Jun. 2017, doi: 10.1007/s13389-017-0152-y.
[11] P. Singh, P. Pranav, and S. Dutta, “Optimizing cryptographic protocols against side-channel attacks using WGAN-GP and genetic algorithms,” Sci. Rep., vol. 15, no. 1, p. 2130, Jan. 2025, doi: 10.1038/s41598-025-86118-4.
[12] C. Luo, Y. Fei, and D. Kaeli, “Side-channel timing attack of RSA on a GPU,” ACM Trans. Archit. Code Optim., vol. 16, no. 3, Aug. 2019, doi: 10.1145/3341729.
[13] H. Ferradi, R. Géraud, S. Guilley, D. Naccache, and M. Tibouchi, “Recovering secrets from prefix-dependent leakage,” Journal of Mathematical Cryptology, vol. 14, no. 1, pp. 15–24, Jan. 2020, doi: 10.1515/jmc-2015-0048.
[14] A. S. Chandran, “Review on cryptography and network security zero knowledge technique in blockchain technology,” International Journal of Information Security and Privacy, vol. 16, no. 2, 2022, doi: 10.4018/IJISP.308306.
[15] R. L. Rivest and A. Shamir, “Efficient factoring based on partial information,” in Advances in Cryptology—EUROCRYPT’ 85, vol. 219, Berlin, Heidelberg: Springer Berlin Heidelberg, 1986, pp. 31–34, doi: 10.1007/3-540-39805-8_3.
[16] D. Coppersmith, “Finding a small root of a bivariate integer equation; factoring with high bits known,” vol. 1070, Springer, Berlin, Heidelberg, 1996, pp. 178–189, doi: 10.1007/3-540-68339-9_16.
[17] M. Herrmann and A. May, “Solving linear equations modulo divisors: On factoring given any bits,” Springer, Berlin, Heidelberg, 2008, pp. 406–424, doi: 10.1007/978-3-540-89255-7_25.
[18] N. Heninger and H. Shacham, “Reconstructing RSA private keys from random key bits,” Springer: Berlin/Heidelberg, Germany, 2009, pp. 1–17, doi: 10.1007/978-3-642-03356-8_1.
[19] S. Maitra, S. Sarkar, and S. Sen Gupta, “Factoring RSA modulus using prime reconstruction from random known bits,” Progress in Cryptology—AFRICACRYPT 2010, pp. 82–99, 2010, doi: 10.1007/978-3-642-12678-9_6.
[20] A. H. Abd Ghafar, M. R. Kamel Ariffin, and M. A. Asbullah, “A new LSB attack on special-structured RSA primes,” Symmetry (Basel), vol. 12, no. 5, May 2020, doi: 10.3390/SYM12050838.
[21] A. H. Abd Ghafar, M. R. Kamel Ariffin, and M. A. Asbullah, “A new LSB attack on special-structured RSA primes,” Symmetry (Basel), vol. 12, no. 5, May 2020, doi: 10.3390/SYM12050838.
[22] E. Barker, “Recommendation for key management part 1: General,” Gaithersburg, MD, Jan. 2016, doi: 10.6028/NIST.SP.800-57pt1r4.
[23] J. Zhang et al., “A survey for solving mixed integer programming via machine learning,” Neurocomputing, vol. 519, pp. 205–217, Jan. 2023, doi: 10.1016/j.neucom.2022.11.024.
[24] Y. Xu, D. Stern, and H. Samulowitz, “Learning adaptation to solve constraint satisfaction problems,” in Proceedings of Learning and Intelligent Optimization (LION), p. 14, 2009.
[25] Z. Yang, A. Ishay, and J. Lee, “Learning to solve constraint satisfaction problems with recurrent transformer,” Jul. 2023, [Online]. Available: http://arxiv.org/abs/2307.04895
Cite This Article
Choose your preferred format