Cryptanalysis of RSA with a small parameter revisited

• In short exponent RSA, decrypt and encrypt exponents are both short, then k is the smallest parameter. In this paper, we investigate a birthday attack to recover k, then factor RSA modulus N. This work improves the research of Meng and Zheng at ACISP 2012.
• Our result again shows that if there is a small parameter (other than d) in RSA equation, the RSA scheme may become vulnerable. Our algorithm is based on baby-step giant-step method. We also give a detail explanation on how the baby-step giant-step method works.

Let N=pqN=pq be an RSA modulus with balanced primes p and q. Suppose that the public exponent e and private exponent d   satisfy ed−1=kϕ(N)ed−1=kϕ(N). We revisit the birthday attack against short exponent RSA proposed by Meng and Zheng at ACISP 2012. We show that if e>k(p+q), then N   can be factored in both time and space complexity of O˜(k). This improves the former result. We also give a detail explanation on how the baby-step giant-step method works.