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

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