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

Defence Science Journal

Subhamoy Maitra¹  Santanu Sarkar¹ 

[1] Indian Statistical Institute, Kolkata

关键词: Cryptanalysis;    Ciphertext;    Ciphertext-only attack;    Cost;    Particle Swarm Optimization;    Plaintext;    Simplified-AES.;   

DOI  :  

学科分类：社会科学、人文和艺术（综合）

来源: Defence Scientific Information & Documentation Centre

【 摘 要 】

Let N = pq be the product of two large primes. Consider Chinese remainder theorem-Rivest, Shamir, Adleman (CRT-RSA) with the public encryption exponent e and private decryption exponents dp, dq. It is well known that given any one of dp or dq (or both) one can factorise 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 dp, dq (in addition to the public information e, N) to factorise N for certain ranges of dp, dq. We like to stress that proving the equivalence for all the values of dp, dq may be a nontrivial task. Defence Science Journal, 2012, 62(2), pp.122-126 ,  DOI:http://dx.doi.org/10.14429/dsj. 62.1716

【 授权许可】

Unknown