Cryptology ePrint Archive: Report 2019/283

An Attack on Small Private Keys of RSA Based on Euclidean Algorithm

Dimitrios Poulakis

Abstract: 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.

Category / Keywords: public-key cryptography / RSA cryptosystem ; Euclid’s algorithm ; Integer factorization

Date: received 2 Mar 2019, last revised 10 May 2019

Contact author: poulakis at math auth gr

Available format(s): PDF | BibTeX Citation

Version: 20190510:085913 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]