Merkle-Hellman背包公钥加密

Merkle-Hellman背包加密方案属于子集和问题，这个加密算法易于求解并不安全，但是却是这一类加密算法的基础。主要使用的数学运算是模乘和置换。

1. 超递增序列
   B =（b1，b2，b3，……，bn）是一个正整数序列，对于每一个i，2<= i <= n ，满足bi > $\sum_{j=1}^{i-1}$∑j=1i−1​ bj，也就是说序列中第i个数字，比之前的所有数字的和还大。
2. 求解超递增序列的子集和问题：
   即求解B = {b1，b2，b3，……，bn}某个子集的和，设子集和为s，s与bi（i从n开始到1）做比较，若s<bi则i=i-1，若s>=bi则s=s-bi并记录当前i的值然后i=i-1直到s=0为止。伪代码：

i = n
while i >= 1:
	if  s > bi:
		xi = 1
		s = s - bi
	else:
		xi = 0
	i = i - 1
return (x1, x2, …… ,xn)

xi为1则B中第i位为子集中的元素。

3. 基本的Merkle-Hellman背包加密的秘钥生成
   选择一个超递增序列B = {b1，b2，b3，……，bn} 和模数M，M > sum(B)
   随机选取一个整数W，1 <= W <= M-1, 使得gcd(W，M) = 1
   随机选取整数{1,2,3，……，n}的一个置换$\pi$π
   计算ai = Wb_$\pi$π(i) mod M， i = 1，2，……，n。
   公钥就是(a1，a2，a3，……，an)，私钥是（$\pi$π，M， W，B）
4. 加密
   取出公钥(a1，a2，a3，……，an)
   将明文m表示为长n的二进制串，m = m1，m2，m3……mn
   计算整数c = m1 * a1 + m2 * a2 + …… + mn * an
   c就是密文
5. 解密
   计算d = W ^-1 c mod M
   通过求解超递增子集和问题，求满足d = r1 * b1 + r2 * b2 + …… + rn * bn的整数r1，r2，……rn，ri $\in$∈ {0, 1}
   明文的二进制串为mi = r_$\pi$π(i)
   解密的证明：
   d = W^-1 *c = W^-1$\sum_{i=1}^{n}$∑i=1n​ mi * ai = $\sum_{i=1}^{n}$∑i=1n​ mi * b_$\pi$π(i) (mod M)