@article{Ruzai2024, 
author = {Wan Nur Aqlili Ruzai and You Ying and Khairun Nisak Muhammad and Muhammad Asyraf Asbullah and Muhammad Rezal Kamel Ariffin},
title = {Concurrent factorization of RSA moduli via weak key equations},
year = {2024},
journal = {AIMS Mathematics},
volume = {9},
number = {10},
pages = {28211-28231},
keywords = {asymmetric cryptography, RSA, Diophantine approximations, lattice cryptanalysis, continued fractions},
url = {https://www.sciopen.com/article/10.3934/math.20241368},
doi = {10.3934/math.20241368},
abstract = {The Rivest-Shamir-Adleman (RSA) algorithm is a widely utilized technique in asymmetric cryptography, primarily for verifying digital signatures and encrypting messages. Its security relies on the integer factorization problem's difficulty, which is computationally infeasible with large security parameters. However, this study revealed scenarios where an attacker can concurrently factorize multiple RSA moduli  Ni=piqi under specific conditions. The attack is feasible when the attacker possesses a set of RSA key pairs with certain flaws, allowing each  Ni to be factored in polynomial time. We identified vulnerabilities in RSA keys that satisfy particular equations by applying Diophantine approximation and Coppersmith's lattice-based technique. For instance, the study demonstrates that if RSA public exponents  ei and moduli  Ni adhere to  eir−(Ni−pi−qi+ui)si=ti, where  r,si,ui, and  ti are small integers, then all  Ni can be factorized simultaneously. Additionally, another vulnerability arises when RSA parameters satisfy  eiri−s(Ni−pi−qi+ui)=ti, enabling concurrent factorization with small integers  s,ri,ui, and  ti. This research expands the understanding of RSA security by identifying specific conditions under which RSA public-key pairs can be compromised. These findings are relevant to the broader field of cryptography and the ongoing efforts to secure communication systems against sophisticated adversaries.}
}