Knapsack 背包密码系统：第一个被破解的公钥密码及其对现代密码学的启示

引言：从背包问题到公钥密码

1976 年 Diffie 和 Hellman 发表《密码学的新方向》，首次提出公钥密码思想。1978 年，Merkle 和 Hellman 在此基础上提出背包密码系统（Merkle-Hellman Knapsack，简称 MH 背包），这是历史上第一个实用的公钥密码方案。

背包密码的核心思想简洁优美：将子集和背包问题（NP-hard）作为陷门，构造一个"容易解"的私钥和一个"难以解"的公钥。这种基于难解问题的设计思路深刻影响了后续 RSA、基于格的密码学等方案。

然而，1982 年 Shamir 发现了 MH 背包的第一个有效破译方法，随后 Lagarias 和 Odlyzko、Hermes 等人进一步改进了攻击算法。MH 背包在发明仅四年后即被完全攻破，成为密码学史上最著名的失败案例之一。

本文将从数学原理、攻击方法和历史启示三个维度，系统解析背包密码系统。

一、数学基础：子集和背包问题

1.1 背包问题的定义

给定一个正整数序列 $A = (a_1, a_2, \ldots, a_n)$ 和目标值 $s$，子集和背包问题要求找到一组 $\{b_1, b_2, \ldots, b_n\} \in \{0, 1\}^n$，使得：

$$s = \sum_{i=1}^{n} a_i \cdot b_i$$

这是一个经典的 NP-complete 问题。当序列 $A$ 满足特定条件时（超递增序列），问题可以在多项式时间内求解；但一般情形下，已知最佳算法的复杂度约为 $O(2^{n/2})$（meet-in-the-middle 方法）。

1.2 超递增序列：陷门的本质

超递增序列的定义：对于序列 $A = (a_1, a_2, \ldots, a_n)$，若满足：

$$a_i > \sum_{j=1}^{i-1} a_j, \quad \forall i \geq 2$$

即每个元素大于前面所有元素之和，则该序列为超递增序列。

超递增序列的背包问题是多项式时间可解的。贪心算法即可：

Algorithm SuperIncreasingKnapsack(A, s):
    // A = (a_1, a_2, ..., a_n) 超递增序列
    // 返回 b_i 使得 s = Σ a_i * b_i
    for i from n down to 1:
        if s >= a_i:
            b_i = 1
            s = s - a_i
        else:
            b_i = 0
    return (b_1, b_2, ..., b_n)

贪心正确性的关键：由于 $a_i > \sum_{j=1}^{i-1} a_j$，所以若 $s \geq a_i$，则 $b_i$ 必须为 1（否则剩余元素之和不足以达到 $s$）。

1.3 从超递增序列到一般背包：乘性变换

MH 背包的核心技巧：将超递增序列 $A$ 通过模运算变换为一般序列 $B$，使得从 $B$ 恢复 $A$ 需要知道陷门信息。

变换公式：

$$b_i = w \cdot a_i \mod q$$

其中：

• $q > \sum_{i=1}^{n} a_i$ 是一个足够大的整数
• $w$ 是一个满足 $\gcd(w, q) = 1$ 的整数
• $B = (b_1, b_2, \ldots, b_n)$ 是公钥
• 私钥为 $(w^{-1} \mod q, q, A)$

二、Merkle-Hellman 背包密码体制

2.1 密钥生成

私钥：

• 选择一个超递增序列 $A = (a_1, a_2, \ldots, a_n)$
• 选择一个整数 $q > \sum_{i=1}^{n} a_i$
• 选择一个整数 $w$ 满足 $\gcd(w, q) = 1$
• 计算 $w^{-1} \mod q$

安全性假设：攻击者已知公钥 $B$，但不知道超递增序列 $A$、乘数 $w$ 和模数 $q$，因此无法高效求解背包问题。

2.2 加密过程

给定明文 $m = (m_1, m_2, \ldots, m_n) \in \{0, 1\}^n$：

$$c = \sum_{i=1}^{n} m_i \cdot b_i$$

密文 $c$ 就是背包问题的目标值。

2.3 解密过程

接收方已知私钥 $(w^{-1}, q, A)$：

• 计算 $c' = c \cdot w^{-1} \mod q$
• 由于 $c' \equiv c \cdot w^{-1} \equiv \sum m_i \cdot a_i \mod q$，且 $c' < q$（因为 $\sum m_i \cdot a_i < q$），所以：

• 使用贪心算法求解超递增背包问题，得到明文 $m$

2.4 正确性证明

验证解密正确：

$$c' = c \cdot w^{-1} \mod q = \left(\sum m_i \cdot b_i\right) \cdot w^{-1} \mod q = \sum m_i \cdot (w \cdot a_i) \cdot w^{-1} \mod q = \sum m_i \cdot a_i \mod q$$

由于 $\sum m_i \cdot a_i \leq \sum a_i < q$，所以取模后值不变：

$$c' = \sum_{i=1}^{n} m_i \cdot a_i$$

这就是一个超递增背包问题，可以用贪心算法高效求解。

2.5 参数选择示例

以 $n = 6$ 为例：

私钥生成：

• 超递增序列：$A = (2, 3, 6, 13, 27, 52)$

• $q = 105 > 2+3+6+13+27+52 = 103$ ✓
• $w = 31$，验证 $\gcd(31, 105) = 1$ ✓
• $w^{-1} \mod 105$：通过扩展欧几里得算法计算得 $w^{-1} = 61$（验证：$31 \times 61 = 1891 = 18 \times 105 + 1$）✓

• $b_1 = 31 \times 2 \mod 105 = 62$
• $b_2 = 31 \times 3 \mod 105 = 93$
• $b_3 = 31 \times 6 \mod 105 = 186 \mod 105 = 81$
• $b_4 = 31 \times 13 \mod 105 = 403 \mod 105 = 88$
• $b_5 = 31 \times 27 \mod 105 = 837 \mod 105 = 102$
• $b_6 = 31 \times 52 \mod 105 = 1612 \mod 105 = 37$

加密示例：明文 $m = (1, 0, 1, 1, 0, 1)$

$$c = 1 \times 62 + 0 \times 93 + 1 \times 81 + 1 \times 88 + 0 \times 102 + 1 \times 37 = 268$$

解密： $$c' = 268 \times 61 \mod 105 = 16348 \mod 105 = 73$$

验证：$\sum m_i \cdot a_i = 1 \times 2 + 0 \times 3 + 1 \times 6 + 1 \times 13 + 0 \times 27 + 1 \times 52 = 73$ ✓

贪心求解超递增背包：

• $a_6 = 52 \leq 73$，$m_6 = 1$，$s = 73 - 52 = 21$
• $a_5 = 27 > 21$，$m_5 = 0$
• $a_4 = 13 \leq 21$，$m_4 = 1$，$s = 21 - 13 = 8$
• $a_3 = 6 \leq 8$，$m_3 = 1$，$s = 8 - 6 = 2$
• $a_2 = 3 > 2$，$m_2 = 0$
• $a_1 = 2 \leq 2$，$m_1 = 1$，$s = 0$

三、经典攻击方法

3.1 Shamir 攻击（1982）

Shamir 发现 MH 背包存在一个结构性弱点：即使不知道 $q$ 和 $w$，也可以从公钥 $B$ 直接恢复明文。

核心观察：对于正确选择的参数，$b_i = w \cdot a_i \mod q$ 意味着：

$$b_i \approx w \cdot a_i - k_i \cdot q$$

其中 $k_i$ 是某个整数。如果 $w/q$ 的连分数展开中存在一个收敛项 $p/r$ 接近 $w/q$，则可以得到关于 $w$ 和 $q$ 的近似方程。

攻击步骤：

• 计算 $b_1 / b_n$ 的连分数展开
• 找到近似比值，得到候选的 $w'$ 和 $q'$
• 验证候选值是否满足超递增条件
• 用贪心算法解密

3.2 Lagarias-Odlyzko 攻击（1985）

Lagarias 和 Odlyzko 利用格基约简（Lattice Basis Reduction）方法破解 MH 背包。

格构造：给定公钥 $B = (b_1, b_2, \ldots, b_n)$ 和密文 $c$，构造如下格：

$$L = \left\{ (x_1, x_2, \ldots, x_n, y) \in \mathbb{Z}^{n+1} : \sum_{i=1}^{n} x_i \cdot b_i \equiv y \cdot c \mod q \right\}$$

该格包含一个短向量：

$$v = (m_1, m_2, \ldots, m_n, 1)$$

其中 $m_i \in \{0, 1\}$ 是明文比特。由于明文比特的特殊结构，该向量是格中的一个短向量。

求解方法：使用 LLL（Lenstra-Lenstra-Lovász）格基约简算法：

• 构造格的基矩阵
• 应用 LLL 算法得到约简基
• 从约简基中识别短向量，恢复明文

3.3 Hermes 攻击（1984）

Hermes 提出了一种基于整数规划的攻击方法，通过求解线性不等式系统来恢复明文。

核心思想：将背包问题建模为线性规划问题：

$$\min \sum x_i \quad \text{subject to} \quad \sum b_i x_i = c, \quad 0 \leq x_i \leq 1$$

当参数选择得当时，线性规划的解会自然地落在整数点上，从而恢复明文。

3.4 攻击总结

四、安全分析与失败原因

4.1 为什么 MH 背包不安全？

MH 背包的安全性依赖于"背包问题是 NP-hard"这一假设。然而，这种假设在密码学上是错误的，原因如下：

• 最坏情况 vs 平均情况：NP-hard 性保证的是最坏情况下的难解性，但 MH 背包构造的实例是平均情况下的特例。Shamir 攻击利用了这种特例的结构性弱点。

• 陷门泄露过多信息：MH 背包的变换 $b_i = w \cdot a_i \mod q$ 虽然隐藏了超递增序列 $A$，但公钥 $B$ 仍然保留了足够的代数结构信息，使得攻击者可以绕过陷门直接求解。

• 参数选择的脆弱性：MH 原始论文建议的参数选择策略（$q \approx 2 \sum a_i$，$w$ 随机选择）恰好留下了可以被连分数或格攻击利用的漏洞。

4.2 密码学教训

MH 背包的失败给密码学领域带来了深刻教训：

• 不能仅凭一个难解问题构造密码系统：NP-hard 性是必要的，但不够。密码系统需要证明在最坏情况和平均情况下都难解。

• 陷门密码需要严格的安全性证明：MH 背包的安全性缺乏形式化证明，仅依赖于直觉性的"背包问题难解"假设。现代密码学要求归约安全性（reductionist security）——将破解密码系统归约为求解某个已知的难解问题。

• 结构设计比数学工具更重要：MH 的乘性变换看似巧妙，但泄露了过多代数结构。现代密码系统设计更强调"最小信息泄露"原则。

五、从 MH 背包到现代格密码

5.1 格密码的兴起

MH 背包的失败催生了格密码学的发展。1996 年 Ajtai 提出了第一个具有严格安全性证明的格密码方案，证明了"平均情况下的硬问题可以归约到最坏情况的格问题"。

关键突破：

• Ajtai (1996)：第一个具有归约安全性证明的密码原语
• Goldreich-Goldwasser-Halevi (1997)：基于格的密码方案
• NTRU (1996)：基于格的公钥加密和密钥交换
• Lyubashevsky-Peikert-Regev (2010)：环签名和身份加密

5.2 LWE 问题：格密码的核心

Learning With Errors (LWE) 问题定义为：

给定 $(A, b = As + e \mod q)$，其中：

• $A$ 是随机矩阵 $\mathbb{Z}_q^{m \times n}$
• $s$ 是秘密向量 $\mathbb{Z}_q^n$
• $e$ 是误差向量（通常从高斯分布采样）

5.3 MH 背包与现代格密码的对比

5.4 国密视角下的启示

在中国国密标准体系中，虽然目前没有直接采用格密码的算法（SM2/SM3/SM4 均为传统密码体制），但以下方面值得借鉴：

• GM/T 0028-2014 密码模块安全技术要求：强调密码模块的安全性不能仅依赖单一算法的难解性，需要多层次的安全保障。

• 后量子迁移准备：随着 NIST PQC 标准化的推进（FIPS 203 ML-KEM、FIPS 204 ML-DSA、FIPS 205 SLH-DSA），国密体系也需要考虑后量子安全的演进路径。

• 标准制定方法论：MH 背包的失败提醒我们，标准的制定需要严格的密码分析验证，不能仅凭理论假设。

六、总结

背包密码系统作为公钥密码学的早期探索，虽然最终被证明不安全，但其历史贡献不可替代：

• 概念贡献：首次将 NP-hard 问题引入密码学设计，启发了后续的格密码研究。
• 方法论贡献：揭示了"陷门函数"设计的复杂性，推动了形式化安全证明的发展。
• 教育价值：作为密码学课程中的经典案例，帮助理解安全性证明的重要性。

参考

• Merkle, R., & Hellman, M. (1978). "Hiding Information and Signatures in Trapdoor Knapsacks." IEEE Transactions on Information Theory, 24(5), 525-530.
• Shamir, A. (1982). "A Polynomial-Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem." IEEE Transactions on Information Theory, 28(5), 699-703.
• Lagarias, J. C., & Odlyzko, A. M. (1985). "Solving Low-Density Subset Sums." Computational Complexity, 1(2), 93-109.
• Ajtai, M. (1996). "Generating Hard Instances of Lattice Problems." Proceedings of STOC '96.
• Goldreich, O., Goldwasser, S., & Halevi, S. (1997). "Public-Key Cryptosystems from Lattice Reduction Problems." Proceedings of CRYPTO '97.

相关实践

• 国密算法全链路性能基准
• SM2 椭圆曲线公钥密码算法
• 后量子密码学：从量子威胁到 NIST 标准化
• FIPS 203 (ML-KEM/Kyber) 后量子密钥封装标准深度解读