**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.

**Category / Keywords: **public-key cryptography / CRT-RSA, Cryptanalysis, Factorization, LLL Algorithm, RSA.

**Publication Info: **Presented in WCC 2009

**Date: **received 6 Feb 2009, last revised 11 Feb 2010

**Contact author: **subho at isical ac in

**Available format(s): **PDF | BibTeX Citation

**Note: **A revised and corrected version

**Version: **20100211:102852 (All versions of this report)

**Short URL: **ia.cr/2009/062

[ Cryptology ePrint archive ]