可扩展数字串行求逆器：为超低功耗密码学硬件“瘦身”

1. 项目概述：为超低功耗设备“瘦身”的密码学核心引擎

在无线传感器网络、射频识别标签这些巴掌大小的设备里塞进一套完整的公钥密码系统，一直是个让硬件工程师头疼的难题。这些设备通常只有指甲盖大小的芯片面积和微瓦级别的功耗预算，却要求实现银行级的安全通信。问题的核心，往往卡在一个看似简单的数学运算上：有限域求逆。在椭圆曲线密码学中，一次点加或点倍运算需要调用数十次域运算，而一次求逆的耗时和能耗，可能比十几次乘法加起来还要高。因此，设计一个面积小、功耗低、又能满足实时性需求的求逆器，就成了在资源“螺丝壳里做道场”的关键。

传统的硬件求逆架构，要么是追求极致速度的二维脉动阵列，面积开销随域大小m呈平方级增长，对于m=233这样的常用安全参数，芯片面积根本吃不消；要么是追求极致面积的一维比特串行结构，虽然面积是线性的，但吞吐率低到令人发指，可能一次签名运算要等上好几秒，这在许多实时应用中是不可接受的。数字串行架构试图在面积和速度之间找一个平衡点，但以往的方案要么扩展性差，要么处理单元间的通信开销太大，在超低功耗场景下，通信带来的动态功耗和布线面积同样是不可忽视的成本。

我这次要拆解的，正是一篇试图彻底解决这个平衡问题的经典论文。它提出了一种基于改进扩展欧几里得算法的可扩展数字串行求逆器结构。这个设计的精妙之处在于，它通过一种非线性的调度与投影方法，将算法计算图映射到一个固定大小的处理单元阵列上。无论域大小m如何变化，阵列中处理单元的数量只取决于一个可配置的参数T，而与m无关。这意味着，你可以为一块固定面积的芯片设计一个核心，通过调整T来适配不同安全等级（不同m值）的密码算法，而无需重新设计整个硬件。实测下来，在45纳米工艺下，针对m=233的典型场景，与当时最先进的数字串行设计相比，它在面积上能减少83%到88%，能耗上能降低75%到86%，虽然吞吐率有所牺牲，但对于许多“慢工出细活”的超低功耗场景来说，这无疑是更优的选择。

2. 核心算法与硬件映射原理拆解

2.1 改进的扩展欧几里得算法：从数学到比特操作

有限域GF(2^m)上的求逆，即对于给定的域元素A(x)，找到另一个元素Â(x)，使得 A(x) * Â(x) ≡ 1 mod Q(x)，其中Q(x)是一个m次不可约多项式。扩展欧几里得算法是解决这个问题的经典方法，但其在硬件实现时，每一步都需要进行多项式度数的比较和长除法，控制逻辑复杂，关键路径长。

论文采用的是一种由Yan等人改进的比特级EEA算法。这个算法的核心“骚操作”在于，它用了一个环形计数器D来巧妙地绕开了耗时的度数比较。算法维护四个m位的寄存器R, S, Y, H，以及一个控制位sign。初始时，R被装载为不可约多项式Q(x)的系数（去掉最高位的1），S被装载为输入多项式A(x)的系数，Y初始为0，H初始为1（对应多项式x^m）。算法经过2m-1次迭代后，H寄存器中存储的便是求逆结果Â(x)的系数。

注意：这里有一个关键细节，寄存器Y和H的比特顺序与R、S是相反的。R和S的最高有效位存储的是多项式的最高次项系数，而Y和H的最低有效位存储的才是多项式的最高次项系数。这个“反向存储”的约定在理解数据流和硬件连线时至关重要，如果搞反了，整个计算都会出错。

算法的比特级操作体现在双重循环中：外层循环i迭代2m-1次，内层循环j迭代m次（处理每个比特）。在每一次(i, j)的运算中，根据当前S寄存器的最高位(s_{m-1})和上一轮的sign位，生成两个控制信号c1和c2。这两个信号决定了R, S, Y, H四个寄存器当前比特是进行交换、保持，还是进行模2加（在GF(2)中等同于异或XOR操作）。同时，sign位和环形计数器D也会根据规则更新。整个算法的数据流向形成了一个非常规则的计算依赖图。

2.2 非线性调度与投影：将计算图“折叠”进芯片

直接实现这个双重循环的算法，就是一个完全的比特串行结构，速度太慢。而如果完全展开，就是m*m个处理单元组成的二维阵列，面积太大。论文的核心贡献在于引入了一种非线性调度和投影的方法，在这两个极端之间找到了一个可调的、高效的折中点。

首先，算法中的每个计算节点（对应(i, j)的一次操作）被放置在一个二维的依赖图中。非线性调度函数S为每个节点分配一个时间步t。这个函数的设计非常巧妙：它不再是简单的t = i + j，而是引入了参数T（即我们希望每个时钟周期并行处理的计算节点数）。调度函数确保了在同一个时间步t，最多有T个节点可以同时被计算。这就天然地将计算过程划分成了一个个“时间片”，每个时间片的工作量是可控的T。

实操心得：选择T值是一个设计权衡。T越大，每个时钟周期能处理的数据越多，完成整个求逆运算所需的时钟周期数越少（吞吐率越高），但需要的处理单元也越多，面积和功耗越大。T越小则反之。对于超低功耗设备，通常T不会选得太大，论文中举例的T=64是在m=233下的一个折中，实际设计中需要根据目标频率、面积预算和功耗约束来精确评估。

当m不是T的整数倍时，会出现某些时间片内可并行的节点数不足T个，导致硬件利用率不高。论文采用了一个很实用的技巧：将m“填充”到最近的T的整数倍m‘。具体做法是在R, S, Y, H寄存器的低有效位端补零。这相当于在计算中引入了“虚拟”的比特，这些比特的运算结果不影响最终结果（因为补的是零），但保证了硬件在每个时钟周期都能满负荷运行，简化了控制逻辑。

接下来是关键一步：投影。我们有了一个在时间和空间（节点索引j）上展开的计算图，现在需要把它映射到物理的硬件处理单元上。投影矩阵P的作用，就是将多个在空间维度j上不同、但在调度时间上相同的计算节点，映射到同一个物理处理单元上。论文探讨了两种投影矩阵P1和P2，其中P1产生的架构控制复杂度更低，更适合VLSI实现。

通过P1投影后，我们得到了一个由T+1个处理单元组成的线性脉动阵列。其中，PE_0到PE_{T-1}是负责主要运算的数据处理单元，PE_T是一个特殊的控制单元，负责生成广播给所有PE的控制信号c1, c2和更新sign位。神奇的是，无论m是多少，这个阵列的规模只由T决定。这就是“可扩展”的含义：硬件核心是固定的，通过改变输入数据的组织方式和计算序列的长度（由m决定），来适应不同的安全需求。

3. 可扩展脉动阵列架构详解

3.1 整体架构与数据流

映射后得到的可扩展脉动阵列结构清晰而优雅。T个数据处理单元(PE_0 ... PE_{T-1})和一个控制单元(PE_T)排成一列。数据在这些PE之间以流水线方式流动。

每个数据处理单元PE_j（0 ≤ j ≤ T-1）内部包含几组FIFO（先入先出）缓冲区，用于存储它所负责的那一部分R, S, Y, H的比特位。具体来说，每个PE存储 m‘/T 个比特。由于采用了非线性调度，这些比特并不是连续地属于同一个寄存器，而是按照 (j = k mod T) 的规则被分配到各个PE。这意味着，一个完整的m位寄存器，其比特被“交织”地存储在了T个PE中。

控制单元PE_T则相对简单，它主要包含生成c1, c2的逻辑、更新sign位的逻辑，以及一个存储sign初始值的FIFO。c1和c2信号在每个迭代周期i生成后，会广播给所有T个数据处理单元。

数据输入和输出的过程是精心编排的。在初始的(m‘/T)+1个时钟周期内，输入多项式A(x)和不可约多项式Q(x)的系数，按照特定的时序被加载到各个PE的FIFO_S和FIFO_R中。计算开始后，每个PE在每个时钟周期接收来自左侧PE（或自身FIFO）的比特，根据广播来的控制信号执行算法规定的操作（可能包括异或、选择等），然后将结果写入自身的FIFO或传递给右侧的PE。经过 (2m-1)(⌈m/T⌉+1) 个时钟周期后，结果Â(x)的系数会从H的FIFO链中依次输出。

3.2 处理单元内部设计要点

图4展示了PE_T和PE_j的内部细节，这里蕴含着许多降低面积和功耗的巧思。

对于数据处理单元PE_j：

1. 精简的运算逻辑：核心是一个多路选择器(MUX)网络和少量的异或门(XOR)。控制信号c1和c2直接决定了数据路径。例如，当c1=1时，S的新值来自R的旧值与S移位值的异或；否则，S只是简单移位。这种设计避免了复杂的算术逻辑单元，面积很小。
2. 基于FIFO的存储：使用FIFO而不是寄存器堆来存储中间变量。在脉动阵列中，数据流是规则的，FIFO这种顺序访问存储器比随机访问的寄存器堆面积更小，控制也更简单。每个FIFO的深度正好是 m‘/T，与PE处理的数据块大小匹配。
3. 本地化通信：每个PE只与左右相邻的PE有单比特的数据连接。这种极简的互连结构极大地减少了全局布线，而全局布线在深亚微米工艺下是面积和功耗（尤其是动态功耗）的主要贡献者之一。

对于控制单元PE_T：它的核心是一个移位寄存器和一个比较逻辑，用于生成环形计数器D和判断其最低位以更新sign。它也需要一个深度为 m‘/T 的FIFO来维持sign位的流水线。值得注意的是，控制信号是广播的，这虽然引入了一些布线，但由于信号是单比特的，且控制逻辑简单，其开销远小于在二维阵列中复杂的控制网络。

注意事项：在实现FIFO时，需要特别注意其清零和加载的控制时序。在初始加载阶段，FIFO_H需要被清零，而FIFO_S, FIFO_R, FIFO_Y需要加载初始值。这个控制信号必须与数据输入时序严格同步。在实际的硬件描述语言代码中，这部分控制逻辑是容易出错的地方，建议单独编写一个清晰的状态机来管理初始化阶段。

4. 设计复杂度分析与对比

4.1 理论复杂度模型

论文从架构图中推导出了面积、延时和吞吐率的理论模型。

• 面积复杂度：主要来自T+1个处理单元。每个PE包含常数数量的逻辑门（与门、异或门、多路选择器）和 O(m‘/T) 比特的存储单元（FIFO）。因此，总面积为 O(T + m‘)。由于m‘ = T⌈m/T⌉，所以面积可表示为 O(T + m)，这与传统的数字串行架构O(dm)（d为数字大小）在形式上类似，但常数项和实现细节更优。
• 延时（Latency）：完成一次求逆运算所需的时钟周期数为 L = (2m - 1)(⌈m/T⌉ + 1)。可以看到，延时与m的平方成正比，但与T成反比。增大T可以显著减少时钟周期数。
• 关键路径：在一个PE内部，关键路径通常是一个多路选择器链加上一个异或门的延时，即 τ = 2 * T_MUX。这是一个非常短的路径，意味着该设计可以达到很高的工作频率，这对于降低动态功耗（P_dynamic ∝ C * V^2 * f）非常有利，因为可以在较低的电压下运行以节省功耗。

4.2 综合结果与竞品对比

纸上谈兵终觉浅，论文最有力的证据来自基于45nm CMOS工艺库的综合结果。他们选取了域大小m=233（一个常用的椭圆曲线安全参数），并设置了T=64。作为对比，他们实现了当时文献中报道的两种高效数字串行求逆器设计。

下表清晰地展示了对比结果（基于论文数据整理）：

结果解读与设计权衡：

1. 面积优势碾压：提出的设计面积仅为竞品的11.7%到17%，减少了83%-88.3%。这主要归功于极简的PE设计、FIFO存储替代寄存器堆、以及高度本地化的互连，极大地减少了布线面积和触发器数量。
2. 能耗优势显著：在超低功耗设备典型的工作频率100kHz下，总功耗和单次运算能耗都大幅降低（75%-85.7%）。低功耗来源于三个方面：一是面积小，静态漏电功耗低；二是关键路径短，可以在更低的电源电压下工作（动态功耗与电压平方成正比）；三是简单的控制和无复杂全局信号，减少了不必要的翻转活动。
3. 吞吐率的牺牲：这是为换取超低面积和功耗所付出的代价。竞品设计在350个周期内完成运算，而本设计需要14553个周期，相差40多倍。这是因为本设计本质上是高度串行化的，T=64意味着每个时钟周期只处理约64个比特的“窗口”，而整个计算需要遍历m比特长达2m-1轮迭代。因此，这个设计绝对不适合高性能场景，但其超低的面积功耗特性，正是RFID标签、无线传感器节点等设备所梦寐以求的。在这些应用中，一次密码操作可能几秒甚至几分钟执行一次，极低的待机功耗和芯片成本才是首要考量。

实操心得：在选择密码硬件加速方案时，必须明确应用场景的优先级。是追求每秒成千上万次操作的服务器端，还是追求纽扣电池续航数年的传感器节点？本文的设计是后者的典范。在ASIC设计流程中，综合后一定要在目标频率（如100kHz）下进行功耗分析，而不是在最大频率下。因为低频下的功耗更能反映超低功耗设备的真实工作状态，此时静态功耗可能占主导，而小面积设计恰恰能最小化静态功耗。

5. 实际实现考量与问题排查

5.1 参数选择与设计空间探索

T值是这个设计中最关键的“旋钮”。如何选择T？

1. 面积约束：T直接决定了PE的数量。如果你的芯片有严格的面积预算，那么T就是首要限制条件。
2. 吞吐率要求：根据公式 L = (2m-1)(⌈m/T⌉+1)，可以估算出完成一次运算的时间。结合系统对密码操作的最大容忍延时，可以反推出T的最小值。
3. 工艺与频率：关键路径延时固定（主要是2个MUX的延时）。在选定工艺后，你可以确定一个安全的工作频率。��超低功耗设计中，我们通常故意在远低于最大频率的时钟下工作以降低电压。此时，吞吐率由频率和延迟共同决定。 一个实用的方法是：根据面积预算确定一个T的范围，然后在这个范围内，绘制出“面积-吞吐率”和“面积-能耗”的帕累托前沿曲线，根据你的项目侧重点选择最优解。

5.2 常见实现问题与调试技巧

1. 初始化序列错误：这是最常见的错误。FIFO的加载、清零，以及控制信号MUX的选择，在初始 (m‘/T)+1 个周期必须严格按照算法描述进行。一个有效的调试方法是编写一个简单的Testbench，将前几十个时钟周期每个PE的输入输出都打印出来，与手工计算或软件模型计算的中间结果逐周期比对。
2. 控制信号广播的时序：c1, c2, sign 这些信号需要在一个周期内稳定并传递到所有PE。在物理设计时，要特别注意PE_T到最远端PE的布线延迟，可能需要插入缓冲器来保证时钟偏差满足要求。在低速（如100kHz）下这个问题不突出，但在尝试提高频率时需要重点检查。
3. 结果输出对齐：输出结果H并不是在最后一个周期一次性出现，而是在最后 (m‘/T) 个周期内，从各个PE的FIFO_H中依次输出。需要设计一个简单的输出收集电路，按照正确的顺序将这些分散的比特拼接成完整的m位结果。验证时，务必检查输出序列的完整性和顺序。
4. 针对不同m的配置：设计的优势在于可扩展性。当m改变时，除了输入数据位宽和计算周期数，硬件不需要改动。但是，你需要重新计算初始化加载的周期数、结果输出的窗口周期等参数。建议将这些参数做成可配置的寄存器，通过一个简单的配置接口在启动前写入，从而让同一个硬件核支持多种曲线参数。

5.3 超越求逆：架构的通用性思考

虽然论文聚焦于求逆运算，但其所采用的非线性调度与投影方法具有更广泛的启示。任何具有类似规整二维依赖图的计算（例如，某些类型的矩阵运算、多项式乘法、滤波算法），理论上都可以套用这个框架，将其映射到一个可扩展的、通信开销极低的线性脉动阵列上。对于硬件设计者而言，掌握这种从算法依赖图到高效硬件架构的转换方法，是提升设计水平的关键。下次当你面对一个计算密集、资源受限的算法时，不妨先画出它的依赖图，想想能否用类似的方法给它“瘦身”。

这个设计给我最深的体会是，在硬件设计领域，尤其是面向极致约束的环境，“简单”和“规整”往往能带来最大的收益。用最直接的逻辑、最局部的通信、最匹配的存储，去实现一个核心算法，摒弃所有不必要的复杂性和通用性，最终得到的可能不是性能最强的，但一定是能让你在严格的面积和功耗预算下，把产品做出来的那个最踏实可靠的方案。在超低功耗的战场上，有时候“活下去”比“跑得快”更重要。