背包算法为第一个推广的公开密钥加密算法，背包算法的安全性起源于背包难题，他是一个NP完全问题，但后来发现该算法并不安全，但是由于它演绎了如何将NP完全问题用于公开秘钥密码学，因此，值得去学习
背包问题描述
现在有物品A，B，C，D，E种物品， 质量分别为Aw，Bw，Cw，Dw，Ew； 现在有一个包，包里装有上述物品，每件物品最多一个，总质量为M；在不打开背包的情况下，求背包里可能装的都是哪些物品
背包难题
由于背包问题是一个NP完全问题， 所以他的结果具有不确定性，最恶劣的结果是你需要遍历出所有种组合才能得到正确解， 算法复杂度为2n
超递增背包
并非所有的背包问题都没有有效算法，有一类特殊的背包问题是容易求解的，这就是超递增背包问题。
超递增序列：它的每一项都大于它之前所有项之和，例如{3，5，11，23，47}是一个超递增序列，而{3，5，8，12，17}则不是。
超递增背包问题的解很容易找到，计算其总量并与序列中最大的数比较，如果总重量小于这个数，则它不在背包中，如果总重量大于这个数，则它在背包中，背包重量减去这个数，进而考察序列中下一个最大的数，重复直到结束。如果总重量减为0，那么只有一个解，否则，无解。
例如：
总重量为31的一个背包，超递增序列为{3，5，11，23，47}；质量为47的物品大于背包总质量31，所以质量为47的物品不在背包里；质量为23的物品小于背包总质量31， 那么质量为23的物品在背包里；计算剩余质量为8, 小于11， 那么质量为11的物品不在背包里; 5<8, 那么质量为5的物品在背包里； 计算剩余质量为3，那么质量为3的物品在背包里，计算剩余质量为0， 结束； 所以质量为3， 5， 23的物品物品在背包里； 如果包的总质量为67，则无解
背包加密算法原理
对于非超递增序列的背包是困难的问题，它们没有快速算法。要决定哪一项在背包中的唯一方法，是依次测试所有解，直到得到正确的解为止。虽然可以优化，不必穷举所有可能，但是最快的算法仍随背包中物品超递增问题困难； 但是对于超递增背包，物品序列里多一项， 也只最多多计算一次
背包加密算法正式利用了这个特性；私钥是一个超递增序列，而公钥则是通过私钥利用模反原理构建出来的非超递增序列
算法实现
取一组超递增序列作为私钥
私钥序列：{3，5，11，23，47，90}
构建公钥序列
公钥序列为私钥序列里每一个数 用n去乘所有的项，再用m做模数进行模运算
其中n不能与私钥序列里的每一个数有公共因子， 这里取质数： 41
模数m 应比私钥序列中所有的数的和还要大， 这里取这个先取一个数p(后面有用) 要求 m=p*n-1； 取p=7 则 m=286
公钥序列：
(3 * 41)%286 = 123
(5 * 41)%286 = 205
(11 * 41)%286 = 165
(23 * 41)%286 = 85
(47 * 41)%286 = 211
(90 * 41)%286 = 258
所以公钥序列为：{123, 205, 165, 85, 211, 258}
加密
给定明文： 101101 011001 010110
加密
101101 对应 123 * 1 + 205 * 0 + 165 * 1 + 85 * 1 + 211 * 0 + 258 * 1 = 123+165+85+258 = 631
011001 对应 205+165+258 = 628
010110 对应 205+85+211 = 501
解密
在构建公钥的时候， 得到两个值
m=286 p=7
得到密文 分别是 631 628 501
私钥序列：{3，5，11，23，47，90}
（631 * 7）%286 = 127 = 90 + 23 + 11 + 3 对应 1 0 1 1 0 1
（628 * 7）%286 = 106 = 90 + 11 + 5 对应 0 1 1 0 0 1
（501 * 7）%286 = 75 = 47+ 23+ 5 对应 0 1 0 1 1 0
因此，恢复出的明文为
101101 011001 010110