An application of Euclidean algorithm in cryptanalysis of RSA (Q827545)

Summary: In this paper, we have presented a new attack on the RSA cryptosystem based only on the extended Euclid algorithm. It computes the factorization of \(n\) in deterministic \(O((\log n)^2)\) bit operations, in the case where the public exponente has the same order of magnitude as \(n\) and one of the integer \(sk=(ed-1)/ \phi (n)\) and \(e-k\) has at most one-quarter as many bits as \(e\). Comparing with Wiener's classical attack and its presentation as a bivariate linear equation problem, our attack is quite simpler, since it avoids the use of continuous fractions and lattices. Its efficiency is comparable to that of Wiener's attack,and its time complexity the same as that of the solution of the corresponding bivariate linear equation problem but better than that of the classical Wiener attac.