327 lines
14 KiB
Markdown
327 lines
14 KiB
Markdown
# 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`（时序分析与修复方案）。
|