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 cryptosystemEuclid’s algorithmInteger 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},
note = {\url{https://eprint.iacr.org/2019/283}},
url = {https://eprint.iacr.org/2019/283}
}
