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

Subhamoy Maitra; Santanu Sarkar

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 = p q$ 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-RSA Cryptanalysis Factorization LLL Algorithm RSA.
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: 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},
      url = {https://eprint.iacr.org/2009/062}
}