对一个背包公钥密码的格攻击  

Lattice attack on knapsack public key cryptosystem

作　　者：王保仓[1,2] 巨春飞[1] 

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

出　　处：《计算机应用研究》2010年第4期1466-1468,1492,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(60803149)

摘　　要：对一个新的基于Merkle-Hellman背包密码和Rabin公钥密码的背包公钥密码算法进行了安全性分析。使用格规约算法求解一个联立丢番图逼近问题和一个二元整数线性规划问题就恢复出了该密码算法的部分密钥。重构的部分密钥可以解密任意密文。因此,该背包公钥密码算法是不安全的。This paper cryptanalyzed a knapsack public key cryptosystem which was constructed by using the Merkle-Hellman knapsack cryptosystem and the Rabin scheme.The attack recovered some partial of the secret keys by solving a simultaneous Diophantine approximation problem with lattice reduction algorithms and a bivariate integral linear programming problem.The recovered partial secret keys were utilized to decrypt any ciphertext.Therefore,the knapsack public key cryptosystem is insecure.

关 键 词：公钥密码 联立丢番图逼近 整数线性规划 格规约 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]