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

Dimitrios Poulakis

Paper 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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: RSA cryptosystem Euclid’s algorithm Integer factorization
Contact author(s): poulakis @ math auth gr
History: 2019-05-10: revised; 2019-03-16: received; See all versions
Short URL: https://ia.cr/2019/283
License: CC BY

BibTeX

@misc{cryptoeprint:2019/283,
      author = {Dimitrios Poulakis},
      title = {An Attack on Small Private Keys of {RSA} Based on Euclidean Algorithm},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/283},
      year = {2019},
      url = {https://eprint.iacr.org/2019/283}
}