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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.