Factoring RSA modulo N with high bits of p known revisited

摘要：

The factorization problem with knowledge of some bits of prime factor p of RSA modulo N is one of the earliest partial key exposure attacks on RSA. The result proposed by Coppersmith 8 is still the best, i.e., when some ofp s higher bits is known as p , assume the unknown part of p and q is p_0 and q_0 , respectively (say, p = (p) + p_0 , q = (q) + q_0 ) , if the upper bounds of them , say X and Y separately, satisfy XY ≤N~0.5 , then N can be factored in polynomial time. Our method shows improved bounds that when RSA private key d < N_0.483, knowing a smaller fraction of p is sufficient in yielding the factorization of N in polynomial time.

关键词： LLL Lattice basis reduction RSA cryptanalysis Partial key ezposure attack

作者: LIU Chang YANG Chi

作者单位: School of Computer Science and Software Engineering, The University of Western Australia

会议类型: 国际会议

会议名称: 2009 IEEE International Symposium on IT in Medicine & Education( IEEE 教育与医药信息化国际会议)

会议地点: 济南

会议语种:英文

页码: 495-500

在线出版日期: 2009-08-14（万方平台首次上网日期，不代表论文的发表时间）