第13章 实例：SHA-1 哈希算法

这一篇在干嘛？

本章把前面学的知识（决策树、参数化、迭代复用）串成一个完整实例：在 FPGA 上实现 SHA-1 安全哈希算法。重点是学习紧凑型迭代架构——不复用流水线换速度，而是反复使用同一块逻辑换面积，并量化评估参数（字宽、字数）对速度/面积的影响。

13.1 SHA-1 是什么

SHA（Secure Hash Algorithm，安全哈希算法）定义了一种把任意消息压缩成定长摘要（message digest）的方法：不拿到原始消息，就不可能（计算上不可行）造出同样的摘要。这个性质让它适合：

• 数字签名：验证消息的真实性/完整性；
• 一些辅助应用，如随机数生成。

SHA 系列算法由 NIST 定义，不同版本的区别主要是哈希长度——它直接对应安全强度。本章实现最基础的 SHA-1。SHA 算法特别适合硬件实现：所有运算都是简单的逻辑操作，在 FPGA 上效率很高。

算法规格

SHA-1 的关键参数：

• 以 32 位字为单位运算；
• 每个中间哈希值由 **512 位（16 个字）**的消息块计算得出；
• 最终摘要 160 位。

为简化讨论，假设消息已经完成填充（padding）和分块（parse）。架构要素：

• 160 位哈希值 H₀~H₄：5 个 32 位字，初值由 SHA 标准规定（记为 H
• 消息调度（message schedule） W₀~W₇₉：80 个 32 位字；
• 5 个工作变量寄存器 A~E；
• 1 个临时字 T。

图 13.1 SHA-1 基本架构：消息调度 + 工作变量更新均迭代复用

运算流程：

1. 用当前哈希值 H₀^(i)H₄^(i) 初始化工作变量 AE（首轮用标准规定的初值）；
2. 循环 80 轮，每轮从消息调度取一个 W_t，与工作变量的函数、常数 K_t 一起在模 2³² 有限域上做加法，更新 A~E；
3. 80 轮结束后，把 AE 分别加到 H₀H₄ 上，得到最终哈希。

其中每轮用到的常数 K_t 和函数 f_t(B,C,D) 按 t 的区间取值，定义如下两表：

表 13.1 常数生成器定义

K_t	迭代 t
5a827999	0 ≤ t ≤ 19
6ed9eba1	20 ≤ t ≤ 39
8f1bbcdc	40 ≤ t ≤ 59
ca62c1d6	60 ≤ t ≤ 79

表 13.2 函数 f_t 定义

f_t	迭代 t
(B & C) ^ (~B & D)	0 ≤ t ≤ 19
B ^ C ^ D	20 ≤ t ≤ 39
(B & C) ^ (C & D) ^ (B & D)	40 ≤ t ≤ 59
B ^ C ^ D	60 ≤ t ≤ 79

紧凑迭代架构的取舍

本章实现刻意选择面积最小的策略：消息调度和工作变量更新都迭代复用同一组逻辑资源。代价是：上一个哈希算完才能开始下一个——几乎没有可流水的地方，吞吐率低但面积小。这是”速度换面积”的经典决策。

Verilog 实现

先看全局常量定义（实际项目中应放在独立的 defines.v 里）：

`define H0INIT 32'h67452301
`define H1INIT 32'hefcdab89
`define H2INIT 32'h98badcfe
`define H3INIT 32'h10325476
`define H4INIT 32'hc3d2e1f0
`define K0 32'h5a827999
`define K1 32'h6ed9eba1
`define K2 32'h8f1bbcdc
`define K3 32'hca62c1d6

注意定义（define）与参数（parameter）的分工：SHA 规范规定的初值和常数表”永远不变”，属于全局常量，用 define；字宽 32、块大小 16 字虽然规范也定了，但这里列成 parameter——万一驱动 SHA 核的总线不足 32 位，改参数就能适配。

主体模块：

module sha1 #(parameter WORDNUM = 16, parameter WORDSIZE = 32,
    parameter WSIZE = 480) (
    output [159:0] oDat,
    output reg oReady,
    input [WORDSIZE-1:0] iDat,
    input iClk,
    input iInitial, iValid);
    reg [6:0] loop;
    reg [WORDSIZE-1:0] H0, H1, H2, H3, H4;
    reg [WSIZE-1:0] W;
    reg [WORDSIZE-1:0] Wt, Kt;
    reg [WORDSIZE-1:0] A, B, C, D, E;
 
    // 哈希函数
    wire [WORDSIZE-1:0] f1,f2,f3, WtRaw, WtROTL1;
    wire [WORDSIZE-1:0] ft;
    wire [WORDSIZE-1:0] T;
    wire [WORDSIZE-1:0] ROTLB; // B 左旋
 
    // 按当前迭代轮数定义 SHA-1 函数
    assign f1 = (B & C) ^ (~B & D);
    assign f2 = B ^ C ^ D;
    assign f3 = (B & C) ^ (C & D) ^ (B & D);
    assign ft = (loop < 21) ? f1:(loop < 41) ? f2:(loop < 61) ?
    f3:f2;
 
    // ROTL1 之前的原始 Wt 计算
    assign WtRaw = {W[(WORDNUM-2)*WORDSIZE-1:(WORDNUM-3)*WORDSIZE]^W[(WORDNUM-7)*WORDSIZE-1:(WORDNUM-8)*WORDSIZE]^W[(WORDNUM-13)*WORDSIZE-1:(WORDNUM-14)*WORDSIZE]^W[(WORDNUM-15)*WORDSIZE-1:(WORDNUM-16)*WORDSIZE]};
    // Wt 循环左移 1 位
    assign WtROTL1 = {WtRaw[WORDSIZE-2:0],
    WtRaw[WORDSIZE-1]};
    assign T = {A[WORDSIZE-6:0],A[WORDSIZE-1:WORDSIZE-5]} + ft + E + Kt + Wt;
 
    assign ROTLB = {B[1:0],B[WORDSIZE-1:2]};
    assign oDat = {H0, H1, H2, H3, H4};
 
    // 按迭代轮数选择 Kt
always @ (posedge iClk)
    if (loop < 20) Kt <= `K0;
    else if (loop < 40) Kt <= `K1;
    else if (loop < 60) Kt <= `K2;
    else Kt <= `K3;

代码点评：

• loop 是轮次计数器（0~80），是全设计的”节拍器”。注意比较用的是 loop < 21、< 41 而不是 < 20、< 40——因为 Kt 在上一拍已按 loop < 20 选好，供下一拍使用，两处区间要错开一拍配合。
• f1/f2/f3 三个函数并行算好，再用一个多路选择器按轮次挑一个（对应表 13.2 的四段区间）。这就是第 12 章讲的”决策树”落地。
• WtRaw 从消息调度 W 的特定位置取 4 个字异或；WtROTL1 是 32 位循环左移 1 位——注意 Verilog 的拼接 {a[30:0], a[31]} 就是循环移位的惯用写法。
• T 的计算：A 循环左移 5 位（{A[26:0], A[31:27]}）后加上 ft、E、Kt、Wt。模 2³² 加法不需要任何额外处理——32 位寄存器天然截断溢出，这也是为什么密码学算法在硬件上做有限域加法比普通算术还简单。

消息调度部分：

// 消息调度
always @(posedge iClk) begin
    // 准备消息调度
    if (loop < WORDNUM) Wt <= iDat;
    else    Wt <= WtROTL1;
 
// 把 iDat 移入最高位
if ((loop < WORDNUM-1) & iValid)
    W[WSIZE-1:0]    <= {iDat, W[WSIZE-1:WORDSIZE]};
// 把 Wt 移入最高位
else if (loop > WORDNUM-1)
    W[WSIZE-1:0]    <= {Wt, W[(WORDNUM-1)*WORDSIZE-1:WORDSIZE]};
end

代码点评：消息调度 W 是一个 16 字（512 位）的移位寄存器阵列。前 16 轮直接从输入 iDat 装载消息字；之后每轮把 WtROTL1（扩展字）从最高位移入，旧数据依次后移。W_t 的生成公式（σ₁(X) = X 异或 ROTL¹(X) 的四个字异或）就藏在这个”取特定位置 + 异或 + 循环移 1”的组合里。

工作变量与状态控制：

always @(posedge iClk)
    if (loop == 0) begin
    if (iValid) begin
    // 初始化工作变量
    if (!iInitial) begin
    A    <= `H0INIT;
    B    <= `H1INIT;
    C    <= `H2INIT;
    D    <= `H3INIT;
    E    <= `H4INIT;
 
    H0    <= `H0INIT;
    H1    <= `H1INIT;
    H2    <= `H2INIT;
    H3    <= `H3INIT;
    H4    <= `H4INIT;
    end
    else begin
    A    <= H0;
    B    <= H1;
    C    <= H2;
    D    <= H3;
    E    <= H4;
    end
    oReady <= 0;
    loop    <= loop + 1;
    end
    else
    oReady    <= 1;
    end
    else if (loop == 80) begin
    // 计算中间哈希
    H0    <= T + H0;
    H1    <= A + H1;
    H2    <= ROTLB + H2;
    H3    <= C + H3;
    H4    <= D + H4;
    oReady <= 1;
    loop    <= 0;
end

else if(loop < 80) begin
    E <= D;
    D <= C;
    C <= ROTLB;
    B <= A;
    A <= T;
    loop <= loop + 1;
end
else
    loop <= 0;
endmodule

代码点评：

• loop == 0 分支：等 iValid 才启动。iInitial 区分两种启动：新消息用标准初值；连续消息（多块长消息的后续块）则把上一轮的 H₀H₄ 载入 AE 继续算——这就是”链式哈希”。
• loop < 80 分支：每拍把 T、A、B、C 依次往下传（E≤D、D≤C、C≤ROTLB、B≤A、A≤T），这就是 80 轮的迭代主体。ROTLB 是 B 循环左移 30 位——标准里 C 的新值是 ROTL³⁰(B)。
• loop == 80 分支：80 轮结束，AE 加回 H₀H₄，置 oReady，回到 0 等下一块。
• 整个状态机结构清晰：装载 → 迭代 80 轮 → 收尾，全是标准的时钟驱动迭代（第 12 章强调的”硬件式 for 循环”）。

综合后的结构

函数 f_t(B,C,D) 和常数 K_t 都实现为按当前轮次选择输出的 mux：

图 13.2 ft 函数实现：三个函数并行计算，按轮次多路选择

图 13.3 常数生成器实现：按轮次选择预定义常数

由于被选择的都是常数，综合工具还能对某些位做进一步优化。有限域加法用普通加法器实现：

图 13.4 有限域加法：32 位寄存器宽度自动处理模 2³²

13.2 实现结果：参数对速度/面积的影响

在同一代码基上只改参数，面向 Xilinx Spartan-3 综合，结果如下：

表 13.3 Spartan-3 上的速度/面积统计

WORDNUM	WORDSIZE	最大时钟频率 (MHz)	面积 (Xilinx LUTs)
16	32	86	858
32	32	86	860
16	64	78	1728

解读这两组对比：

• WORDNUM（输入字数）几乎不影响面积（858 → 860 LUT）和频率（86 MHz 不变）。它只改变初始装载时 mux 进消息调度的输入数量，只多一个比较和一个多路选择，开销可忽略。
• WORDSIZE（字宽）直接缩放整个数据通路。字宽从 32 翻倍到 64，加法器、函数逻辑、移位网络全部翻倍——面积精确翻倍（858 → 1728 LUT），频率还略有下降（86 → 78 MHz）。

这就是参数化的价值：一条经验规律——“数字型参数”如果只影响控制/选择逻辑，代价趋近于零；如果影响数据通路位宽，代价按比例放大。 设计前想清楚每个参数的作用范围，才能预判综合结果。

常见坑

紧凑迭代架构里最容易犯的错是轮次区间的差一错误（off-by-one）：ft 的选择区间和 Kt 的寄存区间相差一拍（loop < 21 选 ft、loop < 20 寄 Kt），因为 Kt 是提前一拍按轮次寄存的。如果你把两处写成同样的区间，每一轮就会用错段的常数/函数，哈希结果全错——而且仿真时不一定立刻发现，因为前 20 轮恰好两段函数有重叠区间。改参数（比如 WORDSIZE）时还要检查所有手写的位切片是否都基于参数推导，别留死数字。

通关标准：

学完本篇你应该能做到：

1. 说出 SHA-1 的关键规格：32 位字、512 位块、80 轮迭代、160 位摘要；
2. 解释紧凑迭代架构与流水线架构的取舍：面积最小 vs 吞吐率高；
3. 看懂 f_t/K_t 的”并行计算 + 按轮次选择”实现，理解消息调度 W 的移位寄存器工作方式；
4. 解释为什么模 2³² 加法在硬件上”免费”（寄存器截断自动处理溢出）；
5. 区分 define（规范规定的全局常量）与 parameter（可能适配变化的模块参数）在本设计中的分工；
6. 根据表 13.3 预判：改”控制型参数”几乎零成本，改”数据通路型参数”成本按位宽比例放大。

自测：为什么本设计的 SHA-1 几乎无法流水化？

因为消息调度和工作变量更新都迭代复用同一组逻辑资源（紧凑架构），80 轮共享同一套加法器/函数逻辑，上一块消息的哈希没算完之前，下一块无法进入这条唯一的运算链。要流水化就得为每轮（或每组轮次）复制独立的运算逻辑，面积成倍增长——这是速度换面积的反面。

自测：ft 的选择为什么用 loop < 21 而不是 loop < 20？

因为 Kt/ft 的选择要和实际使用它们的拍次对齐：Kt 在前一级按 loop < 20 等区间提前一拍寄存，到 ft mux 真正选出函数时轮次已经推进，区间边界因此错开一拍（21/41/61 vs 20/40/60）。两处边界必须配套设计，否则某几轮会用错常数段。

自测：SHA-1 的模 2³² 加法为什么不需要溢出检查？

因为模 2³² 的数学定义就是”保留 32 位最低有效位、丢弃进位”，而 32 位寄存器保存加法结果时天然发生截断——溢出的进位位直接丢掉，结果自动正确。所以用普通 32 位加法器即可，比标准算术还简单。

自测：本设计中哪些量用 define、哪些用 parameter？为什么？

SHA 规范规定的初值 H0INITH4INIT 和常数表 K0K3 用 define——它们是全局/system 级的”永远不变”常量。WORDNUM、WORDSIZE、WSIZE 用 parameter——虽然规范也定了默认值，但设成参数后，总线宽度不足 32 位等场景只改参数即可适配，且所有信号声明和位操作都从参数推导。

自测：把 WORDNUM 从 16 改到 32 面积几乎不变，把 WORDSIZE 从 32 改到 64 面积精确翻倍，为什么？

WORDNUM 只影响初始装载阶段把多少个输入字 mux 进消息调度，增加的只是一个比较器和一级多路选择，逻辑量可忽略。WORDSIZE 是所有核心运算（加法器、ft 函数、循环移位、寄存器）的位宽，数据通路整体随位宽线性缩放，所以面积精确翻倍（858 → 1728 LUT）。