对RSA的部分密钥泄露攻击  

Partial Key Exposure Attack on RSA

作　　者：郑永辉[1] 赵涛[1] 祝跃飞[1] 

机构地区：[1]信息工程大学信息工程学院,河南郑州450002

出　　处：《信息工程大学学报》2003年第1期5-7,共3页Journal of Information Engineering University

基　　金：国家973项目(G1999035804);国家自然科学基金项目(90204015);河南省杰出青年基金项目(0212001400);河南省自然科学基金项目(011105100)

摘　　要：记N=pq为n比特RSA模数,e和d分别为加解密指数,ν为p和q低位相同的比特数,即p≡qmod2ν且p qmod2ν+1。1998年,Boneh、Durfee和Frankel首先提出对RSA的部分密钥泄露攻击:当ν=1,e较小且d的低n/4比特已知时,存在关于n的多项式时间算法分解N。2001年R.Steinfeld和Y.Zheng指出,当ν较大时,对RSA的部分密钥泄露攻击实际不可行。本文的结论是当ν和e均较小且解密指数d的低n/4比特已知时,存在关于n和2ν的多项式时间算法分解N。Let N=pq be an nbit RSA modulus, e and d be encryption and decryption exponents and ν denote the exact number of the least significant bits that p and q equal,i.e., p≡qmod 2ν and pqmod 2ν+1.In 1998, Boneh, Durfee and Frankel proposed the partial key exposure attack on RSA: for low encryption exponent RSA, given a quarter of the bits of the decryption exponent d,an adversary can recover the entire d when ν=1. However, R.Steinfeld and Y.Zheng showed in 2001 that the partial key known attack can be prevented by choosing the modulus with large ν. In this paper,the authors conclude that for low encryption exponent RSA, known as the as n/4 least significant bits of d,one can factor N in time polynomial in n and 2ν when ν is small.

关 键 词：部分密钥泄露攻击 LLL-算法 多项式时间算法 加密指数 解密指数 

分 类 号：TN918.1[电子电信—通信与信息系统]