New RSA Vulnerabilities using Coppersmith's Method

-------------------------------------------------------------------

In 1996, Don Coppersmith proposed a method for finding small solutions of polynomial equations. This method in turn is based on the famous LLL lattice reduction algorithm of Lenstra, Lenstra and Lovasz. The talk gives a brief introduction to Coppersmith's method and shows new applications for the RSA cryptosystem:

1. Partial Key Exposure Attacks on RSA: Assume an attacker succeeds to obtain a fraction of the bits of the secret key d. How many of the bits does he need in order to find the entire secret key? With the help of Coppersmith's method, one can construct polynomial time algorithms that find the entire key using only a fraction of the secret key bits, provided that the public key e is not too large.

2. A Generalized Wiener Attack: In 1990, Wiener showed that small RSA secret keys d < N^0.25 yield the factorization of the RSA-modulus N in polynomial time. Using Coppersmith's method, one can extend this attack to secret keys of the form d=d1/d2 modulo phi(N) with small d1 and d2.

3. Computing d vs. Factoring: One can show that the problem of computing the RSA secret key is deterministic polynomial time equivalent to the problem of factoring the RSA-modulus N.