第27课：后量子密码基础

阶段五实战项目 — 量子计算机威胁现有公钥密码。NIST 后量子密码标准化正在重新定义密码硬件的未来。本课介绍后量子密码的硬件挑战。

1. 量子威胁

Shor 算法可以在多项式时间内分解大整数和计算离散对数，威胁 RSA 和 ECC。Grover 算法将对称密钥的有效安全强度减半。

算法	经典安全	量子安全
RSA-2048	112位	0（Shor 破解）
ECC-256	128位	0（Shor 破解）
AES-128	128位	64位（Grover 减半）
AES-256	256位	128位（仍然安全）

2. NIST 后量子密码候选

2.1 格密码（Lattice-based）

ML-KEM（原 Kyber）和 ML-DSA（原 Dilithium）是 NIST 选定的主要 PQC 方案。

ML-KEM 密钥封装

基于 Module-LWE（Learning With Errors）问题：

b = A·s + e (mod q)

其中 A 是公开矩阵，s 是私钥向量，e 是小错误向量。从 b 恢复 s 等价于最坏情况格问题。

2.2 格密码硬件的核心运算

格密码的硬件实现主要涉及：

数论变换（NTT）：多项式乘法的快速算法
采样：从离散高斯或二项分布采样
压缩/解压缩：降低数据精度

✅Verilator验证通过

// ntt_butterfly.v - NTT 蝶形运算单元
module ntt_butterfly #(
    parameter WIDTH = 12,           // 模数位宽（q=3329）
    parameter [WIDTH-1:0] Q = 12'd3329  // Kyber 模数
)(
    input  wire [WIDTH-1:0] a,
    input  wire [WIDTH-1:0] b,
    input  wire [WIDTH-1:0] twiddle,     // 旋转因子
    output wire [WIDTH-1:0] out_a,
    output wire [WIDTH-1:0] out_b
);

    // 蝶形运算：
    // out_a = (a + b * twiddle) mod q
    // out_b = (a - b * twiddle) mod q

    // 步骤1：b * twiddle
    wire [2*WIDTH-1:0] product = b * twiddle;

    // 步骤2：模约减（Barrett 约减简化版）
    wire [WIDTH-1:0] reduced;
    // 对于小模数，可以用简单条件减法
    assign reduced = (product >= Q) ? product[WIDTH-1:0] - Q : product[WIDTH-1:0];
    // 多级约减
    wire [WIDTH-1:0] reduced2 = (reduced >= Q) ? reduced - Q : reduced;

    // 步骤3：加法和减法
    wire [WIDTH:0] sum = {1'b0, a} + {1'b0, reduced2};
    wire [WIDTH:0] diff = {1'b0, a} - {1'b0, reduced2} + {1'b0, Q};

    // 最终模约减
    assign out_a = (sum >= Q) ? sum[WIDTH-1:0] - Q : sum[WIDTH-1:0];
    assign out_b = (diff >= Q) ? diff[WIDTH-1:0] - Q : diff[WIDTH-1:0];

endmodule

2.3 离散采样器

✅Verilator验证通过

// binomial_sampler.v - 二项分布采样器（Kyber 使用）
module binomial_sampler #(
    parameter ETA = 2,    // Kyber-512 使用 η=3, Kyber-768/1024 使用 η=2
    parameter WIDTH = 12
)(
    input  wire              clk,
    input  wire              rst_n,
    input  wire              sample_req,
    input  wire [64*ETA-1:0] random_bits,  // 2η 组随机位
    output reg  [WIDTH-1:0]  sample_out,
    output reg               sample_valid
);

    // 二项分布采样：centred binomial distribution CBD(η)
    // sample = (a₁+a₂+...+aη) - (b₁+b₂+...+bη)
    // 其中 aᵢ, bᵢ 是独立均匀随机位

    reg [3:0] pos_count, neg_count;
    integer i;

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            sample_out <= 0; sample_valid <= 0;
        end else if (sample_req) begin
            pos_count = 0;
            neg_count = 0;

            // 计算正部分
            for (i = 0; i < ETA; i = i + 1)
                pos_count = pos_count + random_bits[i];

            // 计算负部分
            for (i = 0; i < ETA; i = i + 1)
                neg_count = neg_count + random_bits[ETA + i];

            // 结果 = 正 - 负 + η（偏移使结果非负）
            sample_out <= pos_count - neg_count + ETA;
            sample_valid <= 1;
        end else begin
            sample_valid <= 0;
        end
    end

endmodule

3. 后量子密码的硬件挑战

大内存需求：ML-KEM 公钥 800-1568 字节，远大于 ECC 的 32-64 字节
NTT 加速：多项式乘法是性能瓶颈
采样安全：离散采样器必须抵抗侧信道攻击
解封装失败：ML-KEM 有非零失败概率，需要防护

1. 实现 256 点 NTT：使用蝶形网络，验证前向和逆向变换的正确性。

2. 实现 CBD(2) 采样器：验证输出分布 {-2, -1, 0, 1, 2} 的概率。

3. 估算 ML-KEM-768 密钥封装在 FPGA 上的面积和延迟。

4. 研究：基于哈希的签名（SPHINCS+）与格密码的硬件效率比较。

🏆 成就解锁：量子先行者

你已了解后量子密码的硬件挑战，实现了 NTT 蝶形运算和 CBD 采样器。后量子密码是密码学硬件的下一次革命！

获得徽章：🔮 PQ_PIONEER

💡 扩展阅读与参考资源

NIST FIPS-197: AES 标准（官方文档）
NIST FIPS-180-4: SHA-256 标准规范
NIST SP 800-38D: GCM 模式规范
NIST SP 800-90A/B: 随机数生成器标准
《The Design of Rijndael》— Joan Daemen, Vincent Rijmen
《Cryptographic Engineering》— Çetin Kaya Koç
《Hardware Security and Trust》— Swaroop Ghosh 等编

🔧 实践环境搭建

推荐使用以下工具链进行课程实践：

# 安装 Verilator
sudo apt install verilator

# 安装 Icarus Verilog（可选）
sudo apt install iverilog

# 安装 GTKWave（波形查看器）
sudo apt install gtkwave

# 验证安装
verilator --lint-only --version
iverilog -V

📊 性能指标对比

密码学硬件实现的关键性能指标：

面积：等效门数（GE）或查找表（LUT）数量
频率：最大时钟频率（MHz）
吞吐量：每秒处理的数据量（Mbps/Gbps）
延迟：从输入到输出的时钟周期数
能效：每比特功耗（pJ/bit）

这些指标之间通常存在 trade-off，设计时需根据应用场景权衡。

📚 本课知识图谱

本课涉及的核心概念和技术关系：

前驱知识：Verilog HDL 基础、数字电路设计、有限域运算
核心概念：硬件描述语言实现密码算法、组合逻辑与时序逻辑的选择、面积与速度的 trade-off
后续应用：完整密码引擎集成、侧信道防护、安全 SoC 设计

💡 调试技巧

Verilog 仿真调试的常用方法：

$display：在控制台打印变量值，类似于 C 的 printf
$monitor：自动监视变量变化并打印
$dumpfile/$dumpvars：生成 VCD 波形文件，用 GTKWave 查看
assert：Verilog 2001+ 的断言，验证条件必须为真

// 调试示例
initial begin
    $dumpfile("sim.vcd");
    $dumpvars(0, uut);
end

// 断言验证
assert property (@(posedge clk) valid |-> data !== 'x)
    else $error("Invalid data when valid!");

🔧 Verilator 编译仿真完整流程

# 1. 语法检查
verilator --lint-only module.v

# 2. 创建 C++ 测试主函数
cat > sim_main.cpp << 'EOF'
#include "Vmodule.h"
#include "verilated.h"
int main(int argc, char** argv) {
    Verilated::commandArgs(argc, argv);
    Vmodule* top = new Vmodule;
    top->clk = 0; top->rst_n = 0;
    top->eval();
    top->rst_n = 1;
    for (int i = 0; i < 100; i++) {
        top->clk = !top->clk;
        top->eval();
    }
    delete top;
    return 0;
}
EOF

# 3. 编译
verilator -cc module.v --exe sim_main.cpp
make -C obj_dir -f Vmodule.mk

# 4. 运行
./obj_dir/Vmodule

📖 推荐阅读

《The Design of Rijndael》— Joan Daemen, Vincent Rijmen（AES 设计者亲著）
《Cryptographic Engineering》— Çetin Kaya Koç（密码硬件实现必读）
《Hardware Security and Trust》— Swaroop Ghosh 等编（侧信道与安全设计）
NIST FIPS 系列标准文档（AES, SHA, HMAC 等官方规范）
IEEE P1735 标准（IP 核加密保护）

⚖️ 性能评估框架

密码硬件的性能评估维度：

指标	单位	说明
面积	GE / LUT	等效门数或查找表数量
频率	MHz	最大时钟频率
吞吐量	Gbps	每秒处理的数据量
延迟	周期数	从输入到输出的周期
能效	pJ/bit	每比特能耗
面积效率	Gbps/GE	单位面积吞吐量

不同应用场景对指标优先级不同：IoT 偏重面积和能效，服务器偏重吞吐量。