1. 项目概述在公钥密码学的硬件实现领域性能与面积的权衡是一个永恒的课题。椭圆曲线密码ECC因其在同等安全强度下所需的密钥长度远短于RSA已成为现代安全协议如TLS、数字签名的基石。而在ECC的核心运算——点标量乘法中模平方操作占据了相当大的计算比重。如果你曾尝试设计或优化一个ECC协处理器一定会对模乘法器的庞大面积和关键路径延迟印象深刻。一个直观的想法是既然平方是乘法的特例两个操作数相同其计算过程必然存在冗余能否设计一个专用的“平方器”来替代通用的“乘法器”从而在速度和面积上获得双重收益这正是我们今天要深入探讨的主题。传统的硬件设计往往直接复用模乘法单元来执行平方运算这无疑是一种资源浪费。本文要分享的正是我们团队针对有限域GF(p)上椭圆曲线密码设计的一种高性能、低面积的专用模平方算法及其硬件实现方案。我们从一个最基础的数学观察出发平方运算的部分积矩阵是对称的。基于此我们发展了一套“相同项合并与逻辑组合”方法成功将部分积数量削减了近一半。更进一步我们设计了一种能够同时完成部分积累加和模约减的算法架构并在电路层面利用特定素数的性质进行了大幅简化。最终在0.13µm CMOS工艺下一个256位的模平方运算仅需0.36微秒和17200个逻辑门在性能与面积之间取得了出色的平衡。接下来我将从设计思路、算法核心、电路实现细节以及实际踩坑经验四个方面为你完整拆解这个方案的来龙去脉。2. 核心思路与算法设计拆解2.1 从通用乘法到专用平方的优化契机要理解我们的优化首先要看清通用乘法与平方运算的根本区别。假设我们有一个m位的操作数A其二进制表示为 $A \sum_{i0}^{m-1} a_i \cdot 2^i$。一个标准的m位乘法 $A \times B$ 会产生 $m \times m$ 个部分积partial products每个部分积是 $a_i \cdot b_j$。而平方运算 $A^2$ 中$B A$因此部分积矩阵变成了关于主对角线对称的矩阵。这个对称性就是优化的黄金钥匙。在对称矩阵中非对角线上的项 $a_i a_j$ 和 $a_j a_i$ 是相等的。在硬件实现中计算并累加两个相同的项是纯粹的冗余。我们的第一个目标就是消除这种冗余。通过数学推导具体过程见原论文公式(1)-(3)我们可以将平方运算 $A^2$ 重新表述为 $$A^2 \sum_{i0}^{m-1} a_i \cdot 2^{2i} \sum_{k1}^{2m-3} \left( \left( \sum_{\substack{ijk \ 0 \leq i j m}} a_i a_j \right) \cdot 2^{k1} \right)$$这个形式已经比原始的 $m^2$ 个部分积简化了。对于m8的情况部分积数量从64个减少到了36个节省了约43.75%的计算量。理论上的减少比例由公式 $\frac{1}{2} - \frac{1}{4m}$ 给出当m较大时趋近于50%。但这仅仅是理论上的简化其表达式并不直接适合硬件实现。2.2 关键突破部分积压缩与硬件友好型变换上述简化形式在硬件上仍然不够高效因为它涉及不同权重下多个项的求和。我们的核心创新在于引入了第二个变换使其变得“硬件友好”。我们利用了这样一个逻辑关系 $$(a_i \overline{a_{i1}})2^j a_{i1}2^j (a_i a_{i1})2^{j1} (\overline{a_i} a_{i1})2^j$$ 这里$a_i a_{i1}$ 表示逻辑与操作$\overline{a_i}$ 表示逻辑非。这个变换的精妙之处在于它将同一列中两个可能存在的部分积例如 $a_7 a_6$ 和 $a_7$的加法转换为了一个进位位和一个和位这正好对应了硬件中全加器Full Adder的行为。通过系统性地应用这个变换我们可以将简化后的部分积矩阵如m8时的36个项进一步压缩成仅由4个“压缩部分积”向量P3, P2, P1, P0和少数几个校正项C0, C1, C2组成的集合。为什么这是决定性的因为经过压缩后部分积的数量从m个在简化形式中变成了大约 m/2 个。这意味着后续负责累加这些部分积的加法器阵列的规模可以减半。在硬件中加法器尤其是进位保留加法器CSA树是面积和延迟的主要贡献者。规模减半直接带来了面积的大幅下降和关键路径的缩短。2.3 算法核心同时进行的累加与模约减算法的高效性不止于压缩。在模运算中完成大数平方后还需要进行模p约减即计算 $A^2 \mod p$。传统方法是先计算完整的平方结果T一个最多2m位的数再计算 $T \mod p$。这是一个串行过程且模约减本身也是一个复杂的操作。我们的算法对应原论文Algorithm 1最巧妙的地方在于将累加和约减交织在一起、同时进行。其核心思想类似于Montgomery模乘中的流水线思想但针对平方操作进行了特化。算法概要如下初始化累加器U为0。从最高位的压缩部分积开始依次将其与当前的U相加。关键步骤在每次加法后我们观察U的最高几位例如3位根据其值立即加上一个与模数p的补数相关的项 $4(z_3 \cdot 4p_b z_2 \cdot 2p_b z_1 \cdot p_b)$。这里的 $p_b$ 是素数p的二进制补数。这个操作的目的是逐步地将中间结果“推”向模p的范围内避免其膨胀得过大。将U左移2位这与算法处理部分积的权重有关。重复步骤2-4直到处理完所有部分积。进行最后的校正和输出。这样做的巨大优势它避免了一个完整的、大位宽的约减电路。取而代之的是在每次部分积累加的小周期内进行一个小的、可控的校正加法。这相当于把一个大问题拆解成了许多个小步骤在面积和速度上都非常有利。整个模平方运算只需要大约 m/2 3 个时钟周期而传统方法至少需要m个周期以上。3. 硬件架构与关键电路实现细节3.1 整体架构俯瞰整个模平方模块的顶层架构如图1所示参考原论文图1主要由控制器、压缩部分积生成电路、以及部分积累加与约减电路三大部分构成。控制器是一个有限状态机负责协调数据流和生成所有控制信号。下面我们重点剖析两个最核心的模块。3.2 压缩部分积生成电路的设计与实现这部分电路的任务是根据输入的操作数A实时生成我们之前提到的压缩部分积P‘_i。这是整个设计的基石。其设计充满了巧思核心在于“Xi序列生成电路”。3.2.1 Xi序列的迭代生成我们并不直接硬计算每个P‘i而是先生成一组中间序列Xi公式(8)。观察Xi的构成可以发现X{i} 和 X_{i-1} 之间存在很强的相关性X_{i-1} 几乎是 X_{i} 左移一位并修改个别位得到的。因此我们设计了一个基于移位寄存器和约翰逊计数器Johnson Counter的迭代电路原论文图4。电路工作流程如下初始化将操作数A的低位部分并行加载到一个寄存器中作为初始序列X_n。迭代在每个时钟周期约翰逊计数器状态变化通过一个“约翰逊码转独热码”电路产生控制信号。这个控制信号控制着输入数据流A的高位部分如何被选通并与当前移位寄存器中的值进行组合生成下一个Xi序列。停止经过 m/2 个周期生成全部所需的Xi序列。设计心得使用约翰逊计数器而非二进制计数器来产生控制信号是一个降低电路复杂度的关键技巧。约翰逊计数器的状态变化每次只有一位翻转这使得产生的独热码控制信号更加简单稳定减少了毛刺产生的风险简化了后续组合逻辑。3.2.2 从Xi到压缩部分积P‘_i生成Xi序列后需要通过一个与门阵列AND-gate array和选择器MUX与操作数A的相应位进行“与”操作最终得到压缩部分积P‘_i原论文图6。这里还有一个细节就是校正项C2的合并。我们在电路中巧妙地增加了一个反相器在生成部分积的同时就完成了部分校正避免了额外的校正周期。3.3 部分积累加与约减电路的优化这是算法的执行核心也是速度的瓶颈所在。根据算法1每个周期需要完成一次U U P_i 4*(...)的运算这看起来像一个4操作数的加法。如果直接实现一个4:2的压缩器或两级加法面积和延迟都会比较大。3.3.1 利用素数特性的深度优化我们的第二个重大优化点在这里体现。我们针对中国商用密码标准SM2推荐的256位素数 $p 2^{256} - 2^{224} - 2^{96} 2^{64} - 1$ 进行了特化分析。这个素数具有“稀疏性”在二进制表示中很多位是0。其补数 $p_b$ 也同样具有特定的比特模式。算法中需要根据中间结果U的最高三位(z3, z2, z1)来选择加上的校正值 $4(z_3 \cdot 4p_b z_2 \cdot 2p_b z_1 \cdot p_b)$。由于 $p_b$ 的稀疏性我们通过统计分析发现这个复杂的表达式实际上可以简化为一个比特位有规律变化的向量G[226:0]原论文图7和公式(12)。例如G的很多位直接就是z1, z2, z3的逻辑组合而大段的位是常数0。这意味着我们不需要一个完整的乘法器或查找表来计算这个校正值只需要一个非常小的、由基本逻辑门与、或、非、异或构成的组合电路即可生成向量G。这是一个将算法复杂度“硬编码”到电路逻辑中的经典案例带来了极大的面积和速度收益。3.3.2 两级加法器阵列得益于上述优化原本需要处理4个操作数U, P_i, 4*...的加法可以转化为主要处理2个操作数UP_i和G的加法。因此我们最终采用了一个2级的进位保留加法器CSA阵列原论文图8。第一级CSA处理压缩部分积P_i和上一轮的中间结果第二级CSA则加上由G生成电路产生的校正值。结果存储在一个261位的寄存器Z中用于下一次迭代。注意事项这里寄存器Z的宽度261位是精心设计的它必须足够宽以容纳中间加法可能产生的进位避免溢出。宽度计算需要考虑部分积的最大值、校正值的最大值以及累加过程中的最大可能值。4. 性能评估、对比与实战经验总结4.1 综合结果与横向对比我们在SMIC 0.13µm CMOS工艺和Xilinx Virtex-4 FPGA平台上使用Verilog实现了该设计。ASIC综合结果表明对于一个256位的模平方运算延迟仅需0.36 µs。面积约17200个逻辑门。扩展性通过调整电路可支持384位0.54 µs, 25.7k门和521位0.74 µs, 34.5k门的运算。为了更直观地展示优势我们将其与其他文献中的设计进行对比参见原论文表III。对比维度主要集中在速度时间和面积门数或Slice数量上。与高性能设计对比例如文献[10]采用了4个截断乘法器速度极快~3.6ns但面积巨大629k门是我们的36倍以上。我们的设计在面积效率上具有绝对优势。与小面积设计对比例如文献[4]的面积很小但我们的性能比它快约30%。这体现了我们设计在性能与面积之间取得的平衡。与同类优化思路设计对比文献[1]也采用了类似radix-4交织乘法的思路但我们的部分积压缩和同时约减技术带来了更优的综合结果。核心结论我们的设计不是单纯追求最快或最小而是在一个非常紧凑的面积内实现了接近高端设计的性能。这种“平衡型”设计对于许多嵌入式安全应用如智能卡、物联网节点具有极高的实用价值。4.2 集成至ECC处理器的收益我们将此模平方模块集成到一个简单的ECC点乘处理器原型中。结果显示完成一次256位的ECC点乘仅需0.86ms面积约为77.1k门原论文表IV。与其他ECC处理器相比我们的面积是最小的之一。关键在于复用我们的部分积累加与约减电路图8经过微小调整可以复用来执行模加、模减甚至模乘法通过将输入B也接入部分积生成电路。这种算术逻辑单元ALU的复用极大地节省了整个ECC处理器的面积使得在有限资源下实现完整的公钥运算成为可能。4.3 实操中的经验与避坑指南在实际的RTL编码、综合和验证过程中我们积累了一些宝贵的经验这些是在论文中不会详述的“干货”。4.3.1 控制信号同步与毛刺处理部分积生成电路中的约翰逊计数器和独热码生成逻辑是异步的。虽然约翰逊计数器状态变化平滑但独热码解码逻辑如果设计不当会在计数器状态切换的瞬间产生短暂的毛刺。这些毛刺如果被用作后续时序逻辑的时钟或使能信号会导致灾难性的错误。避坑技巧务必对控制信号如原论文中的O信号进行寄存器打拍Register Pipeline即多用一个时钟周期来同步这些控制信号确保送到数据通路如与门阵列、选择器的控制信号是稳定且无毛刺的。这虽然增加了一个周期的延迟但换来了电路的绝对稳定。4.3.2 关键路径的识别与优化在我们设计的初期版本中关键路径位于部分积累加与约减电路的第二级CSA到寄存器Z的输入之间。这条路径包含了CSA的求和逻辑、以及从Z高位到G生成电路的组合逻辑。优化策略我们对G生成电路的逻辑进行了重新梳理和因式分解使用工具如Design Compiler的综合约束引导其优化。同时将Z寄存器高位的采样时刻提前了半个周期在CSA结果稳定后立即采样而非等到下一个时钟边沿通过插入额外的流水线寄存器来切割这条长路径成功提高了最大工作频率。代价是增加了少量的面积和整体延迟约1个周期但吞吐率反而因为频率提升而增加了。4.3.3 验证策略从算法到门级验证这样一个定制化算术单元极具挑战。我们采用了多层次验证策略算法级建模首先用高级语言如Python或C编写算法1的参考模型用于生成大量的随机测试向量和预期结果。RTL功能仿真在Verilog仿真中将RTL输出与参考模型结果进行对比。重点覆盖 corner cases如操作数A为0、为1、为p-1最大值等情况。形式验证对于控制密集型部分如状态机我们使用了形式验证工具来证明其与一个抽象的状态机模型等价确保没有状态遗漏或死锁。后仿与硬件仿真在FPGA原型上进行实测并与软件库如OpenSSL的计算结果进行交叉验证这是最终信心的保证。4.3.4 可配置性设计虽然论文针对256位优化但一个好的IP核应该具备可配置性。我们在设计时将位宽参数化parameter m 256。对于部分积生成电路中的迭代次数m/2以及累加约减电路中G向量的位宽和生成逻辑都需要根据m进行条件生成generate语句。对于非SM2的素数G生成逻辑需要重新推导和实现这部分是设计中最不“通用”的地方但框架压缩、同时累加约减是通用的。5. 总结与展望回顾整个设计其高性能与低面积的秘诀在于三个层次的创新结合算法层利用了平方的对称性进行部分积压缩架构层创新性地将累加与模约减交织进行避免了庞大的约减器电路层则针对特定素数通过逻辑优化将复杂的校正计算简化为极小的组合电路。这种设计哲学可以推广到其他密码学原语。例如在有限域GF(2^m)上的平方运算也有类似对称性且由于是异或操作优化空间可能更大。此外当前设计是一个独立的模平方模块未来可以探索将其与模乘模块更深度的融合设计一个可配置的“模乘-平方”统一单元根据指令动态切换模式以进一步节省面积。对于有志于从事密码硬件加速的工程师而言这个项目提供了一个完整的范例从数学特性出发推导算法优化将算法映射为高效、并行的硬件结构最后在电路实现层面进行极致的逻辑优化和时序调优。每一个环节都需要深厚的跨领域知识和对细节的执着打磨。希望这篇详尽的拆解能为你打开一扇窗看到密码硬件设计中的精巧与乐趣。