背包加密算法

Knapsack Cryptosystem）是一种公钥加密算法，由美国加州大学博士Markle在1978年提出。它的主要应用场景是在加密数字信息时，用于保护私人信息的传输和存储。本文将从算法原理、安全性、应用场景等多个角度分析背包加密算法。

一、算法原理

背包加密算法的加密过程中，最亮眼的地方就是公钥和私钥的生成。首先，随机选择一个超级递增数列。设置一个初值s0 ，并计算出后续的数列si， s1 = s0 + n1, s2 = s1 +n2 …… si = si-1 + ni i=1, 2, 3….n 其中n为随机数，递增数列中的数字均为n的倍数，其意义是为了加密的随机性。再随机选择一个超级递增数列的和M，作为私钥。公钥则是由超级递增数列生成：

b1= s1 mod M, b2= s2 mod M ,…… , bi= si mod M

公钥和私钥的生成过程一旦完成，加密和解密的算法实现就比较简单了。

加密：明文信息是一个比特序列bi，它的位数小于等于公钥当中的元素个数，将明文中1所在的位与公钥中对应的元素相乘求和，得到加密后的密文。即C= ∑bijbi。

解密：根据M和n的关系，确定n的逆元n--1，用M的逆元M--1乘以密文C，得到一个余数r，则明文中对应的是一个比特序列bi= (n--1r)i mod M。

二、安全性

背包加密算法的安全性最初是建立在背包问题的NP完全性假设上的。总结来说：只要好好选择递增数列和一个大的私有密钥，那么算法就是很安全的。但是这个假设后来被证明是不可信的了。由于在Trump’s Gate - New Cryptanalysis of the Knapsack Encryption Algorithm这篇论文中，研究者通过转化这个问题为一个5个人2次覆盖问题，证明了背包加密算法可以在几乎多项式时间内被突破破解。所以，应用领域上一般不再使用背包加密算法。

三、应用场景

1.抽奖系统

背包加密算法可以用在一些积分或者抽奖系统中。这种场景下，每个用户的私钥都是不同的超级递增数列和大的密钥和一个MD5后的用户名相对应。在用户参与抽奖时，系统会根据中奖概率计算得出此次中奖的比特序列，与用户的公钥进行运算得到中奖结果。

2.密钥交换

背包加密算法可以用在密钥交换中，为了防止在密钥交换的过程中，如在对称加密算法中，密钥被中途拦截。可以采用背包加密算法的公钥-私钥的生成方法，用公钥加密对称加密算法的密钥，保证在传输中的私钥也不泄露。