GiacomoPope/kyber-py

[](https://github.com/GiacomoPope/kyber-py/blob/main/LICENSE) [](https://github.com/GiacomoPope/kyber-py/actions/workflows/ci.yml) [](https://kyber-py.readthedocs.io/en/latest/?badge=latest) [](https://coveralls.io/github/GiacomoPope/kyber-py?branch=main) # ML-KEM / CRYSTALS-Kyber Python 实现 本仓库包含以下两者的纯 Python 实现： 1. **ML-KEM**：NIST 模格基密钥封装机制，遵循 [FIPS 203](https://csrc.nist.gov/pubs/fips/203/final) 标准，源自 NIST 后量子密码学项目。 2. **CRYSTALS-Kyber**：遵循（截至撰写时）最新的 [规范](https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf) (v3.02)。 **注意**：本项目伴随 [`dilithium-py`](https://github.com/GiacomoPope/dilithium-py)，后者是 ML-DSA 和 CRYSTALS-Dilithium 的纯 Python 实现，并共享了本实现中的许多底层代码。 ## 许可证 本项目采用双许可，您可以选择 MIT 许可证或 Apache 许可证 2.0。 ## 免责声明 `kyber-py` 是作为教育工具编写的。本项目的目的是了解 Kyber 的工作原理，并尝试创建一个干净、注释良好的实现，供人们学习。 此代码不是恒定时间的，也不是为了性能而编写的。相反，编写它的目的是让 Python 代码紧密遵循 Kyber [规范](https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf) 和 [FIPS 203](https://csrc.nist.gov/pubs/fips/203/final)。对此工作不作任何密码学保证。 ## 安装 此包可在 [PyPI](https://pypi.org/project/kyber-py/) 上作为 `kyber-py` 获取： ``` pip install kyber-py ``` ## 仓库历史 这项工作最初只是为了好玩而实现 Kyber，然而在 NIST 选择 Kyber 标准化为 ML-KEM 后，仓库不断发展，现在包含了 Kyber 和 ML-KEM 的实现。我假设随着这个仓库的老化，Kyber 的实现将变得不那么有用，而 ML-KEM 将成为重点，但出于历史原因，我们将同时包含两者。哪怕只是为了让人们可以研究 NIST 在协议标准化过程中引入的差异。 ### KAT 此实现目前通过了 `kyber` 和 `ml_kem` 的所有 KAT 测试。有关更多信息，请参阅 [`test_kyber.py`](tests/test_kyber.py) 和 [`test_ml_kem.py`](tests/test_ml_kem.py) 中的单元测试。 KAT 文件是下载或生成的： 1. 对于 **ML-KEM**，KAT 文件下载自 GitHub 仓库 [usnistgov/ACVP-Server/](https://github.com/usnistgov/ACVP-Server/releases/tag/v1.1.0.35) release 1.1.0.35，并包含在 `assets/ML-KEM-*` 目录中。 2. 对于 **Kyber**，KAT 文件是从项目 [GitHub 仓库](https://github.com/pq-crystals/kyber/) 生成的，并包含在 `assets/PQCLkemKAT_*.rsp` 中。 **注意**：对于 Kyber v3.02，规范和参考实现之间存在差异。为了确保所有 KAT 通过，必须在 [规范](https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf) (v3.02) 的算法 7 中的随机字节 $z = \mathcal{B}^{32}$ **之前** 生成公钥。 ### 依赖 最初该项目计划零依赖，然而为了使此工作通过 KAT，我们需要一个确定性的 CSRNG。参考实现使用 AES256 CTR DRBG。我已经在 [`aes256_ctr_drbg.py`](src/kyber_py/drbg/aes256_ctr_drbg.py) 中实现了这一点。 然而，我并没有实现 AES 本身，而是从 `pycryptodome` 导入。如果这个依赖太烦人，请提出 issue，我们可以将纯 Python AES 包含到仓库中。 要安装依赖，请运行 `pip -r install requirements`。 支持将密钥读取和写入 PKCS 格式需要 python-ecdsa 包。可以使用 `pip install ecdsa` 安装，或者通过使用 `pip install 'kyber-py[pkcs]'` 命令安装此包。 ## 使用 kyber-py ### ML-KEM `ML_KEM` 类上公开了四个旨在使用的函数： - `ML_KEM.keygen()`：生成密钥对 `(ek, dk)` - `ML_KEM.key_derive(seed)`：从提供的种子生成密钥对 `(ek, dk)` - `ML_KEM.encaps(ek)`：生成密钥和密文对 `(key, ct)` - `ML_KEM.decaps(dk, ct)`：生成共享密钥 `key` 此外，在 `ml_kem.pkcs` 模块中还有一些用于读取和写入这两种密钥的方法： - `ek_to_der`：用于将封装密钥序列化为 DER 字节字符串 - `ek_to_pem`：用于将封装密钥序列化为 PEM 字符串 - `ek_from_der`：用于从 DER 编码中提取封装密钥 - `ek_from_pem`：用于从 PEM 编码中提取封装密钥 - `dk_to_der`：用于将解封密钥序列化为 DER 字节字符串 - `dk_to_pem`：用于将解封密钥序列化为 PEM 字符串 - `dk_from_der`：用于从 DER 编码中提取解封密钥 - `dk_from_pem`：用于从 PEM 编码中提取解封密钥 这些，连同 `ML_KEM_512`、`ML_KEM_768` 和 `ML_KEM_1024` 对象，构成了 kyber-py 库的稳定 API。 #### 示例 ``` >>> from kyber_py.ml_kem import ML_KEM_512 >>> ek, dk = ML_KEM_512.keygen() >>> key, ct = ML_KEM_512.encaps(ek) >>> _key = ML_KEM_512.decaps(dk, ct) >>> assert key == _key ``` 上述示例也适用于 `ML_KEM_768` 和 `ML_KEM_1024`。 #### 基准测试 | Params | keygen | keygen/s | encap | encap/s | decap | decap/s | |------------|---------:|-----------:|--------:|----------:|--------:|--------:| | ML-KEM-512 | 1.96ms | 511.30 | 2.92ms | 342.26 | 4.20ms | 237.91 | | ML-KEM-768 | 3.31ms | 302.51 | 4.48ms | 223.04 | 6.14ms | 162.86 | | ML-KEM-1024| 5.02ms | 199.07 | 6.41ms | 155.89 | 8.47ms | 118.01 | 所有时间均使用 Intel Core i7-9750H CPU 记录，并在 1000 次运行中取平均值。 ### Kyber `Kyber` 类上公开了三个旨在使用的函数： - `Kyber.keygen()`：生成密钥对 `(pk, sk)` - `Kyber.encaps(pk)`：生成共享密钥和挑战 `(key, c)` - `Kyber.decaps(sk, c)`：生成共享密钥 `key` #### 示例 ``` >>> from kyber_py.kyber import Kyber512 >>> pk, sk = Kyber512.keygen() >>> key, c = Kyber512.encaps(pk) >>> _key = Kyber512.decaps(sk, c) >>> assert key == _key ``` 上述示例也适用于 `Kyber768` 和 `Kyber1024`。 我们期望用户选择使用 Kyber 规范默认参数的三个初始化类之一。这三个选项是 `Kyber512`、`Kyber768` 和 `Kyber1024`。但是，通过遵循 `DEFAULT_PARAMETERS` 中的值，可以调整这些值以查看 Kyber 在不同默认值下的行为。 **注意**：从 Kyber 规范中更改参数 $k$、$\eta_1$、$\eta_2$ $d_u$ 和 $d_v$ 相对容易。但是，如果您希望更改多项式环本身，那么您将失去对 NTT 变换的访问权限，目前仅支持 $q = 3329$ 和 $n = 256$。 #### 基准测试 | Params | keygen | keygen/s | encap | encap/s | decap | decap/s | |------------|---------:|-----------:|--------:|----------:|--------:|--------:| | Kyber512 | 2.02ms | 493.99 | 2.84ms | 352.53 | 4.12ms | 242.82 | | Kyber768 | 3.40ms | 294.13 | 4.38ms | 228.41 | 6.06ms | 165.13 | | Kyber1024 | 5.09ms | 196.61 | 6.22ms | 160.72 | 8.29ms | 120.68 | 所有时间均使用 Intel Core i7-9750H CPU 记录，并在 1000 次运行中取平均值。 ## 文档 - https://kyber-py.readthedocs.io/en/latest/ ## 多项式和模 在实现 Kyber/ML-KEM 时，主要需要考虑两件事。第一件事是数学，它需要在环 $R_q = \mathbb{F}\_q[X] /(X^n + 1)$ 中的元素的模中执行线性代数，第二件事是采样、压缩和解压缩，这与协议的密码学保证有关。 对于不了解的人来说，模是向量空间的推广，其中矩阵的元素不是从域（例如有理数，或有限域 $\mathbb{F}\_{p^k}$ 的元素）中选择，而是在环中（我们不要求环中的每个元素都有乘法逆）。Kyber/ML-KEM 相关的环是一个多项式环，其中多项式的系数在 $\mathbb{F}\_{q}$ 中，且 $q = 3329$，多项式环具有模 $X^n + 1$，其中 $n = 256$（因此多项式环的每个元素最多有 256 个系数）。 ### 多项式 为了帮助尝试这些多项式环本身，文件 [`polynomials_generic.py`](src/kyber_py/polynomials/polynomials_generic.py) 包含单变量多项式环的实现 $$ R_q = \mathbb{F}_q[X] /(X^n + 1) $$ 其中用户可以选择任何 $q, n$。例如，您可以通过以下方式创建环 $R_{11} = \mathbb{F}_{11}[X] /(X^8 + 1)$： #### 示例 ``` >>> from kyber_py.polynomials.polynomials_generic import GenericPolynomialRing >>> R = GenericPolynomialRing(11, 8) >>> x = R.gen() >>> f = 3*x**3 + 4*x**7 >>> g = R.random_element(); g 5 + x^2 + 5*x^3 + 4*x^4 + x^5 + 3*x^6 + 8*x^7 >>> f*g 8 + 9*x + 10*x^3 + 7*x^4 + 2*x^5 + 5*x^6 + 10*x^7 >>> f + f 6*x^3 + 8*x^7 >>> g - g 0 ``` 我们希望这允许在开始使用整个 Kyber/ML-KEM 之前获得一些使用这些多项式的实践经验。 对于实现协议本身所需的“Kyber 特定”函数，我们创建了一个子类 `PolynomialRing(GenericPolynomialRing)`，它具有以下附加方法： - `PolynomialRing` - `ntt_sample(bytes)` 接受 $3n$ 个字节并生成 $R_q$ 中的随机多项式 - `decode(bytes, l)` 接受 $\ell n$ 位并生成 $R_q$ 中的多项式 - `cbd(beta, eta)` 接受 $\eta \cdot n / 4$ 个字节并生成 $R_q$ 中的多项式，其系数取自中心二项分布 - `Polynomial` - `encode(l)` 接受多项式并返回长度为 $\ell n / 8$ 的字节数组 - `to_ntt()` 将多项式转换为 NTT 域以进行高效多项式乘法，并返回 `PolynomialNTT` 类型的元素 - `PolynomialNTT` - `from_ntt()` 将多项式从 NTT 域转换回来，并返回 `Polynomial` 类型的元素 此类固定 $q = 3329$ 和 $n = 256$ 最后，我们根据 [规范](https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf) 第 2 页为多项式定义了 `self.compress(d)` 和 `self.decompress(d)` 方法 $$ \textsf{compress}_q(x, d) = \lceil (2^d / q) \cdot x \rfloor \textrm{mod}^+ 2^d, $$ $$ \textsf{decompress}_q(x, d) = \lceil (q / 2^d) \cdot x \rfloor. $$ 函数 `compress` 和 `decompress` 是为多项式的系数定义的，多项式的（解）压缩是通过作用于每个系数来实现的。类似地，模元素的（解）压缩是通过作用于每个多项式来实现的。 **注意**：压缩是有损的！我们无法通过计算 `f.compress(d).decompress(d)` 得到相同的多项式。然而，它们很*接近*。有关更多信息，请参阅规范。 ### 模 在 `polynomials_generic.py` 的基础上，我们还包含了一个文件 [`modules_generic.py`](src/kyber_py/modules/modules_generic.py)，其中包含给定环执行线性代数所需的所有函数。 请注意，`GenericMatrix` 允许模元素的尺寸为 $m \times n$，但对于 Kyber，我们只需要长度为 $k$ 的量和尺寸为 $k \times k$ 的方阵。 作为我们可以使用 `GenericModule` 执行的操作的示例，让我们重温上一个示例中的环： #### 示例 ``` >>> R = GenericPolynomialRing(11, 8) >>> x = R.gen() >>> >>> M = GenericModule(R) >>> # We create a matrix by feeding the coefficients to M >>> A = M([[x + 3*x**2, 4 + 3*x**7], [3*x**3 + 9*x**7, x**4]]) >>> A [ x + 3*x^2, 4 + 3*x^7] [3*x^3 + 9*x^7, x^4] >>> # We can add and subtract matrices of the same size >>> A + A [ 2*x + 6*x^2, 8 + 6*x^7] [6*x^3 + 7*x^7, 2*x^4] >>> A - A [0, 0] [0, 0] >>> # A vector can be constructed by a list of coefficients >>> v = M([3*x**5, x]) >>> v [3*x^5, x] >>> # We can compute the transpose >>> v.transpose() [3*x^5] [ x] >>> v + v [6*x^5, 2*x] >>> # We can also compute the transpose in place >>> v.transpose_self() [3*x^5] [ x] >>> v + v [6*x^5] [ 2*x] >>> # Matrix multiplication follows python standards and is denoted by @ >>> A @ v [8 + 4*x + 3*x^6 + 9*x^7] [ 2 + 6*x^4 + x^5] ``` 在此类之上，我们有类 `Module(GenericModule)` 和 `Matrix(GenericMatrix)`，它们具有辅助函数，（例如）编码矩阵的每个元素，或将每个元素转换为 NTT 域或从 NTT 域转换。 这些简单的函数为每个元素调用相应的 `Polynomial` 方法。

标签：CRYSTALS-Kyber, FIPS 203, KEM, Kyber, ML-KEM, NIST标准化, PQC, Python安全工具, 加密算法, 后量子密码学, 密码学库, 密钥封装机制, 抗量子计算, 教育工具, 格密码学, 纯Python实现, 逆向工具, 零依赖