第14课：蒙哥马利乘法

阶段三非对称密码 — 蒙哥马利乘法是 RSA 和 ECC 硬件实现的核心算法。它避免了昂贵的模除法，用简单的移位替代。

1. 蒙哥马利域

蒙哥马利乘法在"蒙哥马利域"中运算。对于模数 M，选择 R = 2ⁿ（n 为 M 的位宽），使得 R > M 且 gcd(R, M) = 1。

蒙哥马利形式：ā = a · R mod M
MonPro(ā, b̄) = ā · b̄ · R⁻¹ mod M

关键优势：R⁻¹ 的计算只需要右移和条件减法，不需要除法！

2. MonPro 算法

蒙哥马利乘积算法（MonPro）：

输入：ā, b̄, M, M' = -M⁻¹ mod R
1. t = ā · b̄
2. u = (t + t·M' mod R · M) / R
3. if u ≥ M then return u - M else return u

步骤 2 中 t·M' mod R 只需保留低 n 位（因为 mod R = mod 2ⁿ），/R 只需右移 n 位。这就是蒙哥马利乘法避免除法的核心技巧！

3. 蒙哥马利乘法硬件实现

✅Verilator验证通过
// monpro.v - 蒙哥马利乘积模块
module monpro #(
    parameter WIDTH = 256
)(
    input  wire              clk,
    input  wire              rst_n,
    input  wire              start,
    input  wire [WIDTH-1:0]  a_bar,       // 蒙哥马利形式 a
    input  wire [WIDTH-1:0]  b_bar,       // 蒙哥马利形式 b
    input  wire [WIDTH-1:0]  modulus,     // M
    input  wire [WIDTH-1:0]  m_prime,     // M' = -M⁻¹ mod R
    output reg  [WIDTH-1:0]  result,      // MonPro(a, b)
    output reg               valid
);

    // 算法步骤：
    // 1. t = a_bar * b_bar  (2n 位)
    // 2. q = t[WIDTH-1:0] * m_prime  (取低 n 位)
    // 3. u = (t + q * M) >> WIDTH
    // 4. if u >= M: u = u - M

    reg [2*WIDTH-1:0] t;          // 乘积
    reg [WIDTH-1:0]   q;          // 约减因子
    reg [2*WIDTH-1:0] qm;         // q * M
    reg [WIDTH:0]     u;          // 结果（可能多1位）
    reg [2:0]         phase;
    reg               running;

    // 移位加法乘法器（简化版）
    reg [2*WIDTH-1:0]  mult_acc;
    reg [WIDTH-1:0]    mult_a, mult_b;
    reg [$clog2(WIDTH+1)-1:0] mult_cnt;
    reg                 mult_running;

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            result <= 0; valid <= 0; running <= 0; phase <= 0;
            t <= 0; q <= 0; qm <= 0; u <= 0;
            mult_acc <= 0; mult_running <= 0; mult_cnt <= 0;
        end else if (start && !running) begin
            // 开始第一步乘法: t = a_bar * b_bar
            mult_a <= a_bar;
            mult_b <= b_bar;
            mult_acc <= 0;
            mult_cnt <= 0;
            mult_running <= 1;
            running <= 1;
            phase <= 0;
            valid <= 0;
        end else if (running) begin
            if (phase == 0) begin
                // 执行乘法 t = a_bar * b_bar
                if (mult_cnt < WIDTH) begin
                    if (mult_b[0])
                        mult_acc <= mult_acc + ({{WIDTH{1'b0}}, mult_a} << mult_cnt);
                    mult_b <= mult_b >> 1;
                    mult_cnt <= mult_cnt + 1;
                end else begin
                    t <= mult_acc;
                    phase <= 1;
                    // 准备第二步: q = t[low] * m_prime
                    mult_a <= mult_acc[WIDTH-1:0];
                    mult_b <= m_prime;
                    mult_acc <= 0;
                    mult_cnt <= 0;
                end
            end else if (phase == 1) begin
                // q = t_low * m_prime
                if (mult_cnt < WIDTH) begin
                    if (mult_b[0])
                        mult_acc <= mult_acc + ({{WIDTH{1'b0}}, mult_a} << mult_cnt);
                    mult_b <= mult_b >> 1;
                    mult_cnt <= mult_cnt + 1;
                end else begin
                    q <= mult_acc[WIDTH-1:0];
                    phase <= 2;
                    // 准备第三步: qm = q * M
                    mult_a <= mult_acc[WIDTH-1:0];
                    mult_b <= modulus;
                    mult_acc <= 0;
                    mult_cnt <= 0;
                end
            end else if (phase == 2) begin
                // qm = q * M
                if (mult_cnt < WIDTH) begin
                    if (mult_b[0])
                        mult_acc <= mult_acc + ({{WIDTH{1'b0}}, mult_a} << mult_cnt);
                    mult_b <= mult_b >> 1;
                    mult_cnt <= mult_cnt + 1;
                end else begin
                    qm <= mult_acc;
                    phase <= 3;
                end
            end else begin
                // u = (t + qm) >> WIDTH
                u <= (t + qm) >> WIDTH;
                // 条件减法
                if (((t + qm) >> WIDTH) > {1'b0, modulus})
                    result <= ((t + qm) >> WIDTH) - {1'b0, modulus};
                else
                    result <= ((t + qm) >> WIDTH)[WIDTH-1:0];
                valid <= 1;
                running <= 0;
            end
        end
    end

endmodule

4. 域转换

进入蒙哥马利域：ā = a · R mod M（需要一次 MonPro）

退出蒙哥马利域：a = MonPro(ā, 1)

预计算 R² mod M = R · R mod M，用于快速转换。

✅Verilator验证通过
// mont_domain.v - 蒙哥马利域转换
module mont_domain #(
    parameter WIDTH = 256
)(
    input  wire              clk,
    input  wire              rst_n,
    input  wire              start,
    input  wire [WIDTH-1:0]  data_in,     // 普通域数据
    input  wire [WIDTH-1:0]  r_squared,   // R² mod M (预计算)
    input  wire [WIDTH-1:0]  modulus,
    input  wire [WIDTH-1:0]  m_prime,
    output reg  [WIDTH-1:0]  data_out,    // 蒙哥马利域数据
    output reg               valid
);

    // 转换: ā = MonPro(a, R² mod M)
    // 复用 MonPro 模块
    reg          mp_start;
    wire [WIDTH-1:0] mp_result;
    wire         mp_valid;

    monpro #(.WIDTH(WIDTH)) u_monpro (
        .clk(clk), .rst_n(rst_n), .start(mp_start),
        .a_bar(data_in), .b_bar(r_squared),
        .modulus(modulus), .m_prime(m_prime),
        .result(mp_result), .valid(mp_valid)
    );

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            data_out <= 0; valid <= 0; mp_start <= 0;
        end else if (start) begin
            mp_start <= 1;
        end else if (mp_valid) begin
            data_out <= mp_result;
            valid <= 1;
            mp_start <= 0;
        end
    end

endmodule

1. 验证 MonPro 算法：选择 M=97, R=128，计算 MonPro(50·128 mod 97, 30·128 mod 97)。

2. 预计算 R² mod M 对于常见 RSA 模数（如 M=0xFFFFFFFF...）的值。

3. 优化 MonPro：将三步乘法合并为两步（利用算法变体），减少周期数。

4. 分析蒙哥马利乘法相对于 Barrett 约减的优势：在什么位宽下蒙哥马利更高效？

🏆 成就解锁：蒙哥马利之径

你已掌握蒙哥马利乘法的核心思想和硬件实现，包括 MonPro 算法、域转换和预计算。蒙哥马利乘法是 RSA/ECC 硬件的效率关键！

获得徽章：🛤️ MONTGOMERY_PATH

💡 扩展阅读与参考资源

🔧 实践环境搭建

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

# 安装 Verilator
sudo apt install verilator

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

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

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

📊 性能指标对比

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

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

📚 本课知识图谱

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

💡 调试技巧

Verilog 仿真调试的常用方法：

// 调试示例
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

📖 推荐阅读

⚖️ 性能评估框架

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

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

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

← 上一课📖 目录下一课 →