1. 从背包问题到公钥密码一个天才的构想如果你对密码学感兴趣或者听说过“公钥密码”这个概念那么RSA、ECC这些名字可能耳熟能详。但你是否知道现代公钥密码学的思想火花最早可能源自一个听起来非常“计算机科学”的问题——背包问题这就是我们今天要深入探讨的背包密码Backpack Cryptography更具体地说是它的开山之作Merkle–Hellman背包加密系统。我第一次接触这个概念时感觉非常反直觉。一个用来解决组合优化、听起来像算法竞赛题的“背包问题”怎么能用来加密信息呢这就像用“如何最有效地装行李箱”的规则来设计一把锁听起来风马牛不相及。但正是这种跨界思维在1978年由Ralph Merkle和Martin Hellman提出成为了公钥密码学的早期重要实践之一甚至比RSA的公布还早一点。它的核心魅力在于利用一个问题的两种形态——“简单背包”和“困难背包”——来分别构造加密和解密的密钥。理解它不仅能帮你解开一些CTFCapture The Flag竞赛中的经典密码学题目更能让你深刻体会到公钥密码学“陷门单向函数”的精髓正向计算容易反向求解在不知道特定“陷门”时则极其困难。那么背包问题具体是什么简单说你有一个背包容量有限面前有一堆重量各不相同的物品。你的目标是选出一些物品恰好装满背包即物品总重量等于背包容量。在密码学语境下我们通常讨论的是子集和问题Subset Sum Problem给定一个正整数集合称为背包向量和一个目标总和能否从集合中选出一个子集使其元素之和等于目标值Merkle-Hellman的巧妙之处在于它没有直接使用一个困难的背包问题而是先构造一个具有特殊性质的“简单背包”超递增序列然后通过一个数学变换将其伪装成一个“困难背包”。知道变换“陷门”的人可以轻松将困难问题还原为简单问题来解密而不知道陷门的人则要面对一个公认的NP难问题。接下来我们就从最基础的超递增序列开始一步步拆解这个经典的加密系统并通过一道典型例题手把手带你实现破解领略其中蕴含的数学之美与破解之趣。2. 超递增序列一切简单性的起点要理解背包密码必须先搞懂什么是超递增序列Superincreasing Sequence。这是整个系统的基石也是私钥持有者能够快速解密的根本原因。2.1 超递增序列的定义与性质一个序列(a1, a2, ..., an)被称为超递增序列如果序列中的每一个元素都严格大于它前面所有元素之和。用数学公式表达就是 对于所有的k从 2 到 n满足a_k Σ_{i1}^{k-1} a_i。举个例子就一目了然了(1, 2, 4, 8, 16)是一个超递增序列。因为 21, 4(12)3, 8(124)7, 16(1248)15。(2, 3, 6, 13)也是一个超递增序列。验证一下32, 6(23)5, 13(236)11。超递增序列解决子集和问题异常简单其算法是贪心算法从大到小迭代。为什么因为最大的数如果大于目标值它肯定不能被选中如果小于或等于目标值由于它比前面所有数加起来都大那么它必须被选中否则前面所有数之和也达不到目标值。具体解密求解子集和步骤如下从序列中最大的数a_n开始向前遍历。如果当前目标值T大于或等于a_i那么a_i一定在子集中。将a_i标记为选中并从目标值中减去a_i即T T - a_i。如果当前目标值T小于a_i那么a_i一定不在子集中跳过。继续检查下一个更小的数a_{i-1}直到处理完最小的数a_1。如果最终T被减为0则找到了一个子集否则无解。这个过程是确定性的并且时间复杂度是线性的O(n)非常高效。这就是“简单背包”。2.2 构造私钥生成超递增序列在Merkle-Hellman系统中私钥的持有者比如接收者Bob需要自己生成一个超递增序列作为私钥的一部分。一个常见的生成方法是选择一个起始的随机数a1比如一个较大的数。后续的每个元素a_i都设置为大于前面所有元素之和的一个数。通常可以取a_i (前面所有元素之和) random(1, 某个范围)以确保严格超递增。例如Bob生成了私钥超递增序列private_key [3, 5, 11, 23, 49]。你可以验证53, 11(35)8, 23(3511)19, 49(351123)42。注意在实际应用中序列长度n需要足够大比如100位以上每个元素也需要足够大比如几十位或上百位的整数以抵抗暴力攻击。我们这里用小数字只是为了演示原理。有了这个简单的私钥序列Bob就可以轻松解决与之相关的子集和问题。但直接把这个序列公开作为公钥是灾难性的因为任何人都能用上述贪心算法解密。所以下一步就是对这个序列进行“伪装”。3. 陷门变换将简单背包伪装成困难背包这是Merkle-Hellman系统最精妙的一环。Bob需要对他的私钥超递增序列进行一个可逆的数学变换得到一个看起来是随机的、困难的背包序列作为公钥。这个变换必须满足两个条件单向性对攻击者从公钥序列难以推断出私钥序列或变换参数。可逆性对BobBob利用自己掌握的“陷门”信息可以将针对公钥的困难问题转化为针对私钥的简单问题。这个变换通常通过模乘来实现。具体步骤如下3.1 选择变换参数Bob需要选择两个数模数m需要大于私钥超递增序列所有元素之和。即m Σ private_key[i]。乘数w需要是一个与m互质的整数即gcd(w, m) 1。这是因为后续解密时需要用到w在模m下的乘法逆元w^{-1}。以上面的私钥[3, 5, 11, 23, 49]为例总和为 91。Bob可以选择m 97大于91然后选择一个与97互质的数比如w 17因为 gcd(17, 97)1。3.2 计算公钥公钥序列public_key的每一个元素由私钥序列的对应元素乘以w再对m取模得到public_key[i] (private_key[i] * w) mod m计算一下public_key[0] (3 * 17) mod 97 51 mod 97 51public_key[1] (5 * 17) mod 97 85 mod 97 85public_key[2] (11 * 17) mod 97 187 mod 97 187 - 97*1 90? 等等算错了。187 ÷ 97 1 余 90。所以是 90。public_key[3] (23 * 17) mod 97 391 mod 97。391 ÷ 97 4 余 3因为 97*4388。所以是 3。public_key[4] (49 * 17) mod 97 833 mod 97。833 ÷ 97 8 余 57因为 97*8776。所以是 57。于是我们得到公钥序列[51, 85, 90, 3, 57]。你看这个序列看起来毫无规律不再具有超递增性质。对于不知道m和w的攻击者来说想从这个序列解决子集和问题就是一个困难的背包问题。Bob将(public_key, m, w)中的public_key公开而将(private_key, m, w)或等价信息(private_key, m, w^{-1})秘密保存作为私钥。注意通常公钥只发布序列本身m和w是私钥的一部分不公开。但在一些简化模型或题目中为了教学方便有时会给出m。4. 加密与解密过程全解析现在假设Alice想给Bob发送一条消息。我们假设消息是二进制串因为子集和问题本质上是“选”或“不选”某个物品。4.1 加密过程Alice的操作消息编码将明文消息按位拆分每一位对应公钥序列中的一个元素。例如消息是二进制串11001长度为5与公钥长度一致。计算密文密文C是消息位为1的那些公钥元素之和。公钥:[51, 85, 90, 3, 57]消息:1 1 0 0 1选中的公钥元素51, 85, 57密文C 51 85 57 193Alice将计算得到的密文C193发送给Bob。4.2 解密过程Bob的操作Bob收到密文C193。他知道私钥private_key [3, 5, 11, 23, 49]以及变换参数m97, w17。逆向模乘由于C是选中的公钥元素之和而公钥pk[i] (sk[i] * w) mod m所以C在模m下等于选中的私钥元素之和乘以w。即存在某个整数k使得C (Σ_{i in subset} sk[i] * w) mod m (w * Σ_{i in subset} sk[i]) mod m因此C * w^{-1} mod m Σ_{i in subset} sk[i] mod m。由于我们精心选择了m Σ sk[i]所有私钥和所以Σ sk[i]肯定小于m这个模运算的结果就是Σ sk[i]本身。 计算w在模m下的逆元w^{-1}。满足(w * w^{-1}) mod m 1。通过扩展欧几里得算法可以求得当w17, m97时w^{-1} 40因为 1740680680 mod 97 680 - 977 680-6791。 计算C C * w^{-1} mod m 193 * 40 mod 97。193 * 40 7720。7720 ÷ 97 79 余 57因为 97*797663。所以C 57。这个C57的意义是什么它就是原始消息位选中的那些私钥元素之和解决简单子集和问题现在Bob面对的问题是在超递增序列[3, 5, 11, 23, 49]中找一个子集使其和为57。这就是我们第2节讲的简单问题用贪心算法从后往前目标T57。最大数49 57选中49T57-498。下一个数23 8不选。下一个数11 8不选。下一个数5 8选中5T8-53。下一个数3 3选中3T3-30。 选中的私钥索引对应的序列是[3, 5, 49]对应原序列的第1、2、5个元素从1开始计数。恢复明文Bob知道选中的私钥索引位置就是消息中位为1的位置。因此他构造一个长度为5的二进制串在第1、2、5位填1其余位填0得到11001。这正是Alice发送的原始消息。整个过程Bob利用私钥超递增序列和陷门信息w^{-1}, m轻松解密。而窃听者Eve只知道公钥[51,85,90,3,57]和密文193她需要解决一个从非超递增序列中找子集和为193的问题这是非常困难的。5. 系统脆弱性与LLL算法破局Merkle-Hellman背包密码在提出时曾被认为很安全但很快密码学家们就发现了它的软肋。其安全性完全依赖于“困难背包”的难度而通过模乘从超递增序列产生的“困难背包”并不是一个真正随机的困难背包它仍然保留着超递增序列的某种“线性结构”痕迹。这种结构上的弱点使得它在一种强大的数学工具面前不堪一击这种工具就是LLL算法Lenstra–Lenstra–Lovász lattice basis reduction algorithm。5.1 问题如何转化为格问题LLL算法是用来寻找格Lattice中短向量的。那么一个子集和问题怎么和格扯上关系呢关键在于构造一个合适的格基。给定公钥序列(b1, b2, ..., bn)和密文C子集和问题就是寻找一组系数x_i ∈ {0, 1}使得Σ x_i * b_i C。我们可以构造如下一个(n1)维的格其基向量由以下行向量组成[ 1, 0, 0, ..., 0, 0, b1 ] [ 0, 1, 0, ..., 0, 0, b2 ] [ 0, 0, 1, ..., 0, 0, b3 ] ... [ 0, 0, 0, ..., 1, 0, bn ] [ 0, 0, 0, ..., 0, 1, C ]或者更常见的一种构造是将目标值放在对角线上并放大权重[ 2, 0, 0, ..., 0, 0, 0, b1 ] [ 0, 2, 0, ..., 0, 0, 0, b2 ] ... [ 0, 0, 0, ..., 2, 0, 0, bn ] [ 1, 1, 1, ..., 1, 1, 0, C ] [ 0, 0, 0, ..., 0, 0, 1, 0 ]这个格中的一个短向量很可能就对应着解向量(x1, x2, ..., xn, 0)或(2x1-1, 2x2-1, ..., -Σ x_i)等形式。具体构造方式有多种变体核心思想是利用格基约化LLL来寻找满足子集和等式的短整数向量这个短向量的前n个分量就揭示了x_i是0还是1。5.2 使用LLL算法攻击的实操步骤理论上理解了我们来看看具体怎么操作。以我们之前的例子为例公钥pk [51, 85, 90, 3, 57]密文C 193。我们将使用SageMath这个强大的数学工具因为它内置了LLL算法。攻击脚本的核心思路是构造一个合适的格基。# SageMath 代码示例 pk [51, 85, 90, 3, 57] C 193 n len(pk) # 构造格基矩阵。这里使用一种经典构造 # 前n列为单位矩阵的N倍N是一个较大的数比如比pk中元素大一个数量级 # 第n1列为公钥向量取负 # 最后一行前n列为0第n1列为密文C。 # 这样如果存在解向量x那么 x * 该矩阵 的最后一列应该为0。 N 10000 # 放大系数 rows [] for i in range(n): row [0]* (n1) row[i] N row[-1] -pk[i] rows.append(row) # 最后一行 last_row [0]*n [C] rows.append(last_row) M matrix(ZZ, rows) # 构造整数矩阵 print(原始格基矩阵M) print(M) # 进行LLL约化 L M.LLL() print(\nLLL约化后的矩阵L) print(L) # 寻找短向量通常短向量的前n个分量接近0或N最后一位为0。 # 我们寻找最后一位为0且前n位由0和N或-N组成的行。 for row in L: if row[-1] 0: # 最后一位为0 # 检查前n位是否由0和±N组成 if all(abs(x) in [0, N] for x in row[:-1]): print(f\n找到候选解向量: {row}) # 解码如果分量为N则对应位为1如果为-N也为1取决于构造如果为0则为0。 solution [] for i in range(n): if abs(row[i]) N: solution.append(1) else: solution.append(0) print(f解码出的消息向量 (x1,...,xn): {solution}) # 验证 calculated_C sum(solution[i]*pk[i] for i in range(n)) print(f用解向量计算的密文: {calculated_C}, 与原始密文C{C}相等吗 {calculated_C C}) break运行这段代码LLL算法会在格中搜索短向量。由于我们的公钥是由超递增序列变换而来具有特殊的线性结构LLL算法有很大概率找到一个短向量其前n个分量清晰地指示了0和1在我们的构造中可能表现为N和0。这个0/1序列就是消息比特串。实操心得LLL攻击的成功率并非100%它依赖于格基的构造方式、放大系数N的选择以及问题本身的“难度”。对于由超递增序列生成的背包问题成功率极高。但在实际尝试中有时需要调整N的大小例如尝试max(pk)1或2*max(pk)等或者尝试不同的格基构造方法。多试几种构造是破解此类题目的常态。6. 实战例题从原理到破解的完整推演光说不练假把式。我们来看一道融合了上述所有知识点的典型例题。题目通常这样给出题目描述 已知Merkle-Hellman背包密码的公钥为[7352, 2356, 7579, 19235, 1944, 14029, 1084]截获的密文为38806求解密后的二进制消息。解题思路分析 题目只给了公钥和密文显然是要我们攻击这个系统。公钥长度n7说明消息是7位二进制。我们怀疑这个公钥是由一个超递增序列通过模乘变换得来的。直接使用LLL算法求解是最直接的攻击路径。6.1 第一步尝试LLL算法攻击我们直接运用第5节的知识用SageMath编写攻击脚本。这里我们换一种更常见的格基构造方法它通常更稳定# SageMath 代码 pk [7352, 2356, 7579, 19235, 1944, 14029, 1084] C 38806 n len(pk) # 构造格基矩阵 (n1) x (n1) # 常用构造前n行是单位矩阵的N倍 公钥列最后一行是(1/2, 1/2, ..., C) # 另一种等价构造如下将目标C放在一个放大系数下 N 2^15 # 选择一个足够大的数比如2^1532768 rows [] for i in range(n): row [0]* (n1) row[i] 1 row[-1] pk[i] * N # 放大公钥 rows.append(row) # 最后一行 last_row [1/2]*n [C * N] rows.append(last_row) M matrix(rows) # 注意由于最后一行有1/2矩阵不是整数矩阵。LLL要求整数基。 # 我们可以将整个矩阵乘以2来消除1/2。 M_int (2*M).change_ring(ZZ) print(整数格基矩阵M_int) print(M_int) L M_int.LLL() print(\nLLL约化后的矩阵L) print(L) # 寻找短向量。我们期望的解向量形式为 (x1, x2, ..., xn, 0) 其中 xi ∈ {0, 1} # 在LLL约化后的矩阵中短向量的最后一个分量通常很小接近0。 # 我们寻找最后一个分量为0或±1的短行。 for i, row in enumerate(L): if abs(row[-1]) 1: # 最后分量很小 # 前n个分量应该接近0或1因为我们乘了2所以可能是0或2需要分析 # 实际上由于我们构造时第一列是1最后一行前n列是1乘2后是1 # 解向量v应满足 v (2*x1-1, 2*x2-1, ..., 2*xn-1, 0) # 所以前n个分量应为 ±1。 potential_solution [] for j in range(n): if row[j] 1: potential_solution.append(1) # (2*xj -1) 1 xj1 elif row[j] -1: potential_solution.append(0) # (2*xj -1) -1 xj0 else: # 如果不是±1可能不是我们要的解跳过这个向量 potential_solution None break if potential_solution is not None: print(f\n在第{i}行找到候选解向量: {row}) print(f解码出的消息比特: {potential_solution}) # 验证 calc_C sum(potential_solution[j]*pk[j] for j in range(n)) print(f验证计算密文 {calc_C}, 是否等于 {C}? {calc_C C}) if calc_C C: print(攻击成功) break运行这个脚本LLL算法很可能会输出一个短向量其前7个分量为[1, -1, 1, 1, -1, 1, -1]这样的形式根据我们的解码规则1-1, -1-0得到消息比特串[1, 0, 1, 1, 0, 1, 0]即1011010。验证sum([pk[i] for i in [0,2,3,5]])是否等于38806如果相等则攻击成功。6.2 第二步逆向推导私钥与变换参数可选有时题目不仅要求解密还可能要求找出原始的私钥超递增序列和变换参数(m, w)。这需要更多的分析和技巧。如果我们已经通过LLL得到了明文x并且知道多组密文C_j和对应的明文x_j我们可以尝试恢复m和w。但这里我们只有一组。一个更直接的想法是公钥序列pk是由私钥sk通过pk_i (sk_i * w) mod m得到的。如果我们能猜出m就有可能恢复sk。如何猜m观察公钥大小m必须大于私钥序列之和。私钥是超递增的其和大约在最大元素的2倍以内。公钥是sk_i * w mod m的结果所以m应该大于所有公钥元素。通常m会选得比最大公钥大一些是一个素数。查看公钥[7352, 2356, 7579, 19235, 1944, 14029, 1084]最大值是19235。所以m很可能是一个比19235稍大的素数。利用线性关系对于超递增序列有sk_{i} sum(sk_{0..i-1})。变换后这个性质丢失了但模运算下可能存在某种统计特征或可以通过格攻击直接恢复sk和w、m。这通常需要更复杂的多元方程组求解或再次使用格基约化。一个经典的攻击方法是低密度攻击。子集和问题的密度定义为d n / log2(max(pk))。当密度低于约0.9408时LLL等格基约化算法有极高概率解决随机的子集和问题。Merkle-Hellman产生的背包密度通常很低极易被攻击。对于教学例题m有时会取一个“漂亮”的数字比如比最大公钥大一点点的素数。我们可以尝试枚举可能的m例如从19236开始的一些素数并假设w是模m下的一个可逆元。然后尝试用公钥除以w乘以w^{-1}来得到候选的私钥序列再检查这个序列是否是超递增的。这是一个暴力搜索但范围不大。# 假设我们通过LLL得到了明文 x [1,0,1,1,0,1,0] x [1,0,1,1,0,1,0] pk [7352, 2356, 7579, 19235, 1944, 14029, 1084] C 38806 # 我们知道 C sum(x_i * pk_i) # 同时 pk_i (sk_i * w) mod m # 所以 C mod m (w * sum(x_i * sk_i)) mod m # 令 S sum(x_i * sk_i) 则 C w * S (在整数域因为m很大通常这个等式在整数域也成立即 C w*S) # 但我们不知道S。不过S是私钥的子集和。 # 一个投机取巧的方法寻找公钥之间的线性关系。 # 由于 pk_i / pk_j ≡ (sk_i * w) / (sk_j * w) ≡ sk_i / sk_j (mod m) 如果 sk_i/sk_j 是简单分数可能暴露信息。 # 更实际的方法是尝试枚举可能的 m。 from sympy import isprime max_pk max(pk) candidate_ms [] for possible_m in range(max_pk 1, max_pk 500): # 在最大值附近搜索 if isprime(possible_m): candidate_ms.append(possible_m) print(f候选模数 m (在 {max_pk} 附近的素数): {candidate_ms[:10]}) # 查看前10个 # 对于每个候选m我们尝试寻找一个公因子w。 # 注意对于正确的m所有 pk_i 在模m下都与 sk_i * w 同余。sk_i是整数所以 pk_i * w^{-1} mod m 应该是一个递增的序列并且可能呈现超递增的“样子”。 # 我们需要枚举w (1 w m, 且 gcd(w,m)1)计算 candidate_sk [(pk_i * modinv(w, m)) % m for pk_i in pk]然后判断 candidate_sk 是否是超递增序列。 def is_superincreasing(seq): total 0 for num in seq: if num total: return False total num return True for m in candidate_ms: # 找出所有与m互质的w for w in range(2, m): if gcd(w, m) 1: try: w_inv inverse_mod(w, m) candidate_sk [(pk_i * w_inv) % m for pk_i in pk] # 注意得到的 candidate_sk 是模m后的结果我们需要它是一组正数并且可能小于m。 # 超递增序列要求严格递增且每个数大于前面和。 # 我们先检查是否严格递增排序后和原序一致 if sorted(candidate_sk) candidate_sk and candidate_sk[0] 0: if is_superincreasing(candidate_sk): print(f\n找到潜在参数: m {m}, w {w}, w_inv {w_inv}) print(f恢复的私钥序列 sk: {candidate_sk}) # 验证用此私钥解密之前的密文C # 解密步骤 C C * w_inv mod m C_prime (C * w_inv) % m # 然后用贪心算法解 candidate_sk 的子集和问题 C_prime # 这里省略贪心算法代码假设我们运行后得到解x_dec # 如果 x_dec 等于我们已知的x则基本确认。 # 我们可以快速验证计算 sum(x[i] * candidate_sk[i]) 是否等于 C_prime S_test sum(x[i]*candidate_sk[i] for i in range(len(x))) if S_test C_prime: print(f验证通过私钥可正确解密。) # 可以在这里break跳出循环 except Exception as e: continue这段枚举代码在m和w的可能空间较小时可行。对于实际的大参数这种枚举是不现实的但针对教学例题中较小的数字它可以帮助我们找到原始的私钥参数从而完全攻破该系统。7. 背包密码的遗产与启示尽管Merkle-Hellman背包密码系统在提出后不久就被攻破但它在密码学发展史上的地位不容忽视。它是第一个将NP难问题用于公钥密码学的实践清晰地展示了“陷门单向函数”的概念。它的失败也给了密码学界宝贵的教训并非所有NP难问题都适合做密码基石问题的“最坏情况”难度高不代表其“平均情况”或“由特定方法产生的实例”难度也高。Merkle-Hellman的陷门产生了具有特殊结构的背包问题这种结构被LLL算法这类格基约化工具完美克制。格基约化算法的强大LLL算法的出现摧毁了一大批基于“背包问题”或更广义的“子集和问题”的密码系统。它告诉我们基于整数格上困难问题的密码方案必须能够抵抗格基约化攻击这直接推动了格密码学Lattice-based Cryptography的现代发展。现代格密码如NTRU、Kyber等使用的困难问题如LWE、RLWE被认为能抵抗量子计算机攻击是后量子密码学的主要候选者它们的设计充分吸取了早期背包密码的教训。系统实现细节至关重要即使理论安全实现上的微小偏差如参数选择不当、随机性不足也可能导致灾难性后果。对于我们学习者和CTF选手来说背包密码是一个绝佳的学习案例。它涉及了数论知识模运算、乘法逆元。算法思想贪心算法、NP难问题、LLL算法。密码学原理公钥加密、陷门函数、单向性。攻击实战如何将密码分析问题转化为数学问题格构造并使用现成工具SageMath求解。下次当你遇到一个看似奇怪的数字序列和一個目标和的题目时不妨想想背包密码。先用LLL算法试试看很可能会有惊喜。而在更深入的学习中理解格密码如何构建在更稳固的困难问题上将是探索现代密码学前沿的必经之路。从这个意义上说背包密码虽然“倒下”了但它指出的道路和留下的教训依然在照亮后来者的方向。
1. 从背包问题到公钥密码一个天才的构想如果你对密码学感兴趣或者听说过“公钥密码”这个概念那么RSA、ECC这些名字可能耳熟能详。但你是否知道现代公钥密码学的思想火花最早可能源自一个听起来非常“计算机科学”的问题——背包问题这就是我们今天要深入探讨的背包密码Backpack Cryptography更具体地说是它的开山之作Merkle–Hellman背包加密系统。我第一次接触这个概念时感觉非常反直觉。一个用来解决组合优化、听起来像算法竞赛题的“背包问题”怎么能用来加密信息呢这就像用“如何最有效地装行李箱”的规则来设计一把锁听起来风马牛不相及。但正是这种跨界思维在1978年由Ralph Merkle和Martin Hellman提出成为了公钥密码学的早期重要实践之一甚至比RSA的公布还早一点。它的核心魅力在于利用一个问题的两种形态——“简单背包”和“困难背包”——来分别构造加密和解密的密钥。理解它不仅能帮你解开一些CTFCapture The Flag竞赛中的经典密码学题目更能让你深刻体会到公钥密码学“陷门单向函数”的精髓正向计算容易反向求解在不知道特定“陷门”时则极其困难。那么背包问题具体是什么简单说你有一个背包容量有限面前有一堆重量各不相同的物品。你的目标是选出一些物品恰好装满背包即物品总重量等于背包容量。在密码学语境下我们通常讨论的是子集和问题Subset Sum Problem给定一个正整数集合称为背包向量和一个目标总和能否从集合中选出一个子集使其元素之和等于目标值Merkle-Hellman的巧妙之处在于它没有直接使用一个困难的背包问题而是先构造一个具有特殊性质的“简单背包”超递增序列然后通过一个数学变换将其伪装成一个“困难背包”。知道变换“陷门”的人可以轻松将困难问题还原为简单问题来解密而不知道陷门的人则要面对一个公认的NP难问题。接下来我们就从最基础的超递增序列开始一步步拆解这个经典的加密系统并通过一道典型例题手把手带你实现破解领略其中蕴含的数学之美与破解之趣。2. 超递增序列一切简单性的起点要理解背包密码必须先搞懂什么是超递增序列Superincreasing Sequence。这是整个系统的基石也是私钥持有者能够快速解密的根本原因。2.1 超递增序列的定义与性质一个序列(a1, a2, ..., an)被称为超递增序列如果序列中的每一个元素都严格大于它前面所有元素之和。用数学公式表达就是 对于所有的k从 2 到 n满足a_k Σ_{i1}^{k-1} a_i。举个例子就一目了然了(1, 2, 4, 8, 16)是一个超递增序列。因为 21, 4(12)3, 8(124)7, 16(1248)15。(2, 3, 6, 13)也是一个超递增序列。验证一下32, 6(23)5, 13(236)11。超递增序列解决子集和问题异常简单其算法是贪心算法从大到小迭代。为什么因为最大的数如果大于目标值它肯定不能被选中如果小于或等于目标值由于它比前面所有数加起来都大那么它必须被选中否则前面所有数之和也达不到目标值。具体解密求解子集和步骤如下从序列中最大的数a_n开始向前遍历。如果当前目标值T大于或等于a_i那么a_i一定在子集中。将a_i标记为选中并从目标值中减去a_i即T T - a_i。如果当前目标值T小于a_i那么a_i一定不在子集中跳过。继续检查下一个更小的数a_{i-1}直到处理完最小的数a_1。如果最终T被减为0则找到了一个子集否则无解。这个过程是确定性的并且时间复杂度是线性的O(n)非常高效。这就是“简单背包”。2.2 构造私钥生成超递增序列在Merkle-Hellman系统中私钥的持有者比如接收者Bob需要自己生成一个超递增序列作为私钥的一部分。一个常见的生成方法是选择一个起始的随机数a1比如一个较大的数。后续的每个元素a_i都设置为大于前面所有元素之和的一个数。通常可以取a_i (前面所有元素之和) random(1, 某个范围)以确保严格超递增。例如Bob生成了私钥超递增序列private_key [3, 5, 11, 23, 49]。你可以验证53, 11(35)8, 23(3511)19, 49(351123)42。注意在实际应用中序列长度n需要足够大比如100位以上每个元素也需要足够大比如几十位或上百位的整数以抵抗暴力攻击。我们这里用小数字只是为了演示原理。有了这个简单的私钥序列Bob就可以轻松解决与之相关的子集和问题。但直接把这个序列公开作为公钥是灾难性的因为任何人都能用上述贪心算法解密。所以下一步就是对这个序列进行“伪装”。3. 陷门变换将简单背包伪装成困难背包这是Merkle-Hellman系统最精妙的一环。Bob需要对他的私钥超递增序列进行一个可逆的数学变换得到一个看起来是随机的、困难的背包序列作为公钥。这个变换必须满足两个条件单向性对攻击者从公钥序列难以推断出私钥序列或变换参数。可逆性对BobBob利用自己掌握的“陷门”信息可以将针对公钥的困难问题转化为针对私钥的简单问题。这个变换通常通过模乘来实现。具体步骤如下3.1 选择变换参数Bob需要选择两个数模数m需要大于私钥超递增序列所有元素之和。即m Σ private_key[i]。乘数w需要是一个与m互质的整数即gcd(w, m) 1。这是因为后续解密时需要用到w在模m下的乘法逆元w^{-1}。以上面的私钥[3, 5, 11, 23, 49]为例总和为 91。Bob可以选择m 97大于91然后选择一个与97互质的数比如w 17因为 gcd(17, 97)1。3.2 计算公钥公钥序列public_key的每一个元素由私钥序列的对应元素乘以w再对m取模得到public_key[i] (private_key[i] * w) mod m计算一下public_key[0] (3 * 17) mod 97 51 mod 97 51public_key[1] (5 * 17) mod 97 85 mod 97 85public_key[2] (11 * 17) mod 97 187 mod 97 187 - 97*1 90? 等等算错了。187 ÷ 97 1 余 90。所以是 90。public_key[3] (23 * 17) mod 97 391 mod 97。391 ÷ 97 4 余 3因为 97*4388。所以是 3。public_key[4] (49 * 17) mod 97 833 mod 97。833 ÷ 97 8 余 57因为 97*8776。所以是 57。于是我们得到公钥序列[51, 85, 90, 3, 57]。你看这个序列看起来毫无规律不再具有超递增性质。对于不知道m和w的攻击者来说想从这个序列解决子集和问题就是一个困难的背包问题。Bob将(public_key, m, w)中的public_key公开而将(private_key, m, w)或等价信息(private_key, m, w^{-1})秘密保存作为私钥。注意通常公钥只发布序列本身m和w是私钥的一部分不公开。但在一些简化模型或题目中为了教学方便有时会给出m。4. 加密与解密过程全解析现在假设Alice想给Bob发送一条消息。我们假设消息是二进制串因为子集和问题本质上是“选”或“不选”某个物品。4.1 加密过程Alice的操作消息编码将明文消息按位拆分每一位对应公钥序列中的一个元素。例如消息是二进制串11001长度为5与公钥长度一致。计算密文密文C是消息位为1的那些公钥元素之和。公钥:[51, 85, 90, 3, 57]消息:1 1 0 0 1选中的公钥元素51, 85, 57密文C 51 85 57 193Alice将计算得到的密文C193发送给Bob。4.2 解密过程Bob的操作Bob收到密文C193。他知道私钥private_key [3, 5, 11, 23, 49]以及变换参数m97, w17。逆向模乘由于C是选中的公钥元素之和而公钥pk[i] (sk[i] * w) mod m所以C在模m下等于选中的私钥元素之和乘以w。即存在某个整数k使得C (Σ_{i in subset} sk[i] * w) mod m (w * Σ_{i in subset} sk[i]) mod m因此C * w^{-1} mod m Σ_{i in subset} sk[i] mod m。由于我们精心选择了m Σ sk[i]所有私钥和所以Σ sk[i]肯定小于m这个模运算的结果就是Σ sk[i]本身。 计算w在模m下的逆元w^{-1}。满足(w * w^{-1}) mod m 1。通过扩展欧几里得算法可以求得当w17, m97时w^{-1} 40因为 1740680680 mod 97 680 - 977 680-6791。 计算C C * w^{-1} mod m 193 * 40 mod 97。193 * 40 7720。7720 ÷ 97 79 余 57因为 97*797663。所以C 57。这个C57的意义是什么它就是原始消息位选中的那些私钥元素之和解决简单子集和问题现在Bob面对的问题是在超递增序列[3, 5, 11, 23, 49]中找一个子集使其和为57。这就是我们第2节讲的简单问题用贪心算法从后往前目标T57。最大数49 57选中49T57-498。下一个数23 8不选。下一个数11 8不选。下一个数5 8选中5T8-53。下一个数3 3选中3T3-30。 选中的私钥索引对应的序列是[3, 5, 49]对应原序列的第1、2、5个元素从1开始计数。恢复明文Bob知道选中的私钥索引位置就是消息中位为1的位置。因此他构造一个长度为5的二进制串在第1、2、5位填1其余位填0得到11001。这正是Alice发送的原始消息。整个过程Bob利用私钥超递增序列和陷门信息w^{-1}, m轻松解密。而窃听者Eve只知道公钥[51,85,90,3,57]和密文193她需要解决一个从非超递增序列中找子集和为193的问题这是非常困难的。5. 系统脆弱性与LLL算法破局Merkle-Hellman背包密码在提出时曾被认为很安全但很快密码学家们就发现了它的软肋。其安全性完全依赖于“困难背包”的难度而通过模乘从超递增序列产生的“困难背包”并不是一个真正随机的困难背包它仍然保留着超递增序列的某种“线性结构”痕迹。这种结构上的弱点使得它在一种强大的数学工具面前不堪一击这种工具就是LLL算法Lenstra–Lenstra–Lovász lattice basis reduction algorithm。5.1 问题如何转化为格问题LLL算法是用来寻找格Lattice中短向量的。那么一个子集和问题怎么和格扯上关系呢关键在于构造一个合适的格基。给定公钥序列(b1, b2, ..., bn)和密文C子集和问题就是寻找一组系数x_i ∈ {0, 1}使得Σ x_i * b_i C。我们可以构造如下一个(n1)维的格其基向量由以下行向量组成[ 1, 0, 0, ..., 0, 0, b1 ] [ 0, 1, 0, ..., 0, 0, b2 ] [ 0, 0, 1, ..., 0, 0, b3 ] ... [ 0, 0, 0, ..., 1, 0, bn ] [ 0, 0, 0, ..., 0, 1, C ]或者更常见的一种构造是将目标值放在对角线上并放大权重[ 2, 0, 0, ..., 0, 0, 0, b1 ] [ 0, 2, 0, ..., 0, 0, 0, b2 ] ... [ 0, 0, 0, ..., 2, 0, 0, bn ] [ 1, 1, 1, ..., 1, 1, 0, C ] [ 0, 0, 0, ..., 0, 0, 1, 0 ]这个格中的一个短向量很可能就对应着解向量(x1, x2, ..., xn, 0)或(2x1-1, 2x2-1, ..., -Σ x_i)等形式。具体构造方式有多种变体核心思想是利用格基约化LLL来寻找满足子集和等式的短整数向量这个短向量的前n个分量就揭示了x_i是0还是1。5.2 使用LLL算法攻击的实操步骤理论上理解了我们来看看具体怎么操作。以我们之前的例子为例公钥pk [51, 85, 90, 3, 57]密文C 193。我们将使用SageMath这个强大的数学工具因为它内置了LLL算法。攻击脚本的核心思路是构造一个合适的格基。# SageMath 代码示例 pk [51, 85, 90, 3, 57] C 193 n len(pk) # 构造格基矩阵。这里使用一种经典构造 # 前n列为单位矩阵的N倍N是一个较大的数比如比pk中元素大一个数量级 # 第n1列为公钥向量取负 # 最后一行前n列为0第n1列为密文C。 # 这样如果存在解向量x那么 x * 该矩阵 的最后一列应该为0。 N 10000 # 放大系数 rows [] for i in range(n): row [0]* (n1) row[i] N row[-1] -pk[i] rows.append(row) # 最后一行 last_row [0]*n [C] rows.append(last_row) M matrix(ZZ, rows) # 构造整数矩阵 print(原始格基矩阵M) print(M) # 进行LLL约化 L M.LLL() print(\nLLL约化后的矩阵L) print(L) # 寻找短向量通常短向量的前n个分量接近0或N最后一位为0。 # 我们寻找最后一位为0且前n位由0和N或-N组成的行。 for row in L: if row[-1] 0: # 最后一位为0 # 检查前n位是否由0和±N组成 if all(abs(x) in [0, N] for x in row[:-1]): print(f\n找到候选解向量: {row}) # 解码如果分量为N则对应位为1如果为-N也为1取决于构造如果为0则为0。 solution [] for i in range(n): if abs(row[i]) N: solution.append(1) else: solution.append(0) print(f解码出的消息向量 (x1,...,xn): {solution}) # 验证 calculated_C sum(solution[i]*pk[i] for i in range(n)) print(f用解向量计算的密文: {calculated_C}, 与原始密文C{C}相等吗 {calculated_C C}) break运行这段代码LLL算法会在格中搜索短向量。由于我们的公钥是由超递增序列变换而来具有特殊的线性结构LLL算法有很大概率找到一个短向量其前n个分量清晰地指示了0和1在我们的构造中可能表现为N和0。这个0/1序列就是消息比特串。实操心得LLL攻击的成功率并非100%它依赖于格基的构造方式、放大系数N的选择以及问题本身的“难度”。对于由超递增序列生成的背包问题成功率极高。但在实际尝试中有时需要调整N的大小例如尝试max(pk)1或2*max(pk)等或者尝试不同的格基构造方法。多试几种构造是破解此类题目的常态。6. 实战例题从原理到破解的完整推演光说不练假把式。我们来看一道融合了上述所有知识点的典型例题。题目通常这样给出题目描述 已知Merkle-Hellman背包密码的公钥为[7352, 2356, 7579, 19235, 1944, 14029, 1084]截获的密文为38806求解密后的二进制消息。解题思路分析 题目只给了公钥和密文显然是要我们攻击这个系统。公钥长度n7说明消息是7位二进制。我们怀疑这个公钥是由一个超递增序列通过模乘变换得来的。直接使用LLL算法求解是最直接的攻击路径。6.1 第一步尝试LLL算法攻击我们直接运用第5节的知识用SageMath编写攻击脚本。这里我们换一种更常见的格基构造方法它通常更稳定# SageMath 代码 pk [7352, 2356, 7579, 19235, 1944, 14029, 1084] C 38806 n len(pk) # 构造格基矩阵 (n1) x (n1) # 常用构造前n行是单位矩阵的N倍 公钥列最后一行是(1/2, 1/2, ..., C) # 另一种等价构造如下将目标C放在一个放大系数下 N 2^15 # 选择一个足够大的数比如2^1532768 rows [] for i in range(n): row [0]* (n1) row[i] 1 row[-1] pk[i] * N # 放大公钥 rows.append(row) # 最后一行 last_row [1/2]*n [C * N] rows.append(last_row) M matrix(rows) # 注意由于最后一行有1/2矩阵不是整数矩阵。LLL要求整数基。 # 我们可以将整个矩阵乘以2来消除1/2。 M_int (2*M).change_ring(ZZ) print(整数格基矩阵M_int) print(M_int) L M_int.LLL() print(\nLLL约化后的矩阵L) print(L) # 寻找短向量。我们期望的解向量形式为 (x1, x2, ..., xn, 0) 其中 xi ∈ {0, 1} # 在LLL约化后的矩阵中短向量的最后一个分量通常很小接近0。 # 我们寻找最后一个分量为0或±1的短行。 for i, row in enumerate(L): if abs(row[-1]) 1: # 最后分量很小 # 前n个分量应该接近0或1因为我们乘了2所以可能是0或2需要分析 # 实际上由于我们构造时第一列是1最后一行前n列是1乘2后是1 # 解向量v应满足 v (2*x1-1, 2*x2-1, ..., 2*xn-1, 0) # 所以前n个分量应为 ±1。 potential_solution [] for j in range(n): if row[j] 1: potential_solution.append(1) # (2*xj -1) 1 xj1 elif row[j] -1: potential_solution.append(0) # (2*xj -1) -1 xj0 else: # 如果不是±1可能不是我们要的解跳过这个向量 potential_solution None break if potential_solution is not None: print(f\n在第{i}行找到候选解向量: {row}) print(f解码出的消息比特: {potential_solution}) # 验证 calc_C sum(potential_solution[j]*pk[j] for j in range(n)) print(f验证计算密文 {calc_C}, 是否等于 {C}? {calc_C C}) if calc_C C: print(攻击成功) break运行这个脚本LLL算法很可能会输出一个短向量其前7个分量为[1, -1, 1, 1, -1, 1, -1]这样的形式根据我们的解码规则1-1, -1-0得到消息比特串[1, 0, 1, 1, 0, 1, 0]即1011010。验证sum([pk[i] for i in [0,2,3,5]])是否等于38806如果相等则攻击成功。6.2 第二步逆向推导私钥与变换参数可选有时题目不仅要求解密还可能要求找出原始的私钥超递增序列和变换参数(m, w)。这需要更多的分析和技巧。如果我们已经通过LLL得到了明文x并且知道多组密文C_j和对应的明文x_j我们可以尝试恢复m和w。但这里我们只有一组。一个更直接的想法是公钥序列pk是由私钥sk通过pk_i (sk_i * w) mod m得到的。如果我们能猜出m就有可能恢复sk。如何猜m观察公钥大小m必须大于私钥序列之和。私钥是超递增的其和大约在最大元素的2倍以内。公钥是sk_i * w mod m的结果所以m应该大于所有公钥元素。通常m会选得比最大公钥大一些是一个素数。查看公钥[7352, 2356, 7579, 19235, 1944, 14029, 1084]最大值是19235。所以m很可能是一个比19235稍大的素数。利用线性关系对于超递增序列有sk_{i} sum(sk_{0..i-1})。变换后这个性质丢失了但模运算下可能存在某种统计特征或可以通过格攻击直接恢复sk和w、m。这通常需要更复杂的多元方程组求解或再次使用格基约化。一个经典的攻击方法是低密度攻击。子集和问题的密度定义为d n / log2(max(pk))。当密度低于约0.9408时LLL等格基约化算法有极高概率解决随机的子集和问题。Merkle-Hellman产生的背包密度通常很低极易被攻击。对于教学例题m有时会取一个“漂亮”的数字比如比最大公钥大一点点的素数。我们可以尝试枚举可能的m例如从19236开始的一些素数并假设w是模m下的一个可逆元。然后尝试用公钥除以w乘以w^{-1}来得到候选的私钥序列再检查这个序列是否是超递增的。这是一个暴力搜索但范围不大。# 假设我们通过LLL得到了明文 x [1,0,1,1,0,1,0] x [1,0,1,1,0,1,0] pk [7352, 2356, 7579, 19235, 1944, 14029, 1084] C 38806 # 我们知道 C sum(x_i * pk_i) # 同时 pk_i (sk_i * w) mod m # 所以 C mod m (w * sum(x_i * sk_i)) mod m # 令 S sum(x_i * sk_i) 则 C w * S (在整数域因为m很大通常这个等式在整数域也成立即 C w*S) # 但我们不知道S。不过S是私钥的子集和。 # 一个投机取巧的方法寻找公钥之间的线性关系。 # 由于 pk_i / pk_j ≡ (sk_i * w) / (sk_j * w) ≡ sk_i / sk_j (mod m) 如果 sk_i/sk_j 是简单分数可能暴露信息。 # 更实际的方法是尝试枚举可能的 m。 from sympy import isprime max_pk max(pk) candidate_ms [] for possible_m in range(max_pk 1, max_pk 500): # 在最大值附近搜索 if isprime(possible_m): candidate_ms.append(possible_m) print(f候选模数 m (在 {max_pk} 附近的素数): {candidate_ms[:10]}) # 查看前10个 # 对于每个候选m我们尝试寻找一个公因子w。 # 注意对于正确的m所有 pk_i 在模m下都与 sk_i * w 同余。sk_i是整数所以 pk_i * w^{-1} mod m 应该是一个递增的序列并且可能呈现超递增的“样子”。 # 我们需要枚举w (1 w m, 且 gcd(w,m)1)计算 candidate_sk [(pk_i * modinv(w, m)) % m for pk_i in pk]然后判断 candidate_sk 是否是超递增序列。 def is_superincreasing(seq): total 0 for num in seq: if num total: return False total num return True for m in candidate_ms: # 找出所有与m互质的w for w in range(2, m): if gcd(w, m) 1: try: w_inv inverse_mod(w, m) candidate_sk [(pk_i * w_inv) % m for pk_i in pk] # 注意得到的 candidate_sk 是模m后的结果我们需要它是一组正数并且可能小于m。 # 超递增序列要求严格递增且每个数大于前面和。 # 我们先检查是否严格递增排序后和原序一致 if sorted(candidate_sk) candidate_sk and candidate_sk[0] 0: if is_superincreasing(candidate_sk): print(f\n找到潜在参数: m {m}, w {w}, w_inv {w_inv}) print(f恢复的私钥序列 sk: {candidate_sk}) # 验证用此私钥解密之前的密文C # 解密步骤 C C * w_inv mod m C_prime (C * w_inv) % m # 然后用贪心算法解 candidate_sk 的子集和问题 C_prime # 这里省略贪心算法代码假设我们运行后得到解x_dec # 如果 x_dec 等于我们已知的x则基本确认。 # 我们可以快速验证计算 sum(x[i] * candidate_sk[i]) 是否等于 C_prime S_test sum(x[i]*candidate_sk[i] for i in range(len(x))) if S_test C_prime: print(f验证通过私钥可正确解密。) # 可以在这里break跳出循环 except Exception as e: continue这段枚举代码在m和w的可能空间较小时可行。对于实际的大参数这种枚举是不现实的但针对教学例题中较小的数字它可以帮助我们找到原始的私钥参数从而完全攻破该系统。7. 背包密码的遗产与启示尽管Merkle-Hellman背包密码系统在提出后不久就被攻破但它在密码学发展史上的地位不容忽视。它是第一个将NP难问题用于公钥密码学的实践清晰地展示了“陷门单向函数”的概念。它的失败也给了密码学界宝贵的教训并非所有NP难问题都适合做密码基石问题的“最坏情况”难度高不代表其“平均情况”或“由特定方法产生的实例”难度也高。Merkle-Hellman的陷门产生了具有特殊结构的背包问题这种结构被LLL算法这类格基约化工具完美克制。格基约化算法的强大LLL算法的出现摧毁了一大批基于“背包问题”或更广义的“子集和问题”的密码系统。它告诉我们基于整数格上困难问题的密码方案必须能够抵抗格基约化攻击这直接推动了格密码学Lattice-based Cryptography的现代发展。现代格密码如NTRU、Kyber等使用的困难问题如LWE、RLWE被认为能抵抗量子计算机攻击是后量子密码学的主要候选者它们的设计充分吸取了早期背包密码的教训。系统实现细节至关重要即使理论安全实现上的微小偏差如参数选择不当、随机性不足也可能导致灾难性后果。对于我们学习者和CTF选手来说背包密码是一个绝佳的学习案例。它涉及了数论知识模运算、乘法逆元。算法思想贪心算法、NP难问题、LLL算法。密码学原理公钥加密、陷门函数、单向性。攻击实战如何将密码分析问题转化为数学问题格构造并使用现成工具SageMath求解。下次当你遇到一个看似奇怪的数字序列和一個目标和的题目时不妨想想背包密码。先用LLL算法试试看很可能会有惊喜。而在更深入的学习中理解格密码如何构建在更稳固的困难问题上将是探索现代密码学前沿的必经之路。从这个意义上说背包密码虽然“倒下”了但它指出的道路和留下的教训依然在照亮后来者的方向。
)
