Abstract

Lattice-based cryptanalysis has become one of the most powerful tools for evaluating the security of the RSA cryptosystem. Most existing attacks rely on the classical key equation ed−kφ(N)=1 and are effective mainly when the decryption exponent is sufficiently small or when significant information about the RSA prime factors is available. However, the dependence on this classical equation restricts the applicability of existing attacks and limits the range of weak exponents that can be targeted. In this paper, we propose a generalized lattice-based technique for solving the extended key equation er−xφ(N)=s when an approximation of one of the RSA primes is known and the parameters r, x, and s are suitably small. By transforming this relation into an appropriate modular equation and applying Coppersmith’s method, we derive conditions under which the RSA modulus can be factored in polynomial time, even when the corresponding private exponent is large. Our analysis encompasses several well-known attacks as special cases and significantly enlarges the class of vulnerable RSA exponents. Consequently, the proposed framework remains effective in settings where classical lattice-based approaches are no longer applicable.

IPC Classification

Keywords