Welcome to the resource topic for 2009/062
Title:
On Deterministic Polynomial-Time Equivalence of Computing the CRT-RSA Secret Keys and Factoring
Authors: Subhamoy Maitra, 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.
ePrint: https://eprint.iacr.org/2009/062
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .