计算机工程 ›› 2010, Vol. 36 ›› Issue (8): 150-151.doi: 10.3969/j.issn.1000-3428.2010.08.052

• 安全技术 • 上一篇    下一篇

对一个公钥密码体制的连分式攻击算法

王保仓1,2,刘 辉2,3,胡予濮2   

  1. (1. 西京学院工程技术系,西安 710123;2. 西安电子科技大学计算机网络与信息安全教育部重点实验室,西安 710071;3. 周口师范学院计算机科学系,周口 466001)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-04-20 发布日期:2010-04-20

Continued Fractions Attack Algorithm to A Public Key Cryptosystem

WANG Bao-cang1,2, LIU Hui2,3, HU Yu-pu2   

  1. (1. Dept. of Engineering Technology, Xijing University, Xi’an 710123;2. Key Laboratory of Computer Networks and Information Security of the Ministry of Education, Xidian University, Xi’an 710071;3. Dept. of Computer Science, Zhoukou Normal University, Zhoukou 466001)
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-04-20 Published:2010-04-20

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

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

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

中图分类号: