An Attack on Small Private Keys of RSA Based on Euclidean Algorithm
In this paper, we describe an attack on RSA cryptosystem which is based on Euclid's algorithm. Given a public key $(n,e)$ with corresponding private key $d$ such that $e$ has the same order of magnitude as $n$ and one of the integers $k = (ed-1)/\phi(n)$ and $e-k$ has at most one-quarter as many bits as $e$, it computes the factorization of $n$ in deterministic time $O((\log n)^2)$ bit operations.