模格密码学数学基础

本文面向具有大学数学基础（线性代数、抽象代数初等知识）的读者，系统讲解 ML-DSA、ML-KEM 等 CRYSTALS 系列算法背后的数学基础。我们会从最基本的整数模运算出发，逐步构建到模格问题（Module-LWE 和 Module-SIS），并解释为什么这些问题对量子计算机也是困难的。

目录
  1. 整数模运算与模算术
  2. 多项式与多项式环
  3. 密码学中的环 Rq
  4. 格（Lattice）
  5. 模格（Module Lattice）
  6. SIS 问题（短整数解）
  7. LWE 问题（学习误差）
  8. Module-SIS 与 Module-LWE
  9. 为什么这些问题困难？
  10. 与 ML-DSA / ML-KEM 的联系
  11. 参考文献
1. 整数模运算与模算术

模运算是密码学的基础。如果理解了时钟上的时间计算（13 点就是下午 1 点），你就理解了模运算。

1.1 基本定义

给定正整数 q，模 q 的余数就是做除法后留下的余数。我们用 Zq 表示集合 {0, 1, 2, ..., q−1}，其中的加法和乘法都要对 q 取模：

Zq = {0, 1, 2, ..., q−1}

加法：a + b mod q（先加起来，再取余数）
乘法：a × b mod q（先乘起来，再取余数）

例：令 q = 7
3 + 5 = 8 → 8 mod 7 = 1
3 × 5 = 15 → 15 mod 7 = 1
−3 mod 7 = 4（负数也有对应的模表示）
1.2 中心化表示

在格密码学中，我们经常用中心化的方式表示模 q 的数。即把 {0, 1, ..., q−1} 重新表示为关于 0 对称的数：

如果 q 是奇数：{-(q−1)/2, ..., -1, 0, 1, ..., (q−1)/2}
如果 q 是偶数：{-q/2, ..., -1, 0, 1, ..., q/2−1}，以及 q/2（任意归属一边）

比如 q = 7 时，中心化表示为 {-3, -2, -1, 0, 1, 2, 3}。这种表示让我们可以谈论一个模 q 的数有多「小」——离 0 越近越「小」。

直觉：在 ML-DSA 中，私钥的每个系数都在 {-η, ..., 0, ..., η} 范围内（例如 {-2, -1, 0, 1, 2}）。这些数相对于 q（~195 万）来说极其「小」，这是安全性的关键。
2. 多项式与多项式环
2.1 多项式回顾

一个多项式就是形如 a0 + a1x + a2x2 + ... + anxn 的表达式。在大学数学里，你可能学过实系数多项式（如 3x2 + 2x − 1）。这里我们做两件事：

  1. 把系数限制在 Zq 中（而不是实数）
  2. 用 x256 + 1 = 0 这个规则来「截断」多项式
2.2 多项式模 xn + 1

就像整数模运算中我们做除法取余数一样，多项式也可以做除法取余数。我们选的「模」是 xn + 1（在 ML-DSA 中 n = 256）：

f(x) mod (x256 + 1) 的含义：

规则：x256 = −1

所以 x256 可以替换成 −1：
x256 → −1
x257 = x · x256 → −x
x258 = x2 · x256 → −x2
x512 = (x256)2 → (−1)2 = 1

一般地：xk mod (x256 + 1) = (−1)⌊k/256⌋ · xk mod 256

这意味着任何多项式在模 x256 + 1 之后，最高次只有 255。所以我们的多项式环中每个元素恰好有 256 个系数，可以看作一个 256 维的向量。

2.3 多项式乘法

两个多项式相乘后取模：

例：令 n = 4（简化版），模 x^4 + 1，系数模 q = 5 a = 1 + 2x + x^3 b = 2 + x^2 普通乘积： a · b = 2 + 4x + 2x^2 + x^3 + 2x^4 + 2x^5 + x^6 模 x^4 + 1（用 x^4 = -1 代入）： 2x^4 → 2·(-1) = -2 → -2 mod 5 = 3 2x^5 = 2x·x^4 → 2x·(-1) = -2x → -2 mod 5 = 3 (系数为 3) x^6 = x^2·x^4 → x^2·(-1) = -x^2 → -1 mod 5 = 4 (系数为 4) 结果 a · b mod (x^4+1, 5) = (2+3) + (4+3)x + (2+4)x^2 + x^3 = 0 + 2x + x^2 + x^3 (系数 mod 5) 所以 a · b = 2x + x^2 + x^3

这种乘法在数学上叫做负循环卷积（negacyclic convolution）。它有一个非常好的性质：可以用数论变换（NTT）来加速计算，就像用 FFT 加速普通卷积一样。这使得 ML-DSA 的多项式乘法极其高效。

3. 密码学中的环 Rq

现在我们把模运算和多项式放在一起，定义 CRYSTALS 方案工作的数学世界：

Rq = Zq[x] / (x256 + 1)

这个记号的意思是：

  • 所有系数在 Zq 中（即 0 到 q−1 之间的整数）
  • 多项式最高 255 次（因为 x256 = −1 截断了）
  • 每个元素恰好有 256 个系数 → 可以看作 256 维向量

Rq 中的元素可以做加法（系数逐一相加，mod q）和乘法（多项式乘法，mod x256+1，系数 mod q）。这两个运算让 Rq 成为一个环（Ring）——满足你在抽象代数课上学过的那些性质（结合律、分配律、有零元和单位元等）。

3.1 Rq 上的向量与矩阵

就像实数有向量 (a, b, c) 和矩阵一样，Rq 上也有向量和矩阵。一个 Rql 中的向量包含 l 个 Rq 元素（即 l 个多项式），总共有 l × 256 个整数系数。

在 ML-DSA-65 中： q = 1,952,581（一个 21 位素数） n = 256 R_q 的一个元素：256 个系数，每个 0~1,952,580 矩阵 Â ∈ R_q^(6×5)：6 行 5 列，每项是一个 R_q 元素 → 总共 6 × 5 × 256 = 7,680 个系数 向量 s₁ ∈ R_q^5：5 个多项式，每个 256 个系数 矩阵-向量乘法：Â · s₁ → 得到 R_q^6 中的一个向量

Rq 上的矩阵-向量乘法和普通线性代数几乎一模一样——只是每个元素从「实数」换成了「Rq 中的多项式」，加法和乘法换成了 Rq 中的运算。

3.2 「短」元素

Rq 中的一个元素被称为「短」的，如果它的所有系数都很小（在中心化表示中接近 0）。这是格密码学最核心的概念之一。

Rq 中的元素 a = a0 + a1x + ... + a255x255

无穷范数：‖a‖∞ = max |ai|（最大系数的绝对值）

「短」通常指 ‖a‖∞ ≤ η（η 是一个小整数，如 2 或 4）

例（ML-DSA-65）：私钥 s₁ 的每个系数 ∈ {−4, −3, ..., 0, ..., 3, 4}
而 q ≈ 200 万，所以私钥系数只用了 q 的万分之几
为什么「短」很重要？想象 q 是一个百万级的数，而私钥的每个系数只是个位数。这就好比在一个巨大的沙盒里藏了一根针——你知道沙盒里某处有根针，但要在百万粒沙子中找到它，几乎不可能。
4. 格（Lattice）
4.1 什么是格？

格是 n 维空间中一组等间距排列的点。形式地说，给定 k 个线性无关的向量 b1, b2, ..., bk（称为基），它们生成的格是：

L = { c1b1 + c2b2 + ... + ckbk | ci ∈ Z }

即所有整数线性组合构成的点集。

4.2 二维例子
二维格的例子： 基向量 b₁ = (2, 1), b₂ = (1, 3) 格点是所有 c₁·(2,1) + c₂·(1,3)，c₁, c₂ ∈ Z： (0,0), (2,1), (1,3), (4,2), (3,4), (2,6), (-2,-1), (-1,-3), (4,5), (5,7), (0,2), ... 可视化（只显示一小部分）： · · · · · · · · · · · · · · · · · · · · · · · · · · · · 就像二维平面上的一张「无限大的网格纸」，但网格可以是歪的。
4.3 格的关键性质
  • 同一个格可以有不同的基：比如上面的格也可以用 b1' = (3, 4), b2' = (−1, −2) 作为基——它们生成完全相同的格点集。
  • 短基 vs 长基：有些基的向量很短、几乎正交（像方格纸）；有些基的向量很长、很倾斜。从「长基」找到「短基」是一个非常困难的问题。
  • 最小距离：格中离原点最近的非零格点的距离，记为 λ1。这个量刻画了格的「密度」。
5. 模格（Module Lattice）

「模格」是格概念在多项式环上的推广。理解它的关键是：Rq 中的向量-矩阵运算等价于一个非常高维的格上的运算。

5.1 从 Rq 到格

Rq 中的一个多项式有 256 个系数，可以看作 256 维的整数向量（系数对 q 取模）。Rql 中的一个向量有 l 个多项式，总共 l × 256 个系数，即一个 l×256 维的向量。

所以 Rq 上的一个 k×l 矩阵 Â 对应一个 (k×256) × (l×256) 的整数矩阵（把每个多项式「展开」成 256 个系数）。这个整数矩阵生成的格就是一个模格。

维度的对应： R_q 上的矩阵 Â ∈ R_q^(k×l) ↓ 展开 Z_q 上的矩阵 A ∈ Z_q^((k·256) × (l·256)) 在 ML-DSA-65 中 (k=6, l=5)： A 是 1536 × 1280 的矩阵（在 Z_q 上） → 对应的格是 1280 维空间中的格点阵 这就是为什么量子计算机也搞不定——搜索空间是 1280 维的！
5.2 为什么用「模格」而不是「普通格」？

理论上，直接用高维整数格也能构造密码方案。但模格有一个巨大的实用优势：紧凑性。

  • 普通格方案需要存储完整的高维矩阵（几十 KB 到几百 KB）
  • 模格方案只需要存储一个 Rq 上的小矩阵（几 KB）——因为多项式环的代数结构提供了大量「隐式的维度」

简而言之：模格让你用「少」的参数获得「多」的维度。这就是 ML-DSA 的公钥只要 ~2 KB 的原因。

6. SIS 问题（短整数解）

SIS（Short Integer Solution）是格密码学的两个核心难题之一。它是构造签名方案的安全基础。

6.1 问题定义
SIS 问题

输入：一个随机矩阵 A ∈ Zq(m×n)，一个上界 B
目标：找一个非零的「短」向量 z ∈ Zqn，使得：

A · z ≡ 0 (mod q)，且 ‖z‖ ≤ B

简单说：找一个非零的短向量 z，使得 Az 等于零（模 q）。

6.2 直觉理解
简化例子：2×3 矩阵，q = 11，求短解 A = [1, 2, 3] [4, 5, 6] 要找 z = (z₁, z₂, z₃)，使得： z₁ + 2z₂ + 3z₃ ≡ 0 (mod 11) 4z₁ + 5z₂ + 6z₃ ≡ 0 (mod 11) 一个解：z = (1, 1, -3) (即 z = (1, 1, 8) mod 11) 验证：1 + 2 + 24 = 27 ≡ 5 ✗ (不对，换一个) z = (1, -2, 1) (即 z = (1, 9, 1) mod 11) 验证：1 + 18 + 3 = 22 ≡ 0 ✓ 4 + 45 + 6 = 55 ≡ 0 ✓ ‖z‖∞ = 2 (够短) 在这个小例子里你可以手算，但当 A 是几千×几千的矩阵时， 解空间呈指数爆炸，没有任何已知算法能高效求解。
为什么 SIS 困难？你需要在一个非常高维的空间中找一个离原点很近的格点。这就像站在一片无边无际的沙漠里，要找到离你最近的绿洲——如果没有地图（好的基），你只能漫无目的地搜索。
6.3 SIS 与签名的关系

在 ML-DSA 中，伪造签名本质上需要解决 SIS：攻击者需要找一个短向量 z 使得 ·z 等于某个特定值。由于  是随机的，这等价于一般的 SIS 问题。而 SIS 已被证明至少和最坏情况下的格问题一样难（worst-case to average-case 归约），这是格密码学的一个里程碑式结果。

7. LWE 问题（学习误差）

LWE（Learning With Errors）是格密码学的另一个核心难题。它是构造加密/密钥交换方案（如 ML-KEM）的安全基础，也用于保证 ML-DSA 的签名不泄露私钥。

7.1 问题定义
LWE 问题

输入：若干对 (ai, bi)，其中 ai ← Zqn 是随机向量，
bi = ⟨ai, s⟩ + ei (mod q)，ei 是一个小随机「误差」
目标：恢复出秘密向量 s

简单说：给定一组「带噪声的线性方程」，求未知数 s。

7.2 直觉理解
简化例子：3 个变量，q = 11，误差范围 ±1 秘密 s = (3, 7, 2) 你看到的方程（带噪声）： a₁ = (1, 2, 3), b₁ = 1×3 + 2×7 + 3×2 + 1 = 24 ≡ 2 (真实值是 1) a₂ = (4, 1, 5), b₂ = 4×3 + 1×7 + 5×2 − 1 = 28 ≡ 6 (真实值是 7) a₃ = (2, 3, 1), b₃ = 2×3 + 3×7 + 1×2 + 0 = 29 ≡ 7 (真实值是 7) ... 如果噪声 e = 0，这就是普通线性方程组，高斯消元法轻松求解。 但因为每个方程都有 ±1 的误差，高斯消元会让误差急剧放大。 而且你不知道哪些方程有误差、误差是多少——可能性太多，无法筛选。
关键对比：LWE vs 普通线性方程组
普通线性方程组：Ax = b，已知 A 和 b，求 x。高斯消元法可以在多项式时间内求解。

LWE：Ax + e = b，已知 A 和 b，求 x。e 是未知的小误差。高斯消元会让误差「传染」到所有方程——消掉一个变量的同时，那个变量的误差会乘上系数加到其他方程中，很快所有方程都变得不可靠。

这就像做实验测量：如果每次测量都有微小的误差，经过多步计算后，累积误差可能完全淹没真实值。在低维情况下这还能处理，但在几千维的空间中，这是一个公认的困难问题。
7.3 两种 LWE
名称描述困难性
Search-LWE给定 (A, b = As + e)，求出 s恢复秘密
Decision-LWE区分 (A, As + e) 和 (A, u)，其中 u 是随机数区分「带噪声的方程」和「随机数」

两个版本已知是等价的：如果你无法区分 (A, As+e) 和随机数，那你当然也无法恢复 s。Decision-LWE 在构造加密方案时特别有用——密文和随机数不可区分，就意味着密文不泄露任何信息。

8. Module-SIS 与 Module-LWE

Module-SIS 和 Module-LWE 就是把 SIS/LWE 从整数矩阵推广到多项式环 Rq 上的矩阵。

8.1 Module-SIS
Module-SIS 问题

输入：随机矩阵 Â ∈ Rq(k×l)，上界 B
目标：找非零短向量 z ∈ Rql，使得 Â · z = 0（在 Rq 中）

与普通 SIS 的唯一区别：矩阵和向量的「元素」从整数变成了 Rq 中的多项式
8.2 Module-LWE
Module-LWE 问题

输入：若干对 (â, b = â·ŝ + ê)，其中 â ← Rqk，ê 是短「误差」向量
目标：恢复秘密 ŝ ∈ Rql

与普通 LWE 的唯一区别：运算从整数模 q 变成了 Rq 中的运算
8.3 困难性层级

从一般到特殊，格问题形成了一个困难性层级：

困难性（从一般到特殊）： General Lattice（一般格） ↓ 已证明归约 Ideal Lattice（理想格） — 基于「环」结构 ↓ 已证明归约 Module Lattice（模格） — 介于一般格和理想格之间 Module-SIS/Module-LWE 的困难性 ≥ Ideal-SIS/Ideal-LWE Module-SIS/Module-LWE 的困难性 ≤ General-SIS/General-LWE 也就是说：Module 格比 Ideal 格更安全（因为结构更少）， 但比 General 格更高效（因为还有一定结构可以利用）。 CRYSTALS 选择 Module 格是一个安全性和效率的折中。
9. 为什么这些问题困难？
9.1 经典困难性

SIS 和 LWE 的困难性有非常强的理论保证：

  • 最坏情况归约（Ajtai 1996；Regev 2005）：解决随机实例的 SIS/LWE 至少和解决最坏情况（即最难的实例）的格问题一样难。这在密码学中是非常罕见的——大多数密码假设只保证平均情况安全性。
  • NP-hard 关系：格上的最近向量问题（CVP）已知是 NP-hard 的。虽然 SIS/LWE 不直接等于 CVP，但它们是 CVP 的「近似版本」，而且近似因子足够小，使得所有已知算法都不可行。
9.2 量子困难性

这是后量子密码学最关键的点。目前已知的量子算法对格问题的加速很有限：

问题经典最优算法量子最优算法量子加速
大整数分解亚指数（2n1/3）多项式（Shor 算法）致命
椭圆曲线离散对数亚指数多项式（Shor 算法）致命
SIS / LWE指数（2cn）指数（2c'n，c'<c）仅多项式加速

量子算法（主要是 Grover 搜索及其变体）只能把格问题的指数系数从 c 降低到 c'（比如从 2n/2 降到 2n/2.5），仍然是指数级的。只需适当增大参数（比如增大矩阵维度或模数），就能完全弥补量子加速。

9.3 具体攻击复杂度

对 ML-DSA-65 的最佳已知攻击（BKZ 格基归约）的复杂度估计：

攻击方法经典复杂度量子复杂度
暴力搜索22562128（Grover）
格基归约（BKZ）~2180~2160
混合攻击（组合+格归约）~2175~2155

所有这些数字都远远超出了可计算范围（2100 已经是宇宙级别的不可行）。而且这些估计还偏保守——实际攻击可能更难。

10. 与 ML-DSA / ML-KEM 的联系

现在让我们把数学和具体算法联系起来：

10.1 ML-DSA 的安全归约
ML-DSA 签名方案的安全性链条： 伪造签名 → 解决 Module-SIS → 解决一般格上的 SVP ↑ ↑ ↑ 不可能 困难 NP-hard 级别 签名泄露私钥 → 解决 Module-LWE → 区分随机和带噪声的线性方程 ↑ ↑ 不可能 困难 具体地： • 如果攻击者能以不可忽略的概率伪造签名 → 攻击者能解决 Module-SIS 实例 → 但 Module-SIS 是困难的（有 worst-case 归约保证） → 所以无法伪造 • 如果攻击者能从签名中提取私钥信息 → 攻击者能解决 Module-LWE 实例 → 但 Module-LWE 是困难的 → 所以无法提取 • 拒绝采样保证签名分布接近均匀随机 → 即使收集无限多签名也无法推断 s₁
10.2 ML-KEM 的安全归约
ML-KEM 密钥封装的安全性链条： 从密文推断共享密钥 → 解决 Module-LWE ↑ 不可能（因为 LWE 困难） 密文与随机数不可区分 → Decision-Module-LWE ↑ 成立（因为 Decision-LWE 困难） 被动攻击者无法获得任何优势 → IND-CPA 安全 ↑ FO 变换 主动攻击者也无法获得优势 → IND-CCA 安全
10.3 参数选择逻辑

ML-DSA 的参数是根据安全证明和已知最优攻击来选取的：

  1. 确定目标安全级别（如 NIST Level 3 = 2192 经典安全）
  2. 计算当前最优攻击（BKZ 格归约）在该参数下的复杂度
  3. 确保复杂度 ≥ 目标安全级别
  4. 适当增加裕度以应对未来可能的算法改进

这就是为什么 ML-DSA-65 的矩阵是 6×5 而不是 4×4——更大的矩阵给更大的安全裕度，代价是更大的公钥和签名。

参考文献
  1. Ajtai, M. (1996). "Generating Hard Instances of Lattice Problems". STOC '96, pp. 99-108.
  2. Regev, O. (2005). "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography". STOC '05, pp. 84-93.
  3. Lyubashevsky, V., Peikert, C., Regev, O. (2010). "On Ideal Lattices and Learning with Errors over Rings". EUROCRYPT 2010, LNCS 6110, pp. 1-23.
  4. Langlois, A., Stehlé, D. (2015). "Worst-case to Average-case Reductions for Module Lattices". Designs, Codes and Cryptography 75(3), pp. 565-599.
  5. Bai, S., Ducas, L., et al. (2018). "CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme". TCHES 2018.
  6. NIST (2024). "Module-Lattice-Based Digital Signature Standard". FIPS 204.
  7. NIST (2024). "Module-Lattice-Based Key-Encapsulation Mechanism Standard". FIPS 203.
  8. Peikert, C. (2016). "A Decade of Lattice Cryptography". Foundations and Trends in Theoretical Computer Science 10(4), pp. 283-424.
加密算法导航
AES · DES/3DES · Blowfish · SM4 · ChaCha20 · RC4 · RSA · ECC · DH · SM2 · ML-KEM · ML-DSA · SLH-DSA
分类：密码学 · 后量子密码 · 格密码 · 数学基础