Abstract:
As a rule, large secret exponents are used in practical realizations of RSA cryptosystem with modulus $N=pq$. Nevertheless, there are many theoretical results on the cryptanalysis of RSA system with a small secret exponent. A method suggested by Dujella recovers secret exponents $d<DN^{0.25}$ with a run-time complexity $O(D\ln D)$ and space complexity $O(D)$. Weger have suggested an attack on the secret exponents $d<\frac{N^{0.75}}{p-q}$. We describe a generalization of the Dujella method to attack the exponents $d<D\frac{N^{0.75}}{p-q}$ with run-time complexity $O(D\ln D)$ and space complexity $O(D)$.