International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Subhamoy Maitra
Santanu Sarkar
Download:
URL: http://eprint.iacr.org/2009/062
Search ePrint
Search Google
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$.
BibTeX
@misc{eprint-2009-18254,
  title={Deterministic Polynomial-Time Equivalence of Computing the CRT-RSA Secret Keys and Factoring},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / CRT-RSA, Cryptanalysis, Factorization, LLL Algorithm, RSA.},
  url={http://eprint.iacr.org/2009/062},
  note={ subho@isical.ac.in 14286 received 6 Feb 2009, last revised 10 Feb 2009},
  author={Subhamoy Maitra and Santanu Sarkar},
  year=2009
}