实现Kyber所需的多项式和线性代数知识 - emmansun/gmsm GitHub Wiki
我曾经和一个数学家交谈，试图向他解释椭圆曲线密码学。最后，他突然明白了，说：“哦，那个啊！我想那本书里有一章是讲这个的。你们竟然在这个领域做出了这么大的成就？”
是的，在密码学中，我们最终关注的只是我们使用的通用数学的一小部分。我认为这是好事，因为这有利于良好的工程实践，因为我们需要编写非常擅长特定任务的计算机程序，而这种专注使得我们能够相当熟练地掌握它。[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的角色”是一个很好的阅读材料。