针对离散私钥比特泄漏的RSA格攻击方法  

RSA Lattice Attack Method for Discrete Private Key Bit Leakage

作　　者：刘向辉[1,2] 韩文报[1,2] 王政[1,2] 权建校[3] 

机构地区：[1]解放军信息工程大学四院,郑州450002 [2]数学工程与先进计算国家重点实验室,郑州450002 [3]江南计算技术研究所,江苏无锡214083

出　　处：《计算机工程》2014年第3期163-166,共4页Computer Engineering

基　　金：国家自然科学基金资助项目(61003291);数学工程与先进计算国家重点实验室开放基金资助项目(2013A03)

摘　　要：RSA算法是目前应用最广泛的公钥密码体制之一,而格攻击是针对RSA体制的一类重要攻击方法。为此,将RSA算法的部分私钥泄漏问题转化为多变元线性同余方程的求解问题,基于同余方程构造出特定的格,利用LLL格基约化算法进行约化,从而以一定的概率求得同余方程的小根。以上述多变元线性同余方程的小根求解技术为基础,提出一种针对离散私钥比特泄漏的RSA格攻击方法。在该方法下,如果RSA算法的公钥参数e=N~β≤N^(1/2),并且私钥d的未知部分N≤N^((1/2)-β),则能以高概率恢复出RSA算法的私钥d。通过NTL包对长度为1024 bit的大整数进行实验,结果验证了该攻击方法的有效性。RSA algorithm is one of the most widely used public key cryptosystems at present and lattice attacks play an important role for the analysis of RSA system. The problem of partial discrete private key bit leakage is transformed into the solution of multivariate linear congruence equations and a special lattice is constructed. And then by the lattice reduction algorithms such as LLL algorithm, the small roots of multivariate linear congruence equations can be obtained with a high probability. Based on the above technology, this paper proposes a lattice attack method on RSA for discrete private key bit leakage. With this method, if the public parameter satisfies e=Nβ≤N1/2 and the unknown part of private key d satisfies Nα≤N1/2-β, it can recover the private key d with a high probability. The experiment on 1 024 bit number is given with NTL package and the results verify the availability of the attack method.

关 键 词：RSA算法 格攻击 离散私钥比特泄漏 线性同余方程 小根 格基约化算法 

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