Abstract: Public key cryptography is an important technique to realize network security and information security. But the traditional public key cryptosystems are proved quite slow. To overcome this drawback, several fast public key cryptosystems are proposed. The security of a public key cryptosystem is analyzed. It is pointed out that the decryption can also be carried out without factoring the modulus. An equivalent secret key of the public key cryptosystem can be found in polynomial time by using the continued fraction algorithm. One can decrypt any ciphertext using the equivalent secret key. Hence, the public key cryptosystem is insecure. A novel continued fractions attack algorithm is proposed. Experimental results show it is effective.

Key words: public key cryptosystem, cryptanalysis, continued fractions algorithm

摘要： 公钥密码是实现网络安全和信息安全的重要技术之一，而传统的公钥密码算法速度较慢。为克服这一缺点，一些快速公钥密码算法被提出。对其中一个快速公钥密码算法的安全性进行分析，指出该算法的解密无须通过整数分解，使用连分数算法就可以在多项式时间内求解出该方案的一个等价密钥，使用该等价密钥就能对任意密文进行解密。因此，该公钥密码算法是不安全的，从而提出一种新的连分式攻击算法，实验结果证明了该算法的有效性。

关键词: 公钥密码体制, 密码分析, 连分式算法

CLC Number: 

• N945