Paper 2019/283 Original: eprint.iacr.org/2019/283 ↗
An Attack on Small Private Keys of RSA Based on Euclidean Algorithm
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.
- History
- 2019-05-10: last updated
- 2019-03-16: published
- Short URL
- https://ia.cr/2019/283
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}