A Generalized Wiener Attack on RSA

We present an extension of Wiener’s attack on small RSA secret decryption exponents [10]. Wiener showed that every RSA public key tuple (N,e) with $e \in {\mathbb{Z}}_{\phi(N)}^*$ that satisfies ed − 1 = 0 mod φ(N) for some $d<\frac 1 3 N^{\frac 1 4}$ yields the factorization of N=pq. Our new method finds p and q in polynomial time for every (N,e) satisfying ex + y = 0 mod φ(N) with $$ x < \frac 1 3 N^{\frac 1 4} \quad \textrm{and} \quad |y| = {\cal O}(N^{- \frac 3 4}ex). $$ In other words, the generalization works for all secret keys d= – xy− 1, where x, y are suitably small. We show that the number of these weak keys is at least $N^{\frac 3 4-\epsilon}$ and that the number increases with decreasing prime difference p-q. As an application of our new attack, we present the cryptanalysis of an RSA-type scheme presented by Yen, Kim, Lim and Moon [11,12]. Our results point out again the warning for crypto-designers to be careful when using the RSA key generation process with special parameters.