A New Class of Weak Encryption Exponents in RSA

Consider RSA with N = pq, q < p < 2q, public encryption exponent e and private decryption exponent d. We concentrate on the cases when e(= N-alpha) satisfies eX-ZY = 1, given vertical bar N-Z vertical bar = N-tau. Using the idea of Boneh and Durfee (Eurocrypt 1999, IEEE-IT 2000) we show that the LLL algorithm can be efficiently applied to get Z when vertical bar Y vertical bar = N-gamma and gamma < 4 alpha tau (1/4 tau + 1/12 alpha - root(1/4 tau + 1/12 alpha)(2) + 1/2 alpha tau (1/12 + tau/24 alpha - alpha/8 tau)). This idea substantially extends the class of weak keys presented by Nitaj (Africacrypt 2008) when Z = psi(p,q,u,v) = (p - u)(q - v). Further, we consider Z = psi(p, q, u, v) = N - pu - v to provide a new class of weak keys in RSA. This idea does not require any kind of factorization as used in Nitaj's work. A very conservative estimate for the number of such weak exponents is N0.75-epsilon, where epsilon > 0 is arbitrarily small for suitably large N.