背包公钥密码安全新方案
|
摘要
将M-H公钥密码改进为一个安全方案并不困难,但存在背包维数过大、密钥过长的问题,从而使密码失去实用性。为此提出一种低维数背包密码抵御明文恢复攻击的方法。通过向真实明文填充随机数,使得参与加密的明文长于密文,一个密文对应许多明文,只有密文的指定接收者因掌握着陷门信息,可从密文恢复出真实明文。以此构造了一个背包密码安全新方案。新方案能抵御目前已知的各类攻击,所有运算的复杂度不超过二次方,信息率不是很高,但在可接受范围内;由于背包维数可以很小,密钥长度相应较短,存储性能大为改善。
It is not difficult to refine M-H public-key cryptosystem into a secure scheme,but there exists the problems that the knapsack dimension is too big and the key size is too large,thus making it impractical. Therefore,this paper presented a low dimensional knapsack cryptosystem to avoid plaintext-recovery attack. This approach filled random number in actual plaintext,the encrypted plaintext was longer than the ciphertext,which made a ciphertext correspond to numerous plaintexts. Only the designated ciphertext recipient,because of having the trapdoor information,could restore the actual plaintext from the ciphertext. This paper developed a novel secure scheme on knapsack cryptosystem with this approach. It could avoid all known attacks. All of its computations are no more than quadratic complexity. Its information rate is not very high,but in the acceptable range. As the knapsack dimension may be low,the key size is lesser accordingly,which promotes the storage performance considerably.
It is not difficult to refine M-H public-key cryptosystem into a secure scheme,but there exists the problems that the knapsack dimension is too big and the key size is too large,thus making it impractical. Therefore,this paper presented a low dimensional knapsack cryptosystem to avoid plaintext-recovery attack. This approach filled random number in actual plaintext,the encrypted plaintext was longer than the ciphertext,which made a ciphertext correspond to numerous plaintexts. Only the designated ciphertext recipient,because of having the trapdoor information,could restore the actual plaintext from the ciphertext. This paper developed a novel secure scheme on knapsack cryptosystem with this approach. It could avoid all known attacks. All of its computations are no more than quadratic complexity. Its information rate is not very high,but in the acceptable range. As the knapsack dimension may be low,the key size is lesser accordingly,which promotes the storage performance considerably.
引文
[1]Shor P W.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J].SIAM Journal of Computing,1997,26(5):1484-1509.
[2]Bennett C H,Bernstein E,Brassard G,et al.Strengths and weaknesses of quantum computing[J].SIAM Journal on Computing,1997,26(5):1510-1523.
[3]曹珍富.丢番图方程引论[M].哈尔滨:哈尔滨工业大学出版社,1989:132-148.
[4]Merkle R C,Hellman M E.Hiding information and signatures in trapdoor knapsacks[J].IEEE Trans on Information Theory,1978,24(5):525-530.
[5]Shamir A.A polynomial time algorithm for breaking the basic MerkleHellman cryptosystem[J].IEEE Trans on Information Theory,1984,30(5):699-704.
[6]Odlyzko A M.The rise and fall of knapsack cryptosystems[J].Cryptology and Computational Number Theory,1990,42:75-88.
[7]Ming Kinlai.Knapsack cryptosystems:the past and the future[EB/OL].(2002-03-01)[2016-06-24].https://archive.li/DNMH.
[8]王保仓,胡予濮.高密度背包型公钥密码体制的设计[J].电子与信息学报,2006,28(12):2390-2393.
[9]王保仓,韦永壮,胡予濮.基于中国剩余定理的快速公钥加密算法[J].西安电子科技大学学报,2008,35(3):449-454.
[10]张卫东,王保仓,胡予濮.一种新的背包型公钥密码算法[J].西安电子科技大学学报,2009,36(3):506-511.
[11]韩立东,刘明洁,毕经国.两种背包型的公钥密码算法的安全性分析[J].电子与信息学报,2010,32(6):1485-1488.
[12]毕经国,韩立东,刘明洁.基于中国剩余定理的公钥加密算法的破解[J].北京工业大学学报,2012,38(5):768-772.
[13]Okamoto T,Tanaka K,Uehiyama S.Quantum public-key cryptosystems[C]//Advances in Cryptology-Crypto.Berlin:Springer,2000:147-165.
[14]王青龙,赵祥模.随机背包公钥密码的分析与改进[J].计算机科学,2015,42(6):158-161.
[15]Koblitz N.Algebraic aspects of cryptography[M].Berlin:Springer Verlag,1998:44-45.
[16]Lenstra A K,Jr Lenstra H W,Lovasz L.Factoring polynomilas with rational coefficients[J].Mathematische Annalen,1982,261(4):513-534.
[17]王保仓,巨春飞.对一个背包公钥密码的格攻击[J].计算机应用研究,2010,27(4):1466-1492.
[18]Lagarias J C.Knapsack public key cryptosystems and diophantine approximation[J].Advances in Cryptology-Proceedings of Crypto,1984,83:3-23.
[19]Coster M J,Joux A,La Macchia B A,et al.Improved low-density subset sum algorithms[J].Computational Complexity,1992,2(2):111-128.
[20]Lagarias J C,Odlyzko A M.Solving low-density subset sum problems[J].Journal of the Association for Computing Machinery,1985,32(1):229-246.
[21]Hoffstein J,Pipher J,Silverman J H.NTRU:a ring-based public key cryptosystem[C]∥Proc of the 3rd Algorithmic Number Theory Conference.1998:267-288.
[22]Coppersmith D,Shamir A.Lattice attacks on NTRU[C]//Proc of EUROCRYPT.1997:52-61.
[23]Shannon C E.Communication theory of secrecy systems[J].Bell System Technical Journal,1949,28(4):656-715.
[24]王小云,王明强,孟宪萌.公钥密码学的数学基础[M].北京:科学出版社,2013:130-134.
[25]Kunihiro N.New definition of density on knapsack cryptosystems[C]//Advances in Cryptology-Africacrypt 2008,LNCS 5023.Berlin:Springer,2008:156-173.
[26]卢开澄.组合数学[M].北京:清华大学出版社,1991:135-186.
[27]张雅文.概率论与数理统计[M].北京:中国农民出版社,2009:88-89.
[28]祝跃飞,张亚娟.公钥密码学设计原理与可证明安全[M].北京:高等教育出版社,2010:66-103.
[2]Bennett C H,Bernstein E,Brassard G,et al.Strengths and weaknesses of quantum computing[J].SIAM Journal on Computing,1997,26(5):1510-1523.
[3]曹珍富.丢番图方程引论[M].哈尔滨:哈尔滨工业大学出版社,1989:132-148.
[4]Merkle R C,Hellman M E.Hiding information and signatures in trapdoor knapsacks[J].IEEE Trans on Information Theory,1978,24(5):525-530.
[5]Shamir A.A polynomial time algorithm for breaking the basic MerkleHellman cryptosystem[J].IEEE Trans on Information Theory,1984,30(5):699-704.
[6]Odlyzko A M.The rise and fall of knapsack cryptosystems[J].Cryptology and Computational Number Theory,1990,42:75-88.
[7]Ming Kinlai.Knapsack cryptosystems:the past and the future[EB/OL].(2002-03-01)[2016-06-24].https://archive.li/DNMH.
[8]王保仓,胡予濮.高密度背包型公钥密码体制的设计[J].电子与信息学报,2006,28(12):2390-2393.
[9]王保仓,韦永壮,胡予濮.基于中国剩余定理的快速公钥加密算法[J].西安电子科技大学学报,2008,35(3):449-454.
[10]张卫东,王保仓,胡予濮.一种新的背包型公钥密码算法[J].西安电子科技大学学报,2009,36(3):506-511.
[11]韩立东,刘明洁,毕经国.两种背包型的公钥密码算法的安全性分析[J].电子与信息学报,2010,32(6):1485-1488.
[12]毕经国,韩立东,刘明洁.基于中国剩余定理的公钥加密算法的破解[J].北京工业大学学报,2012,38(5):768-772.
[13]Okamoto T,Tanaka K,Uehiyama S.Quantum public-key cryptosystems[C]//Advances in Cryptology-Crypto.Berlin:Springer,2000:147-165.
[14]王青龙,赵祥模.随机背包公钥密码的分析与改进[J].计算机科学,2015,42(6):158-161.
[15]Koblitz N.Algebraic aspects of cryptography[M].Berlin:Springer Verlag,1998:44-45.
[16]Lenstra A K,Jr Lenstra H W,Lovasz L.Factoring polynomilas with rational coefficients[J].Mathematische Annalen,1982,261(4):513-534.
[17]王保仓,巨春飞.对一个背包公钥密码的格攻击[J].计算机应用研究,2010,27(4):1466-1492.
[18]Lagarias J C.Knapsack public key cryptosystems and diophantine approximation[J].Advances in Cryptology-Proceedings of Crypto,1984,83:3-23.
[19]Coster M J,Joux A,La Macchia B A,et al.Improved low-density subset sum algorithms[J].Computational Complexity,1992,2(2):111-128.
[20]Lagarias J C,Odlyzko A M.Solving low-density subset sum problems[J].Journal of the Association for Computing Machinery,1985,32(1):229-246.
[21]Hoffstein J,Pipher J,Silverman J H.NTRU:a ring-based public key cryptosystem[C]∥Proc of the 3rd Algorithmic Number Theory Conference.1998:267-288.
[22]Coppersmith D,Shamir A.Lattice attacks on NTRU[C]//Proc of EUROCRYPT.1997:52-61.
[23]Shannon C E.Communication theory of secrecy systems[J].Bell System Technical Journal,1949,28(4):656-715.
[24]王小云,王明强,孟宪萌.公钥密码学的数学基础[M].北京:科学出版社,2013:130-134.
[25]Kunihiro N.New definition of density on knapsack cryptosystems[C]//Advances in Cryptology-Africacrypt 2008,LNCS 5023.Berlin:Springer,2008:156-173.
[26]卢开澄.组合数学[M].北京:清华大学出版社,1991:135-186.
[27]张雅文.概率论与数理统计[M].北京:中国农民出版社,2009:88-89.
[28]祝跃飞,张亚娟.公钥密码学设计原理与可证明安全[M].北京:高等教育出版社,2010:66-103.