我们已经知道，基于数学难题，可以构建陷门单向函数，从而生成一套公钥密码体系：这是 RSA、ECC 的思路。NP完全（NP-complete）问题是一类非常困难的问题，目前没有已知的多项式算法。显然可以考虑在其上构建公钥密码体系。
第一个尝试是 Merkle 和 Hellman 在上世纪 70 年代做出的。他们采用了子集和问题——顺带一提，密码学中经常把这个问题也叫做“背包（knapsack）”。描述如下：
子集和问题
给定一个正整数集合 $(M_1, M_2,\dots ,M_n)$ 以及一个整数 $S$. 选择子集使其和等于 $S$.
举个例子：$\newcommand\bm{\boldsymbol{M}} \bm = (2,3,4,9,14,23), S=21$. 我们选取子集 $\{3,4,14\}$，其和等于 21。显然，子集和问题可能有唯一解，可能无解，可能多解。我们只考虑至少有一个解的情况。
接下来，我们尝试利用子集和问题的困难性，构建一个公钥密码体系。取 $$\bm = (M_1, M_2,\dots,M_n)$$ 为公钥，Bob 想发送一条消息，于是将其编码为二进制向量 $\newcommand\bx{\boldsymbol{x}} \bx = (x_1, x_2,\dots,x_n) $，其中 $x_i$ 非 0 即 1。Bob 计算$$S = \sum_{i=1} ^ n x_i M_i$$然后将 $S$ 发送给 Alice. 而 Alice 想要解密，必须找到一个合法的 $\bx$，这等价于找到 $\bm$ 的子集，使之和等于 $S$.
如果 Alice 能快速找到合法的 $\bx$ 而敌手找不到，那么这个密码体系就是有效的，可惜 Alice 并没有这种手段。这个密码体系中没有引入陷门信息，所以 Alice 解密与 Eve 解密的难度是一样的。
来考虑如何较快地解决子集和问题（尽管仍然是指数级的），这也是敌手能用上的最好的手段之一。Eve 把 $\bm$ 划分成两半，然后对于左边那一半，枚举其所有子集 $\newcommand\bi{\boldsymbol{I}} \bi$，记录子集和 $A_\bi$；对于右边，也同样操作，得到 $\newcommand\bj{{\boldsymbol{J}}} B_\bj$. 如果存在一对 $A_{\bi_0},B_{\bj_0}$ 使得它们的和等于 $S$，那我们就解决了问题。
这是一个 Meet In The Middle 算法，核心思想是以空间换时间。纯暴力做法是 $\newcommand\O{\mathcal{O}} \O(1)$ 空间、$\O(2 ^ n)$ 时间，MITM 将之改进到了 $\O(2 ^ {n/2})$ 空间、$\O(2 ^ {n/2})$ 时间。
之前提到过，Alice 必须有陷门信息，才能快速完成解密，这个公钥密码方案才能有效。接下来我们讨论一种非常简单的子集和问题——超级递增序列上的子集和：
超级递增序列
称一个序列 $\newcommand\b{\boldsymbol} \newcommand\br{\b{r}} \br = (r_1, r_2, \dots, r_n)$ 是超级递增序列，当且仅当满足 $$r_{i+1} \geq 2r_i ,\quad \forall ~ 1\leq i \leq n-1$$
也就是说，超级递增序列是指“后一个数比前一个数至少大一倍”的序列。显然就有性质 $$r_k > \sum _{i=1} ^ {k-1} r _i$$归纳法易证。从这个性质出发，立刻就知道，对于超级递增序列的子集和问题，贪心算法是正确的。伪代码如下：
for i in range(n, 0, -1):
if S >= r[i]:
S -= r[i]
print(r[i])给个例子。有 $\bm=(3, 11, 24, 50, 115)$ 是超级递增序列，$S = 142$. 那么首先检查 $142>115$，故输出 115，$S$ 改为 $142 - 115 = 27$。接下来 50 被忽略，输出 24，$S$ 变为 3。最后输出 3。共输出 115、24、3，生成 $\bx = (1,0,1,0,1)$，完成解密。
采用超级递增序列，Alice 是可以快速解密了；但敌手也可以。仍然没有起到添加陷门信息的作用。Merkle 和 Hellman 提出了下面的方案：
- Alice 生成一个超级递增序列 $\br$，还选择两个保密的整数 $A, B$ 满足 $$B>2r_n , \qquad \gcd(A,B)=1$$
- Alice 计算一个公钥序列 $$M \equiv A\cdot r_i \pmod B$$显然它不是超级递增序列。乘以 $A$ 起到了混淆的作用。
- Bob 要加密 $\bx$，他发送 $$S=\bx\cdot\bm= \sum _{i=1} ^ n x_ i M _i$$
- Alice 要解密 $S$，首先计算出 $$S^\prime \equiv A^ {-1} S \pmod B$$然后 Alice 求子集和问题 $(\br, S ^ \prime)$ 的解，即可解密。
要说明为什么新问题的解就是原问题的解。我们注意到 $$S ^ \prime \equiv A ^ {-1} \sum_{i=1} ^n x_i M_i \equiv A ^ {-1} \sum_{i=1} ^n x_i A r_i \equiv \sum_{i=1} ^n x_i r_i \pmod B$$而 $B$ 是一个非常大的数，故 $S$ 就是 $\bx \cdot \br$ 的确切值。
from random import randint
import gmpy2, numpy as np
class MerkleHellman():
def __init__(self, nbits):
r = [randint(10, 20)]
for x in range(nbits - 1):
r.append(randint(2*r[-1], 3*r[-1]))
while True:
B = randint(2*r[-1] + 1, 3*r[-1])
A = randint(2*r[-1] + 1, 3*r[-1])
if gmpy2.gcd(A, B) == 1:
break
print(f'A = {A}, B = {B}')
print(f'r = {r}')
M = [A*x % B for x in r]
print(f'M = {M}')
self.A, self.B, self.r, self.M = A, B, r, M
def enc(self, x):
return np.dot(x, self.M)
def dec(self, S):
S = S * gmpy2.invert(self.A, self.B) % self.B
print(f"S' = {S}")
ans = []
for t in self.r[::-1]:
if S >= t:
ans.append(1)
S -= t
print(f'find {t}, S <- {S}')
else:
ans.append(0)
return ans[::-1]
worker = MerkleHellman(5)
# A = 1049, B = 836
# r = [19, 39, 89, 195, 410]
# M = [703, 783, 565, 571, 386]
c = worker.enc([1,0,1,1,0])
print(c)
# 1839
worker.dec(c)
# S' = 303
# find 195, S <- 108
# find 89, S <- 19
# find 19, S <- 0
# [1, 0, 1, 1, 0]这套公钥加密体系，被称为子集和密码系统，或称背包密码。其核心思想是生成一个超级递增序列，然后用模线性运算进行混淆，将混淆之后的序列作为公钥。
我们之前提到过 MITM 算法。在 MITM 攻击下，要做到 $2 ^ {80}$ 时间安全，需要 $n > 160$ 的密钥；另外，如果 $\br$ 序列很小，则攻击者可以直接猜测 $\br$，故要保证安全，还需要 $r_1 > 2 ^ {n}$，也就是说 $$M _i = \O(2 ^ {2n}), S = \O(2 ^ {2n})$$这些条件会导致公钥 $\bm$ 很大，例如 $n=160$ 的公钥大概需要 51200 bit 的空间来存放，与之相比，做到 $2 ^ {80}$ 安全的 RSA 公钥仅需大概 1000 bit 的空间。不过，背包密码的加密和解密速度都非常快。
1985年，LLL 算法提出之后，背包密码遇到了巨大的挑战。简而言之，如果 $n$ 比 300 要小，那么攻击者可以通过 lattice reduce，从 $S$ 中高效地恢复 $\bx$. 然而，如果 $n>300$，私钥长度将会高达 176kB，很多情况下这是不太能接受的。
接下来，我们看敌手 Eve 如何通过 lattice 来攻击背包密码。首先，她拿到公钥 $\bm = (m_1, \dots, m_n)$，然后构造下面的矩阵$$\begin{pmatrix} 2&0&0&\cdots&0&m_1\\0&2&0&\cdots&0&m_2 \\ 0&0&2&\cdots&0&m_3 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0&0&0&\cdots& 2 & m _ n \\ 1&1&1&\cdots &1&S\end{pmatrix}$$这个矩阵的行向量是$$\newcommand\bv{\b{v}}\begin{aligned} \bv_1 &= (2,0,0,\dots,0,m _1 ) \\ \bv_2 &= (0,2,0,\dots,0,m _2 ) \\ \vdots & \qquad \qquad \vdots\\ \bv_n &= (0,0,0,\dots,2,m _n ) \\ \bv_{n+1} &= (1,1,1,\dots,1, S) \\\end{aligned}$$显然，这些行向量的（整数系数）线性组合构成了一个 lattice： $$L=\{a_1 \bv_1 + a_2 \bv_2 + \cdots + a_n \bv_n + a_{n+1}\bv_{n+1} : a_1, a_2, \dots,a_{n+1} \in \mathbb{Z}\}$$
现在来考虑我们背包问题的解，也就是明文 $\bx = (x_1, \dots, x_n)$。$L$ 显然包含 $$\b{t} = \sum _{i=1} ^ n x_ i \bv_i - \bv_ {n+1} = (2x_1 - 1, 2x_2 - 1, \dots, 2x_n - 1, 0)$$接下来就是问题的关键了。既然 $x_i$ 全是 0 或 1，那么 $\newcommand\bt{\b{t}} \bt$ 的前面 $n$ 个参数都是 $\pm 1$，导致 $\bt$ 很短，有 $\Vert \bt \Vert = \sqrt n$。而生成这个 lattice 的向量，长度都达到了 $\O(2 ^ {2n})$，它们的线性组合能短到 $\sqrt n$ 这个程度的，相当稀有；我们甚至可以认为只有 $\bt$ 这一个（零向量是平凡的，忽略掉）。那么，如果 Eve 可以快速找到 lattice 里面的短向量，那么她就可以恢复出明文。
在 lattice 里面找短向量的算法，称为 lattice reduction（格基规约）算法。著名的 LLL 即是一个格基规约算法，它还有变种 LLL-BKZ。
现在我们利用 LLL 算法来攻击背包密码。考虑下面的问题实例：
M = [816358673, 214551389, 683509053, 377954927, 461648693, 819009687, 833612683, 246393449, 258952137, 592274653, 439857687, 164289531, 138621939, 626982035, 733582939, 561376076, 206910526, 470721180, 1105393379, 848577580]
msg = [1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0]
S = 6545130222于是构造出一个 Lattice 如下：
n = len(M)
L = matrix.zero(n + 1)
for row, x in enumerate(M):
L[row, row] = 2
L[row, -1] = x
L[-1, :] = 1
L[-1, -1] = S运行 LLL 算法进行格基规约：
res = L.LLL()
print(res)
'''
[-1 1 -1 -1 1 -1 1 -1 -1 1 -1 1 -1 -1 1 -1 1 -1 -1 1 0]
[ 2 2 0 2 -2 -2 2 -2 0 0 -4 2 0 0 0 0 0 0 0 0 0]
[ 0 2 0 0 2 -4 0 2 0 0 4 -2 0 0 0 0 0 0 0 0 0]
[-1 -1 1 1 1 -3 -1 -1 1 -1 3 -1 -1 1 3 1 -1 3 1 -1 3]
[ 2 0 0 0 2 2 0 -2 2 0 -4 2 2 -2 -4 2 0 0 0 0 0]
[-1 -1 -1 1 1 1 1 -1 -1 3 -3 1 -1 -1 -1 1 -1 3 -1 -3 2]
[-4 2 0 -2 0 0 2 0 2 2 2 -2 -2 0 0 -2 0 0 -2 -2 -1]
[-1 1 1 1 3 -1 -1 -1 3 1 1 -3 -1 1 1 -3 1 -1 1 1 -1]
[ 1 -3 1 1 -1 -1 1 -1 -3 1 -1 -1 -5 1 1 -1 1 1 1 1 2]
[ 3 -3 -1 -1 1 1 -3 -1 -1 5 -1 -1 1 1 -1 1 -1 1 1 -1 0]
[ 0 2 0 2 4 0 -2 0 -4 0 0 0 -2 0 0 -2 0 0 -2 -2 -1]
[ 2 -2 0 0 2 0 -2 0 0 -2 -4 4 0 0 0 0 0 -2 -2 0 -2]
[ 1 1 1 1 -3 -3 3 1 3 1 1 1 -3 -3 1 1 -1 1 1 -1 0]
[ 1 -1 -1 -1 1 -1 -3 -1 -1 1 1 1 1 3 3 -5 1 1 -1 -1 1]
[-3 1 -3 -1 3 3 3 -1 1 -1 1 -1 1 1 -1 1 -1 1 1 -1 0]
[ 0 0 2 0 0 0 0 2 -2 -2 2 -6 0 0 0 -2 0 0 -2 -2 -1]
[ 0 -2 0 -4 2 0 2 2 0 2 -2 4 -2 0 0 0 0 2 2 0 2]
[-2 -2 -2 -2 2 0 -2 -2 2 0 0 0 2 0 0 -2 -2 0 -2 4 2]
[ 2 -2 0 -2 -4 0 2 0 0 0 -2 0 -2 2 0 -2 -4 0 0 -4 3]
[-2 0 0 -2 0 0 0 0 0 -2 -4 0 -2 -2 -4 2 2 0 0 -2 -1]
[ 1 1 -1 1 1 -1 -1 -1 1 -3 -1 -3 -3 -1 1 1 1 1 -1 1 3]
'''可以发现第一行的相反向量就是解。