标题：Deterministic polynomial-time equivalence of factoring and key-recovery attack on a variant of RSA
作者：Meng, Xianmeng ;Duan, Shili
作者机构：[Meng, Xianmeng ] Dept. of Mathematics and Statistics, Shandong University of Finance, Jinan 250014, China;[Duan, Shili ] School of Mathematics, Shand 更多
会议名称：2009 International Conference on Computational Intelligence and Software Engineering, CiSE 2009
会议日期：11 December 2009 through 13 December 2009
来源：Proceedings - 2009 International Conference on Computational Intelligence and Software Engineering, CiSE 2009
关键词：Coppersmith's theorem; RSA
摘要：In the original paper of RSA, it is proved that there exists a probabilistic polynomial-time equivalence between computing d and factoring N. And later, May presented a deterministic polynomial time algorithm that factors N given (e, d) provided that e, d < φ(N). Let p and q are balanced primes and N = pq, where gcd(p- 1, q-1) = 2g with g being a prime, and (N -1)/(2g) also being a prime. A variant RSA that defines the public/private exponents modulo lcm(p-1, q-1) is called common prime RSA. We show that there exists a deterministic polynomial time algorithm that factors N given (e, d) provided that e, d satisfying a given upper bound depending on g in this variant RSA. ©2009 IEEE.