两种背包型的公钥密码算法的安全性分析
doi: 10.3724/SP.J.1146.2009.01396
Security Analysis of Two Knapsack-Type Public Key Cryptosystems
-
摘要: 背包型公钥密码体制是几个最早的公钥密码体制之一，分析其安全性十分重要。该文对两种抵抗Shamir攻击和低密度攻击的背包型公钥密码体制进行了安全性分析，提出一种新的攻击方法，指出可以利用多项式时间算法以很大的概率找到私钥，从而破解了它们。
-
关键词:
- 公钥密码体制; 陷门背包; 密码分析
Abstract: Knapsack-type public-key cryptosystem is one of several earliest public key cryptosystems, and it is very important to analyze their security. This article argues the security of two new knapsack cryptosystems which are secure against Shamirs attack and low density attack. A new attack method is proposed, and it is showed that can be used a polynomial time algorithm to find the secret keys with high probability, and hence break the new knapsack cryptosystems. -
Merkle R C and Hellman M E. Hiding information and signature in trapdoor knapsack[J].IEEE Transactions on Information Theory.1978, 24(5):525-530[2]Shamir A. A polynomial-time algorithm for breaking the basic Merkle-Hellman cryptosystem[J].IEEE Transactions on Information Theory.1984, 30(5):699-704[3]Coster M J, Joux A, and LaMacchia B A, et al.. Improved low-density subset sum algorithms[J].Computational Complexity.1992, 2(2):111-128[4]Wang B, Wu Q H, and Hu Y P. A knapsack-based encryption scheme[J].Information Sciences.2007, 177(19):3981-3994[5]Wang B C and Hu Y P. Quadratic compact knapsack public-key cryptosystem[J]. Computers and Mathematics with Applications, 2009. doi:10.1016/j.camwa. 2009.08.031.[6]Youssef A M. Cryptanalysis of a knapsack-based probabilistic encryption scheme[J].Information Sciences.2009, 179:3116-3121[7]张卫东，王保仓，胡予濮. 一种新的背包型公钥密码算法[J].西安电子科技大学学报, 2009, 36(3): 506-511.Zhang Wei-dong, Wang Bao-cang, and Hu Yu-pu. New knapsack-type public-key cryptographic algorithm. Journal of Xidian University, 2009, 36(3): 506-511.[8]王保仓，胡予濮. 高密度背包型公钥密码体制的设计[J].电子与信息学报.2006, 28(12):2390-2393浏览Wang Bao-cang and Hu Yu-pu. Knapsack-type public-key cryptosystem with high density[J].Journal of Electronics Information Technology.2006, 28(12):2390-2393 -
计量
- 文章访问数: 3644
- HTML全文浏览量: 136
- PDF下载量: 821
- 被引次数: 0
下载:
