背包密码简记
标签（空格分隔）： 背包密码
基本介绍
假如一个背包 W 满足以下
 其中$a_1,a_2,…a_i$是货物，$x_1,x_2,…,x_i$都只等于0或者1，x相当于决定是否装货物。式子表示而当货物装载的量等于 W 的时候。
 此时很显然，如果我们知道$a_1,a_2,…,a_i$的时候要逆推回去W的话可能要重复$2^i$次（$x_i$只可能等于1/2）
 此时如果我们要对一个密文m进行加密的话可以将m转化为对应的二进制的数值然后再用对应的$a_i$进行赋值，但是此时有一个缺点：解密的人自己也不好解密
 但是当a是超增值的话就有办法来解了。超增值即那边只有以下条件
 为什么满足这样的条件就可以解密了呢？这是因为如果加密后的结果大于$a_n$的话，其前面的系数为必须1的。反之，无论如何也无法使得等式成立。因此，我们可以立马得到对应的明文。
 但是，这样又出现了一个问题，由于$a_i$是公开的，如果攻击者截获了密文，那么它也就很容易去破解这样的密码。为了弥补这样的问题，就出现了Merkle–Hellman这样的加密算法，我们可以使用初始的背包集作为私钥，变换后的背包集作为公钥，再稍微改动加密过程，即可。
Merkle–Hellman
生成私钥
私钥就是我们的初始的背包集，这里我们使用超递增序列，怎么生成呢？我们可以假设$a_1=1$，那么$a_2$大于 1 即可，类似的可以依次生成后面的值。
生成公钥
在生成公匙的过程中运用了模乘的运算，先是生成一个m，m必须满足
选择一个模乘的模数m满足
之后再生成公匙$b_i=w*a_i \ mod \ m$,最后将$b_i$和$m$作为公匙
加密
假设要加密的密文为v，每一个比特位对应的是$v_i$
直接$W = \sum_{1}^ib_i*v_i \ mod \ m $
解密
因为$W = sum_{1}^{i}b_iv_{i}$，
那么$W * w^{-1} mod m = \sum_1^ia_iv_i mod m$
由于m是大于$sum_1^ia_i*v_i$的所以可以直接解。
本文写到这里但是背包密码在提出后两年便被破解了，后续小编将写出破解的笔记