标题:Deterministic polynomial-time equivalence of factoring and key-recovery attack on a variant of RSA
作者:Meng, Xianmeng ;Duan, Shili
通讯作者:Meng, X
作者机构:[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
出版年:2009
DOI:10.1109/CISE.2009.5364206
关键词: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.
收录类别:EI;SCOPUS
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-77949750052&doi=10.1109%2fCISE.2009.5364206&partnerID=40&md5=ed94d6104b65c7ffebe0ded3deb46a9d
TOP