Abstract: RSA encryption algorithm is an asymmetric encryption algorithm. The difficulty of decomposing large integers determines the reliability of RSA algorithm. Aiming at RSA attack problem, this paper proposes an attack algorithm based on the Legendre theorem of continued fraction approximation. On the basis of Wiener attack algorithm, the algorithm is improved by using the real quadratic irrational number approximation method instead of the rational fraction approximation method of Wiener attack algorithm,The result of this algorithm is to weaken the restriction of Wiener attack algorithm on RSA small decryption index, which makes the algorithm more applicable.Theoretical analysis and simulation prove its effectiveness and performance is better than classical wiener attack algorithm.

Key words: public key cryptography, continued fraction, approach, RSA, Wiener

摘要： RSA加密算法是一种非对称加密算法，分解大整数的难度决定了RSA算法的可靠性．针对RSA攻击算法问题，本文提出一种基于连分数逼近Legendre定理的攻击算法，该算法在Wiener攻击算法的基础上，进行适当改进，采用实二次无理数逼近方法，而不是Wiener攻击算法的有理分数逼近方法，本算法得到的结果是弱化Wiener攻击算法对RSA小解密指数的限制条件，使得本算法适用范围更宽．理论分析和计算仿真均证明本算法的有效性，性能优于经典的wiener连分数攻击算法

关键词: 公钥密码, 连分数, 逼近, RSA攻击, Wiener算法