# ML-KEM 硬件实现（FIPS 203）

基于 SystemVerilog 的 **ML-KEM**（Module-Lattice-based Key Encapsulation Mechanism，NIST 后量子密码标准，源自 CRYSTALS-Kyber）同步流水线硬件实现。面向 FPGA，使用 Vivado XSIM 仿真验证，全部与 NIST KAT 标准答案逐字节比对。

单一顶层模块 **`mlkem_top`** 在运行时同时支持三种操作与三种安全等级：

| 操作 | `op_i` | FIPS 203 算法 | 输入 | 输出 |
|:---|:---:|:---|:---|:---|
| **密钥生成** KeyGen | `0` | 算法 16 | 种子 `d`, `z` | `ek`（公钥）, `dk`（私钥） |
| **密钥封装** Encaps | `1` | 算法 17 | `ek`, 消息 `m` | 共享密钥 `K`, 密文 `c` |
| **密钥解封装** Decaps | `2` | 算法 18 | `dk`, 密文 `c` | 共享密钥 `K`（含隐式拒绝） |

模块运行于 **100 MHz**（10 ns 周期），低电平异步复位。

---

## 一、概述

ML-KEM 的安全性基于多项式环 **Z_q[x]/(x²⁵⁶+1)** 上的 Module-LWE 难题。固定参数 **q = 3329**（素数模）、**n = 256**（多项式次数）。

### 运行时参数选择

**安全等级 K 通过输入端口 `k_i` 在运行时选择**，而非编译期参数。存储按最坏情况（ML-KEM-1024，KMAX=4）静态分配，`k_i`、`op_i` 在 `start_i` 时被采样到内部寄存器（`k_r`/`op_r`），据此选取激活的子区间与数据通路。

| k_i | 方案 | K | η₁ | η₂ | (d_u, d_v) | ek | dk | 密文 c | 共享密钥 |
|:---:|:---|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| 2 | ML-KEM-512 | 2 | 3 | 2 | (10, 4) | 800 B | 1632 B | 768 B | 32 B |
| 3 | ML-KEM-768 | 3 | 2 | 2 | (10, 4) | 1184 B | 2400 B | 1088 B | 32 B |
| 4 | ML-KEM-1024 | 4 | 2 | 2 | (11, 5) | 1568 B | 3168 B | 1568 B | 32 B |

参考周期数（K=2，hello_world 实测）：KeyGen ≈ 22.9k、Encaps ≈ 32.5k、Decaps ≈ 50.8k 周期。

> 注：`k_i`/`op_i` 仅在 `start_i` 时采样，且假定 `k_i ∈ {2,3,4}`；越界值不做保护。

### 数据约定

所有 256-bit 端口采用 **“byte0 在低位”** 约定：`value[8m +: 8] = byte m`。例如 `d_i[7:0]` 是种子 d 的第 0 字节。

---

## 二、`mlkem_top` 接口

```verilog
module mlkem_top #(parameter KMAX = 4) (   // KMAX 决定存储规模（最坏情况 = 1024）
    input              clk,
    input              rst_n,           // 低电平复位
    input  [2:0]       k_i,             // 运行时方案：2/3/4（start_i 时采样）
    input  [1:0]       op_i,            // 0=KeyGen 1=Encaps 2=Decaps（start_i 时采样）
    input  [255:0]     d_i,             // KeyGen 种子 d
    input  [255:0]     z_i,             // 隐式拒绝种子 z（写入 dk；Decaps 由 dk 解析）
    input  [255:0]     msg_i,           // Encaps 消息 m
    input              start_i,         // 启动脉冲
    output             busy_o,          // 运行中拉高
    output             done_o,          // 完成时拉高（结果就绪）
    output [255:0]     ss_o,            // 共享密钥 K（Encaps/Decaps 在 done_o 时有效）

    // ---- 流式输入端口（start_i 之前在 ST_IDLE 预加载，每拍 1 字节）----
    // Encaps：把 ek（公钥）写入 ek_bram
    input              ek_in_we,
    input  [10:0]      ek_in_addr,      // 0 .. ek_bytes-1
    input  [7:0]       ek_in_byte,
    // Decaps：把 dk（私钥）写入；按字节区间自动路由：
    //   [0, 384K)          -> dk_pke（dkp_bram）  = ŝ 编码
    //   [384K, 768K+32)    -> ek_pke（ek_bram）   = t̂ 编码 ‖ ρ
    //   [768K+32, 768K+64) -> H(ek)（寄存器）
    //   [768K+64, 768K+96) -> z（寄存器）
    input              dk_in_we,
    input  [11:0]      dk_in_addr,      // 0 .. (768K+96)-1
    input  [7:0]       dk_in_byte,
    // Decaps：把密文 c 写入 c_in_bram（与 ct_bram 分开，便于 c'==c 比较）
    input              c_in_we,
    input  [10:0]      c_in_addr,       // 0 .. ct_bytes-1
    input  [7:0]       c_in_byte,

    // ---- 调试 / 结果回读端口（只读抽头，逐字节，免去宽总线）----
    input  [10:0]      dbg_ct_idx_i,  output [7:0]  dbg_ct_o,    // 密文 c（ct_bram）逐字节
    input  [5:0]       dbg_slot_i, input [7:0] dbg_idx_i, output [11:0] dbg_coeff_o, // 系数回读
    input              dbg_byte_sel_i, input [10:0] dbg_byte_idx_i, output [7:0] dbg_byte_o, // ek(0)/dk_pke(1)
    input  [11:0]      dbg_dk_idx_i,  output [7:0]  dbg_dk_o,    // 完整 dk（1632/2400/3168 B）逐字节
    output [255:0]     dbg_rho_o,     // ρ
    output [255:0]     dbg_sigma_o,   // σ
    output [255:0]     dbg_r_o,       // r（G 高半 / Decaps r'）
    output [255:0]     dbg_hek_o,     // H(ek)
    output [255:0]     dbg_mprime_o,  // m'（Decaps 恢复的消息，存于 m_r）
    output [255:0]     dbg_kbar_o,    // K̄ = J(z‖c)（Decaps 拒绝路径密钥）
    output [255:0]     dbg_decz_o,    // 解析出的 z
    output [255:0]     dbg_dech_o     // 解析出的 H(ek)
);
```

### 端口分组说明

- **控制握手**：`start_i` 拉一拍启动；`busy_o` 标志运行；`done_o` 在结果就绪时拉高。
- **结果**：`ss_o` 给出 Encaps/Decaps 的共享密钥；`ek`/`dk`/`c` 经各自 BRAM 通过 `dbg_*` 抽头逐字节读出。
- **流式输入**：`ek_in_*`/`dk_in_*`/`c_in_*` 在 `start_i` 之前于 `ST_IDLE` 把外部数据预加载进对应 BRAM。
- **调试抽头**：`dbg_*` 为只读，供测试平台核对中间量与最终产物，不引出整条数据总线。

---

## 三、微架构

`mlkem_top` 把 ML-KEM 的全部运算分解为若干已独立验证的**叶子算子**，由顶层 FSM 串行驱动；所有多项式与字节产物存放在统一的 **BRAM 存储库**中，算子与存储之间以 valid/ready 握手串接。

### 叶子算子

| 模块 | 功能 | 备注 |
|:---|:---|:---|
| `keccak_core` / `keccak_round` | Keccak-f[1600] 置换 | 单核共享给 G/H/J、SampleNTT、CBD |
| `sha3_top_shared` | SHA3-512 / SHA3-256 / SHAKE-256，单块 + 多块吸收 | 哈希族封装 |
| `sample_ntt_sync_shared` | SampleNTT —— SHAKE-128 拒绝采样生成 Â | 共享 keccak |
| `sample_cbd_sync_shared` | CBD_η 中心二项分布采样（s/e/y/e1/e2） | 共享 keccak |
| `ntt_core` | 前向 / 逆向 NTT（mode 选择） | 蝶形 + ζ ROM |
| `poly_mul_sync` | NTT 域逐点乘（basecase） | 用于 MAC |
| `comp_decomp_sync` | Compress_d / Decompress_d | 封装/解封装压缩 |
| `sd_bram` | 1R/1W 寄存读 SRAM（1 拍读延迟） | 全部存储库基元 |

> **共享 Keccak**：G/H/J、SampleNTT、CBD 三类消费者各自需要 Keccak 置换，但分处互斥的 FSM 阶段，因此共用一个 `keccak_core`，由相位多路选择输入、并对每个消费者门控输出有效信号。

### 存储库

多项式系数（12-bit）分布在三个 BRAM 库中，槽基址在运行时由 `k_r` 推导；字节产物存于另外几个 8-bit BRAM：

| 存储库 | 宽×深 | 用途 |
|:---|:---|:---|
| `bank_a` | 12×4096 | Â[i][j] 矩阵（KeyGen/Encaps），Decaps 中转 ŝ |
| `bank_se` | 12×2048 | ŝ/ê（KeyGen）、ŷ（Encaps）、û（Decaps） |
| `bank_t` | 12×1024 | t̂、累加结果、Encaps 的 v、Decaps 的 w |
| `ek_bram` | 8×2048 | ek（公钥）= byteEncode₁₂(t̂) ‖ ρ |
| `dkp_bram` | 8×2048 | dk_pke = byteEncode₁₂(ŝ) |
| `ct_bram` | 8×2048 | 计算出的密文 c（Encaps）/ c'（Decaps 重加密） |
| `c_in_bram` | 8×2048 | Decaps 输入密文 c（与 ct_bram 分开以便比较） |

槽位布局（相对基址，K 个一组）：`Â` 占 slot 0..K²-1；`slot_s = K²`、`slot_e = K²+K`、`slot_t = K²+2K`。

### 顶层 FSM

一个 5-bit 状态机，三条数据通路（KeyGen / Encaps / Decaps）从 `ST_IDLE` 按 `op_r` 分支：

```
                ┌─ op=0 KeyGen ─►  G → A → C → N → M → E → H ──────────────────────┐
ST_IDLE ─start─►├─ op=1 Encaps ─►  ENC_H → ENC_G → ENC_LOAD → ENC_A → ENC_TDEC     │
                │                   → ENC_C → ENC_N → ENC_U → ENC_C1 → ENC_E2MV    ├─► ST_DONE
                │                   → ENC_V → ENC_C2 ───────────────────────────────┤
                └─ op=2 Decaps ─►  DEC_LOAD → DEC_DECOMP → DEC_SDEC → DEC_NTT       │
                                    → DEC_W → DEC_MENC → DEC_G → DEC_J              │
                                    →（复用 Encaps 重加密 ENC_LOAD..ENC_C2）→ DEC_CMP ┘
```

#### KeyGen（FIPS 203 算法 16）

```
(ρ,σ) = G(d‖K)                                   ST_G   SHA3-512
Â[i][j] = SampleNTT(ρ‖j‖i)                        ST_A   SHAKE-128
s[i]=CBD_η1(PRF(σ,i)), e[i]=CBD_η1(PRF(σ,K+i))   ST_C   SHAKE-256
ŝ[i]=NTT(s[i]), ê[i]=NTT(e[i])                    ST_N
t̂[i]=ê[i]+Σⱼ Â[i][j]∘ŝ[j]                         ST_M   逐点乘+累加
ek = byteEncode₁₂(t̂)‖ρ,  dk_pke=byteEncode₁₂(ŝ)  ST_E
H(ek)                                             ST_H   多块 SHA3-256
dk = dk_pke ‖ ek ‖ H(ek) ‖ z
```

#### Encaps（FIPS 203 算法 17）

```
H(ek), (K,r)=G(m‖H(ek))                          ENC_H, ENC_G   SHA3-256 / SHA3-512
ρ 载入, Â 重生成, t̂=byteDecode₁₂(ek)              ENC_LOAD/A/TDEC
y,e1,e2 = CBD 采样(PRF(r,·)), ŷ=NTT(y)            ENC_C, ENC_N
u = INTT(Σ Âᵀ∘ŷ) + e1                            ENC_U
c1 = byteEncode_du(Compress_du(u))               ENC_C1
v = INTT(Σ t̂∘ŷ) + e2 + Decompress₁(m)            ENC_V
c2 = byteEncode_dv(Compress_dv(v))               ENC_C2
c = c1‖c2,  共享密钥 = K
```

#### Decaps（FIPS 203 算法 18，含 FO 变换与隐式拒绝）

```
u'=Decompress_du(byteDecode(c1)), v'=Decompress_dv(byteDecode(c2))   DEC_DECOMP   D1
ŝ = byteDecode₁₂(dk_pke), û[i]=NTT(u'[i])                            DEC_SDEC/NTT D2
w = v' - INTT(Σⱼ ŝ[j]∘û[j])                                          DEC_W        D3
m' = byteEncode₁(Compress₁(w))                                       DEC_MENC     D4
(K',r')=G(m'‖h),  K̄=J(z‖c)                                          DEC_G/DEC_J  D5
c' = K-PKE.Encrypt(ek_pke, m', r')   ←── 复用整条 Encaps 流水         （重加密）    D6
共享密钥 = (c'==c) ? K' : K̄          ←── 逐字节比较 + 隐式拒绝         DEC_CMP      D7
```

> **设计亮点**：Decaps 的重加密（D6）**直接复用整条 Encaps 流水线**（ENC_LOAD..ENC_C2），不另起数据通路——m' 写入 `m_r`、r' 在 `r_r`、ek_pke 留在 `ek_bram`，前置条件天然就位。D7 逐字节比较 c'（`ct_bram`）与 c（`c_in_bram`），恒定工作量（无早退），按结果在 K'（`ss_r`）与 K̄（`kbar_r`）间选择 `ss_o`。

---

## 四、测试与验证

验证策略：**对全部三种安全等级，把硬件产出与 NIST KAT 标准答案逐字节比对**，分阶段（D0..D7 / E1..E7）验证中间量，再做端到端协议测试。

### 黄金向量

测试向量来自 NIST FIPS 203 的 KAT 响应文件，由 `sync_rtl/top/TB/` 下的 Python 脚本解析为每用例独立的 hex 文件，存于 `sync_rtl/top/TB/vectors/`。Decaps 还包含 `ct_n`/`ss_n`（损坏密文 + 对应拒绝密钥），用于验证隐式拒绝路径。

### 参数化测试平台

| 测试平台 | 操作 | 说明 |
|:---|:---|:---|
| `tb_mlkem_kg_katK_xsim.v` | KeyGen | 逐字节核对 `ek==pk`、`dk==sk` |
| `tb_mlkem_enc_katK_xsim.v` | Encaps | 核对 `ss`、`c` |
| `tb_mlkem_dec_katK_xsim.v` | Decaps | 核对 D0..D7 各阶段；正常密文 `ss==KAT.ss`、损坏密文 `ss==KAT.ss_n` |
| `tb_mlkem_hello_world_xsim.v` | 全流程（单实例） | 端到端演示：KeyGen→Encaps→XOR→Decaps→XOR |
| `tb_mlkem_two_inst_xsim.v` | 全流程（双实例） | 实例 A 做 KeyGen+Encaps，实例 B 做 Decaps |

每个参数化 TB 通过 `xelab -generic_top KP=2|3|4` 选安全等级（驱动到运行时 `k_i`），`+CASE=n` 选用例号。

### 运行测试

统一脚本 `run_tb.sh`（自动 source Vivado 环境并设置 `LD_PRELOAD`）：

```bash
./run_tb.sh top      # KeyGen，全部 K 全部用例
./run_tb.sh enc      # Encaps
./run_tb.sh dec      # Decaps（含拒绝路径）
./run_tb.sh dec 2 0  # 仅 K=2 用例 0

./run_tb.sh hello      # hello_world 端到端（单实例）
./run_tb.sh hello two  # hello_world 端到端（双实例：genenc + dec）
```

`hello_world` 硬件端到端输出：`shared_key=ced0c031a4bee34a...`、`encrypted=a6b5ac5dcb9e9425b9e3b8`、`decrypted="hello world"`，密钥匹配、消息正确还原。

### 验证注意事项

- **干净重跑**：每轮仿真前清理 `xsim.dir`、`.Xil`，避免旧快照污染。
- **`$readmemh` 缺文件只是 WARNING**：文件名拼错时数据读为 X，不会报错，极易造成假 PASS。务必确认日志中无 `cannot be opened` 警告。
- **以日志文件为准**：将每个 `xsim` 调用重定向到独立日志后再 grep `PASS|FAIL|cannot be opened`。

---

## 五、先决条件与兼容性

- **Vivado 2019.2+**（XSIM 仿真）：`/opt/Xilinx/Vivado/2019.2/`
- **Python 3.10+**（向量生成，仅标准库）

Vivado 2019.2 在 Fedora 上经实测的必要 workaround：

```bash
source /opt/Xilinx/Vivado/2019.2/settings64.sh
export LD_PRELOAD=/usr/lib64/libtinfo.so.5   # 必需：ncurses 兼容库
xvlog -sv --relax -i . <file>.v              # -i 指定包含目录；--relax 放宽严格 SV 检查
xelab <top> -s <snap> --timescale 1ns/1ps    # xelab 需显式 --timescale
```

---

## 参考

- [FIPS 203: ML-KEM](https://csrc.nist.gov/pubs/fips/203/final) —— NIST 标准（算法 16/17/18）
- [FIPS 202: SHA-3 / SHAKE](https://csrc.nist.gov/pubs/fips/202/final) —— Keccak 哈希族
- [CRYSTALS-Kyber](https://pq-crystals.org/kyber/) —— 原始提案