Paper 2004/208 Original: eprint.iacr.org/2004/208 ↗
Deterministic Polynomial Time Equivalence of Computing the RSA Secret Key and Factoring
Abstract
We address one of the most fundamental problems concerning the RSA cryptosystem: does the knowledge of the RSA public and secret key-pair (e,d) yield the factorization of N=pq in polynomial time? It is well-known that there is a probabilistic polynomial time algorithm that on input (N,e,d) outputs the factors p and q. We present the first deterministic polynomial time algorithm that factors N provided that e,d<N. Our approach is an application of Coppersmith's technique for finding small roots of univariate modular polynomials.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2004-08-23: last updated
- 2004-08-23: published
- Short URL
- https://ia.cr/2004/208
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2004/208,
author = {Jean-Sebastien Coron and Alexander May},
title = {Deterministic Polynomial Time Equivalence of Computing the RSA Secret Key and Factoring},
howpublished = {Cryptology {ePrint} Archive, Paper 2004/208},
year = {2004},
url = {https://eprint.iacr.org/2004/208}
}