# ML-KEM 硬件 IP 设计报告

> 模块:`mlkem_top`（FIPS 203 ML-KEM 全功能加速器）
> 器件:Xilinx Artix-7 `xc7a200tfbg676-1`
> 工具:Vivado 2019.2（综合）+ XSIM（功能仿真）
> 日期:2026-06

---

## 1. 概述

### 1.1 设计目标

本 IP 实现 NIST FIPS 203 标准化的后量子密钥封装机制 **ML-KEM**（源自 CRYSTALS-Kyber），
在单一硬件模块 `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`（含隐式拒绝） |

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

固定参数:模数 **q = 3329**、多项式次数 **n = 256**、共享密钥 32 B。

### 1.2 关键特性

- **运行时可重构**:`k_i`/`op_i` 在 `start_i` 时锁存，存储按最坏情况（ML-KEM-1024）静态分配，
  无需为不同等级重新综合。
- **资源高度复用**:同一套叶子算子与存储库被三条数据通路分时复用;Decaps 的重加密
  （FO 变换核心）直接复用整条 Encaps 流水线。
- **共享 Keccak 核**:G/H/J、SampleNTT、CBD 三类哈希消费者分时共用单个 `keccak_core`。
- **逐字节流式 I/O**:`ek/dk/c` 经 BRAM 端口逐字节装载与回读，避免超宽顶层总线。
- **常量时间隐式拒绝**:Decaps 比较 `c'==c` 全程恒定工作量，无早退分支。
- **完整 KAT 验证**:三种等级、三种操作全部对 NIST KAT 标准答案逐字节比对通过。

### 1.3 代码规模

| 项 | 行数 |
|:---|:---:|
| `mlkem_top.v`（顶层集成 + FSM + 数据通路） | 2252 |
| RTL 合计（不含测试平台） | 5517 |

---

## 2. 顶层接口

```verilog
module mlkem_top #(parameter KMAX = 4) (
    input              clk, rst_n,        // 100 MHz 设计时钟, 低电平异步复位
    input  [2:0]       k_i,              // 运行时等级 2/3/4 (start_i 锁存)
    input  [1:0]       op_i,             // 0=KeyGen 1=Encaps 2=Decaps
    input  [255:0]     d_i, z_i, msg_i,  // 种子 d/z, Encaps 消息 m
    input              start_i,
    output             busy_o, done_o,
    output [255:0]     ss_o,             // 共享密钥 K

    input              ek_in_we;  input [10:0] ek_in_addr;  input [7:0] ek_in_byte; // Encaps ek 装载
    input              dk_in_we;  input [11:0] dk_in_addr;  input [7:0] dk_in_byte; // Decaps dk 装载
    input              c_in_we;   input [10:0] c_in_addr;   input [7:0] c_in_byte;  // Decaps c 装载

    // 调试 / 结果回读抽头(只读)
    input  [10:0] dbg_ct_idx_i;  output [7:0]  dbg_ct_o;      // 密文 c
    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/dk_pke
    input  [11:0] dbg_dk_idx_i;  output [7:0]  dbg_dk_o;      // 完整 dk
    output [255:0] dbg_rho_o, dbg_sigma_o, dbg_r_o, dbg_hek_o,
                   dbg_mprime_o, dbg_kbar_o, dbg_decz_o, dbg_dech_o
);
```

**握手时序**:外部先经流式端口预装载所需数据（Encaps→ek，Decaps→dk+c），
`start_i` 拉一拍锁存 `k_i/op_i` 并启动;`busy_o` 在 `st≠IDLE` 期间为高;
`done_o` 在 `st==DONE` 拉高，此时 `ss_o` 及各 BRAM 产物有效。

数据约定:所有 256-bit 端口为「byte0 在低位」，即 `value[8m+:8] = byte m`。

---

## 3. 微架构

### 3.1 总体结构

`mlkem_top` 采用「**单 FSM 调度 + 共享叶子算子 + 统一存储库**」架构。顶层 RTL 结构见
`docs/mlkem_top_rtl.svg`。数据流分为四层:

```
输入端口 ──► 控制 FSM / 状态寄存器 ──► 叶子算子(共享 keccak + 算术引擎) ◄──► 存储库 ──► 输出/回读
```

### 3.2 叶子算子

| 实例 | 模块 | 功能 |
|:---|:---|:---|
| `u_keccak` | `keccak_core` | Keccak-f[1600] 置换（单核，三方共享） |
| `u_sha3` | `sha3_top_shared` | SHA3-512 (G) / SHA3-256 (H) / SHAKE-256 (J)，单/多块吸收 |
| `u_snt` | `sample_ntt_sync_shared` | SampleNTT（SHAKE-128 拒绝采样）生成 Â |
| `u_cbd` | `sample_cbd_sync_shared` | CBD_η 中心二项分布采样（s/e/y/e1/e2） |
| `u_ntt` | `ntt_core` | 前向 NTT / 逆向 NTT（mode 选择，×3303 尾乘） |
| `u_pmul` | `poly_mul_sync` | NTT 域逐点乘（basecase，含 Barrett 模乘） |
| `u_comp` | `comp_decomp_sync` | Compress_d / Decompress_d（Barrett 除法约简） |

模加、byteEncode₁₂/byteDecode₁₂、bit-packer/解包、`c'==c` 比较等轻量逻辑在顶层内联实现。

### 3.3 共享 Keccak 核

G/H/J、SampleNTT、CBD 都需要 Keccak 置换，但分处互斥的 FSM 阶段，故共用单个 `u_keccak`:

- **输入复用**:`kc_state_i_mux` / `kc_valid_i_mux` 按相位三选一
  （`sel_snt` / `sel_cbd` / 默认 SHA3）。
- **输出门控**:核输出 `kc_state_o` / `kc_valid_o` 广播给所有消费者，但只有当前激活方看到有效信号
  （`kc_valid_o_sha3` / `_snt` / `_cbd`）。
- 相位选择由 FSM 状态推导:`sel_sha3 = (st∈{G,H,J,…})`、`sel_snt = (st∈{A,ENC_A})`、
  `sel_cbd = (st∈{C,ENC_C})`。

此设计省去 Keccak 核的多份例化（Keccak-f 是面积大户），是 LUT 占用仅 25% 的主要原因之一。

### 3.4 存储库

| 实例 | 宽×深 | 用途 | 读写信号 |
|:---|:---|:---|:---|
| `u_bank_a` | 12×4096 | Â[i][j] 矩阵；Decaps 中转 ŝ/e2/v' | `ba_rd_*` / `ba_we/wa/wd` |
| `u_bank_se` | 12×2048 | ŝ/ê (KeyGen)·ŷ (Encaps)·û (Decaps) | `bse_rd_*` / `bse_we/wa/wd` |
| `u_bank_t` | 12×1024 | t̂·累加和·Encaps v·Decaps w | `bt_rd_*` / `bt_we/wa/wd` |
| `u_ek_bram` | 8×2048 | ek = byteEncode₁₂(t̂)‖ρ | — |
| `u_dkp_bram` | 8×2048 | dk_pke = byteEncode₁₂(ŝ) | — |
| `u_ct_bram` | 8×2048 | 计算出的密文 c / Decaps c' | — |
| `u_c_in_bram` | 8×2048 | Decaps 输入密文 c（与 ct 分开以便比较） | — |

全部基于 `sd_bram`（1R/1W、寄存读、1 拍读延迟，综合映射为块 RAM）。系数库槽基址由 `k_r`
运行时推导:Â 占 slot 0..K²-1，`slot_s=K²`、`slot_e=K²+K`、`slot_t=K²+2K`。

### 3.5 控制 FSM 与数据流

5-bit 状态机从 `ST_IDLE` 按锁存的 `op_r` 分支为三条数据通路:

**KeyGen（算法 16）**
```
G:  (ρ,σ)=G(d‖K)                         SHA3-512
A:  Â[i][j]=SampleNTT(ρ‖j‖i)             → bank_a
C:  s/e = CBD_η1(PRF(σ,·))               → bank_se
N:  ŝ=NTT(s), ê=NTT(e)                    原地
M:  t̂=ê+Σⱼ Â∘ŝ                            逐点乘+modQ 累加 → bank_t
E:  ek=Enc12(t̂)‖ρ, dk_pke=Enc12(ŝ)       → ek/dkp_bram
H:  H(ek)                                 多块 SHA3-256
    dk = dk_pke‖ek‖H(ek)‖z
```

**Encaps（算法 17）**
```
ENC_H/G:  H(ek), (K,r)=G(m‖H(ek))
ENC_LOAD/A/TDEC: ρ载入, Â重生成, t̂=byteDecode12(ek)
ENC_C/N:  y,e1,e2=CBD(PRF(r,·)), ŷ=NTT(y)
ENC_U:    u=INTT(Σ Âᵀ∘ŷ)+e1
ENC_C1:   c1=Enc_du(Compress_du(u))
ENC_V:    v=INTT(Σ t̂∘ŷ)+e2+Decompress1(m)
ENC_C2:   c2=Enc_dv(Compress_dv(v));  c=c1‖c2;  K=共享密钥
```

**Decaps（算法 18，FO 变换 + 隐式拒绝）**
```
DEC_DECOMP:  u'/v' = Decompress(byteDecode(c))         D1
DEC_SDEC/NTT: ŝ=byteDecode12(dk_pke), û=NTT(u')         D2
DEC_W:       w=v'-INTT(Σⱼ ŝ∘û)                          D3
DEC_MENC:    m'=Enc1(Compress1(w))                      D4
DEC_G/J:     (K',r')=G(m'‖h),  K̄=J(z‖c)                D5
(重加密):    c'=K-PKE.Encrypt(ek_pke,m',r')  ←复用 Encaps 流水  D6
DEC_CMP:     ss = (c'==c) ? K' : K̄                      D7
```

**核心复用点**:D6 重加密整段复用 Encaps 的 `ENC_LOAD…ENC_C2`——m' 写入 `m_r`、
r' 在 `r_r`、ek_pke 已在 `ek_bram`，前置条件天然就位，无需另起数据通路。
D7 逐字节比较 `u_ct_bram`(c') 与 `u_c_in_bram`(c)，恒定工作量，按 `dec_reject`
在 `ss_r`(K') 与 `kbar_r`(K̄) 间选择:`ss_o = dec_reject ? kbar_r : ss_r`。

### 3.6 模运算策略

所有模 q（q=3329）约简采用 **Barrett 乘法**替代除法器:`floor(x/q) ≈ (x·5039)>>24`，
其中 `5039 = floor(2²⁴/q)`，再做至多两次条件减校正。`q·x` 用移位加实现
（3329 = 2048+512+256+1，无需第二个乘法器）。早期版本使用组合除法器，已于提交 `717a992`
替换为 Barrett，显著缩短关键路径。按设计约束，**全部乘法标注 `use_dsp="no"`，不使用 DSP48**。

---

## 4. 功能验证

### 4.1 验证策略

采用「分阶段中间量核对 + 端到端 KAT 比对」双层策略，全部对照 NIST FIPS 203 的 KAT 标准答案:

- **分阶段**:KeyGen 按 G/A/C/N/M/E/H、Encaps 按 E1–E7、Decaps 按 D0–D7 逐级验证中间多项式
  /哈希/编码，经调试抽头逐字节回读比对。
- **端到端**:KeyGen 核对 `ek==pk`、`dk==sk`;Encaps 核对 `ss`、`c`;Decaps 核对最终 `ss`，
  并用 KAT 自带的损坏密文 `ct_n`/`ss_n` 验证隐式拒绝路径（`ss==ss_n=J(z‖ct_n)`）。

### 4.2 测试平台

| 测试平台 | 操作 | 覆盖 |
|:---|:---|:---|
| `tb_mlkem_kg_katK_xsim.v` | KeyGen | K=2/3/4 各 KAT 用例，`ek==pk`/`dk==sk` |
| `tb_mlkem_enc_katK_xsim.v` | Encaps | E1–E7 分阶段 + `ss`/`c` |
| `tb_mlkem_dec_katK_xsim.v` | Decaps | D0–D7 分阶段 + 接受/拒绝双路径 |
| `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` 选等级，`+CASE=n` 选用例。统一脚本
`run_tb.sh {top|enc|dec|hello}` 驱动。

### 4.3 验证结果

- **KeyGen / Encaps / Decaps** 三操作、K=2/3/4 三等级全部 KAT 用例逐字节 PASS。
- **隐式拒绝**:损坏密文路径正确输出 K̄，`dec_reject=1`。
- **端到端**:`hello_world` 单/双实例均通过，共享密钥与消息正确还原
  （`shared_key=ced0c031a4bee34a…`，`decrypted="hello world"`）。

### 4.4 增量验证里程碑（git 记录）

设计按阶段增量构建，每阶段独立提交并通过 KAT，历史可二分定位:

```
KeyGen 各阶段 → Encaps E1–E7 (7228beb…) → Decaps D0–D7 (030931d…2b70431)
→ hello_world 端到端 (f279222, ee2bf1c)
```

---

## 5. 综合与实现结果

### 5.1 资源占用（OOC 综合，xc7a200tfbg676-1）

| 资源 | 使用 | 可用 | 占用率 |
|:---|:---:|:---:|:---:|
| Slice LUTs（全为逻辑） | 34 318 | 134 600 | 25.5 % |
| Slice Registers (FF) | 23 254 | 269 200 | 8.6 % |
| F7 Muxes | 3 645 | 67 300 | 5.4 % |
| F8 Muxes | 1 191 | 33 650 | 3.5 % |
| Block RAM Tile | 5（RAMB36×2 + RAMB18×6） | 365 | 1.4 % |
| **DSP48** | **0** | 740 | **0 %** |

面积占用低，DSP 完全未用（符合设计约束），器件资源充裕。

### 5.2 性能（周期数，实测）

| 操作 | 周期数（K=2，ML-KEM-512） |
|:---|:---:|
| KeyGen | ≈ 22 904 |
| Encaps | ≈ 32 493 |
| Decaps | ≈ 50 819 |

K=3/4 因模秩增大按比例上升。Decaps 最长，因其包含完整重加密（≈ 一次 Encaps）。

### 5.3 时序现状与瓶颈

当前对 **50 MHz（20 ns）** 目标**尚未收敛**:

| 指标 | 值 |
|:---|:---|
| WNS | -32.2 ns（关键路径实际 ≈ 52 ns） |
| 失败端点 | 3 132 / 44 689 |
| Hold (WHS) | +0.134 ns（无违例） |
| 关键路径 | `u_pmul/mem_A_reg → u_pmul/c0_reg`，70 逻辑级 |

**根因**:`basecase_mul` 单周期组合计算 `c0=(a0·b0+(a1·b1)·zeta) mod q`，其中
**两级 Barrett 模乘串联**（`t2=a1·b1` 再 `t2·zeta`）+ 模加;在 `use_dsp="no"` 约束下，
每级 Barrett 约 24 ns，串联即 ≈ 52 ns。

**修复方向**（不使用 DSP，详见 `timing_analysis.md`）:将 `barrett_mul` 改为 3 级内部流水
（乘法 / ×K 移位 / ×q 约简各一拍），`basecase_mul` 的 c0 双乘级联为 6 拍、c1 对齐，
`poly_mul_sync` 节拍相应加深。吞吐几乎不变（仅增加固定启动延迟，相对数万周期可忽略），
WNS 预计转正。每步需重跑全部 KAT 确保功能不变。

---

## 6. 设计权衡与结论

### 6.1 主要权衡

| 决策 | 收益 | 代价 |
|:---|:---|:---|
| 单 FSM 串行调度 + 资源复用 | 面积小（LUT 25%）、控制清晰 | 串行执行，周期数较高 |
| 共享单 Keccak 核 | 省大量面积 | 哈希/采样不能并行 |
| Decaps 复用 Encaps 流水 | 省去独立重加密通路 | FSM 状态耦合较紧 |
| 运行时选 k_i/op_i | 单比特流支持全部配置 | 存储按最坏情况分配 |
| 不使用 DSP | 满足约束、可移植性强 | 乘法走 LUT，时序压力大 |

### 6.2 结论

`mlkem_top` 是一个**功能完整、KAT 全过**的 ML-KEM 硬件 IP，在单模块内支持 KeyGen/Encaps/Decaps
三种操作与三种安全等级，面积占用低（LUT 25.5%、零 DSP）。设计经分阶段增量验证，正确性可靠。

当前唯一未达标项是 **50 MHz 时序收敛**:瓶颈明确（`basecase_mul` 双 Barrett 串联组合路径），
修复方案已制定（纯流水化，不依赖 DSP），改动范围可控。完成该流水化改造并重跑 KAT 后，
预计可收敛至 50 MHz 目标。

### 6.3 后续工作

1. 按 `timing_analysis.md` 实施 Barrett / basecase / poly_mul 流水化，收敛 50 MHz。
2. 流水化后检查次要瓶颈（如 `comp_decomp` 的 Barrett），同法处理。
3. 补充布局布线（implementation）后的时序签核，目前仅有综合后时序。
4. 视吞吐需求，评估关键算子（NTT、采样）并行化以降低周期数。

---

## 附:复现命令

```bash
source /opt/Xilinx/Vivado/2019.2/settings64.sh
export LD_PRELOAD=/usr/lib64/libtinfo.so.5

# 功能验证
./run_tb.sh top        # KeyGen KAT (K=2/3/4)
./run_tb.sh enc        # Encaps KAT
./run_tb.sh dec        # Decaps KAT (含拒绝路径)
./run_tb.sh hello      # 端到端 hello_world

# 综合 + 时序报告
vivado -mode batch -source synth_timing.tcl   # → timing.rpt / timing_worst.rpt / util.rpt
```

**相关文档**:`README.md`（使用说明）、`docs/mlkem_top_rtl.svg`（RTL 结构图）、
`timing_analysis.md`（时序分析与修复方案）。