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

• 研究论文 • 上一篇    下一篇

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

张卫东;王保仓;胡予濮   

  1. (西安电子科技大学 计算机网络与信息安全教育部重点实验室,陕西 西安  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   

  1. (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

摘要:

基于一类易解背包问题构造了一个新的背包型公钥密码体制.该公钥密码体制未使用超递增背包序列,因此可以抵抗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