New Attacks on RSA with Small Secret CRT-Exponents

Speaker: Dr Daniel Bleichenbacher , Bell Labs


It is well-known that there is an efficient method for decrypting/signing with RSA when the secret exponent d is small modulo p-1 and q-1. We call such an exponent d a small CRT-exponent. It is one of the major open problems in attacking RSA whether there exists a polynomial time attack for small CRT-exponents, i.e. a result that can be considered as an equivalent to the Wiener and Boneh-Durfee bound for small d. At Crypto 2002, May presented a partial solution in the case of an RSA modulus N=pq with unbalanced prime factors p and q. In this talk we present two imporoved algorithms for breaking RSA with small CRT-exponents.