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

Continued Fractions Attack Algorithm to A Public Key Cryptosystem

作　　者：王保仓[1,2] 刘辉[2,3] 胡予濮[2] 

机构地区：[1]西京学院工程技术系,西安710123 [2]西安电子科技大学计算机网络与信息安全教育部重点实验室,西安710071 [3]周口师范学院计算机科学系,周口466001

出　　处：《计算机工程》2010年第8期150-151,154,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(60803149);国家"973"计划基金资助项目(2007CB311201);国家"111"计划基金资助项目(B08038)

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

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

分 类 号：N945[自然科学总论—系统科学]