对RSA的部分密钥泄露攻击

Partial key exposure attack on RSA

记N=pq为n比特RSA模数,e和d分别为加解密指数,v为p和q低位相同的比特数,即p≡qmod2v且p qmod2v+1.考察了基于格基约化理论的对RSA的部分密钥泄露攻击.证明了当v和ed均较小且解密指数d的低n/4比特已知时,存在关于n和2v的多项式时间算法分解N.

Let N=pq be an n-bit RSA modulus,e(or d) be encryption (or decryption) exponent and v denote the exact number of the least significant bits that p and q equal,i.e.,p≡q mod 2~v and pq mod 2^(v+1).Based on lattice reduction theory the partial key exposure attack on RSA is considered in this paper.It is proved that known the n/4 least significant bits of d,one can factor N in time polynomial in n and 2~v when v and the product of e and d are small.