1976 年，Diffie 和 Hellman 刚把"公钥密码"这个概念抛出来，整个圈子都在找一件事：谁能先造出一个真正能跑的方案。

两年后，Hellman 拉着 Merkle 率先交了卷。他们没用大数分解，也没用离散对数，而是用了一个谁都能听懂的问题——如何往背包里装满东西？。这就是背包密码，历史上第一个公钥密码体制，比 RSA 的论文正式发表还早几个月。

后来的事你大概知道，今天它只出现在课本里，而且多半是作为反面教材。本文将科普介绍背包密码的过程和原理。

一、背包到底是什么？

想象地上摊着一堆哑铃，每个重量不一样，我再报一个目标重量给你——你能不能挑出其中几个，往秤上一放，指针正好停在我说的数上  呢？

密码学里这叫子集和问题，也常直接叫"背包"问题。n 个物品每个只有装或不装两种状态，朴素穷举就得挨个试过来，n 个物品最坏要试 2ⁿ 种挑法，这是指数级的，n 一大时间复杂度就耗不起。它是 NP‑完全问题，1978 年 Merkle 和 Hellman 看中的就是这一点。

但这里有个特别有意思的反转：背包问题并不是都一样难。

有一种背包简直是送分题，叫超递增序列——每一项都比它前面所有项加起来还大。比如 1, 3, 5, 11, 22：3 比 1 大，5 比 1+3 大，11 比 1+3+5 大……以此类推。

这种背包问题的解决从最大的开始往回贪心就行：从最大的一项开始，倒着往回走。当前剩余重量记作 S，看当前项 rₖ：S ≥ rₖ 就装上，把 S 减去 rₖ；S < rₖ 就跳过。走到头，S 归零就说明凑出来了。

用 1, 3, 5, 11, 22 凑 30：

结果 (0, 1, 1, 0, 1)，即 22 + 5 + 3 = 30。

你会发现，上面这五行里，没有任何一行存在第二种选法。

动作为 跳过那几行好理解——rₖ 比剩余重量还大，装进去必然超。动作为 装那一步才是超递增的性质作祟：

对于第k个物品，我们只有装和不装两种选项。而我们偏选择背包里不装 rₖ，那就只能从 r₁ 到 rₖ₋₁ 里凑。可这些项加起来也小于 rₖ（这正是超递增的定义），更小于 S，凑不满。所以只要 S ≥ rₖ，rₖ 就必须在解里。

两个方向都被堵死，每一位的 0 或 1 都是唯一确定的。由此得到：

• 解是唯一的；
• 不需要回溯，n 个物品扫一遍就完事；
• 如果走到最后 S 不为零，那不是没找对，而是根本无解。

对照一下普通背包就知道超递增序列的巧妙了。拿 3, 5, 6, 7 凑 11：贪心先拿 7 剩 4，6 和 5 都太大跳过，拿 3 剩 1，卡住。但 5 + 6 = 11 明明是解——6 < 3 + 5，这个序列不满足超递增，贪心立刻就失效了。

所以私钥这一边不只是比较好算，还有线性时间、无分支、答案唯一。这个落差正是整个方案设计的根因。

看上面这张图就明白了：左边是超递增的私钥，规规矩矩、一眼能看穿；右边是它化过妆之后的样子，杂乱无章、难以下手。Merkle–Hellman 的全部玄机，就藏在这"两副面孔"之间。

二、Merkle–Hellman 背包密码

真正麻烦的地方，其实不只是要找到一个别人难解的问题，合法接收方自己也需要高效解密。公钥密码真正需要的是一种“陷门”：对外看起来很难，但掌握某些秘密信息后，问题就能迅速变简单。

Merkle-Hellman 背包密码采用的就是这个思路。

它先选取一个超递增序列 r 作为私钥。超递增序列的特点是，每一项都大于前面所有项之和，对应的子集和问题可以直接用贪心算法求解，本身并不困难。

接下来再选择两个秘密参数 A 和 B。其中 B 要大于超递增序列所有元素的总和，同时要求 A 与 B 互质。

然后对私钥中的每个元素做一次模乘：

得到的新序列 M 就作为公钥公开。

经过这一步之后，原本超递增序列中很明显的大小关系被打乱，从外部看，M 更像一个普通的背包序列，很难再直接使用贪心算法求解。

加密时，发送方把明文表示成一串二进制比特 xi。某一位为 1，就取公钥中对应的 Mi，最后把这些数相加，得到密文：

解密时，接收方因为知道秘密参数 A 和 B，可以先求出 A 在模 B 下的逆元，再计算：

由于公钥本身是由 A⋅ri 模 B 得到的，这一步相当于把之前的模乘变换逆回来，使问题重新回到原来的超递增背包上。

这时再按照从大到小的顺序做一次贪心选择，就可以很快恢复出原来的 0/1 比特，也就是明文。

所以 Merkle-Hellman 的核心其实很直接：先构造一个自己容易求解的背包，再通过模乘把它伪装成一个看起来困难的背包；公钥负责隐藏结构，私钥负责把这个结构恢复出来。

三、流程示例

下面用一组很小的参数走一遍完整流程。

先选一个超递增序列作为私钥：

r = (2, 3, 7, 14, 30, 57, 120, 251)

再取：

A = 41, B = 491

这里需要满足两个条件：

B > 2+3+7+14+30+57+120+251 = 484

同时：

gcd(41, 491) = 1

所以这组参数是符合要求的。

因为 41 和 491 互质，可以求出 41 在模 491 下的逆元：

A⁻¹ ≡ 12 (mod 491)

接下来生成公钥：

Mᵢ = 41·rᵢ (mod 491)

得到：

M = (82, 123, 287, 83, 248, 373, 10, 471)

这时已经很难从表面上看出它原来来自一个超递增序列。

假设要加密的明文比特为：

x = (1, 0, 1, 1, 0, 1, 0, 1)

这里最关键的是中间那一步。

对不知道私钥的人来说，他看到的是公钥

(82, 123, 287, 83, 248, 373, 10, 471)

以及密文 1296，面对的是一个普通的子集和问题。

而掌握 A 和 B 的接收方，只需要乘上模逆元，就能把问题重新变回：

331 = 251 + 57 + 14 + 7 + 2

到了超递增序列这一步，后面的求解就很简单了。

这就是 Merkle–Hellman 最核心的设计：公开的是一个看起来没有明显结构的背包，私钥保存的则是把它恢复成简单背包的方法。

四、退出历史舞台

这个方案的问题也恰恰出在这里。

Merkle 和 Hellman 原本希望通过模乘，把一个容易求解的超递增背包伪装成普通背包。但这种变换并没有把原来的结构完全隐藏掉。

1982 年，Adi Shamir 给出了针对基本 Merkle–Hellman 方案的多项式时间攻击。

这里有一个很重要的地方：攻击者并不一定要恢复原始的 A、B 和超递增序列。

只要能找到另一组参数，使公钥重新对应到一个容易求解的超递增背包，就已经足够解密了。

换句话说，密码分析者需要找到的不是“原来的私钥”，而是一组能够发挥同样作用的等价陷门。

这件事也暴露出了 Merkle–Hellman 更根本的问题：公钥虽然经过了变换，但仍然保留了过多与私钥结构有关的信息。

同一时期，格算法的发展又给背包密码带来了更大的压力。

1982 年，Lenstra、Lenstra 和 Lovász 提出了著名的 LLL 格基约简算法。它最初并不是为攻击背包密码设计的，但很快就被密码分析者用于子集和问题。

基本思路是把子集和关系编码到一个高维格中。

设密文满足：

其中：

因为明文系数只能取 0 或 1，所以正确解在构造出的格中往往对应某种异常短的向量。

而 LLL 擅长做的事情，正是寻找格中的短向量。

因此，原本看起来需要在大量 0/1 组合中搜索的问题，可以被转化成一个格约简问题。对于某些参数范围，尤其是低密度背包，这种攻击非常有效。

这里通常会引入一个指标，叫做背包的密度：

其中 n 是背包元素的数量，max M_i 大致反映每个元素的数值规模。

直观地说，如果元素数量不多，但每个数都很大，那么这个背包在数值空间里就比较“稀疏”，也就是低密度。

低密度情况下，正确的 0/1 解在格中往往更加突出，也更容易被格约简算法找到。

Lagarias 和 Odlyzko 在后续工作中系统研究了低密度子集和问题，给出了大约 0.6463 的经典密度界。之后的研究又进一步提高了格攻击能够处理的密度范围。这也是为什么后来谈到背包密码时，“低密度”几乎总会和“格攻击”一起出现。

当然，也可以继续增大参数，把背包密度做高。

问题是这样做之后，密钥规模和计算量也会迅速增加。为了同时抵抗中间相遇攻击、格攻击以及其他针对背包结构的分析，参数需要不断膨胀，最后会失去早期背包密码原本希望获得的效率优势。

而与此同时，RSA 等公钥密码体制已经有了更清晰的安全分析和更成熟的工程实现。

于是 Merkle–Hellman 面临的就不再只是“某个参数被攻破”的问题，而是整个设计路线的性价比开始变得很差。

1990 年，Andrew Odlyzko 写下了那篇很有名的文章：

The Rise and Fall of Knapsack Cryptosystems

从今天回头看，Merkle–Hellman 确实已经退出了实际密码系统，但它留下来的东西远比这个算法本身更重要。

五、遗留瑰宝

Merkle–Hellman 最值得记住的地方，其实不是“背包密码失败了”，而是它非常清楚地说明了两个问题。

• NP 完全，不等于一个密码系统就安全
• 格既能攻击密码，也能构造密码

子集和问题是 NP 完全问题，这一点没有错。但密码系统使用的并不是“所有可能的子集和实例”，而是一类经过专门构造的实例。这两件事不能混为一谈。

Merkle–Hellman 为了解密方便，先选了一个超递增背包，然后再通过模乘把它变成公钥。问题就在于，这种特殊的生成方式给公钥留下了额外结构。攻击者并不需要解决任意的 NP 完全问题。

他只需要解决：

而这个问题，比一般的子集和问题简单得多。所以在密码学里，仅仅说“方案基于一个 NP 完全问题”基本没有意义。真正需要分析的是：你实际生成出来的这些实例，到底是不是难的。

这也是 Merkle–Hellman 留下的一个非常典型的教训。

背包密码的另一段历史也很有意思。

LLL 和格约简最早进入很多密码学教材时，经常是作为密码分析工具出现的。

它们可以攻击低密度背包、分析某些 RSA 特殊情况，也可以用于寻找隐藏在整数关系中的短向量。

但几十年之后，格本身又成了现代公钥密码的重要基础。

现在常见的 LWE、Module-LWE、Module-SIS 等问题，以及 NIST 后量子密码标准中的 ML-KEM（原 Kyber）和 ML-DSA（原 Dilithium），背后都和格问题密切相关。不过现代格密码和 Merkle–Hellman 并不是同一种思路。

Merkle–Hellman 的核心是：

而现代 LWE 类密码的核心则更接近：

两者都和整数结构、格以及短向量有关，但安全机制完全不同。所以把后量子格密码简单理解成“现代版背包密码”，其实并不准确。还有一个比较特别的例子是 Chor–Rivest 背包密码。它没有继续采用 Merkle–Hellman 那种“超递增序列 + 模乘”的构造，而是换了一条完全不同的路线。这也从侧面说明了Merkle–Hellman 的失败，并不能简单归结为“子集和不能拿来做密码”，真正出问题的，是它选择的那套陷门结构没有隐藏好。

写在最后

Merkle–Hellman 今天已经没有实际部署价值，但它仍然是一个很适合入门公钥密码的例子。它几乎把公钥密码里几个很重要的概念都集中在了一起——困难问题、陷门、公钥与私钥的关系、特殊实例的安全性、密度，以及后来非常重要的格攻击。

而且这些东西都可以用很小的参数亲手算一遍。从学习的角度看，它比单纯记一个“Merkle–Hellman 已被攻破”的结论有价值得多。因为真正值得理解的不是它为什么失败，而是一个看起来建立在困难问题上的密码系统，为什么仍然可能因为自己的构造方式而变得容易攻击。

这也是 Merkle–Hellman 到今天仍然值得讲的原因。至于实际系统，就不要再考虑它了。它很适合拿来学习密码学，却不适合拿来保护任何真实数据。到 1990 年，Odlyzko 干脆写了篇《兴衰史》（The rise and fall of knapsack cryptosystems）给这段历史盖棺：背包密码正式进博物馆。

参考资料与延伸阅读

正史文献

• R. Merkle, M. Hellman, Hiding information and signatures in trapdoor knapsacks, IEEE Trans. Information Theory, 1978（被引≈1430）｜https://ieeexplore.ieee.org/abstract/document/1055927/

• A. Shamir, A polynomial time algorithm for breaking the basic Merkle‑Hellman cryptosystem, FOCS 1982（被引≈809）｜https://ieeexplore.ieee.org/abstract/document/4568386/

• A. K. Lenstra, H. W. Lenstra, L. Lovász, Factoring polynomials with rational coefficients（LLL 原文）, Mathematische Annalen, 1982（被引≈6769）

• L. M. Adleman, On breaking generalized knapsack public key cryptosystems, STOC 1983（被引≈113）

• E. F. Brickell, Solving low density knapsacks, CRYPTO'83 论文集, 1984（被引≈183）

• A. Odlyzko, Cryptanalytic attacks on the multiplicative knapsack cryptosystem…, IEEE Trans. Inf. Theory, 1984（被引≈93）

• J. C. Lagarias, A. M. Odlyzko, Solving low‑density subset sum problems, Journal of the ACM, 1985（被引≈745）｜https://dl.acm.org/doi/abs/10.1145/2455.2461

• E. F. Brickell, A. M. Odlyzko, Cryptanalysis: A survey of recent results, Proceedings of the IEEE, 1988（被引≈245；Chor–Rivest 的论述在这）

• P. Q. Nguyen, J. Stern, The two faces of lattices in cryptology, CaLC 2001（被引≈383；0.6463 这个密度阈值的综述出处）

• A. M. Odlyzko, The rise and fall of knapsack cryptosystems, 1990

• J. Surin, S. Cohney, A gentle tutorial for lattice‑based cryptanalysis, ePrint 2023/032