实现 KYBER所需的多项式和线性代数知识
原文：https://words.filippo.io/dispatches/kyber-math/↳
译者：Kurt Pan
我曾和一位数学家聊天并试图向他解释椭圆曲线密码学。他最后好像突然懂了，说：“哦，那个呀！书里有一章是关于这些的。你们用这个做出了一个完整的领域？”
是的，在密码学中我们最终只关注一般数学中的一小部分。我认为这挺好，有助于良好的工程，因为我们需要写出非常擅长它们所做之事的计算机程序，领域足够窄让我们能够很好地对之擅长。[^1]
不管怎样，在实现 RSA 和椭圆曲线的这些年里，我们一起学习了很多关于模算术、大有限域和群逻辑的知识。很多年里我们一直搞不定这些，但现在我想我们大多都知道如何把这些做对了。[^2]
只是现在后量子算法即将到来，它们会使用格、矩阵和多项式。那么，你需要了解多少线性代数和多项式代数才能去实现这些后量子密码学原语呢？事实证明，少得惊人！除了名字里出现之外，“格”一词甚至没有出现在标准规范中。
如果你想学习数学，那么这篇文章不适合你。如果你想实现 ML-KEM（FIPS 203，以前称为 Kyber），你马上就可以准备就绪了。
请注意，FIPS 203（草案）的第 2.4 节对所有这些进行了非常清楚和更详细的解释。FIPS 标准实际上在避免形式主义和与工程师交流方面做得很好了。就把这篇当作一个更友好、更务实的总结吧。
多项式
一个多项式是环 中的一个元素 [^3] ，看起来就像这样
但你甚至不需要知道这一点。对于你作为一个实现者而言，ML-KEM 多项式就是一个包括 256 个系数的数组。每一个系数就是一个模的整数，是3329。系数数组是在 中，因为其由256个系数组成，每一个系数在，也就是整数模中。
每个系数都可放在一个 uint16 中，于是你可以写出来多项式的类型，比如 [256]uint16。
要相加或相减两个多项式（环元素），你需要逐系数去做（c[0] = a[0] + b[0]，依此类推）。你永远不会直接在 ML-KEM 中相乘环元素。
模算术
正如我们所说，每个系数都是模3329的整数，虽然可以放到一个uint16中，但你确实需要对其应用正确的常量时间模算术。
你可能习惯了对非常大的模数进行基于limb的模运算。这里是类似的，但更容易，因为域大小只有 12 位。
对于加法和减法，你可以执行经典的条件减法。[^4] 你会发现条件减法对于 ByteDecode_12 也很有用。
乘积用一个uint32够了。然后你可以选择Montgomery或Barrett约简。我发现Barrett更简单，速度也足够快。（注意Barrett 约简的内积是 37 比特，因此你得需要一个 uint64 的中间值。别问我怎么知道的！）你不能使用 % ，因为除法在硬件中并不总是常量时间的。
https://www.nayuki.io/page/barrett-reduction-algorithm
这个域非常小，你可以在不到一秒的时间内完全测试你加法、减法和乘法的实现。去试试。
NTT
ML-KEM 标准中听起来最可怕的部分之一就是数论变换NTT。好消息是，你也不需要理解这一点。
你需要知道的是, 这是表示多项式的一种不同方式。每个多项式（ 的元素）都可以映射到 （NTT 域）的元素且能映射回来。进行映射的函数称为 NTT, 映射回来的函数是逆 NTT（或 NTT）。 的元素称为“NTT 代表元”, 由带有帽子的字母（比如 ）表示, 并且像多项式一样存储：256 个模 整数。
技术上讲, NTT 代表元是一个由 128 个多项式组成的序列, 每个多项式都有两个系数, 但你不需要考虑这一点, 你可以对 和 的元素用相同的数据结构表示, 比如[256] uint16。尽管如此, 在类型系统中为它们分配不同的类型仍然是一个好主意, 这样就不会混淆它们。
如果你之前使用过Montgomery约简和Montgomery域，你已经熟悉将值映射到不同域的概念，在其中某些运算（再次乘法）更快。就像Montgomery域一样，用于表示元素的数据结构在域内和域外是相同的，但它们在语义上具有不同的类型。
你可以实现 NTT 和 NTT，而无需了解它们背后的数学原理。注意NTT 和 NTT 中有一个复杂的术语，称为 zeta。你需要预先计算 128 个可能的zeta值。
NTT 代表元的加减运算与多项式的加减运算相同。但你还是不能混合搭配它们。（如果你有弱类型系统或泛型，你实际上可以使用相同的函数。）
用 NTT 的全部原因是 NTT 域中的乘法更快。事实上， MultiplyNTTs 算法你闭着眼睛都能实现出来。它有一个 项，你需要像 NTT 的 zeta 一样预先计算它。
ML-KEM 的特殊之处在于 NTT 是系统有机的一部分，而不仅仅是一个幕后优化，因为加密和解密密钥直接以其 NTT 表示形式进行序列化和反序列化。[^5]
矩阵和向量
除了系数、多项式和 NTT 代表元之外，你需要处理的其他主要类型就是向量和矩阵。
出于我们的目的, 向量就是 或 的 元素的数组。 为 或 4 , 具体取决于参数集。你可以将向量表示为 [k][256] uint16。向量用粗体小写字母表示, 例如 或 。
向量是 矩阵的特例。矩阵是 rows columns, 因此向量是一个具有 行和一列的矩阵。我们遇到的唯一其他矩阵是 , 是一个 矩阵。我建议将其存储在一个 [k * k][256] uint16 数组中, 而不是一个 [k][k][256] uint16 中，因为后者会导致像 A[column] [row] 这样的索引与向量类型就一样了, 相比于符号 row, column] 是一种退步。
将 NTT 或 ByteEncode 等函数作用在向量或矩阵上只是将其作用于每个元素。
向量加法是逐坐标进行的（ c[0] = a[0] + b[0] 等）。
ML-KEM 中只有两种矩阵乘法: 矩阵乘以向量 和转置向量乘以向量 。它们可能看起来很吓人, 但其实都非常简单。(它们都有帽子, 因为正如 NTT 部分中提到的, 我们只在 NTT 域中进行乘法。)
我不会比其他在线资源更好地解释矩阵乘法和点积的一般概念, 但我会告诉你它在你将遇到的两种情况下是如何工作的。要记住的规则是两个矩阵相乘的结果是另一个矩阵。更具体地说, 矩阵 与矩阵 相乘的结果是维度为 的矩阵。
https://www.mathsisfun.com/algebra/matrix-multiplying.html
矩阵与向量相乘 , 也称为通过矩阵变换向量 是 , 因此会产生一个向量。要做矩阵向量乘法, 你需要在矩阵中逐行进行计算, 对于每一行, 将每个元素乘以相应的向量元素, 然后将所有这些乘积加在一起。每个结果向量元素是向量和一个矩阵行的“点积”（相应乘积的和）。
下面是 的示例, 如 ML-KEM-768 中所示。
向量转置乘以向量 ( , 也称为内积) 是 ,因此在实践中, 这只是一种来表示一个点积的高级说法, 并且它会产生“标量" (单个元素)。你只需将元素逐坐标相乘并将它们全部加在一起即可。
这还是一个 的示例。
请注意, 你实际上从未对内存中的向量或矩阵应用转置。如上所述, 转置向量仅用在点积的左侧, 以及 K-PKE.Encrypt 中的转置矩阵 可以通过转置 中的列和矩阵来生成预转置输入到 SampleNTT。（实际上, 第一版 ML-KEM 草案中存在一个围绕此问题的错误, 该错误可以通过将 表示为 来解决, 这将明确说明你实际上并没有在做任何转置。)
https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/s-C-zIAeKfE/m/eZJmXYsSAQAJ
就是这样，这就是实现 ML-KEM 所需的全部线性代数知识！
[^1]: 也有密码学工程师接受的是数学训练，你会看到这一点，因为他们会使用其他人没有的技巧来优化东西，或者他们会用比我理解的速度更快地在 Sage 中制作原型。有时他们也是优秀的工程师，我们为工程问题提供数学解决方案，例如Decaf。
[^2]: 如何正确处理椭圆曲线可能是它自己的问题，但它也涉及法币-加密货币、Montgomery域、完备公式、素数阶曲线或通过 Decaf/Ristretto 清除协因子、具有明确定义的解码/编码的基于字节的 API 以及压缩点。filippo.io/nistec、filippo.io/edwards25519 和 gitlab.com/yawning/secp256k1-voi 就是这样制作出来的。
[^3]: 受过数学训练的人会反对说多项式和环元素不是同一件事，就像整数和有限域元素是不是一样的。这是对的，但出于本文的目的，我们会互换使用多项式和环元素。.
[^4]: 条件减法是先减去，然后在减法下溢时将其加回来。对于减法，你将 加到差值中，然后应用条件减法。
[^5]: Kyber 第三轮提交的“NTT 的角色”部分是关于这一切的好读物。https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf