Alex May, Paderborn, speaks on:
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.