GiacomoPope/dilithium-py

[](https://github.com/GiacomoPope/dilithium-py/blob/main/LICENSE) [](https://github.com/GiacomoPope/dilithium-py/actions/workflows/ci.yml) [](https://github.com/astral-sh/ruff) # CRYSTALS-Dilithium Python 实现 本代码库包含以下两者的纯 Python 实现： 1. **ML-DSA**：NIST 基于模块格的数字签名标准，基于提交给 NIST 后量子项目的 Dilithium，遵循 [FIPS 204](https://csrc.nist.gov/pubs/fips/204/final)。 2. **CRYSTALS-Dilithium**：遵循（截至撰写时）最新的[规范](https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf)（v3.1）。 **注意**：本项目紧随 [`kyber-py`](https://github.com/GiacomoPope/kyber-py)，后者是 CRYSTALS-Kyber 和 ML-KEM 的纯 Python 实现，并且复用了大量代码。 ## 许可证 本项目采用双重许可，您可以选择 MIT 许可证或 Apache 许可证 2.0。 ## 免责声明 我编写 `dilithium-py` 的目的是为了学习该协议的工作原理，并尝试创建一个清晰、注释丰富的实现，供人们学习。 此代码不是恒定时间（constant time）的，也不是为了性能而编写的。相反，编写它的目的是为了让[规范](https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf)中的伪代码与我们在 `dilithium.py` 和支持文件中使用的代码紧密匹配。 ## 安装 该软件包可在 [PyPI](https://pypi.org/project/dilithium-py/) 上作为 `dilithium-py` 获取： ``` pip install dilithium-py ``` ## 代码库历史 这项工作最初只是为了好玩而实现 Dilithium，但在 NIST 选择 Dilithium 标准化为 ML-DSA 后，该代码库不断发展，现在包含 Dilithium 和 ML-DSA 的实现。我假设随着这个代码库的年代久远，Dilithium 实现将变得不那么有用，而 ML-DSA 将成为重点，但由于历史原因，我们将保留两者。哪怕只是为了人们可以研究 NIST 在协议标准化过程中引入的差异。 ### KATs 此实现通过了 `dilithium` 和 `ml_dsa` 的所有 KAT 向量。有关更多信息，请参阅 [`test_ml_dsa.py`](tests/test_ml_dsa.py) 和 [`test_dilithium.py`](tests/test_dilithium.py) 中的单元测试。 KAT 文件是下载或生成的： 1. 对于 **ML-DSA**，KAT 文件是从 GitHub 代码库 [usnistgov/ACVP-Server/](https://github.com/usnistgov/ACVP-Server/releases/tag/v1.1.0.35) release 1.1.0.35 下载的，并包含在 `assets/ML-DSA-*` 目录中。 2. 对于 **Dilithium**，KAT 文件是从项目的 [GitHub 代码库](https://github.com/pq-crystals/dilithium/)生成的，并包含在 `assets/PQCsignKAT_*.rsp` 中。 ### 为 Dilithium 生成 KAT 文件 此实现基于最新的规范（v3.1）。 当 Dilithium 更新到 3.1 时，提交给 NIST 的 KAT 文件发生了[破坏性更改](https://github.com/pq-crystals/dilithium/commit/e989e691ae3d3f5933d012ab074bdc413ebc6fad)，因此 NIST KAT 文件将与我们的代码不匹配。 为了解决这个问题，我们从 3.1 版本的[参考实现](https://github.com/pq-crystals/dilithium/releases/tag/v3.1)生成了自己的 KAT 文件。这些是 [assets](assets/) 中的文件。 ### 依赖项 最初，与 `kyber-py` 一样，该项目计划零依赖，然而像 `kyber-py` 一样，为了通过 KAT，我需要一个确定性的 CSRNG。参考实现使用 AES256 CTR DRBG。我已经在 [`ase256_ctr_drbg.py`](src/dilithium_py/drbg/ase256_ctr_drbg.py) 中实现了这一点。 但是，我没有实现 AES 本身，而是从 `pycryptodome` 导入它。 要安装依赖项，请运行 `pip install -r requirements.txt`。 如果您愿意使用系统随机性（`os.urandom`），则不需要此依赖项。 #### `xoflib` 还有一个可选的依赖项 [`xoflib`](https://github.com/GiacomoPope/xoflib)，它是一个 Python 包，绑定了许多可扩展输出函数 的 Rust 实现。这个包的创建是受此代码库的启发，因为 Dilithium 需要 `hashlib` 不支持的来自 shake XOF 的流式 API。 可以通过运行 `pip install xoflib` 或通过上述 requirements 安装 `xoflib`。 如果您不希望安装此依赖项，那么我们包含了一个小型 [`shake_wrapper`](src/dilithium_py/shake/shake_wrapper.py) 来模仿 `xoflib`，但由于 `hashlib` 的限制，内存消耗要高得多。 ## 使用 dilithium-py ### ML DSA `ML_DSA` 类上公开了三个旨在使用的函数： - `ML_DSA.keygen()`：生成一个位打包的密钥对 `(pk, sk)` - `ML_DSA.sign(sk, msg)`：根据消息 `msg` 和位打包的私钥 `sk` 生成一个位打包的签名 `sig`。 - `ML_DSA.verify(pk, msg, sig)`：验证位打包的 `sig` 对于给定消息 `msg` 和位打包的公钥 `pk` 是否有效。 要使用 `ML_DSA()`，必须使用协议参数字典对其进行初始化。可以在 [`ml_dsa.py`](src/dilithium_py/ml_dsa/default_parameters.py) 文件中的 `DEFAULT_PARAMETERS` 中看到一个示例。 此外，该类已使用这些默认参数进行了初始化，因此您可以简单地导入想要使用的 NIST 级别： #### 示例 ``` >>> from dilithium_py.ml_dsa import ML_DSA_44 >>> >>> # Example of signing >>> pk, sk = ML_DSA_44.keygen() >>> msg = b"Your message signed by ML_DSA" >>> sig = ML_DSA_44.sign(sk, msg) >>> assert ML_DSA_44.verify(pk, msg, sig) >>> >>> # Verification will fail with the wrong msg or pk >>> assert not ML_DSA_44.verify(pk, b"", sig) >>> pk_new, sk_new = ML_DSA_44.keygen() >>> assert not ML_DSA_44.verify(pk_new, msg, sig) ``` 上面的示例也适用于其他 NIST 级别 `ML_DSA_65` 和 `ML_DSA_87`。 #### Hash ML-DSA 遵循 FIPS 204 的算法 4 和 5，我们还包含了一个预哈希 ML-DSA 版本，该版本在签名前使用 SHA512 对消息进行哈希处理（默认情况下用于所有三个安全级别）。其使用方式与 ML-DSA 大致相同： ``` >>> from dilithium_py.ml_dsa import HASH_ML_DSA_44_WITH_SHA512 >>> >>> # Example of signing >>> pk, sk = HASH_ML_DSA_44_WITH_SHA512.keygen() >>> msg = b"Your message signed by ML_DSA" >>> sig = HASH_ML_DSA_44_WITH_SHA512.sign(sk, msg) >>> assert HASH_ML_DSA_44_WITH_SHA512.verify(pk, msg, sig) >>> >>> # Verification will fail with the wrong msg or pk >>> assert not HASH_ML_DSA_44_WITH_SHA512.verify(pk, b"", sig) >>> pk_new, sk_new = HASH_ML_DSA_44_WITH_SHA512.keygen() >>> assert not HASH_ML_DSA_44_WITH_SHA512.verify(pk_new, msg, sig) ``` 还支持其他哈希函数（目前仅支持 SHA256 和 SHAKE128），但似乎只有使用 SHA512 的预哈希版本才有 OID，因此这是包含的内容。要使用其他哈希函数进行签名，方法是 `HASH_ML_DSA_44_WITH_SHA512._sign_with_pre_hash` 和 `HASH_ML_DSA_44_WITH_SHA512._verify_with_pre_hash`。有关更多信息，请参阅 `hash_ml_dsa.py` 中的实现和注释。 ML-DSA 的预哈希版本被有意添加到 ML-DSA 的子类中，因为这些变体之间生成的签名是不兼容的。 ### 基准测试 一些非常粗略的基准测试，以了解性能： | 1000 次迭代 | `ML_DSA_44` | `ML_DSA_65` | `ML_DSA_87` | |--------------------------|--------------|--------------|--------------| | `KeyGen()` 中位时间 | 6 ms | 10 ms | 14 ms | | `Sign()` 中位时间 | 29 ms | 49 ms | 59 ms | | `Sign()` 平均时间 | 36 ms | 62 ms | 75 ms | | `Verify()` 中位时间 | 8 ms | 11 ms | 17 ms | 所有时间均使用 Intel Core i7-9750H CPU 记录，超过 1000 次调用的平均值。 ### Dilithium `Dilithium` 类上公开了三个旨在使用的函数： - `Dilithium.keygen()`：生成一个位打包的密钥对 `(pk, sk)` - `Dilithium.sign(sk, msg)`：根据消息 `msg` 和位打包的私钥 `sk` 生成一个位打包的签名 `sig`。 - `Dilithium.verify(pk, msg, sig)`：验证位打包的 `sig` 对于给定消息 `msg` 和位打包的公钥 `pk` 是否有效。 要使用 `Dilithium()`，必须使用协议参数字典对其进行初始化。可以在 [`dilithium.py`](src/dilithium_py/dilithium/default_parameters.py) 文件中的 `DEFAULT_PARAMETERS` 中看到一个示例。 此外，该类已使用这些默认参数进行了初始化，因此您可以简单地导入想要使用的 NIST 级别： #### 示例 ``` >>> from dilithium_py.dilithium import Dilithium2 >>> >>> # Example of signing >>> pk, sk = Dilithium2.keygen() >>> msg = b"Your message signed by Dilithium" >>> sig = Dilithium2.sign(sk, msg) >>> assert Dilithium2.verify(pk, msg, sig) >>> >>> # Verification will fail with the wrong msg or pk >>> assert not Dilithium2.verify(pk, b"", sig) >>> pk_new, sk_new = Dilithium2.keygen() >>> assert not Dilithium2.verify(pk_new, msg, sig) ``` 上面的示例也适用于其他 NIST 级别 `Dilithium3` 和 `Dilithium5`。 ### 基准测试 一些非常粗略的基准测试，以了解性能： | 1000 次迭代 | `Dilithium2` | `Dilithium3` | `Dilithium5` | |--------------------------|---------------|--------------|--------------| | `KeyGen()` 中位时间 | 6 ms | 9 ms | 15 ms | | `Sign()` 中位时间 | 27 ms | 46 ms | 58 ms | | `Sign()` 平均时间 | 35 ms | 58 ms | 72 ms | | `Verify()` 中位时间 | 7 ms | 11 ms | 18 ms | 所有时间均使用 Intel Core i7-9750H CPU 记录，超过 1000 次调用的平均值。 ## 实现讨论 ### External Mu 在 FIPS 204 中，签名时可以选择将值 $\mu = H(H(\textsf{pk}) || M')$ 在主签名算法之外计算，然后作为显式输入传递给签名。请注意，$\mu$ 仅由公共数据形成，并允许签名固定大小（哈希）消息（64 字节）而不是任意大小的消息 $M'$。 一个给定 $\mu$ 而不是消息 $m$ 进行签名的 API 被称为 "external mu ML-DSA"，并且由于“纯”ML-DSA 和 external mu ML-DSA 都可以使用相同的方法进行验证，而 Hash-ML-DSA 必然需要单独的验证函数从而导致复杂性，因此它是比 Hash-ML-DSA 更受欢迎的选择。 遵循 [lamps dilithium signature draft](https://datatracker.ietf.org/doc/html/draft-ietf-lamps-dilithium-certificates-07) 的附录 D，我们通过公开两个额外的方法来提供 external mu API。 ``` >>> from dilithium_py.ml_dsa import ML_DSA_44 >>> >>> # Example of signing with external mu >>> pk, sk = ML_DSA_44.keygen() >>> msg = b"Your message signed by ML_DSA" >>> mu = ML_DSA_44.prehash_external_mu(pk, msg) >>> sig = ML_DSA_44.sign_external_mu(sk, mu) >>> assert ML_DSA_44.verify(pk, msg, sig) ``` 方法 `prehash_external_mu(pk, m)` 将公共数据作为输入并计算预哈希 `mu`。然后将其传递给一个新的签名 API，该 API 预期 $\mu$ 而不是消息本身。要验证此签名，我们可以使用常规的验证方法。 ### 优化分解和提示生成 您可能会注意到，ML DSA 的签名时间比上面报告的 Dilithium 时间略慢。这是因为 ML DSA 实现遵循 NIST 规范，而 Dilithium 实现包含分解和提示生成的优化。[Dilithium 规范](https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf)的第 5.1 节中给出了详细信息。 我们在下面非正式地讨论它，并感谢 Keegan Ryan 帮助理解两个提示生成函数之间的差异。 在实现优化时，不仅计算期间使用的向量略有不同，而且提示 $\mathbf{h}$ 系数本身的生成也存在细微差异。 对于 NIST 规范，提示是通过考虑向量 $-c\mathbf{t}_0$ 和 $\mathbf{w} -c\mathbf{s}_1 + -c\mathbf{t}_0$ 生成的，并且 $\mathbf{h}$ 内每个多项式的每个系数都是通过检查当系数 `r` 和 `r + z` 相加时高位是否会发生变化来计算的。这是使用 FIPS 204 中的算法 39 计算的： ``` def make_hint(z, r, a, q): """ Check whether the top bit of z will change when r is added """ r1 = high_bits(r, a, q) v1 = high_bits(r + z, a, q) return int(r1 != v1) ``` 此函数成对地用于两个向量中每个多项式的每个系数：$-c\mathbf{t}_0$ 和 $\mathbf{w} -c\mathbf{s}_1 + -c\mathbf{t}_0$。 对于 Dilithium 优化，与其仅计算 $\mathbf{w}$ 的高位作为 $\mathbf{w}_1$，不如以相同的代价同时计算高位和低位，记为 $\mathbf{w}_1$ 和 $\mathbf{w}_0$。然后，可以从 $\mathbf{w}_0$ 构造提示（并且可以避免在 FIPS 204 算法 7 的第 21 行中进一步调用 $\mathbf{r}_0$ 的低位）。准确地说，提示是从两个向量 $\mathbf{w}_0 -c\mathbf{s}_1 + -c\mathbf{t}_0$ 和 $\mathbf{w}_1$ 生成的。 由于提示生成的输入现在来自分解，其中高位已被移除，因此 `make_hint()` 函数必须检查 `low_bits(r) + z` 的结果中是否设置了高位，这是使用以下函数计算的： ``` def make_hint_optimised(z, r, a, q): """ Optimised version of the above used when the low bits w0 are extracted from `w = (A_hat @ y_hat).from_ntt()` during signing """ gamma2 = a >> 1 if z <= gamma2 or z > (q - gamma2) or (z == (q - gamma2) and r == 0): return 0 return 1 ``` 特别是，当 `z = q-1` 时，`make_hint()` 将返回 `1`，而 `make_hint_optimised()` 返回 `0`。 由于此优化存在于大多数实现中，这引起了关于 `make_hint()` 是否正确的困惑，因为输出与 `make_hint_optimised()` 不同。 重要的是要意识到对于相同的输入向量，这些 make hints 函数的输出是不同的，但在以下情况下，提示向量将是相同的： - `make_hint()` 与 $-c\mathbf{t}_0$ 和 $\mathbf{w} -c\mathbf{s}_1 + -c\mathbf{t}_0$ 一起使用 - `make_hint_optimised()` 与 $\mathbf{w}_0 -c\mathbf{s}_1 + -c\mathbf{t}_0$ 和 $\mathbf{w}_1$ 一起使用 这意味着对于实现，您可以选择 NIST 记录的算法或 Dilithium 5.1 中的优化，生成的签名将是相同的（实际上，您可以使用任一方法并通过所有 KAT 向量。） ### 多项式 文件 [`polynomials.py`](src/dilithium_py/polynomials/polynomials_generic.py) 包含类 `PolynomialRingGeneric` 和 `PolynomialGeneric`。这实现了一元多项式环 $$ R_q = \mathbb{F}_q[X] /(X^n + 1) $$ 该实现受 `SageMath` 启发，您可以通过以下方式创建环 $R_{11} = \mathbb{F}_{11}[X] /(X^8 + 1)$： #### 示例 ``` >>> R = PolynomialRingGeneric(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 ``` ### 模 文件 [`modules.py`](src/dilithium_py/modules/modules_generic.py) 包含类 `ModuleGeneric` 和 `MatrixGeneric`。 模是向量空间的推广，其中标量场被环替换。在 Dilithium 的情况下，我们需要具有上述环 $R_q$ 的模。 `MatrixGeneric` 允许模元素的大小为 $m \times n$ 对于 Dilithium，我们需要长度为 $k$ 和 $l$ 的向量以及大小为 $l \times k$ 的矩阵。 作为我们可以使用 `ModuleGeneric` 执行的操作的示例，让我们回顾上一个示例中的环： #### 示例 ``` >>> R = PolynomialRingGeneric(11, 8) >>> x = R.gen() >>> >>> M = ModuleGeneric(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 matricies 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 coefficents >>> 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] ``` ### 数论变换 我们可以使用 `poly.to_ntt()` 和 `poly.from_ntt()` 将多项式转换为 NTT 形式和从 NTT 形式转换。 当我们在多项式之间执行操作时，`(+, -, *)` 两者必须都处于 NTT 形式或都不处于 NTT 形式。 ``` >>> f = R.random_element() >>> f == f.to_ntt().from_ntt() True >>> g = R.random_element() >>> h = f*g >>> h == (f.to_ntt() * g.to_ntt()).from_ntt() True ``` 在编写此 README 时，在使用 Dilithium 使用的环进行操作时，NTT 形式的多项式乘法大约快 100 倍。 ``` >>> # Lets work in the ring we use for Dilithium >>> R = Dilithium2.R >>> # Generate some random elements >>> f = R.random_element() >>> g = R.random_element() >>> # Takes about 10 seconds to perform 1000 multiplications >>> timeit.timeit("f*g", globals=globals(), number=1000) 9.621509193995735 >>> # Now lets convert to NTT and try again >>> f.to_ntt() >>> g.to_ntt() >>> # Now it only takes ~0.1s to perform 1000 multiplications! >>> timeit.timeit("f*g", globals=globals(), number=1000) 0.12979038299818058 ``` 这些函数扩展到模 ``` >>> M = Dilithium2.M >>> R = Dilithium2.R >>> v = M([R.random_element(), R.random_element()]) >>> u = M([R.random_element(), R.random_element()]).transpose() >>> A = u @ v >>> A == (u.to_ntt() @ v.to_ntt()).from_ntt() True ``` 由于模上的操作只是元素之间的操作，我们预计在 NTT 形式下工作时也有类似的 100 倍加速： ``` >>> u = M([R.random_element(), R.random_element()]).transpose() >>> v = M([R.random_element(), R.random_element()]) >>> timeit.timeit("u@v", globals=globals(), number=1000) 38.39359304799291 >>> u = u.to_ntt() >>> v = v.to_ntt() >>> timeit.timeit("u@v", globals=globals(), number=1000) 0.495470915993792 ```

标签：CRYSTALS-Dilithium, CVE, FIPS 204, Kyber, meg, ML-DSA, ML-KEM, NIST标准化, PQC, Python, 信息安全, 加解密, 后量子密码学, 学术研究, 密码学库, 抗量子计算, 数字签名, 无后门, 格密码学, 算法实现, 纯Python实现, 逆向工具