摘要： RSA算法是目前应用最广泛的公钥密码体制之一，而格攻击是针对RSA体制的一类重要攻击方法。为此，将RSA算法的部分私钥泄漏问题转化为多变元线性同余方程的求解问题，基于同余方程构造出特定的格，利用LLL格基约化算法进行约化，从而以一定的概率求得同余方程的小根。以上述多变元线性同余方程的小根求解技术为基础，提出一种针对离散私钥比特泄漏的RSA格攻击方法。在该方法下，如果RSA算法的公钥参数e=Nβ≤N1/2，并且私钥d的未知部分Nα≤N1/2–β，则能以高概率恢复出RSA算法的私钥d。通过NTL包对长度为1 024 bit的大整数进行实验，结果验证了该攻击方法的有效性。
关键词:
RSA算法,
格攻击,
离散私钥比特泄漏,
线性同余方程,
小根,
格基约化算法
Abstract: 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.
Key words:
RSA algorithm,
lattice attack,
discrete private key bit leakage,
linear congruence equation,
small root,
lattice base reduction algorithm
中图分类号: