4.1 Regev 加密手算与 Kyber 全流程

4.1 Regev 加密手算与 Kyber 全流程

Kyber（FIPS 203 的 ML-KEM） 是第 2 章那个 Regev 玩具加密的三步升级版：把系数向量换成多项式环元素、把秘密与误差换成居中二项分布、加一轮压缩去冗余。本节在模 25、维数 4 的迷你参数上完整推演一轮加解密，再逐项对照 ML-KEM 的官方参数与尺寸表——迷你版跑通了，标准版只是数字变大。

承接第 2 章：你已经能模 17 加密一个比特；本节把这套机器换上多项式环的发动机，一路开到标准化门口，并通往 4.2 节的签名世界。

升级第一站：把向量装进多项式环

玩具 LWE 里一个样本是一个 n 维向量，传输密文要传整个向量组，体积大得吓人。格密码的回答是把整排系数打包装进一个环元素：取 \mathbb{Z}_q[X]/(X^{256} + 1)——所有系数在模 q 的整系数多项式，乘法对 X^{256} \equiv -1 折叠。一次环乘法的代价约等于一次长度 256 的卷积，传输量却只是一行 256 个系数。Kyber 的 MLWE（模块环带误差学习）再进一步：把若干个环元素捆成"向量"（捆数 k = 2, 3, 4），在安全与效率间调档。

在动手推演前，先在迷你参数上把环乘法跑熟：取 N=4、q=25，环为 \mathbb{Z}_{25}[X]/(X^4+1)。计算 a \cdot s，其中 a = (2,1,3,5)、s = (1,2,0,0)：展开得 2 + 5X + 5X^2 + 11X^3 + 10X^4，用 X^4 \equiv -1 折叠后 10X^4 变成 -10，所以 a \cdot s = (-8, 5, 5, 11)。规则只有一条：卷积后第 4 位起的系数反号折叠回前面。记住这条，下面全部推演你都能逐位复核。

完整推演：模 25 的迷你 Kyber

参数：q = 25，N = 4，噪声取自 \{-1, 0, 1\}，编码值取 \lfloor q/2 \rfloor = 12。密钥生成：私钥 s = (1,2,0,0)；随机环元素 a = (2,1,3,5)；误差 e = (0,-1,1,0)；公钥为

加密：消息四比特 m = (1,0,1,1)；随机"盲化"多项式 r = (0,1,1,0)，误差 e_1 = (1,0,0,-1)、e_2 = (-1,1,0,0)。密文两件：

逐项算 v：先 t \cdot r，用 t = (-8,4,6,11) 展开折叠得 (-17,-19,-4,10)；加 e_2 得 (-18,-18,-4,10)；加 12m = (12,0,12,12) 得 (-6,-18,8,22)，模 25 取正代表元：v = (19, 7, 8, 22)。解密：计算

其中 u \cdot s \equiv (12,8,22,9)，你可以用折叠规则逐位验证。把 w 居中成 (-q/2, q/2] 内的代表元：(7, -1, 11, -12)。解码规则与 2.2 节同款：每个系数离 0 更近判 0、离 \pm 12 更近判 1，即 |w_i| > q/4 = 6.25 判 1。四个系数 7, 1, 11, 12 依次越线，解出 m = (1,0,1,1)——逐位全对。对照理论预期：w 应当等于 12m + (\text{累计噪声})，本例噪声是 e\cdot r + e_2 - e_1 \cdot s = (-5,-1,-1,1)，代回得 (7,-1,11,13)，与手算严丝合缝。下面二十行代码是这次推演的机器复现：

import numpy as np

q, N = 25, 4

def polmul(a, b):                       # 模 X^4 + 1 与模 q 的乘法
    c = np.convolve(a, b)
    r = c[:N].astype(int).copy()
    r[:len(c) - N] -= c[N:]             # X^4 ≡ -1，X^5 ≡ -X，以此类推
    return r % q

a = np.array([2, 1, 3, 5]); s = np.array([1, 2, 0, 0])
e = np.array([0, -1, 1, 0])
t = (polmul(a, s) + e) % q
print("公钥 t =", t)                                 # [17  4  6 11]

r = np.array([0, 1, 1, 0]); e1 = np.array([1, 0, 0, -1])
e2 = np.array([-1, 1, 0, 0]); m = np.array([1, 0, 1, 1])
u = (polmul(a, r) + e1) % q
v = (polmul(t, r) + e2 + (q // 2) * m) % q
print("密文 u =", u, " v =", v)                       # [18 22  3  3] [19  7  8 22]

w = (v - polmul(u, s)) % q
w = np.where(w > q // 2, w - q, w)                   # 居中代表元
print("w =", w)                                      # [ 7 -1 11 -12]
print("解出 m =", (np.abs(w) > q / 4).astype(int))    # [1 0 1 1]
​

与真实 Kyber 的差距只剩工程三件套：N=4 换成 256 后用数论变换把环乘法从 N^2 加速到 N \log N；\{-1,0,1\} 换成居中二项分布 CBD（取两组 \eta 个随机比特相减，好写好实现）；密文系数做压缩——低位比特几乎不带信息，砍掉存高几位，密文立省三成体积。这三件套没有一个改变动摇安全性，全是搬运与打包。

图：从 LWE 到 Kyber 的结构升级栈

对照官方参数表：迷你版与正式版

把本节推演的每个角色映射到 ML-KEM 的正式参数上，尺寸数字全部来自 FIPS 203：

读表三问。一问：密文比 X25519 的 32 字节大了三十多倍，为什么业界照收？答：抗量子是刚需，1088 字节在单个 TLS 握手里完全装得下（第 7 章看实测）。二问：\eta_1 从 512 档的 3 降到 768 档的 2，参数反而收紧了？答：k 变大已把安全垫抬起来，\eta 收窄是在给解密失败率与密文尺寸腾空间——参数表是一盘联动的棋，不要单看一格。三问：q = 3329 这个数凭什么入选？答：3329 - 1 = 3328 = 2^7 \times 26，能整除 256，支撑 256 点数论变换，同时二进制形态友好（3329 = 13 \times 256 + 1），压缩除法也快——每个数字背后都是一道工程账。

要点速记：Kyber 等于 Regev 加密的环化加模块化，迷你版四维环可完整手算；噪声累计公式决定解密成败，q/4 是生死线；ML-KEM 三档尺寸从 768 到 1568 字节，参数联动而非孤立；每个"怪数字"背后都有一笔工程账。

下一节看它的孪生兄弟：签名。同一个环，同一套噪声经济学，换一副流程骨架——Fiat-Shamir 与拒绝采样登场。