New simultaneous Diophantine attacks on generalized RSA key equations

Abstract

RSA stands as a widely adopted method within asymmetric cryptography, commonly applied for digital signature validation and message encryption. The security of RSA relies on the challenge of integer factorization, a problem considered either computationally infeasible or highly intricate, especially when dealing with sufficiently large security parameters. Effective exploits of the integer factorization problem in RSA can allow an adversary to assume the identity of the key holder and decrypt such confidential messages. The keys employed in secure hardware are particularly significant due to the typically greater value of the information they safeguard, such as in the context of securing payment transactions. In general, RSA faces various attacks exploiting weaknesses in its key equations. This paper introduces a new vulnerability that enables the concurrent factorization of multiple RSA moduli. By working with pairs (Ni,ei) and a fixed value y satisfying the Diophantine equation eixi2−y2ϕ(Ni)=zi, we successfully factorized these moduli simultaneously using the lattice basis reduction technique. Notably, our research expands the scope of RSA decryption exponents considered as insecure.

Keywords

• Public-key cryptography
• RSA cryptosystem
• Integer factorization problem
• Diophantine approximations
• Coppersmith’s method
• Lattice reduction