RSA and a higher degree diophantine equation.
Abderrahmane Nitaj · 2006
Abstract. Let N = pq be an RSA modulus where p, q are large primes of the same bitsize. We study the class of the public exponents e for which there exist an integer m with 1 ≤ m ≤ and small integers u, X, Y and Z satisfying log N log 32 (e + u)Y m − ψ(N)X m = Z, where ψ(N) = (p + 1)(q − 1). First we show that these exponents are of improper use in RSA cryptosystems. Next we show that their number is at least O mN 1 2 + α m −α−ε” where α is defined by N 1−α = ψ(N). 1