This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
我曾经和一个数学家交谈，试图向他解释椭圆曲线密码学。最后，他突然明白了，说：“哦，那个啊！我想那本书里有一章是讲这个的。你们竟然在这个领域做出了这么大的成就？”
是的，在密码学中，我们最终关注的只是我们使用的通用数学的一小部分。我认为这是好事，因为这有利于良好的工程实践，因为我们需要编写非常擅长特定任务的计算机程序，而这种专注使得我们能够相当熟练地掌握它。[1]
总之，在多年实施RSA和椭圆曲线的过程中，我们集体学到了很多关于模运算、大有限域和群逻辑的知识。我们在很多年里都做错了，但现在我认为我们基本上已经知道如何正确地做了。[2]
现在，后量子算法正在兴起，它们使用格、矩阵和多项式。那么，为了实现这些后量子密码学原语，你需要了解多少线性代数和多项式代数呢？结果发现，出乎意料地少！在规范中，“格”这个词甚至只出现在名称中。
如果你想学习数学，这篇文章可能不适合你。但如果你想要实现ML-KEM（FIPS 203，以前被称为Kyber），那么你即将准备就绪。
请注意，所有这些内容在FIPS 203（草案）的第2.4节中都有非常清晰且更详细的解释。FIPS规范实际上做得很好，避免了形式主义，直接与工程师交流。可以将这看作是一个更友好、更实用的总结。
多项式
一个多项式是环 R_q 的一个元素[3]，看起来像这样：
f = f_0 + f_1 X + f_2 X^2 + \cdots + f_{255} X^{255}
但你甚至不需要知道这些。对你作为一个实施者来说，一个ML-KEM多项式就是一个有256个系数的数组。每个系数都是一个整数模 $q$，其中 $q = 3329 = 2^8 \times 13 + 1$。一个系数数组被称为在 \mathbb{Z}_q^{256} 中，因为它由 256 个系数组成，每个系数都在 $\mathbb{Z}_q$，即整数模 $q$。
f_0 + f_1X + f_2X^2 + \cdots + f_{255}X^{255} \in R_q
\downarrow
(f_0, f_1, f_2, ..., f_{255}) \in \mathbb{Z}_q^{256}
每个系数都适合放在一个uint16中，所以你可以为多项式编写一个类型，比如[256]uint16。
要加或减两个多项式（或者环元素），你需要逐个系数地进行（ c[0] = a[0] + b[0] ，以此类推）。在ML-KEM中，你永远不会直接乘以环元素。
模运算
正如我们所说，每个系数都是一个模3329的整数，所以虽然它可以放在一个uint16中，但你确实需要对其应用正确的恒定时间模运算。
你可能习惯于对非常大的模数进行基于limb的模运算。这种方法与此类似，但简单得多，因为字段大小只有12位。
对于加法和减法，你进行经典的条件减法。[4]你会发现条件减法在ByteDecode₁₂中也很有用。
乘法结果适合放在一个uint32中。然后你可以选择Montgomery或Barrett约简算法。我发现Barrett算法更简单，也足够快。（注意，Barrett约减的内积是37位，所以你需要一个uint64的中间值。问我怎么知道的！）你不能使用%，因为除法在硬件中不是总是恒定时间的。
这个域非常小，你可以在不到一秒钟的时间内详尽地测试你的加法、减法和乘法实现。去做这个测试。
NTT
ML-KEM规范中听起来最令人害怕的部分之一是数论变换。好消息是，你也不需要理解这部分内容。
你需要知道的是，数论变换（NTT）是表示多项式的一种不同方式。每个多项式，或者说是 R_q 中的一个元素，都可以映射到 T_q （NTT域）中的一个元素，并且可以反向映射回去。执行这种映射的函数称为NTT，而执行反向映射的函数称为逆NTT（或 NTT^{-1} ）。 T_q 中的一个元素被称为“NTT代表”，用带帽子的字母表示，比如 $\hat{f}$，并且像多项式一样存储：作为256个模 q 的整数。
T_q 中的元素看起来象这样：
\hat{g} = (\hat{g}_{0,0} + \hat{g}_{0,1}X, \hat{g}_{1,0} + \hat{g}_{1,1}X, \cdots, \hat{g}_{127,0} + \hat{g}_{127,1}X) \in T_q
\downarrow
(\hat{g}_{0,0}, \hat{g}_{0,1}, \hat{g}_{1,0}, \hat{g}_{1,1}, ..., \hat{g}_{127,0}, \hat{g}_{127,1}) \in \mathbb{Z}_q^{256}
从技术上来说，NTT（数论变换）代表的是一个由128个多项式组成的序列，每个多项式有两个系数。但您不需要深入考虑这一点，您可以使用同样的数据结构，例如 [256]uint16，来表示
R_q 和 T_q 中的元素。不过，在你的类型系统中为它们分配不同的类型是个好主意，这样可以避免混淆。
如果你之前使用过蒙哥马利约简（Montgomery reduction）和蒙哥马利域（Montgomery domain），那么你应该已经熟悉将值映射到不同的域（在这里也是乘法运算更快）的概念。与蒙哥马利域类似，你用来表示元素的数据结构在域内和域外是相同的，但它们在语义上有不同的类型。
你可以在不理解 NTT（数论变换）和 NTT⁻¹（数论变换的逆）背后的数学原理的情况下实现它们。需要注意的是，在 NTT 和 NTT⁻¹ 中有一个复杂的术语叫做 \zeta = 17 \in \mathbb{Z}_q 。你需要预先计算它的128个可能的值 \zeta^{BitRev_7(i)} 。
NTT（数论变换）代表的加法和减法操作与多项式的加法和减法相同。只是不能混合匹配它们。（如果你有一个弱的类型系统或泛型，你甚至可以使用相同的函数。）
使用 NTT（数论变换）的整个原因是因为在 NTT 域中乘法运算更快。实际上，有一个叫做 MultiplyNTTs 的算法，你可以直接实现它。这个算法中有一个叫做 \gamma=\zeta^{2 \times BitRev_7(i)+1} 的项，你需要像 NTT 中的 \zeta 一样预先计算它。
ML-KEM（基于模块化学习误差问题的密钥封装机制）的特殊之处在于，NTT（数论变换）是网络传输格式的一部分，而不仅仅是一个幕后优化。因为加密和解密密钥是直接以它们的 NTT 表示形式进行序列化和反序列化的。[5]
矩阵和向量
除了系数、多项式和NTT（数论变换）代表外，你需要处理的其他主要类型是向量和矩阵。
对我们来说，向量就是一个包含 k 个元素的 R_q 或 T_q 的数组。k 的值取决于参数集，可能是 2、3 或 4。你可以用一个 [k][256]uint16 的数组来表示一个向量。向量通常用粗体小写字母表示，比如 \bf{v} 或 \bf{v}' 。
\bf{v}=\begin{bmatrix}
v_0 \\
v_1 \\
{\vdots} \\
v_{k-1}
\end{bmatrix}
向量是矩阵的一种特殊情况，具体来说，它是 k×1 的矩阵。这里的 k 表示行数，而 1 表示列数，所以一个向量就是一个有 k 行和 1 列的矩阵。我们还会遇到的另一种矩阵是
$\bf{A}$，它是一个 k×k 的矩阵。我建议用 [k×k][256]uint16 的数组来存储它，而不是 [k][k][256]uint16 ，因为后者会导致索引方式像 \bf{A}[column][row] ，这与向量类型的表示方法不一致，而在我们的表示法中， \bf{A}[row,column] 才是正确的。
$$\bf{A}=\begin{bmatrix} {a_{0,0}}&{a_{0,1}}&{\cdots}&{a_{0,k-1}}\ {a_{1,0}}&{a_{1,1}}&{\cdots}&{a_{1,k-1}}\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\ {a_{k-1,1}}&{a_{k-1,1}}&{\cdots}&{a_{k-1,k-1}}\ \end{bmatrix}$$
当我们对一个向量或矩阵应用像 NTT（数论变换）或 ByteEncode 这样的函数时，实际上是对其每个元素分别应用这些函数。
向量的加法是按坐标逐个相加的，也就是说，如果我们要把向量 a 和向量 b 相加，那么结果向量的每个坐标都是对应坐标相加得到的（比如 c[0] = a[0] + b[0] ，以此类推）。
在 ML-KEM 中，只存在两种矩阵乘法：矩阵与向量的乘法 \left( \hat{A} \circ \hat{v} \right) ，以及转置向量与向量的乘法 \left( {\hat{v}}^T \circ \hat{v} \right) 。它们看起来可能有些复杂，但实际上都非常简单。（这些符号上面都有帽子，是因为正如在 NTT 部分提到的，我们只在 NTT 域内进行乘法运算。）
我无法比其他在线资源更好地解释矩阵乘法和点积的一般概念，但我将告诉你在我们遇到的两种情况下的具体操作方法。你需要记住的一个规则是，两个矩阵相乘的结果是一个新的矩阵。更具体地说，一个 m \times n 的矩阵与一个 n \times p 的矩阵相乘，得到的结果是一个 m \times p 的矩阵。
矩阵与向量的乘法（ \hat{A} \circ \hat{v} ，也被称作将向量通过矩阵进行变换）是 k \times k \circ k \times 1 = k \times 1 的操作，所以它产生的是一个向量。要进行矩阵与向量的乘法，你需要按矩阵的行逐行进行操作，对于每一行，你将每个元素与对应向量的元素相乘，然后将这些乘积相加。每个结果向量的元素都是矩阵的一行与向量的“点积”（对应元素乘积的和）。
这里有一个例子，其中 k 等于 3，就像在 ML-KEM-768 中一样。
\hat{A} \circ \hat{v} =
\begin{bmatrix}
\hat{a}_{0,0} & \hat{a}_{0,1} & \hat{a}_{0,2} \\
\hat{a}_{1,0} & \hat{a}_{1,1} & \hat{a}_{1,2} \\
\hat{a}_{2,0} & \hat{a}_{2,1} & \hat{a}_{2,2} \\
\end{bmatrix}
\circ
\begin{bmatrix}
\hat{v}_{0} \\
\hat{v}_{1} \\
\hat{v}_{2} \\
\end{bmatrix}
=
\begin{bmatrix}
\hat{a}_{0,0}\hat{v}_{0} + \hat{a}_{0,1}\hat{v}_{1} + \hat{a}_{0,2}\hat{v}_{2} \\
\hat{a}_{1,0}\hat{v}_{0} + \hat{a}_{1,1}\hat{v}_{1} + \hat{a}_{1,2}\hat{v}_{2} \\
\hat{a}_{2,0}\hat{v}_{0} + \hat{a}_{2,1}\hat{v}_{1} + \hat{a}_{2,2}\hat{v}_{2} \\
\end{bmatrix}
当我们将一个向量（记为 \hat{v} ）进行转置后与它自己相乘（即 \hat{v}^T \circ \hat{v} ，这也被称为内积），其结果是一个 1×k 维的矩阵与一个 k×1 维的矩阵相乘，最终得到一个 1×1 的矩阵。实际上，这只不过是说它是一个点积的复杂表达方式，其结果是产生一个“标量”（即一个单独的元素）。你只需要按坐标逐个相乘这些元素，然后将它们全部加在一起。
这里有一个例子，其中 k 还是等于 3。
\hat{u}^T \circ \hat{v} =
\begin{bmatrix}
\hat{u}_0 & \hat{u}_1 & \hat{u}_2 \\
\end{bmatrix}
\circ
\begin{bmatrix}
\hat{v}_{0} \\
\hat{v}_{1} \\
\hat{v}_{2} \\
\end{bmatrix}
=\hat{u}_0\hat{v}_{0} + \hat{u}_1\hat{v}_{1} + \hat{u}_2\hat{v}_{2}
请注意，在实际操作中，你并不会真的去对向量或矩阵进行转置操作。转置向量只在点积的左侧使用，就像上面解释的那样。在K-PKE.Encrypt中，转置矩阵 \hat{A}^T 可以通过在SampleNTT的输入中反转列和矩阵来预先生成（即，在实际转置之前生成）。实际上，在最初的ML-KEM草案中，关于这一点有一个错误，这个错误可能会通过将 \hat{A}^T 表示为 \hat{B} 来解决，这样可以清楚地表明你实际上并没有进行任何转置操作。
就是这样，这些就是你需要实现ML-KEM所需的线性代数知识！如果你已经理解到这里，那么你已经掌握了所需的全部知识。
附录
1.有时候，加密工程师会接受数学训练，你能够从他们的工作中看出这一点，因为他们会使用其他人不会使用的技巧来优化事物，或者他们用Sage软件原型化的速度比我理解它们还要快。有时候，他们也是优秀的工程师，我们因此得到了工程问题的数学解决方案，比如Decaf。
2.如何正确地处理椭圆曲线问题本身就是一个复杂的议题，但它涉及到 fiat-crypto（一种密码学原语）、Montgomery域、完整的公式、素数阶曲线或通过Decaf/Ristretto去除共因子、基于字节的API及其明确定义的解码/编码方式，以及压缩点。这就是如何创建 filippo.io/nistec, filippo.io/edwards25519, 和 gitlab.com/yawning/secp256k1-voi 这些资源的方式。
3.数学训练有素的人会正确地指出，多项式和环元素并不是同一回事，就像整数和有限域元素不是同一回事一样。但在本文中，我们将交替使用多项式和环元素这两个术语。
4.条件减法是指你先从一个数中减去q，如果这个减法操作导致了下溢（即结果为负数），你就把q再加回去。对于减法操作，你先把q加到差值上，然后应用条件减法。
5.关于所有这些内容，Kyber Round 3 submission的“NTT的角色”是一个很好的阅读材料。