Security Analysis of Two Knapsack-Type Public Key Cryptosystems

Han Li-dong; Liu Ming-jie; Bi Jing-guo

doi:10.3724/SP.J.1146.2009.01396

Volume 32 Issue 6

Jun. 2010

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2010 > 32(6): 1485-1488

Han Li-dong, Liu Ming-jie, Bi Jing-guo. Security Analysis of Two Knapsack-Type Public Key Cryptosystems[J]. Journal of Electronics & Information Technology, 2010, 32(6): 1485-1488. doi: 10.3724/SP.J.1146.2009.01396

Citation:

Han Li-dong, Liu Ming-jie, Bi Jing-guo. Security Analysis of Two Knapsack-Type Public Key Cryptosystems[J]. Journal of Electronics & Information Technology, 2010, 32(6): 1485-1488. doi: 10.3724/SP.J.1146.2009.01396

Citation:

PDF( 187 KB)

Security Analysis of Two Knapsack-Type Public Key Cryptosystems

doi: 10.3724/SP.J.1146.2009.01396

Han Li-dong^{①;刘明洁
,},
Liu Ming-jie,
Bi Jing-guo

Received Date: 2009-10-19
Rev Recd Date: 2010-03-03
Publish Date: 2010-06-19

Abstract

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.

FullText(HTML)

References(1)

References

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

Relative Articles

Supplements(0)

Cited By

Proportional views