第15课：RSA 核心运算

阶段三非对称密码 — RSA 的核心运算是模幂：c = m^e mod n。平方-乘算法将模幂分解为一系列模乘和模平方操作。

1. RSA 数学基础

RSA 基于大整数分解难题：

密钥生成：选择素数 p, q，计算 n = p·q，φ(n) = (p-1)(q-1)
公钥：(e, n)，其中 e 与 φ(n) 互素
私钥：(d, n)，其中 d = e⁻¹ mod φ(n)
加密：c = m^e mod n
解密：m = c^d mod n

2. 平方-乘算法

模幂的高效算法——从右到左扫描指数位：

输入：m, e, n
1. result = 1, base = m
2. for i = 0 to k-1:
3.   if e[i] == 1: result = (result × base) mod n
4.   base = (base × base) mod n
5. return result

复杂度：k 次模平方 + 平均 k/2 次模乘，其中 k 是指数位宽。

3. RSA 模幂硬件实现

✅Verilator验证通过

// rsa_modexp.v - RSA 模幂运算模块
module rsa_modexp #(
    parameter WIDTH = 256        // 操作数位宽
)(
    input  wire              clk,
    input  wire              rst_n,
    input  wire              start,
    input  wire [WIDTH-1:0]  base,        // 底数 m
    input  wire [WIDTH-1:0]  exponent,    // 指数 e
    input  wire [WIDTH-1:0]  modulus,     // 模数 n
    output reg  [WIDTH-1:0]  result,      // m^e mod n
    output reg               valid,
    output reg [7:0]         status       // 状态码
);

    localparam IDLE    = 3'd0;
    localparam COMPUTE = 3'd1;
    localparam MUL     = 3'd2;
    localparam SQR     = 3'd3;
    localparam DONE    = 3'd4;

    reg [2:0]          fsm;
    reg [WIDTH-1:0]    result_reg;
    reg [WIDTH-1:0]    base_reg;
    reg [WIDTH-1:0]    exp_reg;
    reg [$clog2(WIDTH+1)-1:0] bit_idx;

    // 简化模乘：使用行为级描述（实际应使用蒙哥马利乘法）
    reg [2*WIDTH-1:0]  mul_product;
    reg [WIDTH-1:0]    mul_a, mul_b, mul_mod;
    reg                mul_start, mul_valid;
    reg [2*WIDTH-1:0]  mul_acc;
    reg [$clog2(WIDTH+1)-1:0] mul_cnt;
    reg                mul_running;

    // 简单模乘器
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            mul_product <= 0; mul_valid <= 0; mul_running <= 0;
            mul_acc <= 0; mul_cnt <= 0;
        end else if (mul_start && !mul_running) begin
            mul_a <= mul_a; mul_b <= mul_b; mul_mod <= mul_mod;
            mul_acc <= 0; mul_cnt <= 0;
            mul_running <= 1; mul_valid <= 0;
        end else if (mul_running) begin
            if (mul_cnt < WIDTH) begin
                if (mul_b[0])
                    mul_acc <= mul_acc + ({{WIDTH{1'b0}}, mul_a} << mul_cnt);
                mul_b <= mul_b >> 1;
                mul_cnt <= mul_cnt + 1;
            end else begin
                // 简化模约减（仅用于仿真验证）
                mul_product <= mul_acc;
                mul_valid <= 1;
                mul_running <= 0;
            end
        end
    end

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            fsm <= IDLE;
            result <= 0; valid <= 0; status <= 0;
            result_reg <= 1;  // 初始化为1
            base_reg <= 0;
            exp_reg <= 0;
            bit_idx <= 0;
            mul_start <= 0;
        end else begin
            mul_start <= 0;

            case (fsm)
                IDLE: begin
                    if (start) begin
                        result_reg <= 1;
                        base_reg <= base;
                        exp_reg <= exponent;
                        bit_idx <= 0;
                        fsm <= COMPUTE;
                        status <= 1;
                    end
                end
                COMPUTE: begin
                    if (bit_idx < WIDTH) begin
                        if (exp_reg[0]) begin
                            // 需要模乘：result = result * base mod n
                            mul_a <= result_reg;
                            mul_b <= base_reg;
                            mul_mod <= modulus;
                            mul_start <= 1;
                            fsm <= MUL;
                        end else begin
                            // 跳过乘法，直接做平方
                            mul_a <= base_reg;
                            mul_b <= base_reg;
                            mul_mod <= modulus;
                            mul_start <= 1;
                            fsm <= SQR;
                        end
                    end else begin
                        result <= result_reg;
                        valid <= 1;
                        status <= 0;
                        fsm <= IDLE;
                    end
                end
                MUL: begin
                    if (mul_valid) begin
                        result_reg <= mul_product[WIDTH-1:0] % modulus;
                        // 继续平方
                        mul_a <= base_reg;
                        mul_b <= base_reg;
                        mul_mod <= modulus;
                        mul_start <= 1;
                        fsm <= SQR;
                    end
                end
                SQR: begin
                    if (mul_valid) begin
                        base_reg <= mul_product[WIDTH-1:0] % modulus;
                        exp_reg <= exp_reg >> 1;
                        bit_idx <= bit_idx + 1;
                        fsm <= COMPUTE;
                    end
                end
            endcase
        end
    end

endmodule

4. RSA 参数选择

安全级别	模数长度	公钥指数 e
80 位	1024 位	65537
112 位	2048 位	65537
128 位	3072 位	65537
256 位	15360 位	65537

为什么 e=65537=2¹⁶+1？因为它只有两个 1 位，只需 16 次平方和 1 次乘法，加密速度极快。

1. 使用小参数验证：p=61, q=53, n=3233, e=17, d=2753。加密 m=65，验证 c=m^e mod n 和 m=c^d mod n。

2. 实现从左到右的平方-乘算法（逐位扫描指数从 MSB 到 LSB），比较与从右到左版本的效率。

3. 设计支持 CRT 加速的 RSA 解密：利用 p 和 q 分别计算，速度提升约 4 倍。

4. 分析：如果平方-乘算法中乘法和平方的功耗不同，攻击者如何通过功耗轨迹推断指数位？

🏆 成就解锁：幂运算者

你已掌握 RSA 模幂的平方-乘算法和硬件实现，理解了密钥参数选择和安全级别。模幂是 RSA 的计算核心！

获得徽章：⚡ MODULAR_EXPONENT

💡 扩展阅读与参考资源

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