运用格规约分析RSA解密指数安全性

分析RSA算法的解密指数的安全性是业界关注的重点问题，目前多项研究给出了解密指数的不安全范围，其局限性均为仅使用基于连分数逼近的分析方法，且仅指出了解密指数与模数的关系。实际上，RSA算法的解密指数的安全性还与其所使用的素数和加密指数大小有关。为分析更广义的RSA算法的解密指数的安全范围，文章提出了一种运用格规约攻击小解密指数的攻击算法(LW)：首先构造最短向量与解密指数相关的二维格，然后寻找该二维格中的最短向量，最终从最短向量中提取解密指数。分析LW算法攻击成功的条件可知：令N、e、d分别为RSA算法所使用的模数、加密指数、解密指数，p、q(p≥q)为大素数，则当ped²≤N²时，使用LW算法可破解得解密指数。同时证明了LW算法与基于连分数逼近的攻击方法具有等价关系，即若满足连分数逼近方法的攻击条件，则使用LW算法也可攻击成功，反之亦然。最后，在3种基于连分数逼近的攻击算法的已知条件下使用LW算法，分别得到攻击成功时的广义解密指数不安全范围，分析结果展示了LW算法的通用性。

A method for obtaining digital signatures and public-key cryptosystems

Cryptanalysis of the RSA decryption exponent is a pivotal issue in public-key cryptography. Currently, many studies have given the insecure ranges of the decryption exponent, which are limited to only using the continued fraction approximation method and considering relationships between the decryption exponent and the modulus. In fact, the security of the RSA decryption exponent is also related to the encryption exponent and the primes. To propose a general security relation, the LW method, a new method to attack the RSA with small decryption exponent is given in this paper. This method first constructs a 2-dimensional lattice using the RSA public key, whose shortest vector is related to the decryption exponent. By finding the shortest vector of this lattice, the decryption exponent can be recovered. The analysis then shows that the LW method will succeed when ped²≤N², where N,e,d are the module, the encryption exponent and the decryption exponent as well as p and q are the primesp≥q of the RSA scheme. Such an attack has the same effect as attacks based on continued fraction approximation, i.e. if the continued fraction approximation succeeds, the LW method succeeds. The LW method is applied to the environment of three kinds of attacks based on the continued fraction approximation to get general insecure ranges of the decryption exponent, which shows that the LW method is general.