377 lines
16 KiB
Markdown
Executable File
377 lines
16 KiB
Markdown
Executable File
# ML-KEM 哈希函数实现文档
|
||
|
||
---
|
||
|
||
## 一、整体架构
|
||
|
||
```
|
||
┌──────────────────────────────────────────────────────────────┐
|
||
│ ML-KEM 专用函数层 │
|
||
│ mlkem_G mlkem_H mlkem_J mlkem_PRF(_eta2/_eta3) │
|
||
└──────────────────────────┬───────────────────────────────────┘
|
||
│ 调用
|
||
┌──────────────────────────▼───────────────────────────────────┐
|
||
│ 一次性便捷函数层 │
|
||
│ sha3_256 sha3_512 shake128<N> shake256<N> │
|
||
└──────────────────────────┬───────────────────────────────────┘
|
||
│ 调用
|
||
┌──────────────────────────▼───────────────────────────────────┐
|
||
│ HashGenerator<RATE_BYTES, D_BYTES> │
|
||
│ 海绵构造：process() → finish() → 输出 │
|
||
│ 填充规则：SHA("01"后缀) / SHAKE("1111"后缀) │
|
||
└──────────────────────────┬───────────────────────────────────┘
|
||
│ 底层
|
||
┌──────────────────────────▼───────────────────────────────────┐
|
||
│ KECCAK-p[1600, 24] 置换 │
|
||
│ θ → ρ → π → χ → ι × 24轮 → 状态数组 [[u64;5];5] │
|
||
└──────────────────────────────────────────────────────────────┘
|
||
```
|
||
|
||
---
|
||
|
||
## 二、底层：KECCAK-p[1600, 24] 置换
|
||
|
||
对应 FIPS 202 §3。状态为 5×5×64 位三维数组 `[[u64; 5]; 5]`。
|
||
|
||
### 五步映射（每轮一轮，共 24 轮）
|
||
|
||
| 步映射 | 函数 | 作用 |
|
||
|--------|------|------|
|
||
| **θ** (theta) | `theta(A)` | 列奇偶校验扩散：每列 XOR 相邻两列的奇偶校验值 |
|
||
| **ρ** (rho) | `rho(A)` | 通道旋转：每条通道按固定偏移量循环移位 |
|
||
| **π** (pi) | `pi(A)` | 通道重排：`A[x][y] ← A[(x+3y) mod 5][x]` |
|
||
| **χ** (chi) | `chi(A)` | 非线性变换：`A[x][y] ← A[x][y] ⊕ (¬A[x+1][y] ∧ A[x+2][y])` |
|
||
| **ι** (iota) | `iota(A, ir)` | 轮常数注入：`A[0][0] ⊕= RC[ir]` |
|
||
|
||
### 轮常数 RC[24]（16 进制）
|
||
|
||
| ir | RC[ir] |
|
||
|----|--------|
|
||
| 0 | `0x0000000000000001` |
|
||
| 1 | `0x0000000000008082` |
|
||
| 2 | `0x800000000000808A` |
|
||
| 3 | `0x8000000080008000` |
|
||
| 4 | `0x000000000000808B` |
|
||
| 5 | `0x0000000080000001` |
|
||
| 6 | `0x8000000080008081` |
|
||
| 7 | `0x8000000000008009` |
|
||
| 8 | `0x000000000000008A` |
|
||
| 9 | `0x0000000000000088` |
|
||
| 10 | `0x0000000080008009` |
|
||
| 11 | `0x000000008000000A` |
|
||
| 12 | `0x000000008000808B` |
|
||
| 13 | `0x800000000000008B` |
|
||
| 14 | `0x8000000000008089` |
|
||
| 15 | `0x8000000000008003` |
|
||
| 16 | `0x8000000000008002` |
|
||
| 17 | `0x8000000000000080` |
|
||
| 18 | `0x000000000000800A` |
|
||
| 19 | `0x800000008000000A` |
|
||
| 20 | `0x8000000080008081` |
|
||
| 21 | `0x8000000000008080` |
|
||
| 22 | `0x0000000080000001` |
|
||
| 23 | `0x8000000080008008` |
|
||
|
||
---
|
||
|
||
## 三、海绵构造（Sponge Construction）
|
||
|
||
对应 FIPS 202 §4。
|
||
|
||
```
|
||
吸收阶段 挤压阶段
|
||
┌───┬───┬───┐ ┌───┬───┬───┐
|
||
│P0 │P1 │Pn │ 填充+吸收 │Z0 │Z1 │...│ 输出
|
||
└─┬─┴─┬─┴─┬─┘ └─┬─┴─┬─┴───┘
|
||
│ │ │ ╲ ╱ │
|
||
▼ ▼ ▼ ╲ ╱ ▼
|
||
┌──────────┐ ┌──────────────┐
|
||
│ 状态 1600│◄──►│ 状态 1600 │
|
||
│ (全零) │ f │ │
|
||
└──────────┘ └──────────────┘
|
||
```
|
||
|
||
- **宽度 b** = 1600 位（固定）
|
||
- **速率 r** = 1600 − c（每种哈希不同，见下表）
|
||
- **容量 c** = 2 × 输出长度（SHA-3 固定输出）/ 2 × 安全强度（SHAKE）
|
||
- **核心置换 f** = KECCAK-p[1600, 24]
|
||
|
||
### HashGenerator\<RATE_BYTES, D_BYTES\> 核心方法
|
||
|
||
| 方法 | 说明 |
|
||
|------|------|
|
||
| `new(padding_type)` | 创建哈希器，状态初始化为零 |
|
||
| `process(data)` | 吸收数据，每满 RATE_BYTES 字节执行一次 Keccak-p |
|
||
| `finish()` | 填充最后一组数据，执行 Keccak-p，挤压输出 |
|
||
| `get_hash_bytes()` | 获取结果字节数组引用（需先调用 finish，否则 panic） |
|
||
| `get_hex_string()` | 获取结果十六进制字符串（需先调用 finish，否则 panic） |
|
||
| `compute_bytes(data)` | 便捷一次性方法：process → finish → 返回字节数组 → 清零状态 |
|
||
| `compute_hex_string(data)` | 同上，但返回十六进制字符串 |
|
||
| `clear()` | 清零状态和缓冲区（复用前调用） |
|
||
|
||
---
|
||
|
||
## 四、填充规则与域分离
|
||
|
||
对应 FIPS 202 §5.1（pad10\*1）和 Table 6。
|
||
|
||
两种 `PaddingType` 内含域分离后缀：
|
||
|
||
| PaddingType | 域分离后缀 | 用途 | q=1 时 | q>1 时 |
|
||
|-------------|-----------|------|--------|--------|
|
||
| **SHA** | `01` (2 bit) | SHA3-224/256/384/512 | `0x86` | `0x06 ... 0x80` |
|
||
| **SHAKE** | `1111` (4 bit) | SHAKE128/256 | `0x9F` | `0x1F ... 0x80` |
|
||
|
||
> `q = RATE_BYTES − buffer_pos`，即当前块剩余可填充字节数。
|
||
> 域分离后缀 "01" 和 "1111" 已预计算合并到填充字节中，符合 FIPS 202 Table 6。
|
||
|
||
---
|
||
|
||
## 五、SHA-3 / SHAKE 参数对照表
|
||
|
||
| 函数 | 速率 r (位) | 速率 r (字节) | 容量 c (位) | 输出 d (位/字节) | 填充类型 |
|
||
|------|------------|--------------|------------|-----------------|---------|
|
||
| SHA3-224 | 1152 | 144 | 448 | 224b / 28B | SHA |
|
||
| **SHA3-256** | 1088 | **136** | 512 | 256b / **32B** | SHA |
|
||
| SHA3-384 | 832 | 104 | 768 | 384b / 48B | SHA |
|
||
| **SHA3-512** | 576 | **72** | 1024 | 512b / **64B** | SHA |
|
||
| **SHAKE128** | 1344 | **168** | 256 | 任意 (d) | SHAKE |
|
||
| **SHAKE256** | 1088 | **136** | 512 | 任意 (d) | SHAKE |
|
||
|
||
> 加粗的为 ML-KEM 实际使用的函数。
|
||
|
||
---
|
||
|
||
## 六、工厂函数（构造 HashGenerator 实例）
|
||
|
||
```rust
|
||
// ===== SHA-3 固定输出 =====
|
||
pub fn get_sha3_224() -> HashGenerator<144, 28> // PaddingType::SHA
|
||
pub fn get_sha3_256() -> HashGenerator<136, 32> // ← ML-KEM H 底层
|
||
pub fn get_sha3_384() -> HashGenerator<104, 48>
|
||
pub fn get_sha3_512() -> HashGenerator<72, 64> // ← ML-KEM G 底层
|
||
|
||
// ===== SHAKE 可变输出 =====
|
||
pub fn get_shake_128<const D_BYTES>() -> HashGenerator<168, D_BYTES> // ← SampleNTT 底层
|
||
pub fn get_shake_256<const D_BYTES>() -> HashGenerator<136, D_BYTES> // ← ML-KEM J, PRF 底层
|
||
```
|
||
|
||
---
|
||
|
||
## 七、一次性便捷函数
|
||
|
||
无需手动 `process()` → `finish()` → `get_hash_bytes()`，所有均标记 `#[must_use]`：
|
||
|
||
```rust
|
||
pub fn sha3_256(data: &[u8]) -> [u8; 32]
|
||
|
||
pub fn sha3_512(data: &[u8]) -> [u8; 64]
|
||
|
||
pub fn shake128<const N: usize>(data: &[u8]) -> [u8; N]
|
||
|
||
pub fn shake256<const N: usize>(data: &[u8]) -> [u8; N]
|
||
```
|
||
|
||
---
|
||
|
||
## 八、ML-KEM (FIPS 203) 专用哈希函数
|
||
|
||
### 8.1 函数总览
|
||
|
||
| 函数 | FIPS 203 定义 | 底层实现 | 输入 | 输出 |
|
||
|------|--------------|---------|------|------|
|
||
| **G** | §6.2, §5.1 | `SHA3-512` | 变长字节串 | `([u8; 32], [u8; 32])` |
|
||
| **H** | §6.1 | `SHA3-256` | 变长字节串 | `[u8; 32]` |
|
||
| **J** | §6.3 | `SHAKE256(_, 256)` | 变长字节串 | `[u8; 32]` |
|
||
| **PRF(η=2)** | §4.1 | `SHAKE256(σ ‖ N, 128)` | σ: 32B + nonce: 1B | `[u8; 16]` |
|
||
| **PRF(η=3)** | §4.1 | `SHAKE256(σ ‖ N, 192)` | σ: 32B + nonce: 1B | `[u8; 24]` |
|
||
| **PRF(泛型)** | §4.1 | `SHAKE256(σ ‖ N, η·64)` | σ: 32B + nonce: 1B | `[u8; ETA_BYTES]` |
|
||
|
||
### 8.2 函数签名
|
||
|
||
```rust
|
||
// G: SHA3-512 → 拆分为两个32字节值 (ρ, σ) 或 (K, r)
|
||
#[must_use]
|
||
#[allow(non_snake_case)]
|
||
pub fn mlkem_G(input: &[u8]) -> ([u8; 32], [u8; 32])
|
||
|
||
// H: SHA3-256 → 32字节哈希值
|
||
#[must_use]
|
||
#[allow(non_snake_case)]
|
||
pub fn mlkem_H(input: &[u8]) -> [u8; 32]
|
||
|
||
// J: SHAKE256 → 32字节 (用于隐式拒绝)
|
||
#[must_use]
|
||
#[allow(non_snake_case)]
|
||
pub fn mlkem_J(input: &[u8]) -> [u8; 32]
|
||
|
||
// PRF_η2: SHAKE256(σ || N, 128位=16字节)
|
||
#[must_use]
|
||
#[allow(non_snake_case)]
|
||
pub fn mlkem_PRF_eta2(sigma: &[u8; 32], nonce: u8) -> [u8; 16]
|
||
|
||
// PRF_η3: SHAKE256(σ || N, 192位=24字节)
|
||
#[must_use]
|
||
#[allow(non_snake_case)]
|
||
pub fn mlkem_PRF_eta3(sigma: &[u8; 32], nonce: u8) -> [u8; 24]
|
||
|
||
// PRF 泛型: SHAKE256(σ || N, η·64位=ETA_BYTES字节)
|
||
#[must_use]
|
||
#[allow(non_snake_case)]
|
||
pub fn mlkem_PRF<const ETA_BYTES: usize>(sigma: &[u8; 32], nonce: u8) -> [u8; ETA_BYTES]
|
||
```
|
||
|
||
### 8.3 在 ML-KEM 算法中的具体用途
|
||
|
||
**密钥生成 `K-PKE.KeyGen` (Algorithm 13):**
|
||
|
||
```
|
||
(ρ, σ) ← G(d || k) ← G 输出64字节 → 前32B=ρ、后32B=σ
|
||
Â[i][j] ← SampleNTT(ρ||j||i) ← 均匀分布采样，内部用 SHAKE128
|
||
s[i] ← SamplePolyCBDη1(PRFη1(σ, N)) ← PRF 生成 CBD 采样比特串
|
||
e[i] ← SamplePolyCBDη1(PRFη1(σ, N)) ← PRF 生成 CBD 采样比特串
|
||
```
|
||
|
||
**封装 `ML-KEM.Encaps_internal` (Algorithm 17):**
|
||
|
||
```
|
||
(K, r) ← G(m || H(ek)) ← H 先哈希 ek，再 G 生成共享密钥 K 和随机数 r
|
||
c ← K-PKE.Encrypt(ek, m, r)
|
||
```
|
||
|
||
**解封装 `ML-KEM.Decaps_internal` (Algorithm 18):**
|
||
|
||
```
|
||
(K', r') ← G(m' || h) ← G 生成候选 K' 和随机数 r'
|
||
K̄ ← J(z || c) ← J 用于隐式拒绝时的备选共享密钥
|
||
```
|
||
|
||
**加密 `K-PKE.Encrypt` (Algorithm 14):**
|
||
|
||
```
|
||
Â[i][j] ← SampleNTT(ρ||j||i) ← SHAKE128
|
||
y[i] ← SamplePolyCBDη1(PRFη1(r, N)) ← PRF 生成 CBD 采样比特串
|
||
e1[i] ← SamplePolyCBDη2(PRFη2(r, N)) ← PRF 生成 CBD 采样比特串
|
||
e2 ← SamplePolyCBDη2(PRFη2(r, N)) ← PRF 生成 CBD 采样比特串
|
||
```
|
||
|
||
### 8.4 参数集与 η 值对应
|
||
|
||
| 参数集 | k | η₁ | η₂ | PRF(η₁) 输出 | PRF(η₂) 输出 | 安全强度 |
|
||
|--------|---|----|----|-------------|-------------|---------|
|
||
| ML-KEM-512 | 2 | 3 | 2 | 24 字节 (192b) | 16 字节 (128b) | 128 位 |
|
||
| ML-KEM-768 | 3 | 2 | 2 | 16 字节 (128b) | 16 字节 (128b) | 192 位 |
|
||
| ML-KEM-1024 | 4 | 2 | 2 | 16 字节 (128b) | 16 字节 (128b) | 256 位 |
|
||
|
||
---
|
||
|
||
## 九、当前 sample.rs 中的使用
|
||
|
||
`sample.rs` 实现了 `SampleNTT`（均匀分布采样），对应 FIPS 203 Algorithm 7。
|
||
|
||
**当前使用方式**（手动三步）：
|
||
|
||
```rust
|
||
let mut hasher = get_shake_128::<1024>();
|
||
hasher.process(b.as_bytes());
|
||
hasher.finish();
|
||
let bytes = hasher.get_hash_bytes();
|
||
// 然后从 bytes 中进行拒绝采样...
|
||
```
|
||
|
||
**可升级为一次性调用：**
|
||
|
||
```rust
|
||
let bytes = shake128::<1024>(b.as_bytes());
|
||
// 更简洁，自动完成 process + finish + get_hash_bytes
|
||
```
|
||
|
||
---
|
||
|
||
## 十、公开接口汇总
|
||
|
||
```rust
|
||
// === 类型 ===
|
||
pub type State = [[u64; 5]; 5]; // 1600位状态数组
|
||
pub enum PaddingType { SHA, SHAKE } // 填充类型（含域分离后缀）
|
||
pub struct HashGenerator<RATE_BYTES, D_BYTES> { .. }
|
||
|
||
// === 核心方法 (HashGenerator) ===
|
||
impl HashGenerator<RATE_BYTES, D_BYTES> {
|
||
pub fn new(padding_type: PaddingType) -> Self
|
||
pub fn clear(&mut self)
|
||
pub fn process(&mut self, data: &[u8])
|
||
pub fn finish(&mut self)
|
||
pub fn get_hash_bytes(&self) -> &[u8; D_BYTES] // 注意：未 finish 会 panic
|
||
pub fn get_hex_string(&self) -> String // 注意：未 finish 会 panic
|
||
pub fn compute_hex_string(&mut self, data: &[u8]) -> String
|
||
pub fn compute_bytes(&mut self, data: &[u8]) -> [u8; D_BYTES] // 新增
|
||
}
|
||
|
||
// === 工厂函数 ===
|
||
pub fn get_sha3_224() -> HashGenerator<144, 28>
|
||
pub fn get_sha3_256() -> HashGenerator<136, 32>
|
||
pub fn get_sha3_384() -> HashGenerator<104, 48>
|
||
pub fn get_sha3_512() -> HashGenerator<72, 64>
|
||
pub fn get_shake_128<const D: usize>() -> HashGenerator<168, D>
|
||
pub fn get_shake_256<const D: usize>() -> HashGenerator<136, D>
|
||
|
||
// === 一次性便捷函数 (新增) ===
|
||
pub fn sha3_256(data: &[u8]) -> [u8; 32] // #[must_use]
|
||
pub fn sha3_512(data: &[u8]) -> [u8; 64] // #[must_use]
|
||
pub fn shake128<const N: usize>(data: &[u8]) -> [u8; N] // #[must_use]
|
||
pub fn shake256<const N: usize>(data: &[u8]) -> [u8; N] // #[must_use]
|
||
|
||
// === ML-KEM (FIPS 203) 专用函数 (新增) ===
|
||
pub fn mlkem_G (input: &[u8]) -> ([u8; 32], [u8; 32]) // #[must_use]
|
||
pub fn mlkem_H (input: &[u8]) -> [u8; 32] // #[must_use]
|
||
pub fn mlkem_J (input: &[u8]) -> [u8; 32] // #[must_use]
|
||
pub fn mlkem_PRF_eta2 (sigma: &[u8; 32], nonce: u8) -> [u8; 16] // #[must_use]
|
||
pub fn mlkem_PRF_eta3 (sigma: &[u8; 32], nonce: u8) -> [u8; 24] // #[must_use]
|
||
pub fn mlkem_PRF<const ETA_BYTES: usize> (sigma: &[u8; 32], nonce: u8) -> [u8; ETA_BYTES]
|
||
```
|
||
|
||
---
|
||
|
||
## 十一、测试覆盖
|
||
|
||
共 35 项测试全部通过（`cargo test` 0 警告 0 失败）：
|
||
|
||
| 分类 | 测试数 | 覆盖内容 |
|
||
|------|--------|---------|
|
||
| 标准 SHA-3 向量 | 3 | SHA3-256 空串/"abc"、SHA3-512 空串 |
|
||
| SHAKE 标准向量 | 1 | SHAKE128 空串 → 32 字节 |
|
||
| 多次 process | 1 | `process("ab") + process("c") == process("abc")` |
|
||
| compute_bytes | 1 | 验证 `compute_bytes` 返回值 |
|
||
| 一次性函数正确性 | 5 | sha3_256/512、shake128/256 与手动方式对比 |
|
||
| ML-KEM G | 3 | 输出拆分正确性、确定性、不同输入不同输出 |
|
||
| ML-KEM H | 2 | 等于 sha3_256、确定性 |
|
||
| ML-KEM J | 2 | 输出 32 字节、确定性 |
|
||
| ML-KEM PRF | 5 | 输出尺寸、不同 nonce 产生不同输出、泛型一致性、确定性 |
|
||
| 边界情况 | 2 | 空输入、4096 字节大输入 |
|
||
|
||
运行方式：
|
||
```sh
|
||
cargo test # 运行全部 35 项测试
|
||
cargo test sha3 # 仅运行哈希模块测试
|
||
cargo build # 编译（0 警告）
|
||
```
|
||
|
||
---
|
||
|
||
## 十二、关键设计说明
|
||
|
||
1. **域分离（Domain Separation）**：SHA-3 在消息后自动追加 2 位 `01`，SHAKE 追加 4 位 `1111`。此操作已在 `PaddingType` 的填充字节中预计算合并（`0x86`/`0x06...0x80` 对应 SHA，`0x9F`/`0x1F...0x80` 对应 SHAKE），符合 FIPS 202 Table 6。无需调用方手动追加。
|
||
|
||
2. **速率与容量**：`c = 2d`（SHA-3 定长输出）或 `c = 2 × 安全强度`（SHAKE），确保 `r = 1600 − c`。
|
||
|
||
3. **`#[must_use]`**：所有公开哈希函数均标记此属性，防止调用方意外丢弃哈希输出。
|
||
|
||
4. **`#[allow(non_snake_case)]`**：G/H/J/PRF 命名保持与 FIPS 203 规范一致，便于代码审查时对照规范。
|
||
|
||
5. **`clear()` 安全性**：清零所有状态数组（`a`）、缓冲区（`buffer`）和哈希输出（`hash`），防止哈希器复用时残留敏感数据。
|
||
|
||
6. **panic 行为**：`get_hash_bytes()` 和 `get_hex_string()` 在 `finish()` 未调用时 panic。一次性函数（`compute_bytes`、`sha3_256` 等）内部保证先调用 `finish()`，因此不会 panic。
|
||
|
||
7. **const 泛型**：利用 Rust const generics 在编译期确定速率和输出长度，避免运行时开销。例如 `HashGenerator<136, 32>` 的 136 字节缓冲区和 32 字节输出均在栈上分配。
|