标题:Weak Keys in RSA with Primes Sharing Least Significant Bits
作者:Meng, Xianmeng; Bi, Jingguo
通讯作者:Meng, X
作者机构:[Meng, Xianmeng] Shandong Univ Finance, Dept Math & Stat, Jinan 250014, Peoples R China.; [Bi, Jingguo] Shandong Univ, Lab Cryptog Technol & Informa 更多
会议名称:5th China International Conference on Information Security and Cryptology
会议日期:DEC 12-15, 2009
来源:INFORMATION SECURITY AND CRYPTOLOGY
出版年:2010
卷:6151
页码:278-287
DOI:10.1007/978-3-642-16342-5_20
关键词:RSA; Coppersmith's theorem
摘要:Let N = pq be an LSBS-RSA modulus where primes p and q have the same bit-length and share the m least significant bits, and (p - 1, q - 1) = 2. Given (N, e) with e is an element of Z*(phi(N)/4) that satisfies ew + z . 2(2(m-1)) = 0 (mod phi(N)/4) with 0 < w <= 1/9 root phi(N)/e N (1/4+theta) and vertical bar z vertical bar <= c cw/phi(N) N1/4-theta, we can find p and q in polynomial time. We show that the number of these weak keys e is at least N3/4+theta-epsilon, where theta = m/log(2) N, and there exists a probabilistic algorithm that can factor N in time O(N1/4-theta+epsilon).
收录类别:CPCI-S;EI;SCOPUS
Scopus被引频次:2
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-78650193528&doi=10.1007%2f978-3-642-16342-5_20&partnerID=40&md5=efaa2369593d8a31b0ed6121e25b378d
TOP