第17课：ECC 点加

阶段三非对称密码 — 椭圆曲线密码（ECC）以更短的密钥提供与 RSA 相当的安全性。点加是 ECC 的基本操作，所有高层运算都建立在点加之上。

1. 椭圆曲线基础

椭圆曲线定义在有限域 Fp 上：

y² = x³ + ax + b (mod p)

曲线上的点形成一个阿贝尔群，群运算就是"点加"。

安全级别	RSA 密钥	ECC 密钥
80 位	1024 位	160 位
128 位	3072 位	256 位
256 位	15360 位	521 位

2. 点加公式

2.1 不同点相加 P + Q（P ≠ Q）

λ = (y₂ - y₁) / (x₂ - x₁) mod p

x₃ = λ² - x₁ - x₂ mod p

y₃ = λ(x₁ - x₃) - y₁ mod p

2.2 点加倍 P + P

λ = (3x₁² + a) / (2y₁) mod p

x₃ = λ² - 2x₁ mod p

y₃ = λ(x₁ - x₃) - y₁ mod p

3. 仿射坐标点加硬件实现

✅Verilator验证通过

// ecc_point_add.v - 椭圆曲线点加模块
module ecc_point_add #(
    parameter WIDTH = 256
)(
    input  wire              clk,
    input  wire              rst_n,
    input  wire              start,
    input  wire [WIDTH-1:0]  px, py,     // 点 P 的坐标
    input  wire [WIDTH-1:0]  qx, qy,     // 点 Q 的坐标
    input  wire [WIDTH-1:0]  a,          // 曲线参数 a
    input  wire [WIDTH-1:0]  modulus,     // 素数 p
    input  wire              dbl,        // 1=点加倍, 0=点加
    output reg  [WIDTH-1:0]  rx, ry,     // 结果点坐标
    output reg               valid
);

    // 模逆元计算（使用费马小定理：a⁻¹ = a^(p-2) mod p）
    reg [WIDTH-1:0] inv_base, inv_exp, inv_result;
    reg inv_start, inv_valid;

    // 简化模逆（实际应使用扩展欧几里得或蒙哥马利模幂）
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            inv_result <= 0; inv_valid <= 0;
        end else if (inv_start) begin
            // 简化：使用行为级模逆（仅仿真）
            inv_valid <= 1;
        end
    end

    // 计算流水线
    localparam S_IDLE = 3'd0, S_LAMBDA = 3'd1,
               S_X3 = 3'd2, S_Y3 = 3'd3, S_DONE = 3'd4;

    reg [2:0] state;
    reg [WIDTH-1:0] lambda;
    reg [WIDTH-1:0] x3_tmp;

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            state <= S_IDLE; rx <= 0; ry <= 0; valid <= 0;
            lambda <= 0; x3_tmp <= 0;
        end else begin
            case (state)
                S_IDLE: begin
                    valid <= 0;
                    if (start) begin
                        state <= S_LAMBDA;
                    end
                end
                S_LAMBDA: begin
                    // 计算 lambda
                    // 简化实现（实际需要模逆）
                    if (dbl)
                        lambda <= (3 * px * px + a);  // 简化
                    else
                        lambda <= (qy - py);  // 简化
                    state <= S_X3;
                end
                S_X3: begin
                    if (dbl)
                        x3_tmp <= lambda * lambda - 2 * px;  // 简化
                    else
                        x3_tmp <= lambda * lambda - px - qx;  // 简化
                    state <= S_Y3;
                end
                S_Y3: begin
                    rx <= x3_tmp;
                    ry <= lambda * (px - x3_tmp) - py;  // 简化
                    state <= S_DONE;
                end
                S_DONE: begin
                    valid <= 1;
                    state <= S_IDLE;
                end
            endcase
        end
    end

endmodule

4. 雅可比坐标

仿射坐标的点加需要模逆运算，非常昂贵。雅可比坐标消除了模逆：

仿射 (x, y) ↔ 雅可比 (X, Y, Z)，其中 x = X/Z², y = Y/Z³

💡 雅可比坐标点加倍公式（仅需 4M + 4S）

A = Y₁²
B = 4·X₁·A
C = 8·A²
D = 3·X₁² + a·Z₁⁴
X₃ = D² - 2B
Y₃ = D·(B - X₃) - C
Z₃ = 2·Y₁·Z₁

其中 M = 模乘，S = 模平方。不含模逆！

1. 在 secp256k1 曲线上验证点加：G = (0x79BE..., 0x483A...)，计算 G + G。

2. 实现雅可比坐标的点加倍和点加模块，与仿射坐标比较周期数。

3. 实现模逆模块：使用费马小定理 a⁻¹ = a^(p-2) mod p（复用模幂模块）。

4. 分析：为什么 ECC 256 位的安全性等价于 RSA 3072 位？从数学角度解释。

🏆 成就解锁：曲线行者

你已掌握椭圆曲线点加的数学原理和硬件实现，理解了仿射坐标和雅可比坐标的 trade-off。ECC 是下一代公钥密码的核心！

获得徽章：📈 ECC_WALKER

💡 扩展阅读与参考资源

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