[Resource Topic] 2019/283: An Attack on Small Private Keys of RSA Based on Euclidean Algorithm

Resource Public-key cryptography
#1

Welcome to the resource topic for 2019/283

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

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

ePrint: https://eprint.iacr.org/2019/283

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .