Computer Science ›› 2015, Vol. 42 ›› Issue (6): 158-161.doi: 10.11896/j.issn.1002-137X.2015.06.034

Previous Articles     Next Articles

Analysis and Improvement of Public Key Cryptosystem Using Random Knapsacks

WANG Qing-long and ZHAO Xiang-mo   

  • Online:2018-11-14 Published:2018-11-14

Abstract: A new key recovery attack against Wang et al.’s cryptosystem which was built using random knapsacks was proposed in this paper.We found out that it is not a real random knapsack public key cryptosystem.Actually,a special super increasing knapsack is unobviously used in their scheme.By substituting the special super increasing knapsack with normal super increasing knapsack and hiding the normal super increasing knapsack into a random knapsack,we proposed an improved knapsack public key cryptosystem based on Chinese reminder theorem.Our scheme revises the shortage of the Wang et al.’s scheme and can resist the lattice basis reduction algorithm attack and low-density attack,as well as Shamir attack.

Key words: Random knapsack,Knapsack public key cryptosystem,Chinese reminder theorem,Lattice basis reduction algorithm

[1] Merkle R C,Hellman M E.Hiding information and signatures in trapdoor knapsacks [J].IEEE Transactions on Information Theory,1978,24(5):525-530
[2] Shamir A.A polynomial-time algorithm for breaking the basic Merkle-Hellman[C]∥Proceedings of the 23rd Annual Sympo-sium on Foundations of Computer Science,1982.Washington:IEEE,1982:145-152
[3] Lagarias J C.Knapsack public key cryptosystems and Diophantine approximation:Advances in Cryptology,1983 [C]∥New York:Plenum.1984:3-23
[4] Coster M J,Joux A,LaMacehia B A,et a1.Improved low-density subset sum algorithms [J].Computational Complexity,1992,2(2):111-128
[5] Nasako T,Murakami Y,Kasahara M.Security of a class ofknapsack public-key cryptosystems against low-density attack [J].IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences,2008,E91-A(1O):2889-2892
[6] Wang Bao-cang,Hu Lei.Lattice Attack on the Knapsack Cipher 0/255[C]∥Proceedings of the 2012 Fourth International Conference on Intelligent Networking and Collaborative Systems,2012.Washington:IEEE,2012:577-580
[7] Murakami Y,Kasahara M.New Trapdoor Sequences in Modular Knapsack Cryptosystem[C]∥7th International Conference on Computing and Convergence Technology,2012.Washington:IEEE,2012:604-609
[8] Murakami Y,Kasahara M.A differential knapsack publickeycryptosystem[C]∥6th International Conference on Computer Sciences and Convergence Information Technology.Washington:IEEE,2011:613-617
[9] Murakami Y.A New Construction of Knapsack PKC by Using A Random Sequence[C]∥Global Telecommunications Conference.Washington:IEEE,2009:1-6
[10] 王保仓,韦永壮,胡予濮.基于随机背包的公钥密码[J].电子与信息学报,2010,32(7):1580-1584Wang Bao-cang,Wei Yong-zhuang,Hu Yu-pu.Public Key Cryptosystem Using Random Knapsacks[J].Journal of Electronics& Information Technology,2010,32(7):1580-1584
[11] 王保仓,胡予濮.高密度背包型公钥密码体制的设计[J].电子与信息学报,2006,28(12):2390-2393 Wang Bao-cang,Hu Yu-pu.Knapsack-Type Public-Key Cryptosystem with High Density[J].Journal of Electronics& Information Technology,2006,28(12):2390-2393
[12] Murakami Y,Nasako T.Knapsack Public-Key Cryptosystem Using Chinese Remainder Theorem[DB/OL].2014-9-6.
[13] Wang Bao-cang,Hu Yu-pu.Quadratic compact knapsack pub-lickey cryptosystem[J].Computers & Mathematics with Applications,2010,59(1):194-206
[14] Peng Li-qiang,Zuo Jin-yin,Hu Lei,et al.Analysis of Two Public Key Cryptosystems Based on Randomized Knapsack Sequences[J].Chinese Journal of Electronics,2014,23(1):175-178
[15] 古春生,于志敏,景征骏.基于随机背包公钥密码的攻击[J].计算机应用研究,2012,29(9):3486-3488 Gu Chun-sheng,Yu Zhi-min,Jing Zheng-jun.Attack on random knapsack-based public key cryptosystems[J].Application Research of Computers,2012,29(9):3486-3488
[16] Lee M S.Improved cryptanalysis of a knapsack-based probabilistic encryption scheme[J].Information Sciences,2013,222(2):779-783
[17] Rastaghi R,Oskouei H R D.Cryptanalysis of a Public-key Cryptosystem Using Lattice Basis Reduction Algorithm[J].International Journal of Computer Science,2012,9(1):110-117

No related articles found!
Full text



No Suggested Reading articles found!