背包公钥密码系统与格基约化攻击

See here

第一部分：背景知识 - 公钥密码学

基本思想：
- 使用一对数学上相关的密钥：公钥 (Public Key) 和 私钥 (Private Key)。
- 公钥可以公开，用于加密或验证签名。
- 私钥必须保密，用于解密或生成签名。
安全基础：
- 基于陷门单向函数 (Trapdoor One-Way Function)。
- 正向计算容易：给定明文和公钥，计算密文很容易。
- 逆向计算困难：仅给定密文和公钥，恢复明文在计算上不可行。
- 陷门存在：拥有私钥（陷门信息）的人可以轻松地进行逆向计算（解密）。
经典实例：
- RSA：基于大整数分解难题。
- Diffie-Hellman / ElGamal：基于离散对数难题。
- Merkle-Hellman Knapsack：基于子集和问题（本章主题）。

第二部分：背包（Knapsack）问题

一般背包问题 (General Knapsack, GK)：
- 定义：给定一个正整数集合（“重量”）W = {W₀, W₁, ..., Wₙ₋₁} 和一个目标和 S，是否存在一个二进制向量 a = (a₀, a₁, ..., aₙ₋₁)（其中 aᵢ ∈ {0, 1}），使得 S = a₀W₀ + a₁W₁ + ... + aₙ₋₁Wₙ₋₁？
- 性质：这是一个经典的 NP-完全 (NP-Complete) 问题。对于大的 n，在经典计算机上没有已知的高效（多项式时间）通用解法。
超递增背包问题 (Superincreasing Knapsack, SIK)：
- 定义：一个特殊的背包序列，其中每个元素都大于其前面所有元素之和。即 Wᵢ > Σⱼ₌₀ⁱ⁻¹ Wⱼ 对所有 i > 0 成立。
- 示例：(2, 3, 7, 14, 30, 57, 120, 251) 是一个超递增序列。
- 求解方法：非常简单高效（贪心算法）。
  - 从最大的重量开始比较。
  - 如果 S >= Wᵢ，则 aᵢ = 1，并令 S = S - Wᵢ。
  - 否则 aᵢ = 0。
  - 依次向前处理，直到 S = 0。
- 性质：SIK 问题是 P 问题（可在多项式时间内解决）。

第三部分：Merkle-Hellman 背包公钥密码系统

设计思路：
- 利用 SIK 的易解性作为私钥。
- 将 SIK 通过一个数学变换“伪装”成一个看似随机的 GK，作为公钥。
- 加密使用公钥（GK），对合法接收者来说，解密时先将密文“还原”回 SIK 问题，然后利用 SIK 的易解性快速解密。
密钥生成：
1. 选择私钥：
  - 生成一个超递增序列 S = (s₀, s₁, ..., sₙ₋₁)。
  - 选择一个模数 n，要求 n > Σ(sᵢ)（即大于 SIK 所有元素之和）。
  - 选择一个乘数 m，要求 gcd(m, n) = 1（m 和 n 互质）。
  - 计算 m 在模 n 下的乘法逆元 m⁻¹，即 m * m⁻¹ ≡ 1 (mod n)。
2. 生成公钥：
  - 将 SIK 序列 S 中的每个元素 sᵢ 乘以 m 并对 n 取模，得到公钥序列 T = (t₀, t₁, ..., tₙ₋₁)，其中 tᵢ = (m * sᵢ) mod n。
  - 这个 T 序列看起来是随机的，是一个（看似）困难的 GK。
- 总结：
  - 私钥：(S, m⁻¹, n)
  - 公钥：T
加解密过程：
- 加密 (由发送方执行)：
  - 将明文 M 分成 n 位一组的块。
  - 对于每个明文块 a = (a₀, a₁, ..., aₙ₋₁)，计算密文 C： C = a₀*t₀ + a₁*t₁ + ... + aₙ₋₁*tₙ₋₁
  - 发送密文 C。
- 解密 (由接收方执行)：
  1. 还原为 SIK 问题：利用私钥中的 m⁻¹ 和 n，计算： C' = (C * m⁻¹) mod n
  2. 求解 SIK：现在 C' 正是明文块 a 与私钥 SIK 序列 S 的点积： C' = a₀*s₀ + a₁*s₁ + ... + aₙ₋₁*sₙ₋₁
  3. 使用 SIK 的贪心算法，从 C' 和 S 中轻松恢复出明文块 a。

第四部分：格（Lattice）理论基础

格的定义：
- 给定一组在 ℝᵐ 中线性无关的向量 b₁, b₂, ..., bₙ（称为基向量）。
- 由这组基向量张成的格 (Lattice) L 是所有这些基向量的整系数线性组合构成的点集： L = { α₁b₁ + α₂b₂ + ... + αₙbₙ | αᵢ ∈ ℤ }
- 直观理解：格是空间中规则排列的离散点阵。例如，二维平面上的所有整数坐标点 (x, y) 构成一个格。
格的行列式 (Determinant)：
- 定义为 d(L) = |det(B)|，其中 B 是以基向量为列（或行）构成的矩阵。
- 行列式代表了格的基本区域（平行多面体）的体积，是格的一个重要不变量。
格中的困难问题：
- 最短向量问题 (SVP)：在格 L 中找到长度最短的非零向量。
- 最近向量问题 (CVP)：给定一个不在格上的目标向量 t，在格 L 中找到离 t 最近的格点。
- 这些问题是许多后量子密码方案的安全基础。

第五部分：使用格基约化攻击背包密码

攻击模型：
- 已知：公钥 T = (t₀, t₁, ..., tₙ₋₁) 和密文 C。
- 目标：找到明文 a = (a₀, a₁, ..., aₙ₋₁)，其中 aᵢ ∈ {0, 1}，使得 T · a = C。
将问题转化为格问题：
- 攻击者希望找到满足 Σ(tᵢ * aᵢ) = C 的 aᵢ ∈ {0,1}。
- 这可以重写为寻找一个向量 V，使得 M * V = W，其中：
  - M 是一个 (n+1) x (n+1) 的矩阵，其构造如下：
```
[ 1   0   0  ...  0   t₀ ]
[ 0   1   0  ...  0   t₁ ]
[ 0   0   1  ...  0   t₂ ]
[ ... ... ... ... ... ...]
[ 0   0   0  ...  1  tₙ₋₁]
[ 0   0   0  ...  0   -C ]
```
    1
    2
    3
    4
    5
    6
  - V = (a₀, a₁, ..., aₙ₋₁, 1)ᵀ
  - W = (a₀, a₁, ..., aₙ₋₁, 0)ᵀ
- 关键观察：W 是由 M 的列向量张成的格 L 中的一个向量。
W 向量的特殊性质：
- W 的前 n 个分量是 0 或 1。
- W 的最后一个分量是 0。
- 因此，W 的欧几里得范数（长度）为 ||W|| = √(a₀² + ... + aₙ₋₁²) ≤ √n。
- 结论：W 是格 L 中一个非常短的向量。
格基约化 (Lattice Reduction)：
- 目标：给定一个格的任意基，找到一组由相对较短且近似正交的向量组成的新基。
- LLL 算法 (Lenstra-Lenstra-Lovász)：
  - 1982年提出的第一个高效的格基约化算法。
  - 能在多项式时间内，找到一个长度不超过最短向量指数倍的短向量。
  - 虽然不保证找到最短向量，但对于 Merkle-Hellman 这种“伪装”得不够好的格，极有可能找到像 W 这样具有特殊结构（分量小且最后一位为0）的短向量。
攻击流程：
1. 根据公钥 T 和密文 C 构造矩阵 M。
2. 将 M 的列向量视为格 L 的一个基。
3. 对这个基运行 LLL 算法。
4. LLL 算法会输出一组新的、更“好”的基向量。
5. 在这些新基向量中，检查是否存在一个向量，其前 n 个分量是 0/1，且最后一个分量是 0。
6. 如果找到，该向量的前 n 个分量就是所求的明文 a。
历史意义：
- Adi Shamir 在 1983 年利用这种基于格的攻击，在一台 Apple II 个人电脑上成功破解了 Merkle-Hellman 背包密码系统。
- 这标志着 Merkle-Hellman 方案的彻底失败，也展示了格理论作为强大密码分析工具的威力。

第六部分：总结与启示

Merkle-Hellman 的失败原因：
- 其“伪装”过程（线性同余变换）不足以将 SIK 完全隐藏成一个真正的随机 GK。
- 公钥 T 与私钥 S 之间仍然存在可被格基约化技术探测到的线性结构。
核心教训：
- 密码系统的安全性不仅依赖于底层问题的理论难度（如 NP-完全），更依赖于具体实现方案是否真正消除了所有可利用的结构。
- 数学的进步（如格基约化算法的发展）可以直接导致曾经被认为安全的密码系统被攻破。
- 这次失败推动了公钥密码学向更稳健的数论难题（如 RSA、ECC）发展，同时也为后来基于格的后量子密码学埋下了伏笔。

练习题与答案

题目 1：Merkle-Hellman 密钥生成与加解密

假设 Alice 想要建立一个 Merkle-Hellman 背包密码系统。

她选择了超递增序列 S = (3, 5, 11, 22)。
她选择了模数 n = 50（因为 3+5+11+22=41 < 50）。
她选择了乘数 m = 7（因为 gcd(7, 50)=1）。 a) 计算 m 在模 50 下的逆元 m⁻¹。 b) 生成公钥 T。 c) Bob 想发送明文 1011 给 Alice。请计算他生成的密文 C。 d) Alice 收到密文 C 后，请演示她如何解密恢复明文。

答案: a) 计算 m⁻¹: 我们需要找到一个数 x 使得 7x ≡ 1 (mod 50)。通过尝试或扩展欧几里得算法，可以找到 7 * 43 = 301，而 301 mod 50 = 1。因此，m⁻¹ = 43。

b) 生成公钥 T: tᵢ = (m * sᵢ) mod n = (7 * sᵢ) mod 50

t₀ = (7 * 3) mod 50 = 21
t₁ = (7 * 5) mod 50 = 35
t₂ = (7 * 11) mod 50 = 77 mod 50 = 27
t₃ = (7 * 22) mod 50 = 154 mod 50 = 4 所以，公钥 T = (21, 35, 27, 4)。

c) Bob 加密 (1011): 明文 a = (1, 0, 1, 1)C = 1*21 + 0*35 + 1*27 + 1*4 = 21 + 0 + 27 + 4 = 52

d) Alice 解密:

还原: C' = (C * m⁻¹) mod n = (52 * 43) mod 50
- 52 mod 50 = 2, 所以 (2 * 43) mod 50 = 86 mod 50 = 36
- (或者直接算 52*43=2236, 2236 / 50 = 44*50=2200, 2236-2200=36)
求解 SIK: 在 S=(3,5,11,22) 中找到和为 36 的子集。
- 从最大开始: 36 >= 22 → a₃=1, 36-22=14
- 14 >= 11 → a₂=1, 14-11=3
- 3 < 5 → a₁=0
- 3 >= 3 → a₀=1, 3-3=0
- 得到 a = (1, 0, 1, 1)，与原始明文一致。

题目 2：概念理解

解释为什么 Merkle-Hellman 背包密码系统被认为是不安全的，尽管它基于 NP-完全的子集和问题？

答案: Merkle-Hellman 的不安全性源于其具体的构造方式，而非子集和问题本身。

问题不对等：虽然一般子集和问题是 NP-完全的，但 Merkle-Hellman 的公钥 T 并不是一个真正随机的背包实例。它是通过对一个超递增背包 (SIK) 进行线性变换（乘以 m 并模 n）得到的。
隐藏的结构：这种变换在公钥 T 中留下了可被利用的数学结构。攻击者（如 Shamir）发现，可以将破解问题（从 T 和 C 恢复 a）转化为在一个特定构造的格 (Lattice) 中寻找一个非常短的向量的问题。
高效的攻击工具：LLL 格基约化算法提供了一种高效的（多项式时间） 方法来寻找格中的短向量。对于 Merkle-Hellman 产生的格，LLL 算法极有可能找到那个对应于明文 a 的特殊短向量，从而完全破解系统。
结论：因此，Merkle-Hellman 的安全性依赖于一个比一般子集和问题弱得多的假设。它的“困难性”被格基约化这一强大的数学工具所瓦解。

题目 3：格与攻击

在针对背包密码的格攻击中，为什么要构造一个包含 -C 的 (n+1) x (n+1) 矩阵？向量 W = (a₀, a₁, ..., aₙ₋₁, 0)ᵀ 为什么是格中的一个短向量？

答案:

构造矩阵的目的：
- 我们的目标方程是 Σ(tᵢ * aᵢ) = C，其中 aᵢ ∈ {0,1}。
- 为了将这个问题嵌入到格中，我们需要一个齐次方程（等于零）。我们将方程改写为 Σ(tᵢ * aᵢ) - 1*C = 0。
- 构造的矩阵 M 的前 n 列是单位矩阵，确保了未知数 aᵢ 能直接出现在结果向量的前 n 个位置。
- 最后一列是 (t₀, t₁, ..., tₙ₋₁, -C)ᵀ，这样当我们将 M 乘以向量 V=(a₀,...,aₙ₋₁, 1)ᵀ 时，最后一行的计算结果正好是 Σ(tᵢ * aᵢ) - C。我们希望这个结果为 0，这正是我们要求解的方程。
- 因此，这个巧妙的构造将原始的非齐次方程求解问题，转化为了在由 M 的列张成的格中寻找一个最后一个分量为 0 的特殊向量 W 的问题。
W 是短向量的原因：
- 向量 W 的形式是 (a₀, a₁, ..., aₙ₋₁, 0)ᵀ。
- 由于明文比特 aᵢ 只能是 0 或 1，所以 W 的每个分量的绝对值都不超过 1。
- 向量的欧几里得长度（范数）为 ||W|| = √(a₀² + a₁² + ... + aₙ₋₁² + 0²)。
- 因为 aᵢ² = aᵢ（0²=0, 1²=1），所以 ||W|| = √(a₀ + a₁ + ... + aₙ₋₁) ≤ √n。
- 相比之下，格 L 中由公钥 T（其元素通常是与模数 n 同数量级的大数）和密文 C 构成的基向量，其长度通常远大于 √n。
- 因此，W 在格 L 中是一个异常地短的向量。格基约化算法（如 LLL）的设计目标就是寻找这样的短向量，这使得攻击成为可能。

背包公钥密码系统与格基约化攻击 ​

第一部分：背景知识 - 公钥密码学 ​

第二部分：背包（Knapsack）问题 ​

第三部分：Merkle-Hellman 背包公钥密码系统 ​

第四部分：格（Lattice）理论基础 ​

第五部分：使用格基约化攻击背包密码 ​

第六部分：总结与启示 ​

练习题与答案 ​

题目 1：Merkle-Hellman 密钥生成与加解密 ​

题目 2：概念理解 ​

题目 3：格与攻击 ​