Paper 2009/062

On Deterministic Polynomial-Time Equivalence of Computing the CRT-RSA Secret Keys and Factoring

Subhamoy Maitra and Santanu Sarkar

Abstract

Let $N = pq$ be the product of two large primes. Consider CRT-RSA with the public encryption exponent $e$ and private decryption exponents $d_p, d_q$. It is well known that given any one of $d_p$ or $d_q$ (or both) one can factorize $N$ in probabilistic poly$(\log N)$ time with success probability almost equal to 1. Though this serves all the practical purposes, from theoretical point of view, this is not a deterministic polynomial time algorithm. In this paper, we present a lattice based deterministic poly$(\log N)$ time algorithm that uses both $d_p, d_q$ (in addition to the public information $e, N$) to factorize $N$ for certain ranges of $d_p, d_q$. We like to stress that proving the equivalence for all the values of $d_p, d_q$ may be a nontrivial task.

Note: A revised and corrected version

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Presented in WCC 2009
Keywords
CRT-RSACryptanalysisFactorizationLLL AlgorithmRSA.
Contact author(s)
subho @ isical ac in
History
2010-02-11: last of 3 revisions
2009-02-06: received
See all versions
Short URL
https://ia.cr/2009/062
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/062,
      author = {Subhamoy Maitra and Santanu Sarkar},
      title = {On Deterministic Polynomial-Time Equivalence of Computing the CRT-RSA Secret Keys and Factoring},
      howpublished = {Cryptology ePrint Archive, Paper 2009/062},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/062}},
      url = {https://eprint.iacr.org/2009/062}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.