CryptoDB
Deterministic Polynomial Time Equivalence of Computing the RSA Secret Key and Factoring
Authors: | |
---|---|
Download: | |
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. |
BibTeX
@misc{eprint-2004-12180, title={Deterministic Polynomial Time Equivalence of Computing the RSA Secret Key and Factoring}, booktitle={IACR Eprint archive}, keywords={public-key cryptography / RSA, factoring.}, url={http://eprint.iacr.org/2004/208}, note={Extended version of a Crypto 2004 paper published by A. May. coron@clipper.ens.fr 12653 received 23 Aug 2004, last revised 23 Aug 2004}, author={Jean-Sébastien Coron and Alexander May}, year=2004 }