4. ML-DSA密钥生成工程实现
ML-DSA（FIPS 204）的密钥生成并不是“随机生成一对大数”那么简单，它是一条由种子驱动的确定性扩展链：从一个 32 字节随机种子 ξ 出发，经 SHAKE256 扩展出 ρ、ρ′、K，再由 ρ 通过 SHAKE128 的拒绝采样生成矩阵 Â，由 ρ′ 采样出短向量 s₁、s₂，最后计算 t = A·s₁ + s₂ 并做编码与序列化。理解这条链的每一步输入、输出与约束，是工程实现正确性的基础。
一、种子扩展：从 ξ 到 ρ、ρ′、K
密钥生成的第一步是获取 32 字节的随机种子 ξ。工程上必须使用密码学安全的随机源（如操作系统 CSPRNG），绝不能使用时间戳、进程号或普通伪随机数。ξ 一旦确定，整个密钥对就完全确定，因此 ξ 的保密性直接决定私钥安全性。
随后执行种子扩展：
(ρ, ρ′, K) ← H(ξ ‖ IntegerToBytes(κ, 2), 128)
其中 H 为 SHAKE256，κ 为密钥生成计数器（通常取 0）
输出 128 字节：ρ 占 32 字节，ρ′ 占 64 字节，K 占 32 字节这里 ρ 用于生成矩阵 Â，ρ′ 用于采样短向量 s₁、s₂，K 用于后续签名阶段的确定性随机化。三者职责分离，是 ML-DSA 设计上的重要特征：即使 ρ 公开（它最终会出现在公钥中），也无法反推 ρ′ 和 K。
二、矩阵 Â 的 SHAKE128 采样
ML-DSA 的矩阵 Â 是 k×ℓ 个多项式，每个多项式系数取自 Z_q（q = 8380417）。矩阵元素并非直接存储，而是由 ρ 通过 SHAKE128 的拒绝采样按需生成，这样公钥只需携带 ρ 即可重建整个矩阵，大幅压缩密钥体积。
对矩阵中位置 (i, j) 的元素，采样过程为：
输入：ρ（32 字节）、i、j
1. 构造种子：ρ ‖ IntegerToBytes(j, 1) ‖ IntegerToBytes(i, 1)
2. 用 SHAKE128 以该种子为输入，持续输出字节流
3. 每 3 字节解析为一个 23 位无符号整数 c
4. 若 c < q，则接受为系数；否则丢弃，继续读取
5. 重复直到收集满 256 个系数拒绝采样意味着输出长度不固定，实现时必须使用可增量读取的 XOF 接口，而不能一次性申请固定长度缓冲区。这是工程实现中最容易出错的地方之一：若错误地截断或补零，生成的矩阵将不符合标准，导致验签失败。
三、s₁ 与 s₂ 短向量生成
s₁ 是长度为 ℓ 的多项式向量，s₂ 是长度为 k 的多项式向量，它们的系数都取自很小的范围 [−η, η]。以 ML-DSA-44 为例，η = 2，系数只有 −2、−1、0、1、2 五种取值。采样同样由 ρ′ 驱动，使用 SHAKE256 的拒绝采样：每次读取若干比特，映射到 [−η, η] 区间，超出范围则丢弃重采。
短向量是 ML-DSA 安全性的核心：s₁、s₂ 的系数越小，攻击者从 t = A·s₁ + s₂ 中恢复 s₁、s₂ 的难度越大（对应 Module-LWE / Module-SIS 困难问题）。因此采样实现必须严格保证系数落在规定范围内，任何越界都会破坏安全性证明的前提。
四、公钥 t 的计算与编码
得到 Â、s₁、s₂ 后，计算 t = ·s₁ + s₂ mod q。这是一个 k×ℓ 矩阵与 ℓ 维向量的多项式乘法，再逐系数模 q 并加上 s₂。工程实现中通常使用 NTT（数论变换）加速多项式乘法，将 O(n²) 的卷积降为 O(n log n)。
计算完成后，t 需要被压缩编码为 t₁：
t₁ = Power2Round(t, d) // d = 13 (ML-DSA-44)
即 t = t₁ · 2^d + t₀，其中 t₀ ∈ [−2^(d−1), 2^(d−1)]
公钥只编码 t₁，t₀ 被丢弃t₁ 的每个系数用 10 比特表示，k 个多项式共 256k 个系数，因此公钥中 t₁ 部分长度为 320k 字节。以 ML-DSA-44（k=4）为例，t₁ 占 1280 字节，加上 ρ 的 32 字节，公钥总长 1312 字节。
五、密钥序列化格式与存储要求
ML-DSA 的密钥序列化格式在 FIPS 204 中有明确规定，实现时必须严格遵循字节序与字段顺序：
| 对象 | 字段组成 | ML-DSA-44 长度 |
|---|---|---|
| 公钥 pk | ρ (32B) ‖ t₁ (320k B) | 1312 字节 |
| 私钥 sk | ρ (32B) ‖ K (32B) ‖ tr (64B) ‖ s₁ (96ℓ B) ‖ s₂ (96k B) | 2560 字节 |
其中 tr 是公钥的哈希（tr = H(pk, 64)），用于签名阶段绑定公钥；s₁、s₂ 的每个系数用 3 比特或 4 比特紧凑编码（取决于 η），因此 ℓ 个多项式占 96ℓ 字节。
最后需要强调：密钥生成过程中的所有中间量（ρ′、K、s₁、s₂、t₀）都属于敏感数据，使用完毕后应及时清零，避免残留在内存中被侧信道或内存转储攻击获取。工程上可使用显式清零函数（如 memset_s 或平台提供的 secure zero）覆盖相关缓冲区。