Journal of Cybersecurity and Information Management JCIM 2690-6775 2769-7851 10.54216/JCIM https://www.americaspg.com/journals/show/3589 2019 2019 Department of Computer Science and Informatics, University of Energy and Natural Resources, Sunyani, Ghana Daniel Daniel Department of Computer Science and Informatics, University of Energy and Natural Resources, Sunyani, Ghana Patrick Kwabena Mensah Department of Information Technology and Decision Sciences, University of Energy and Natural Resources, Sunyani, Ghana Peter Appiahene Department of Computer Science and Informatics, University of Energy and Natural Resources, Sunyani, Ghana Peter Nimbe 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. 2025 2025 38 52 10.54216/JCIM.160104 https://www.americaspg.com/articleinfo/2/show/3589