A New Generalized Attack on RSA-Like Cryptosystems

Rivest, Shamir, and Adleman published the RSA cryptosystem in 1978, which has been widely used over the last four decades. The security of RSA is based on the difficulty of factoring large integers N=pq, where p and q are prime numbers. The public exponent e and the private exponent d are related by the equation ed-k(p-1)(q-1)=1. Recently, Cotan and Teşeleanu (NordSec 2023) introduced a variant of RSA, where the public exponent e and the private exponent d satisfy the equation ed-k(pⁿ-1)(qⁿ-1)=1 for some positive integer n. In this paper, we study the general equation eu-(pⁿ-1)(qⁿ-1)v=w with positive integers u and v, and w∈Z. We show that, given the public parameters N and e, one can recover u and v and factor the modulus N in polynomial time by combining continued fractions with Coppersmith’s algorithm which relies on lattice reduction techniques, under specific conditions on u, v, and w. Furthermore, we show that if the private exponent d in an RSA-like cryptosystem is either small or too large, then N can be factored in polynomial time. This attack applies to the standard RSA cryptosystem.