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



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


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