**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: **ia.cr/2019/283

[ Cryptology ePrint archive ]