对RSA的部分密钥泄露攻击

Partial Key Exposure Attack on RSA

记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.