Paper 2004/208
Deterministic Polynomial Time Equivalence of Computing the RSA Secret Key and Factoring
Jean-Sebastien Coron and Alexander May
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
PS
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Extended version of a Crypto 2004 paper published by A. May.
- Keywords
- RSAfactoring.
- Contact author(s)
- coron @ clipper ens fr
- History
- 2004-08-23: last of 2 revisions
- 2004-08-23: received
- See all versions
- Short URL
- https://ia.cr/2004/208
- License
-
CC BY
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},
note = {\url{https://eprint.iacr.org/2004/208}},
url = {https://eprint.iacr.org/2004/208}
}
