后量子密码科普

全文分三层：

1. 通俗理解：量子计算机到底威胁什么、为什么现在就要换、格密码的直觉
2. 实际用处：NIST 标准、浏览器 / Signal / iMessage / SSH 的真实部署、迁移时间表、区块链
3. 数学原理：格与 SVP/CVP、LWE、Ring/Module-LWE、Kyber 全流程、NTT 与 CRT、哈希签名，并附手算例子

第一层：通俗理解

1.1 今天的密码学靠什么撑着

几乎所有"陌生人之间建立安全连接"的场景，都靠公钥密码：

公钥算法的安全性建立在一句话上："这个数学题，经典计算机要算到宇宙毁灭。" 比如把一个 2048 位的数 $N = pq$ 分解回 $p$ 和 $q$，已知最好的经典算法（数域筛法）需要的时间大约是

$$\exp\!\Big(c\,(\ln N)^{1/3}(\ln\ln N)^{2/3}\Big),$$

对 RSA-2048 来说完全不可行。

1.2 Shor 算法：RSA 和 ECC 会被彻底攻破

1994 年，Peter Shor 证明：量子计算机可以在多项式时间内分解整数、求离散对数。

直觉是这样的。分解 $N$ 可以归结为求一个函数的周期：随便取 $a$，看

$$f(k) = a^k \bmod N$$

多久重复一次。设周期是 $r$，也就是 $a^r \equiv 1 \pmod N$。如果 $r$ 是偶数，那么

$$(a^{r/2}-1)(a^{r/2}+1) \equiv 0 \pmod N,$$

于是 $\gcd(a^{r/2}-1,\,N)$ 很可能就是 $N$ 的一个真因子。

经典计算机找周期只能一个个地试；量子计算机却能让所有 $k$ 同时"叠加"，再做一次量子傅里叶变换，周期就像光栅衍射出的条纹一样显现出来。椭圆曲线离散对数也是一个"隐藏周期"问题，同样会被攻破，而且需要的量子比特比 RSA 还少。

1.3 Grover 算法：AES 只是被削弱

对称密码（AES）和哈希（SHA-256）没有 Shor 能利用的代数结构，量子计算机只能做"无结构搜索"。Grover 算法把在 $N$ 个候选里找答案的时间从 $N$ 降到大约 $\sqrt{N}$：

$$2^{128} \;\longrightarrow\; \sqrt{2^{128}} = 2^{64}.$$

所以 AES-128 在量子攻击下"名义上"只剩 64 位安全性。但这只是平方级加速：

• 把密钥加倍就抵消了：AES-256 在量子攻击下仍有约 $2^{128}$ 的强度。
• Grover 必须串行执行，很难像经典暴力搜索那样分到成千上万台机器上并行，所以实际上连 AES-128 都没那么危险。

结论：真正需要换掉的是公钥密码，也就是密钥交换和数字签名。

1.4 "先存储，后解密"：为什么现在就要换

量子计算机还没造出来，为什么 2024 年就急着换？因为有一种攻击今天就已经在发生：

衡量是否危险，可以用一个经典的不等式（Mosca 不等式）：设

• $x$：你的数据需要保密多少年，
• $y$：整个系统迁移到后量子算法要多少年，
• $z$：距离量子计算机能破解 RSA 还有多少年。

如果

$$x + y > z,$$

那你已经晚了。病历、国家机密、基因数据的 $x$ 动辄几十年，大机构的 $y$ 也常常要十年，所以哪怕 $z$ 是 15 年也不安全。

注意两类用途的紧迫程度不同：

• 加密 / 密钥交换：受"先存储后解密"威胁，最紧迫，所以各大公司先换的都是这个。
• 签名：签名只需要在验证的那一刻是安全的。量子计算机出现之前签的名，当时验证就是可信的，所以可以晚一点换。但如果像比特币那样，公钥长期暴露在链上，就另当别论（见 2.5）。

1.5 格密码的直觉：在高维格子里找最近点

后量子密码有好几个流派（格、哈希、编码、多变量、同源），其中格密码是绝对主力。

格就是空间里排列整齐的点阵。在二维平面上，取两个向量 $b_1, b_2$，它们所有的整数组合

$$\{\, a_1 b_1 + a_2 b_2 \;:\; a_1, a_2 \in \mathbb{Z} \,\}$$

就构成一个格，看起来像一张倾斜的网格纸。

一个格有很多组不同的"基"能生成它：

• 好基：两个向量又短又接近垂直，网格方方正正。
• 坏基：两个向量又长又几乎平行，生成的是同一个格，但看起来乱七八糟。

最近向量问题（CVP）：给你空间里任意一个点，找格里离它最近的格点。

• 拿着好基：把点的坐标四舍五入到最近的整数组合，基本就对了。
• 拿着坏基：四舍五入会跑到很远的地方。

在二维里你可以靠眼睛看，但把维度提到 500 维、1000 维，就没有人知道怎么高效地做了。已知最好的算法（无论经典还是量子）都需要指数时间。

为什么量子计算机帮不上忙？ Shor 算法依赖"隐藏周期"这种代数结构，格问题里没有能直接利用的周期。几十年来人们找过量子格算法，最好的也只是常数级的改进。这也是 NIST 选择格作为主力的原因。

第二层：实际用处

2.1 NIST 标准化结果

美国国家标准与技术研究院（NIST）从 2016 年开始公开征集后量子算法，收到 82 份提案，经过三轮多公开分析，于 2024 年 8 月 13 日发布了前三个正式标准：

各个算法的定位：

• ML-KEM：通用的密钥交换。几乎所有部署都用它，最常用的参数是 ML-KEM-768。
• ML-DSA：通用签名，速度快、实现简单。
• SLH-DSA：只要哈希函数不被攻破它就安全，假设最少、最保守。代价是签名很大，而且签名慢。适合根证书、固件签名这类"签得少、要存很久"的场合。
• FN-DSA（Falcon）：签名和公钥都比 ML-DSA 小很多，但签名时要在浮点数上做离散高斯采样，很难实现成常数时间、防侧信道，所以标准一直落后。截至 2026 年 10 月仍是草案。
• HQC：2025 年 3 月被 NIST 选为 ML-KEM 的备份。它基于纠错码而不是格，所以万一哪天格被攻破，还有一个数学上完全不同的方案可用。标准计划 2027 年定稿。

参数大小对比（单位：字节）：

2.2 为什么要"混合"（hybrid）

几乎所有实际部署都不是直接把 X25519 换成 ML-KEM，而是两个一起用：

$$K = \mathrm{KDF}\big(K_{\text{X25519}} \,\|\, K_{\text{ML-KEM}}\big).$$

攻击者必须同时攻破两者才能拿到 $K$：

• 如果量子计算机来了，X25519 失守，ML-KEM 还撑着。
• 如果 ML-KEM 被发现有数学漏洞或实现漏洞，X25519 至少保证不比今天差。

这种谨慎是有教训的：2022 年，NIST 第四轮候选 SIKE（同源密码）被一台普通笔记本一个小时内攻破；签名候选 Rainbow（多变量）也在同年被攻破。新数学难题需要时间检验。

2.3 实际部署

浏览器与 TLS（HTTPS）

• Chrome：2024 年 4 月的 Chrome 124 在桌面端默认启用 X25519+Kyber768 混合密钥交换；2024 年 11 月的 Chrome 131 换成了标准化后的 X25519MLKEM768。Firefox、Edge 随后跟进，Apple 也在 2025 年的系统更新中给 TLS 加入了混合 ML-KEM。
• Cloudflare：从 2022 年起服务端支持后量子握手。2025 年 10 月底，Cloudflare 上过半的人类流量已经使用后量子密钥交换；据 2026 年 4 月的报道，这一比例已超过 65%。Cloudflare 的目标是 2029 年让认证（签名）也全面后量子化。

Signal

• PQXDH（2023 年 9 月）：在初始的 X3DH 握手中加入 Kyber-1024，保护会话的建立。
• SPQR / 三重棘轮（2025 年 10 月 2 日发布）：Signal 原本的双棘轮（Double Ratchet）会随着聊天不断更新密钥。SPQR（Sparse Post-Quantum Ratchet）再加一条基于 ML-KEM-768 的棘轮，两边的密钥一起输入 KDF。这样后量子保护覆盖到整个对话过程，而不只是开头。
  • 一个和本系列相关的细节：ML-KEM 的数据有一千多字节，Signal 把它切块，并用纠删码保护，丢掉几块消息也能恢复，原理和 Reed–Solomon 纠错码相同。

Apple iMessage PQ3（2024 年 2 月，iOS 17.4）

• 初始握手用 Kyber-1024 和 ECC 混合，之后还会周期性地用 Kyber-768 重新换密钥。即使某一刻的密钥泄露，之后的消息也能自动恢复安全。Apple 称之为"Level 3"安全等级。

OpenSSH

• OpenSSH 9.0（2022 年 4 月）就默认使用 sntrup761x25519-sha512（NTRU Prime + X25519 混合）。
• OpenSSH 10.0（2025 年 4 月）把默认密钥交换改为 mlkem768x25519-sha256。之后的 10.1 版本还会在连接没有使用后量子密钥交换时发出警告。
• 但主机密钥和用户密钥（Ed25519、RSA）仍然是经典签名，因为 SSH 的后量子签名标准还在 IETF 讨论中。这再次说明：先换密钥交换，再换签名。

2.4 迁移时间表

总之，2035 年是各国几乎一致的"RSA/ECC 退役"截止线。

2.5 区块链面临的威胁

区块链对量子攻击特别敏感，因为签名就是所有权，而且历史数据永远公开。

比特币

• 用的是 secp256k1 上的 ECDSA / Schnorr 签名，Shor 算法可以从公钥直接算出私钥。
• 地址通常是公钥的哈希，哈希只受 Grover 威胁，所以"只收过款、从未花过"的地址相对安全。
• 危险的是公钥已经暴露的币：
  • 早期 P2PK 输出直接把公钥写在链上，包括大约一百万枚被认为属于中本聪的币；
  • 重复使用的地址（花过一次，公钥就公开了）；
  • Taproot（P2TR）输出直接包含公钥。
• 即使地址没暴露，交易广播到上链之间的几分钟里公钥也是公开的，足够快的量子计算机可以抢先算出私钥、发出冲突交易。
• 社区在讨论 BIP-360 之类的后量子地址类型提案，但还要面对一个社会问题：那些不迁移的老币怎么办？冻结还是放任被"量子矿工"拿走？

以太坊

• 外部账户（EOA）同样基于 secp256k1，发过一笔交易后公钥就能从签名里恢复出来。
• 账户抽象让钱包可以换用任意签名算法，这是以太坊后量子迁移的主要路径之一。
• 零知识证明层面：基于配对的 SNARK（Groth16、KZG 承诺）依赖椭圆曲线离散对数，会被 Shor 攻破；而基于哈希的 STARK（以及里面用到的 FRI 和 Reed–Solomon 码）是后量子安全的。

工作量证明本身（SHA-256 挖矿）只受 Grover 的平方级加速，而且量子计算机的时钟频率远低于 ASIC 矿机，短期内不是问题。

第三层：数学原理

3.1 格、SVP 与 CVP

用代数的语言说，格就是 $\mathbb{R}^n$ 中秩为 $n$ 的离散加法子群，作为 $\mathbb{Z}$-模同构于 $\mathbb{Z}^n$。

同一个格有很多组基：$B$ 和 $B'$ 生成同一个格，当且仅当存在 $U \in GL_n(\mathbb{Z})$（整数矩阵，行列式为 $\pm 1$）使得 $B' = BU$。所以 $|\det B|$ 不依赖于基的选择，它是格的"基本区域体积"。

两个核心难题：

• 最短向量问题（SVP）：找格里最短的非零向量，长度记为 $$\lambda_1(\mathcal{L}) = \min_{v \in \mathcal{L}\setminus\{0\}} \|v\|.$$
• 最近向量问题（CVP）：给定目标点 $t \in \mathbb{R}^n$，找 $v \in \mathcal{L}$ 使 $\|t - v\|$ 最小。

已知结果：

• LLL 算法（1982）在多项式时间内找到长度不超过 $2^{O(n)}\lambda_1$ 的向量。近似因子是指数级的，对密码学没用。
• BKZ 算法可以在近似因子和运行时间之间取舍，但要得到多项式近似因子，仍然需要 $2^{\Theta(n)}$ 时间。
• 精确 SVP 在随机归约下是 NP-困难的。目前没有任何量子算法能在多项式时间内把 SVP 近似到多项式因子。

密码学实际依赖的是近似因子为多项式的 SVP（GapSVP、SIVP）的困难性。

3.2 LWE：带误差的学习

直接用格基构造密码系统（GGH、早期 NTRU 变体）不太方便。2005 年 Oded Regev 提出了一个"代数化"的版本：Learning With Errors（LWE）。

为什么 $e$ 是关键？ 如果没有 $e$，$b = As$ 就是一个线性方程组，在 $\mathbb{Z}_q$（$q$ 为素数时是域）上用高斯消元，几步就解出 $s$。加入一点点噪声后：

• 高斯消元会把误差放大：每做一次行变换，误差就乘上系数、互相累加，很快就淹没了信号。
• 从格的角度看，$\{\,Ax \bmod q : x\in\mathbb{Z}_q^n\,\}$ 加上 $q\mathbb{Z}^m$ 构成一个格，而 $b$ 是离某个格点距离很小的一个点。解 LWE 就是解这个格上的 CVP。

这个"最坏情况到平均情况"的归约非常强：破解一个随机生成的 LWE 实例，就等于能解决所有格上的困难问题。RSA 就没有这样的保证。

从 LWE 到公钥加密（Regev 方案，加密一个比特）：

• 私钥：$s \in \mathbb{Z}_q^n$。
• 公钥：$(A,\, b = As + e)$。
• 加密比特 $\mu \in \{0,1\}$：随机选 $r \in \{0,1\}^m$，计算 $$u = A^{\mathsf T} r, \qquad v = b^{\mathsf T} r + \mu \cdot \left\lfloor \tfrac{q}{2} \right\rfloor .$$ 密文是 $(u, v)$。
• 解密：计算 $$d = v - u^{\mathsf T} s = (As+e)^{\mathsf T} r + \mu\lfloor q/2\rfloor - r^{\mathsf T} A s = e^{\mathsf T} r + \mu \left\lfloor \tfrac{q}{2} \right\rfloor .$$ 因为 $e^{\mathsf T} r$ 很小，$d$ 接近 $0$ 就输出 $0$，接近 $q/2$ 就输出 $1$。
• 正确性条件：$|e^{\mathsf T} r| < q/4$。

3.3 手算例子：玩具 LWE 加密一个比特

第 1 步：生成公钥。 先算 $As$：

$$As = \begin{pmatrix} 3\cdot 2 + 7\cdot 5 \\ 5\cdot 2 + 1\cdot 5 \\ 11\cdot 2 + 4\cdot 5 \\ 2\cdot 2 + 9\cdot 5 \end{pmatrix} = \begin{pmatrix} 41 \\ 15 \\ 42 \\ 49 \end{pmatrix} \equiv \begin{pmatrix} 7 \\ 15 \\ 8 \\ 15 \end{pmatrix} \pmod{17}.$$

再加上误差：

$$b = As + e \equiv \begin{pmatrix} 7+1 \\ 15-1 \\ 8+0 \\ 15+1 \end{pmatrix} = \begin{pmatrix} 8 \\ 14 \\ 8 \\ 16 \end{pmatrix} \pmod{17}.$$

公开 $(A, b)$，保密 $s$。

第 2 步：加密比特 $\mu = 1$。 随机选 $r = (1, 0, 1, 1)^{\mathsf T}$，也就是取第 1、3、4 个样本相加：

$$u = A^{\mathsf T} r = \begin{pmatrix} 3 + 11 + 2 \\ 7 + 4 + 9 \end{pmatrix} = \begin{pmatrix} 16 \\ 20 \end{pmatrix} \equiv \begin{pmatrix} 16 \\ 3 \end{pmatrix} \pmod{17},$$

$$v = b^{\mathsf T} r + 8 = (8 + 8 + 16) + 8 = 40 \equiv 6 \pmod{17}.$$

密文是 $(u, v) = \big((16, 3)^{\mathsf T},\; 6\big)$。

第 3 步：解密。 用私钥算

$$u^{\mathsf T} s = 16\cdot 2 + 3 \cdot 5 = 47 \equiv 13 \pmod{17},$$

$$d = v - u^{\mathsf T} s = 6 - 13 = -7 \equiv 10 \pmod{17}.$$

判断规则：$\mathbb{Z}_{17}$ 里离 $0$ 近的是 $\{13,\dots,16, 0, 1, \dots, 4\}$，离 $8$ 近的是 $\{5, \dots, 12\}$。$d = 10$ 离 $8$ 只差 $2$，所以解密为 $1$ ✓。

验证一下理论：$e^{\mathsf T} r = 1 + 0 + 1 = 2$，确实有

$$d = e^{\mathsf T} r + 8 = 2 + 8 = 10.$$

对照：加密 $\mu = 0$。 用同一个 $r$，$u$ 不变，$v = 32 \equiv 15$，于是 $d = 15 - 13 = 2$，离 $0$ 近，解密为 $0$ ✓。

为什么总是正确？ $e$ 各分量的绝对值之和是 $3$，所以对任意 $r \in \{0,1\}^4$ 都有 $|e^{\mathsf T} r| \le 3 < 17/4$，解密永远不会出错。（已用 Python 枚举全部 $2^4$ 个 $r$ 和两种比特验证。）

3.4 Ring-LWE 与 Module-LWE

普通 LWE 有个大问题：公钥太大。矩阵 $A$ 有 $m \times n$ 个元素，$n = 768$ 时就是几十万个数，公钥要几百 KB。

Ring-LWE 的想法：让 $A$ 有结构，用一个多项式代替整个矩阵。

取商环

$$R_q = \mathbb{Z}_q[x] / (x^n + 1),$$

它的元素是次数 $< n$、系数在 $\mathbb{Z}_q$ 中的多项式，乘法做完后用 $x^n = -1$ 化简。用抽象代数的语言说，$R_q$ 就是 $\mathbb{Z}[x]$ 模掉理想 $(q,\; x^n+1)$ 得到的商环：

$$R_q \;\cong\; \mathbb{Z}[x] / (q,\; x^n + 1).$$

在 $R_q$ 中，"乘以 $a(x)$"是 $\mathbb{Z}_q$-线性映射，对应一个 $n\times n$ 矩阵：

$$a(x) \cdot s(x) \quad\longleftrightarrow\quad \begin{pmatrix} a_0 & -a_{n-1} & \cdots & -a_1 \\ a_1 & a_0 & \cdots & -a_2 \\ \vdots & \vdots & \ddots & \vdots \\ a_{n-1} & a_{n-2} & \cdots & a_0 \end{pmatrix} \begin{pmatrix} s_0 \\ s_1 \\ \vdots \\ s_{n-1} \end{pmatrix}.$$

这种矩阵叫反循环矩阵（negacyclic）：每一列都是上一列往下"转一格"，转到顶上的元素变号，因为 $x \cdot x^{n-1} = x^n = -1$。整个矩阵只由 $n$ 个数决定，存储量从 $n^2$ 降到 $n$。

为什么用 $x^n + 1$？ 取 $n = 2^k$，此时

$$x^n + 1 = \Phi_{2n}(x)$$

是第 $2n$ 个分圆多项式（它的复根恰好是全部 $2n$ 次本原单位根 $e^{\pi i (2j+1)/n}$）。选它有几个原因：

1. 在 $\mathbb{Q}$ 上不可约（对 $\Phi_{2^{k+1}}$ 可以对 $f(x+1)$ 用 Eisenstein 判别法，$p=2$）。于是 $\mathbb{Z}[x]/(x^n+1)$ 是分圆域 $\mathbb{Q}(\zeta_{2n})$ 的整数环。Lyubashevsky–Peikert–Regev（2010）正是借助这个代数数论结构，把 Ring-LWE 的困难性归约到理想格上的最坏情况困难问题。
2. 不可约很重要。反例：如果用 $x^n - 1 = (x-1)(\cdots)$，就有环同态 $$\mathbb{Z}_q[x]/(x^n - 1) \to \mathbb{Z}_q, \qquad f(x) \mapsto f(1).$$ 把 $b = as + e$ 两边代入 $x = 1$，得到 $b(1) = a(1)s(1) + e(1)$。这是只有 1 个未知数的小问题，$e(1)$ 又比较小，泄露的信息足以发起攻击。
3. 约化很便宜：$x^n \equiv -1$，模运算只需把高次项变号加回低次项。而且系数不会在约化中膨胀（"扩张因子"小），误差保持很小。
4. 适合 NTT：当 $q \equiv 1 \pmod{2n}$（或 $\pmod n$）时，$x^n+1$ 在 $\mathbb{Z}_q$ 上能分解，乘法可以用 NTT 加速（见 3.6）。

Module-LWE：介于两者之间。 Ring-LWE 的结构太"满"，Module-LWE 退回一点：用 $k \times k$ 的环元素矩阵

$$\mathbf{A} \in R_q^{k\times k}, \qquad \mathbf{s}, \mathbf{e} \in R_q^{k}, \qquad \mathbf{t} = \mathbf{A}\mathbf{s} + \mathbf{e}.$$

这是 $R_q$-模 $R_q^k$ 上的 LWE，所以叫 Module-LWE。好处：

• 环 $R_q$ 固定为 $n = 256$，只改 $k$ 就能调安全等级，同一套 NTT 代码通用。
• 相比 Ring-LWE，代数结构更少，理论上更不容易被针对结构的攻击利用。

三者都用 $n = 256$、$q = 3329$。

3.5 Kyber（ML-KEM）的流程

记号：$R_q = \mathbb{Z}_q[x]/(x^{256}+1)$，$q = 3329$。"小"多项式的系数从中心二项分布 $\beta_\eta$ 中采样，取值在 $\{-\eta, \dots, \eta\}$，ML-KEM-768 中 $\eta = 2$。

推导只用了 $\mathbf{t} = \mathbf{A}\mathbf{s}+\mathbf{e}$ 和 $R_q$ 的交换性：

$$\mathbf{t}^{\mathsf T}\mathbf{r} - \mathbf{s}^{\mathsf T}\mathbf{A}^{\mathsf T}\mathbf{r} = (\mathbf{A}\mathbf{s})^{\mathsf T}\mathbf{r} + \mathbf{e}^{\mathsf T}\mathbf{r} - \mathbf{s}^{\mathsf T}\mathbf{A}^{\mathsf T}\mathbf{r} = \mathbf{e}^{\mathsf T}\mathbf{r}.$$

这和 3.3 的玩具例子结构完全相同，只是把"整数"换成了"$R_q$ 里的多项式"，一次加密 256 个比特而不是 1 个。

3.6 NTT：用中国剩余定理加速乘法

Kyber 的主要计算量是 $R_q$ 中的多项式乘法。直接相乘需要 $256^2 = 65536$ 次系数乘法，NTT（数论变换） 可以把它降到 $O(n\log n)$ 量级。NTT 就是有限域上的 FFT，背后的数学是抽象代数里的中国剩余定理。

关键点：同构右边的乘法是逐分量的。所以计算 $g \cdot h$ 时，可以：

1. 把 $g, h$ 分别映到右边（正向 NTT）；
2. 逐分量相乘（便宜）；
3. 映回左边（逆向 NTT）。

而第 1、3 步可以像 FFT 那样递归地对半拆分 $x^{2m} - c^2 = (x^m - c)(x^m + c)$，总共 $\log n$ 层。

先看一个小例子：$\mathbb{Z}_{17}[x]/(x^4+1)$。

因为 $17 \equiv 1 \pmod 8$，$\mathbb{Z}_{17}^\times$（循环群，阶为 $16$）中有 8 次本原单位根，所以 $x^4 + 1$ 在 $\mathbb{Z}_{17}$ 上完全分解。它的四个根是 $2, 8, 9, 15$（例如 $2^4 = 16 \equiv -1$）。于是

$$\mathbb{Z}_{17}[x]/(x^4+1) \;\cong\; \mathbb{Z}_{17}[x]/(x-2) \times \mathbb{Z}_{17}[x]/(x-8) \times \mathbb{Z}_{17}[x]/(x-9) \times \mathbb{Z}_{17}[x]/(x-15) \;\cong\; \mathbb{Z}_{17}^4,$$

同构映射就是代值 $g \mapsto \big(g(2), g(8), g(9), g(15)\big)$。

取 $f = 1 + 2x + x^3$，$g = 3 + x^2$。直接计算（用 $x^4 = -1$，$x^5 = -x$）：

$$fg = 3 + 6x + x^2 + 5x^3 + x^5 = 3 + 5x + x^2 + 5x^3.$$

用代值验证：

完全吻合。顺便注意 $f(9) = 0$：$f$ 不是零多项式，却在一个分量上为零，所以 $f$ 是这个环里的零因子。这说明 $R_q$ 不是整环，和"$x^4+1$ 在 $\mathbb{Z}_{17}$ 上可约"是一回事。

回到 Kyber：$q = 3329$，$q - 1 = 3328 = 2^8 \cdot 13$。

• $\mathbb{Z}_{3329}^\times$ 是 $3328$ 阶循环群，含有 $256$ 次本原单位根，Kyber 取 $\zeta = 17$（可以验证 $17$ 的阶恰好是 $256$，且 $17^{128} \equiv -1$）。
• 但 $512 \nmid 3328$，没有 512 次本原单位根，所以 $x^{256}+1$ 不能完全分解成一次因子，只能分解成 128 个二次因子：

$$x^{256} + 1 = \prod_{i=0}^{127} \big(x^2 - \zeta_i\big), \qquad \zeta_i = \zeta^{\,2\,\mathrm{br}_7(i)+1},$$

其中 $\mathrm{br}_7(i)$ 表示把 $i$ 的 7 位二进制表示反转（这只是为了 FFT 递归时的顺序）。这 128 个 $\zeta_i$ 恰好是 $y^{128} = -1$ 的全部根。由 CRT：

$$R_q = \mathbb{Z}_q[x]/(x^{256}+1) \;\cong\; \prod_{i=0}^{127} \mathbb{Z}_q[x]/(x^2 - \zeta_i).$$

再进一步：$x^2 - \zeta_i$ 在 $\mathbb{Z}_q$ 上不可约。如果 $\zeta_i = y^2$，那么 $y$ 的阶就是 $512$，而这样的元素不存在。所以每个因子都是一个域 $\mathbb{F}_{q^2}$，于是

$$R_q \;\cong\; \underbrace{\mathbb{F}_{q^2} \times \cdots \times \mathbb{F}_{q^2}}_{128\text{ 个}}.$$

在 NTT 域里，两个多项式相乘就变成 128 次"模 $x^2 - \zeta_i$ 的一次多项式乘法"：

$$(a_0 + a_1 x)(b_0 + b_1 x) \equiv (a_0 b_0 + \zeta_i\, a_1 b_1) + (a_0 b_1 + a_1 b_0)\, x \pmod{x^2 - \zeta_i}.$$

3.7 ML-DSA 的签名思路（简述）

ML-DSA（Dilithium）采用"带中止的 Fiat–Shamir"：

1. 承诺：随机选小的 $\mathbf{y}$，计算 $\mathbf{w} = \mathbf{A}\mathbf{y}$ 的高位比特 $\mathbf{w}_1$。
2. 挑战：$c = H(\text{消息} \,\|\, \mathbf{w}_1)$，$c$ 是只有少数系数为 $\pm 1$ 的稀疏多项式。
3. 响应：$\mathbf{z} = \mathbf{y} + c\,\mathbf{s}_1$。
4. 中止检查：如果 $\mathbf{z}$ 的系数太大（可能泄露 $\mathbf{s}_1$ 的信息），就丢掉重来。通过拒绝采样，$\mathbf{z}$ 的分布与私钥无关。

验证者检查 $\mathbf{A}\mathbf{z} - c\,\mathbf{t}$ 的高位是否等于 $\mathbf{w}_1$，以及 $\mathbf{z}$ 是否足够小。其安全性依赖 Module-LWE 和 Module-SIS（找短向量 $\mathbf{x}$ 使 $\mathbf{A}\mathbf{x} = 0$）。

3.8 基于哈希的签名：从 Lamport 到 SPHINCS+

哈希签名的安全性只依赖哈希函数的单向性和抗碰撞性，没有任何代数结构。这是最保守的方案。

Lamport 一次性签名（1979）：设 $H$ 输出 256 比特。

• 私钥：$512$ 个随机字符串 $x_{i,0}, x_{i,1}$，$i = 1, \dots, 256$。
• 公钥：它们的哈希 $y_{i,b} = H(x_{i,b})$。
• 签名消息 $M$：设 $h = H(M) = h_1 h_2 \cdots h_{256}$，对每一位公开 $x_{i,h_i}$。
• 验证：检查 $H(\text{签名}_i) = y_{i,h_i}$ 对所有 $i$ 成立。

伪造签名需要对某个 $y_{i,b}$ 求哈希原像。但每个密钥只能用一次：签两条消息就会暴露两边的部分私钥，攻击者可以拼出新签名。

改进路线：

• Winternitz（WOTS）：每次处理 $w$ 个比特，用哈希链 $x \to H(x) \to H(H(x)) \to \cdots$ 表示 $0$ 到 $2^w - 1$，签名大幅变短。

• Merkle 树：把 $2^h$ 个一次性公钥作为叶子，建一棵哈希树，根就是总公钥。签名 = 一次性签名 + 从叶子到根的认证路径（$h$ 个哈希值）。缺点是签名者必须记住用过哪些叶子（有状态），XMSS、LMS（NIST SP 800-208）就是这一类。状态一旦出错（比如虚拟机快照回滚），就可能复用叶子，导致私钥泄露。

• SPHINCS+（SLH-DSA）：

  • 用超树（多层 Merkle 树叠起来）提供海量叶子，例如 $2^{63}$ 个以上；
  • 用消息的哈希伪随机地选一个叶子，叶子多到几乎不可能撞上；
  • 叶子上用 FORS（少次签名）而不是一次性签名，即使偶尔撞上同一个叶子也还安全。

  于是不需要记录状态。代价是签名有 7.8 KB 到约 50 KB，签名速度也比 ML-DSA 慢得多。

总结