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

Abstract

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

CLC Number:

TN911.22

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

References

［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]	LI Chunteng,JIANG Yuzhong,ZHANG Ning,LIU Fangjun. Improved generalized sidelobe cancellation algorithm in ELF communication [J]. Journal of Xidian University, 2019, 46(1): 98-105.
[2]	LI Hui,XI Yuanyuan,MA Yuxin,ZHANG Ruimei. Traffic flow cycle prediction based on the PCA-ESN model [J]. Journal of Xidian University, 2019, 46(1): 20-26.
[3]	XING Nan;ZHANG Jianqi;LIU Pengfei;CAO Furong. Novel method of destroyed document reconstruction [J]. Journal of Xidian University, 2018, 45(4): 34-39.
[4]	ZHOU Zhiwen;HUANG Gaoming;GAO Jun;MAN Xin. Radar emitter identification algorithm based on deep learning [J]. Journal of Xidian University, 2017, 44(3): 77-82.
[5]	WANG Fan;GONG Shuxi;WANG Fuwei. Resistive FSS applied to the RCS reduction of array antennas [J]. Journal of Xidian University, 2016, 43(4): 81-85.
[6]	YANG Xin;WEI Bing. New modeling method for ray tracing [J]. Journal of Xidian University, 2016, 43(3): 73-77.
[7]	LUO Xiaomei;SUO Zhiyong;LIU Qiegen. InSAR noise reduction using adaptive dictionary learning [J]. J4, 2016, 43(1): 18-23.
[8]	WANG Wei;LI Yongzhao;ZHANG Hailin. Low complexity lattice reduction aided precoding algorithm with orthogonality defect threshold for MIMO systems [J]. J4, 2015, 42(5): 1-6+32.
[9]	SUN Jinhua;HAN Huimei;ZHU Jili. Reduced state demodulator for the SOQPSK-TG signal [J]. J4, 2014, 41(5): 1-6+12.
[10]	ZHAO Yangyang;ZHOU Shuisheng;WU Yajing. Non-iterative GLRAM algorithm for face recognition [J]. J4, 2014, 41(2): 144-150.
[11]	LIU Yan;JIAO Yongchang;ZHANG Yaming;WANG Xinkuan. Application of the invasive weed optimization algorithm to the pattern synthesis of array antennas [J]. J4, 2014, 41(1): 29-33+86.
[12]	YAO Xu;CAO Xiangyu;GAO Jun;ZHAO Yi;YANG Huanhuan. Polarization-dependent mutiband low RCS reflection screen [J]. J4, 2014, 41(1): 153-157.
[13]	WANG Fuwei;LIANG Ruixiang;GONG Shuxi;YU Songtao;JIANG Wen. Left-handed metamaterials applied to the RCS reduction of the antenna [J]. J4, 2013, 40(6): 96-100+161.
[14]	WANG Xinkuan;JIAO Yongchang;TAN Yanyan. Adaptive iteration Fourier technique applied for antenna arrays pattern synthesis [J]. J4, 2013, 40(4): 85-89+187.
[15]	WANG Fuwei;GONG Shuxi;ZHANG Pengfei;HONG Tao;YU Songtao;MA Ji. Radar absorbing material applied to the RCS reduction of array antennas [J]. J4, 2012, 39(5): 91-95.

New knapsack-type public-key cryptographic algorithm

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 0