基于随机背包的公钥密码

王保仓; 韦永壮; 胡予濮

doi:10.3724/SP.J.1146.2009.01113

基于随机背包的公钥密码

doi: 10.3724/SP.J.1146.2009.01113

王保仓^{①②;韦永壮,},
韦永壮,
胡予濮

计量
- 文章访问数: 3444
- HTML全文浏览量: 103
- PDF下载量: 1273
- 被引次数: 0
出版历程
- 收稿日期: 2009-08-21
- 修回日期: 2010-02-22
- 刊出日期: 2010-07-19

Public Key Cryptosystem Using Random Knapsacks

Wang Bao-cang^{①②;韦永壮
,},
Wei Yong-zhuang,
Hu Yu-pu

摘要

摘要: 该文构造了一个背包型公钥密码算法。该背包公钥密码具有如下优点：加解密只需要加法和模减法运算，因此加解密速度快；该算法是基于随机背包问题而不是易解背包问题而构造的；证明了在攻击者不掌握私钥信息情况下该密码算法能抵抗直接求解背包问题的攻击，包括低密度攻击和联立丢番图逼近攻击等；证明了攻击者能够恢复私钥信息与攻击者能够分解一个大整数是等价的。分析表明，该算法是一个安全高效的公钥加密算法。
- 公钥密码; 随机背包; 密钥恢复攻击; 安全性
Abstract: A knapsack-type public key cryptosystem is proposed. The proposed knapsack cryptosystem has the following advantages. The encryption and decryption only need addition and modular minus operations, so the encryption and decryption speed is high; The cryptosystem is constructed based on random knapsacks but not easy-to-solve knapsack problems; It is proven that if the secret key is not possessed by the attacker, the proposed cryptosystem can withstand the attacks launched by directly solving the underlying knapsack problem, including low-density attack and simultaneous Diophantine approximation attack; It is proven that the attacker can recover the secret keys if and only if he can factor a large integer. Analysis shows that the proposal is an efficient and secure public key encryption algorithm.

HTML全文

参考文献(1)

姜正涛，张京良，王育民. 一种新的等价于大整数分解的公钥密码体制研究[J].电子与信息学报.2008, 30(6):1450-1452浏览[2]杨军，周贤伟. 基于离散对数问题的两层分散式组密钥管理方案[J].电子与信息学报.2008, 30(6):1457-1461浏览[3]Merkle R C and Hellman M E. Hiding information andsignatures in trapdoor knapsacks[J].IEEE Transactions onInformation Theory.1978, 24(5):525-530[4]杨健，杜增吉，乔军. 基于Rabin 算法的超递增背包公钥密码体制的研究与改进[J]. 数学的实践与认识，2009, 39(2):109-114.Yang Jian, Du Zeng-ji, and Qiao Jun. The study in knapsackof public-key system based on Merkle-Hellman knapsacksystem and Rabin algorithm[J]. Mathematics in Practice andTheory, 2009, 39(2): 109-114.[5]张卫东，王保仓，胡予濮. 一种新的背包型公钥密码[J]. 西安电子科技大学学报，2009, 36(3): 506-511.Zhang Wei-dong, Wang Bao-cang, and Hu Yu-pu. Newknapsack-type public-key cryptographic algorithm[J]. Journalof Xidian University, 2009, 36(3): 506-511.[6]Murakami Y and Nasako T. A new trapdoor in knapsackpublic-key cryptosystem with two sequences as the publickey[C]. The Third International Conference on Convergenceand Hybrid Information Technology-ICCIT 2008, Busan,Korea 2008: 357-362.[7]Su P and Tsai C. New cryptosystems design based onhybrid-mode problems[J]. Computers and ElectricalEngineering, 2009, 35(3): 478-484.[8]Hwang M, Lee C, and Tzeng S. A new knapsack public-keycryptosystem based on permutation combinationalgorithm[J]. International Journal of Applied Mathematicsand Computer Sciences, 2009, 5(1): 33-38.[9]Coster M J, Joux A, and LaMacchia B A, et al.. Improvedlow-density subset sum algorithms[J]. ComputationalComplexity, 1992, 2(2): 111-128.[10]Lagarias J C. Knapsack public key cryptosystems andDiophantine approximation[C]. Advances in Cryptology-CRYPTO 1983, New York: Plenum, 1984: 3-23.[11]Nguyen P and Stern J. Merkle-Hellman revisited: acryptanalysis of the Qu-Vanstone cryptosystem based ongroup factorizations[C]. Advances in Cryptology-Crypto 1997,Berlin: Springer-Verlag, 1997, LNCS 1294: 198-212.[12]Brickell E F and Odlyzko A M. Cryptanalysis: A survey ofrecent results[C]. Contemporary Cryptology, The Science ofInformation Integrity, New York, IEEE Press, 1992: 501-540.[13]Nasako T, Murakami Y, and Kasahara M. Security of a classof knapsack public-key cryptosystems against low-densityattack[J].IEICE Transactions on Fundamentals ofElectronics, Communications and Computer Sciences.2008,E91-A(10):2889-2892[14]Youssef A M. Cryptanalysis of a knapsack-based probabilisticencryption scheme[J].Information Sciences.2009, 179(18):3116-3121[15]Koblitz N. Algebraic Aspects of Cryptography[M]. Berlin:Springer-Verlag, 1998: 44-45.

施引文献

资源附件(0)

访问统计