前言

背包密码（Knapsack Cryptosystem）是一类把“背包问题”用于加密的公钥密码。是人类历史上第一个公钥密码体系，但是在现代格密码体系下已经被攻破。本文我们将认识背包密码的同时，了解现代格密码体系是如何攻破它的。

背包问题

想象你有一个背包，以及一堆重量各异的物品。问题是：从中挑选哪些物品，能恰好装满背包？ 用数学语言说，就是给定一堆数字，问是否存在一个子集，其和恰好等于目标值。

例如，我们有重量如下的物品：

1
2, 3, 7, 14

你选择其中一些，要求总重量等于某个目标值。例如选择 2、7、14：

1
2 + 7 + 14 = 23

这个问题看似很简单，但是它已经被证明是一个 NP完全问题，也就是说不存在多项式级别的算法，这使得当数字很多时，暴力尝试所有组合的计算量会呈指数级爆炸，在经典计算机上几乎无法在合理时间内求解。

加密

将明文转换成二进制：

1
1101

这对应着我们选择了2、3、14，加密结果就是 $2+3+14=19$。

所以背包密码的加密如下：

  • 公钥：一串数字，表示可选的物品。
  • 明文：转换为二进制，一串 0/1 字符串。
  • 密文：选中的数字总和。

别人拿到密文 19 ，需要进行计算背包问题才能得到明文 1101。

解密

读到这里，聪明的你一定发现背包密码的解密是非常复杂的，如果公钥是普通的数字，那么我们解密它就等价于暴力解决一个NP完全问题，这显然是不行的。

但是，早期的背包密码应用了一个特殊的结构：超递增序列。

超递增序列：一个序列是超递增的，如果每一项都大于它前面所有项的总和。例如 {2, 3, 7, 14} 就是一个超递增序列。

我们接下来以 {2, 3, 7, 14} 为例，它满足：

1
2
3
3 > 2
7 > 2 + 3
14 > 2 + 3 + 7

这种序列是很容易解密的。对于总和 23，我们只需要从最大的数开始：

  1. $23 \ge 14$，选择 $14$ 剩下 $9$
  2. $9 \ge 7$，选择 $7$ 剩下 $2$
  3. $2 \lt 3$，不选
  4. $2 = 2$，选上，结束

得到明文：1011

这个过程是一个贪心算法。它的原理是超递增序列的性质，我们以 $23 \ge 14$ 时为例，如果我们不选择 $14$ ，那么剩下的所有数字加起来都没有 $14$ 大，那显然我们就选不出来了。

伪装

超递增序列解决了背包密码解密困难的问题，但是新的问题也出现了：如果直接把超递增序列公布出去，别人也能轻松解密。

为了解决这个新问题，我们需要对超递增序列进行“伪装”，本文以经典的 Merkle-Hellman 背包密码为例：

私钥中保存如下信息：

1
2
3
超递增序列 w
模数 m
乘数 a

其中满足 $gcd(a,m) = 1$，即 $a$ 与 $m$ 互素。

接下来根据私钥生成公钥，将每个私钥数字转化为：

$$b_i = a \times w_i \bmod m$$

这样公钥就不再是明显的超递增序列了。

举个例子：

1
2
3
w = [2, 3, 7, 14]
m = 31
a = 3

得到公钥：

1
b = [6, 9, 21, 11]

假设现在明文是 1101，我们选择公钥的 1 2 4 数字，得到密文 $6+9+11=26$。

这样进行加密后由于攻击者不知道模乘参数，无法精确恢复原始的超递增序列，而我们解密时只需要使用 a 的模逆元，就可以恢复超递增序列来贪心求解。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
import secrets
import gmpy2
from Crypto.Util.number import bytes_to_long, long_to_bytes


def keygen(n=64):
    """
    生成密钥

    w: 私钥超递增序列
    m: 模数
    a: 乘数
    pub: 公钥
    """

    # 生成超递增序列 w
    w = []
    total = 0

    for _ in range(n):
        x = total + secrets.randbits(128) + 1
        w.append(x)
        total += x

    # 生成大素数 m，保证 m > sum(w)
    m = int(gmpy2.next_prime(
        total + secrets.randbits(128) + 1
    ))

    # 随机生成与 m 互质的 a
    while True:
        a = secrets.randbelow(m - 2) + 2
        if gmpy2.gcd(a, m) == 1:
            break

    # 公钥
    pub = [(a * x) % m for x in w]

    return w, m, a, pub


def encrypt(data, pub, n=64):
    """
    使用公钥加密 bytes
    """

    bits = ""

    for x in data:
        bits += bin(x)[2:].zfill(8)

    # 补零到 n 的整数倍
    while len(bits) % n != 0:
        bits += "0"

    c = []

    for start in range(0, len(bits), n):
        block = bits[start:start + n]

        value = 0
        for i in range(n):
            if block[i] == "1":
                value += pub[i]

        c.append(value)

    return c, len(data)


def decrypt(c, w, m, a, length, n=64):
    """
    使用私钥解密
    """

    # 计算 a 在 mod m 下的逆元
    a_inv = int(gmpy2.invert(a, m))

    bits = ""

    for x in c:
        # 还原私有背包和
        s = (x * a_inv) % m

        block = ["0"] * n

        # 超递增序列贪心求解
        for i in range(n - 1, -1, -1):
            if w[i] <= s:
                block[i] = "1"
                s -= w[i]

        bits += "".join(block)

    # 二进制转回 bytes
    data = bytearray()

    for i in range(0, len(bits), 8):
        x = int(bits[i:i + 8], 2)
        data.append(x)

    return bytes(data[:length])


if __name__ == "__main__":
    # 生成密钥
    w, m, a, pub = keygen(n=64)

    # 明文
    plaintext = b"hello knapsack"

    # 加密
    c, length = encrypt(plaintext, pub)

    # 解密
    result = decrypt(c, w, m, a, length)

    print("ciphertext =", c)
    print("plaintext  =", plaintext)
    print("result     =", result)
    print("success    =", plaintext == result)

格攻击

约定

设背包公开参数为

$$ a_1,a_2,\ldots,a_n, $$

明文对应的比特为

$$ x_1,x_2,\ldots,x_n,\qquad x_i\in{0,1}, $$

密文为

$$ c=\sum_{i=1}^{n}a_i x_i. $$

攻击者知道 $a_i$ 和 $c$，但不知道 $x_i$。

构造格基

选择一个足够大的缩放参数 $M$，构造格向量：

$$ \begin{aligned} \mathbf v_1&=(2,0,\ldots,0,2Ma_1),\ \mathbf v_2&=(0,2,\ldots,0,2Ma_2),\ &\ \vdots\ \mathbf v_n&=(0,0,\ldots,2,2Ma_n). \end{aligned} $$

这里构造时都乘了 2，目的是避免待会儿我们找到希望距离一样近的点出现 $\frac{1}{2}$。

格中的每个点可以表示为：

$$ \mathbf p = \sum_{i=1}^{n}2z_i\mathbf v_i, \qquad z_i\in\mathbb Z. $$

展开得到：

$$ \mathbf p = (2z_1,2z_2,\ldots,2z_n,;2M\sum_{i=1}^{n}a_i z_i). $$

构造目标点

当所有的 $z_i = x_i$ 的时候，这个向量就表示了背包问题的解。

原因是：

$$\sum_{i=1}^{n}a_i x_i=c. $$

所以正确明文会产生一个最后坐标恰好等于 $2Mc$ 的格点。

我们令目标点为：

$$ \mathbf t = \left( 1,1,\ldots,1,;2Mc \right). $$

这里令前面都是 $1$ 的原因是我们希望目标到 $0$ 和 $2$ 的距离一样近，只有这样才能前面无论是 $0$ 还是 $2$ 误差都一样大，才能不让算法偏向于选择 $0$ 或者 $1$。在后面的构造中会讲到。

正确的格点与目标点之差为：

$$ \mathbf p^\ast-\mathbf t = \left( 2x_1-1, 2x_2-1, \ldots, 2x_n-1, 0 \right). $$

由于 $2x_i \in {0,2}$

所以每个坐标都满足：$2x_i - 1 \in {-1,1}$

因此正确答案对应的向量长度为：

$$ \left|\mathbf p^\ast-\mathbf t\right| = \sqrt{ \sum_{i=1}^{n} \left(2x_i-1\right)^2 } = \sqrt {n}. $$

而错误的格点由于：

$$\sum_{i=1}^{n}a_i x_i \ne c. $$

这会导致最后一维的误差会被 $M$ 放大成一个极大的误差，这就得到了以下的结论：

  • 正确答案最后一维的误差是 $0$
  • 错误答案最后一维误差极大

这可以推出 $p^\ast - t$ 对应的是一个短向量。

将目标点加入格构造

上面我们已经证明了正确格点与目标点的差很短，为了让这个差本身成为格向量，我们将目标点也加入生成向量：

$$b_0 = t = \left( 1,1,\ldots,1,;2Mc \right)$$

于是，新格中包含了这个整数线性组合：

$$\sum_{i=1}^{n}x_iv_i-b_0 = p^\ast-t = (2x_1-1,\ldots,2x_n-1,;0)$$

注意：这里的 $v_i$ 本身已经给 $x_i$ 提供了 $2$ 的系数！

格基规约

我们已经知道了正确的明文会在这个格中产生一个向量 $p^\ast - t$ ，而它等于 $(2x_1-1,\ldots,2x_n-1,;0)$。

因此我们可以将这个格使用 LLL 算法进行格基规约，得到更短的基向量。

因为这个向量 $p^\ast - t$ 是一个短向量，所以它很有可能在格基规约后的格基之中，因此我们在新的格基中找到：

$$\mathbf w=(w_1,\ldots,w_n,0),\qquad w_i\in{-1,1}.$$

这就是我们要找的向量，根据我们刚刚的构造，$w_i = 2x_i -1$，进行移项：

$$x_i = \frac{w_i +1}{2}$$

这样我们就能恢复 $x_i$ 了，接下来就贪心解密即可！

注意：这里 -1 的贡献是因为我们刚刚对整体进行了一个减去 $b_0$ 的操作的原因。