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
-
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}
}
