一种新的背包型公钥密码算法

J4 ›› 2009, Vol. 36 ›› Issue (3): 506-511.

一种新的背包型公钥密码算法

张卫东;王保仓;胡予濮

(西安电子科技大学计算机网络与信息安全教育部重点实验室，陕西西安 710071)

收稿日期:2008-11-05 修回日期:2008-12-12 出版日期:2009-06-20 发布日期:2009-07-04
通讯作者: 张卫东
基金资助:
国家自然科学基金资助(60803149, 60673072);国家973计划资助(2007CB311201);111计划资助(B08038);国家科技支撑计划课题资助(2007BAH08B01)

New knapsack-type public-key cryptographic algorithm

ZHANG Wei-dong;WANG Bao-cang;HU Yu-pu

(Ministry of Education Key Lab. of Computer Network and Information Security, Xidian Univ., Xi'an 710071， China)

Received:2008-11-05 Revised:2008-12-12 Online:2009-06-20 Published:2009-07-04
Contact: ZHANG Wei-dong

摘要/Abstract

摘要：

基于一类易解背包问题构造了一个新的背包型公钥密码体制．该公钥密码体制未使用超递增背包序列，因此可以抵抗Shamir的密钥恢复攻击．证明该公钥密码具有较高的背包密度，因此可以抵抗低密度子集和攻击．证明了该密码体制能够抵抗一些暴力攻击及联立丢番图逼近攻击．该公钥密码的加密只使用了n个加法运算，解密只需要n个模2的除法运算，因此具有很快的加解密速度，而且易于软硬件实现．

关键词: 公钥密码学, 陷门背包, 数据安全, 规约

Abstract:

A new knapsack-type public key cryptosystem is proposed, which is based on an easy knapsack problem. The cryptosystem is secure against Shamir's key-recovery attack in that it prevents the use of the super-increasing knapsack sequence in the construction of the cryptosystem. The cryptosystem is also invulnerable to the low-density subset-sum attack in that it obtains a relatively high density. It is shown that the cryptosystem withstands some brute-force attacks and the simultaneous Diophantine approximation attack. It only performs n addition operations for the cryptosystem to encrypt a plaintext, and the decryption algorithm only carries out n modular 2 divisions. Therefore, the cryptosystem is efficient with respect to the encryption and the decryption. Furthermore, the cryptosystem is suited for software and hardware implementations.

Key words: public key cryptography, trapdoor knapsack, security of data, reduction

中图分类号:

TN911.22

张卫东;王保仓;胡予濮. 一种新的背包型公钥密码算法[J]. J4, 2009, 36(3): 506-511.

ZHANG Wei-dong;WANG Bao-cang;HU Yu-pu. New knapsack-type public-key cryptographic algorithm[J]. J4, 2009, 36(3): 506-511.

参考文献

［1］王保仓，韦永壮，胡予濮. 基于中国剩余定理的快速公钥加密算法［J］. 西安电子科技大学学报，2008，35(3): 486-491.
Wang Baocang, Wei Yongzhuang, Yupu Hu. Fast Public-Key Encryption Scheme Based on the Chinese Remainder Theorem［J］. Journal of Xidian University, 2008，35(3): 486-491.
［2］张跃宇，李晖，王育民. 一种基于群签名的安全电子拍卖方案［J］. 西安电子科技大学学报，2008, 35(4): 614-619.
Zhang Yueyu, Li Hui, Wang Yumin. Secure Electronic Auction Scheme Based on the Group Signature［J］. Journal of Xidian University, 2008, 35(4): 614-619.
［3］孙纪敏, 孙玉, 张思东, 等. 基于ID的认证及密钥协商协议［J］. 西安电子科技大学学报, 2008, 35(3): 559-562.
Sun Jimin, Sun Yu, Zhang Sidong, et al. Identity (ID)-Based Authentication and the Key Agreement Protocol［J］. Journal of Xidian University, 2008, 35(3): 559-562.
［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］Coster M J, Joux A, LaMacchia B A, et al. Improved Low-Density Subset Sum Algorithms［J］. Computational Complexity, 1992, 2(2): 111-128.
［6］Shamir A. A Polynomial-Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem［J］. IEEE Trans on Information Theory, 1984, 30(5): 699-704.
［7］Wang B C, Hu Y P. Diophantine Approximation Attack on a Fast Public Key Cryptosystem［C］//The 2nd Information Security Practice and Experience (ISPEC 2006): LNCS 3903. Berlin: Springer, 2006: 25-32.
［8］Lagarias J C. Knapsack Public Key Cryptosystems and Diophantine Approximation［C］//Advances in Cryptology-CRYPTO 1983. New York: Plenum, 1984: 3-23.
［9］Kunihiro N. New Definition of Density on Knapsack Cryptosystems［C］//Advances in Cryptology-Africacrypt 2008: LNCS 5023. Berlin: Springer, 2008: 156-173.
［10］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.
［11］丁勇. 一种用椭圆曲线密码构建的传感器网络密钥管理方案［J］. 西安电子科技大学学报, 2008, 35(4): 739-742.
Ding Yong. Key Management Scheme for WSN Using ECC［J］. Journal of Xidian University, 2008, 35(4): 739-742.
［12］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.
［13］王保仓, 胡予濮. 高密度背包型公钥密码体制的设计［J］. 电子与信息学报, 2006, 28(12): 2390-2393.
Wang Baocang, Hu Yupu. Knapsack-Type Public-Key Cryptosystem with High Density［J］. Journal of Electronics ＆ Information Technology, 2006, 28(12): 2390-2393.
［14］Wang B C, Hu Y P. Public Key Cryptosystem Based on Two Cryptographic Assumptions［J］. IEE Proceedings of Communications, 2005, 152(6): 861-865.
［15］Wang B C, Wu Q H, Hu Y P. A Knapsack-Based Encryption Scheme［J］. Information Sciences, 2007, 177(19): 3981-3994.
［16］Ko K H, Lee S J, Cheon J H, et al. New Public-Key Cryptosystem Using Braid Groups［C］//Advances in Cryptology-Crypto'2000: LNCS 1880. Berlin: Springer, 2000: 166-183.
［17］Okamoto T, Tanaka K, Uchiyama S. Quantum Public-Key Cryptosystems［C］//Advances in Cryptology-Crypto'2000: LNCS 1880. Berlin: Springer, 2000: 147-165.

[1]	邢楠;张建奇;刘鹏飞;曹芙蓉. 一种新颖的破碎文件重构方法[J]. 西安电子科技大学学报, 2018, 45(4): 34-39.
[2]	李建东;陈睿;李长乐;刘伟;陈丹. MIMO空间相关信道下格规约辅助的信号检测[J]. J4, 2012, 39(1): 11-16+22.
[3]	邱钢;王宏;肖鸿;肖国镇. 两个前向安全盲签名体制的安全性分析[J]. J4, 2010, 37(1): 107-112+147.
[4]	王保仓1;韦永壮1;2;胡予濮1. 基于中国剩余定理的快速公钥加密算法 [J]. J4, 2008, 35(3): 449-454.
[5]	李慧贤1;蔡皖东1;裴庆祺2. 可验证秘密共享方案的设计与分析 [J]. J4, 2008, 35(1): 148-151.
[6]	李继红;张玉清;肖国镇. 在Pinch方案中检测欺骗者[J]. J4, 1999, 26(4): 444-448.