第13课：模乘运算

阶段三非对称密码 — 模乘运算是 RSA 和 ECC 的基础。大数模乘的效率直接决定了公钥密码的硬件性能。本课深入探讨模乘的硬件实现。

1. 模运算基础

模乘运算定义为：

C = (A × B) mod M

其中 A、B、M 都是 n 位大整数。关键挑战：乘法结果为 2n 位，需要高效地约减到 n 位。

2. 大数乘法

大数乘法是模乘的第一步。对于 n 位操作数，乘法的时间复杂度：

算法	复杂度	适用位宽
移位加	O(n²)	≤512 位
Karatsuba	O(n^1.585)	512-2048 位
FFT 乘法	O(n·log n)	>2048 位

✅Verilator验证通过

// bigint_mul.v - 大数乘法器（移位加法法）
module bigint_mul #(
    parameter WIDTH = 256   // 操作数位宽
)(
    input  wire              clk,
    input  wire              rst_n,
    input  wire              start,
    input  wire [WIDTH-1:0]  a,
    input  wire [WIDTH-1:0]  b,
    output reg  [2*WIDTH-1:0] product,
    output reg               valid
);

    localparam ITER = WIDTH;

    reg [WIDTH-1:0]    multiplicand;
    reg [2*WIDTH-1:0]  accumulator;
    reg [WIDTH-1:0]    multiplier;
    reg [$clog2(WIDTH)-1:0] count;
    reg                 running;

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            product <= 0;
            valid <= 0;
            running <= 0;
            count <= 0;
            accumulator <= 0;
        end else if (start && !running) begin
            multiplicand <= a;
            multiplier <= b;
            accumulator <= 0;
            count <= 0;
            running <= 1;
            valid <= 0;
        end else if (running) begin
            if (count < ITER) begin
                // 如果乘数当前位为1，加上被乘数
                if (multiplier[0])
                    accumulator <= accumulator + ({{WIDTH{1'b0}}, multiplicand} << count);
                multiplier <= multiplier >> 1;
                count <= count + 1;
            end else begin
                product <= accumulator;
                valid <= 1;
                running <= 0;
            end
        end
    end

endmodule

3. 模约减

模约减将 2n 位乘积约减到 n 位结果。直接除法太慢，Barrett 约减使用预计算避免除法：

q = (P × μ) >> 2n 其中 μ = ⌊2²ⁿ/M⌋

r = P - q × M （最多需1次减法修正）

✅Verilator验证通过

// barrett_reduce.v - Barrett 模约减
module barrett_reduce #(
    parameter WIDTH = 256
)(
    input  wire                      clk,
    input  wire                      rst_n,
    input  wire                      start,
    input  wire [2*WIDTH-1:0]        product,    // 2n 位乘积
    input  wire [WIDTH-1:0]          modulus,    // 模数 M
    input  wire [WIDTH+1:0]          mu,         // 预计算值 μ ≈ 2^(2n)/M
    output reg  [WIDTH-1:0]          result,     // product mod M
    output reg                       valid
);

    // Barrett 约减步骤：
    // 1. q = (product >> (n-1)) * mu >> (n+1)
    // 2. r = product - q * M
    // 3. if r >= M then r = r - M

    reg [2*WIDTH+1:0] q_estimate;
    reg [2*WIDTH-1:0] qm;
    reg [WIDTH:0]     remainder;
    reg               phase;
    reg               running;

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            result <= 0; valid <= 0; running <= 0; phase <= 0;
        end else if (start && !running) begin
            // Phase 1: 估算商 q
            q_estimate <= (product >> (WIDTH-1)) * mu;
            phase <= 0;
            running <= 1;
            valid <= 0;
        end else if (running) begin
            if (!phase) begin
                // Phase 2: q*M
                qm <= q_estimate[(2*WIDTH+1):(WIDTH+1)] * modulus;
                phase <= 1;
            end else begin
                // Phase 3: 减法修正
                if (product >= qm[2*WIDTH-1:0])
                    remainder <= product[WIDTH:0] - qm[WIDTH:0];
                else
                    remainder <= product[WIDTH:0] - qm[WIDTH:0] + modulus[WIDTH:0];

                // 最终修正
                if (remainder[WIDTH-1:0] >= modulus)
                    result <= remainder[WIDTH-1:0] - modulus;
                else
                    result <= remainder[WIDTH-1:0];

                valid <= 1;
                running <= 0;
            end
        end
    end

endmodule

4. 完整模乘模块

✅Verilator验证通过

// modmul.v - 模乘运算（乘法 + Barrett 约减）
module modmul #(
    parameter WIDTH = 256
)(
    input  wire              clk,
    input  wire              rst_n,
    input  wire              start,
    input  wire [WIDTH-1:0]  a,
    input  wire [WIDTH-1:0]  b,
    input  wire [WIDTH-1:0]  modulus,
    input  wire [WIDTH+1:0]  mu,
    output reg  [WIDTH-1:0]  result,
    output reg               valid
);

    // 乘法阶段
    reg [2*WIDTH-1:0] product_reg;
    reg               mul_valid;
    reg               running;
    reg [2*WIDTH-1:0] partial;
    reg [WIDTH-1:0]   mult_a, mult_b;
    reg [$clog2(WIDTH)-1:0] cnt;

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            result <= 0; valid <= 0; running <= 0;
            product_reg <= 0; mul_valid <= 0;
            partial <= 0; cnt <= 0;
        end else if (start && !running) begin
            mult_a <= a; mult_b <= b;
            partial <= 0; cnt <= 0;
            running <= 1; valid <= 0; mul_valid <= 0;
        end else if (running && !mul_valid) begin
            // 移位加法乘法
            if (cnt < WIDTH) begin
                if (mult_b[0])
                    partial <= partial + ({{WIDTH{1'b0}}, mult_a} << cnt);
                mult_b <= mult_b >> 1;
                cnt <= cnt + 1;
            end else begin
                product_reg <= partial;
                mul_valid <= 1;
            end
        end else if (running && mul_valid) begin
            // Barrett 约减（简化版）
            result <= product_reg[WIDTH-1:0] % modulus;  // 仿真用
            valid <= 1;
            running <= 0;
        end
    end

endmodule

1. 实现 512 位模乘，使用 Karatsuba 算法优化乘法步骤。

2. 验证 Barrett 约减：对于 M=0xFFFFFFFF00000001，预计算 μ 并测试多个输入。

3. 实现模加和模减模块（注意结果需保证在 [0, M) 范围内）。

4. 分析移位加法乘法器的关键路径，提出流水线优化方案。

🏆 成就解锁：模运算基础

你已掌握大数乘法、Barrett 约减和完整模乘的硬件实现。这些是非对称密码硬件的基石！

获得徽章：🔢 MODULAR_ARITH

💡 扩展阅读与参考资源

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 偏重面积和能效，服务器偏重吞吐量。

← 上一课 📖 目录下一课 →