A Constraint Satisfaction Approach for Estimating the RSA Prime Factors towards Known Bits Factorization Attacks

Daniel Asiedu^1,*, Patrick Kwabena Mensah¹, Peter Appiahene², Peter Nimbe¹

¹Department of Computer Science and Informatics, University of Energy and Natural Resources, Sunyani, Ghana

²Department of Information Technology and Decision Sciences, University of Energy and Natural Resources, Sunyani, Ghana

Emails: daniel.asiedu.stu@uenr.edu.gh; patrick.mensah@uenr.edu.gh; peter.appiahene@uenr.edu.gh; peter.nimbe@uenr.edu.gh

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: RSA cryptosystem; Constraint satisfaction problem; key exposure attacks; Factorization attacks; Cryptography; Attack mitigation