总结归纳了有限域层模乘、模加减、模除运算在算法级和硬件结构级的特点及兼容性。通过对大量主流有限域算法的对比、算法优化、流水加速设计及结构兼容扩展，提出了一种提升模运算结构兼容的模乘优化算法：改进的radix-4交错模乘算法。该算法关键路径短、结构简单，在兼容设计方面有优势，并能实现全流水加速运算，运算效率高，达到高速可重构的设计目的。不同于传统的结构，本文在此模乘基础上直接适配plus-minus模除和模加减，有效解决了资源浪费的问题。该统一模单元在65 nm CMOS工艺下进行综合，面积为0.22 mm2，时钟频率为526 MHz。完成一次576 bit的模乘、模除运算分别用时0.55 μs和2.98 μs。
中文引用格式： 陈琳，唐俊，曲彤洲，等. 高速可重构高资源利用率统一模单元设计与研究[J].电子技术应用，2019，45(10)：58-65.
英文引用格式： Chen Lin，Tang Jun，Qu Tongzhou，et al. High-speed reconfigurable advanced-utilization unified modular operation unit[J]. Application of Electronic Technique，2019，45(10)：58-65.
随着科技的飞速发展，信息技术已经成为了人们生活工作不可或缺的一部分，随之而来的信息安全隐患成为了当前亟待解决的问题。公钥密码体制在信息安全领域的重要性不言而喻，椭圆曲线密码体制在经过多年的研究成熟之后逐渐成为了新一代的公钥密码标准。由于高度密集的运算特性，公钥密码处理器在速度、灵活性、面积资源消耗等方面存在着较大矛盾。本文基于对椭圆曲线体制层次化运算特性的深入研究，通过对底层运算进行算法优化和单元结构兼容，设计了一种基于改进的radix-4交错模乘算法的统一模运算单元，达到提高椭圆曲线处理器运算速度、灵活性和优化底层单元资源消耗的目的。本文对模加减和模除运算进行了优化和基于模乘单元的兼容设计。模除的结构复杂且调用率低，传统的兼容设计思路是在模除单元基础上实现模乘和模加减，或者在模乘基础上扩展结构实现模除。这种设计往往出现资源浪费的问题。本文提出的改进的radix-4交错模乘单元，能够在不增加大位宽加减运算结构的基础上，直接适配plus-minus模除和模加减，有效解决了资源浪费的问题。
1.1 算法兼容性研究
二元域与素数域运算的差异体现在运算规则上，素数域的所有运算都是有进位的，而二元域的运算则约束在对应位之中不存在进位，只是按位异或操作。目前业内出现了很多支持双域操作的结构统一的运算架构，主要的策略有三种，一种为在素数域运算架构基础上加入部分二元域专用的结构，以此来实现双域操作；一种则是在主流的CSA加CPA结构基础上，直接取用CSA的本位作为二元域输出；一种为直接大素数域进位加法器中加入进位屏蔽信号，来实现无进位加法，即二元域加法。总之，二元域与素数域运算无论是在算法层次还是硬件结构层次都具有优秀的兼容性。综上所述，有限域层运算无论是在模运算内部操作还是运算域方面都具有较好的兼容性。图1是模运算系统的兼容关系。如图所示，模乘加完全兼容于模乘与模逆算法。但是，模乘与模逆的兼容性关系根据算法的不同有可能是：模乘完全兼容模逆、模逆完全兼容模乘或二者部分兼容。素数域的运算均能较好地兼容相应的二元域运算。以上主要讨论了有限域层运算在单元数据路径上的结构兼容性。而它们在存储单元方面也有较好的兼容性。有限域层各种运算所涉及到输入数据中间变量情况如表1所示。
由表1中信息可知，三种运算的数据输入均为相同规格输入，可以复用相同的寄存器，中间变量牵扯到的U、V在三种运算中皆为运算位宽加1~3 bit的进位，因此结构完全可以复用，而模逆/除运算中的标志位β、α根据它们在算法中的定义，其极限数据长度有限，与A、B、p、U、V等数据长度不在同一量级。因此三种运算所涉及的寄存器可以达到很高的复用率。为了适配NIST规定的标准，本文设计的运算位宽要兼容576 bit以内的任意长度的双域运算。
1.2 算法分析及改进
如表2所示，算法1所述的基交错模乘，在运算过程中进位链太过复杂，如“C=C+b0·A+b1·2·A(mod p)”要进行三个数据的算术加法和模约减运算。且其中一项“0<b1·2·A<2p”，导致这一步运算的结果0<C<4p，则需要进行C-0·p、C-1·p、C-2·p、C-3·p的四种模约减运算，硬件实现上需要两级CSA一级CPA。
如果能够在累加之前预先计算出b1·2·A(mod p)，就可以将2.1操作的结果约束到0<C<3p而后再约减，从而降低约减的运算复杂度，简化电路。另外考虑到模乘操作本质上是一连串的加法和约减运算的合集，加法与模减的先后顺序并不会影响到最终的结果。即，C=C+b0·A+b1·2·A(mod p)中的b0·A和b1·2·A可以分开进行加和约减。因此可以将乘数B分为奇数位和偶数位进行并行计算，结尾时再将两个部分乘积进行加和约减得到最终结果。该种并行运算操作可以将2.1步所需要的三输入加法器改成二输入加法器，进而缩短关键路径。但是如果奇偶分开之后2.2步的提前约减就会变得相对复杂，此处的操作顺序与流水加速实现方法将在3.2.3进行详细描述。改进的并行2n基交错模乘算法如表3所示。
在算法2中，O为乘数B奇数位扫描的部分和，E则为偶数部分和。在算法2中只有2.3的模约减数据A1的约束范围是0<4A1<4p，需要进行C-0·p、C-1·p、C-2·p、C-3·p的四种模约减运算。其余所有操作均约束在2p以内，不需要C-2·p、C-3·p操作，降低算法约减代价。同时，简化子运算过程势必会降低对应硬件结构的复杂度，将三输入加法器改为并行二输入加法器来实现，降低了数据路径的延迟。需要注意的是，以上两种算法均为双域统一的模乘算法，且之前的分析均为基于素数域的分析。基于二元域的运算相对简单，将所有的进位信号进行屏蔽即可，两者的具体区别将在后续的硬件设计过程中详细描述。综上所述，本小节对两种算法在算法结构上进行了一定的改进，两种类型的模乘算法各有利弊，具体的区别，如运算效率、功耗、面积将在后面的小节进行更为详细的分析比较。对算法2的循环部分分析可知，核心循环部分主要有三个步骤。(1)O←0+b0·A1 mod p与E←E+b1·A2 mod p mod p，完成扫描结果的累加；(2)A1←4·A1 mod p，奇数部分累加值更新；(3)A2←2·A1 mod p与B←B<<2，偶数部分累加值更新与乘数B移位。如果按照这样的步骤分析，每个轮循环需要3个时钟周期才能完成，且步骤(1)与步骤(3)有数据相关性无法完成全流水。若将步骤(1)中的两个累加过程进行分步执行就可以防止这种数据相关性导致的流水障碍。即将算法步骤调整为两步：(1)O←O+b0·A1 mod p，A2←2·A1 mod p，完成奇数位累加及偶数位累加数据更新。(2)E←E+b1·A2 mod p，A1←4·A1 mod p，B←B<<2，完成偶数位累加、奇数位累加数据更新及乘数B移位。进行上述改进之后，步骤(1)与步骤(2)可以流水并行执行。在第一个clk来临时，步骤(1)的O←O+b0·A1mod p、A2←2·A1 mod p与步骤(2)的A1←4·A1 mod p同时执行。这三者产生的结果，分别是O的更新值，用于E累加的A2，用于O累加的A1。第二个clk开始，O←O+b0·A1 mod p需要的O与A1上一周期已经得到；E←E+b1·A2 mod p需要的A2也在上一周期得到；A2←2·A1 mod p所需要的A1已经在上一周期更新；A1←4·A1 mod p所需的A1也在上一周期更新。因此步骤(1)可以和步骤(2)并行运行，但是需要注意的是步骤(2)的运算轮次慢于步骤(1)一个时钟周期。则算法更新为表4所示的算法3。
为使该算法的流水线描述更加详细，图2对该算法每个时钟每个模块的运算以及数据流向进行详细标注描述。其中横向为同一时钟周期完成的操作，纵向为时间流逝方向，箭头表示数据流向。由图2可知，算法3可以实现全流水，相对于蒙哥马利模乘，其运算效率更高。但是由于其数据高低位之间存在严格的数据相关性，难以实现高低位数据之间的并行加速改进。
3.1 模乘单元研究
根据前文对算法3的分析以及流水线的设计，可知radix-4交错模乘算法的核心运算主要包括以下4个：
由上式可知，这四种运算以A1←4·A1 mod p的约减过程最为复杂，需要判断约减3p、2p、p或者不约减，需要三个并行的约减CPA。A2←2·A1 mod p最为简单，可以通过移位代替2A1运算，而后只需要进行是否减p判断即可。这4种运算的具体结构如图3所示。
4种结构思路均为通过并行多路运算提前完成加np约减预计算，而后根据不同加np路径的进位进行判断并选择正确的约减结果。该种结构面积会有一定的增大，但是运算效率极高。前文已经提到了，将原算法1的C=C+b0·A+b1·2·A(mod p)分解为并行运行的O←O+b0·A1 mod p与E←E+b1·A2 mod p。在算法运算逻辑上虽然分开的两者可以并行，但实际上E←E+b1·A2 mod p的累加比O←O+b0·A1 mod p的累加要落后一个周期，即比原来的结构多用2～3个时钟，但是相对整个运算过程的用时，可以忽略不计，同时图3这种改进的结构比原结构的关键路径更短，综合考虑改进后的结构更优化。图3所有结构均为双域统一的模乘运算单元。下面以A1←4·A1 mod p的结构为例，分析二元域运算原理，此时的运算变为A1(x)←x2·A1(x) mod f(x)，即需要进行两次连续的x乘。首先通过field信号将所有CPA中的进位信号屏蔽，同时将CSA中的输入进位全部拉低，将CPA和CSA的本位输出均转化为两个输入数据的异或。而后将两个输入，一个定义为A1(x)<<1，另一个定义为f(x)或0。选择f(x)或0的判断条件是A1(x)左移前的最高位。图4是x乘A1(x)←x1·A1(x) mod f(x)的硬件原理图。二元域的模除运算运用同样的原理，将除2模变成x除运算。
本文设计基于radix-4交错模乘算法的总体硬件结构，如图5所示。
3.2 模除单元研究
根据p-m 算法分析可知，该算法需要经历“数据更新路径裁决”（J-path）和“数据更新”（U-path）两个过程。p-m算法引入了两个变量ε=min(α，β)和λ=α-β，其中α、β分别表示，中间变量A、B的阶，但在算法中不会直接使用α、β，而是使用两者的变化量ε、λ。ε、λ的引入可以代替经典欧几里得模除算法A、B大小的比较，使得J-path的路径复杂度大幅度降低。算法4如表5所示，表6是算法4的判断条件及路径选择。
这种算法在硬件结构设计时较传统蒙哥马利模除算法具有较大优势。该算法的J-path路径结构比较简单，不需要依靠大位宽CPA，从而一定程度上降低了相应延迟，同时也节省了面积资源。但是其判断条件及数据更新的关系较蒙哥马利模乘算法稍显复杂，规律性较低，在控制路径设计时可能会导致复杂度上升。不过这两种结构的关键路径均不在控制路径上，其对单元的整体性能影响微乎其微。而更新过程也分为相对独立的两部分。其中U-pathA主要是运算数据的更新，U-pathB主要是路径裁决信息的更新(B←A，E←O为简单的赋值运算，不作考虑)。通过分析表6中的不同运算可以发现。U-path与J-path之间是有数据相关性的，不能采取流水线划分。J-path的路径延迟由小比特的加减法和数据选择器构成；而U-path则由大位宽的加法器和数据选择器构成。两者的延迟不在同一量级。如果采取流水线加速策略，将J-path和U-path划分为两级流水，会出现运算频率提升有限而控制路径复杂度大幅度提升的情况。因此本文并未对p-m模除算法进行流水线加速设计，而是采取“相似路径整合，不同路径并行，统一数据选择”的策略。即将相似运算进行结构兼容，不能兼容的则并行运算，并根据判断条件选择出最终的正确结果。图6给出了该模除算法的结构简图。主要由I/O接口、控制状态机和数据路径构成。数据路径包括J-path数据更新裁决路径、U-pathA数据更新路径、U-pathB裁决信息更新路径。
面对表6给出的各条路径进行运算分析和归纳分类。由于该算法与radix-4交错模乘算法的兼容性主要体现在U-pathA中，此处着重分析U-pathA的相关操作。U-pathA操作可以归纳为一种算术移位运算Z←(X+Y)/n和三种模移位运算Z←X/2 mod p、Z←X/4 mod p、Z←(X+Y)/4 mod p。其中三种模移位运算在结构实现上比2 bit扫描的蒙哥马利模除算法中的Z←4 X mod p等模约减运算简单得多。因为0<4X<4p需要通过多次p减运算，最终通过进位判断正确结果，消耗的硬件资源是3个三输入加法器。完成(X+Y)/4 mod p需要进行四种运算，而后对结果进行左移两位操作。但是与Z←4 X mod p路径选择方式不同，该运算的选择信号与X、Y、p的末尾2 bit数据有关。因此不需要将这四种运算并行实现后对结果进行选择，而是在输入端就选择+np，仅需一个3输入加法器就可以实现。在此基础上本文设计了如图7(a)所示的U-pathA结构图。U-pathB的结构为小位宽的加法，结构如图7(b)所示。J-path的结构与统一模运算单元的兼容性并不强，且结构简单、占用资源少，在此不进行详细描述。
模除运算的核心运算部分在于U-pathA，其主要运算由一种算术移位运算Z←(X+Y)/n和三种模移位运算Z←X/2 mod p、Z←X/4 mod p、Z←(X+Y)/4 mod p构成。由于运算原理的不同，模移位运算的选择信号由最低位而不是最高位进位确定，因此可以在运算之前就可以根据运算数据的尾数确定运算正确路径。且由于后三种操作不会在一轮运算中同时出现，因此这三者可由同一结构实现。图8为U-pathA模移位运算路径在radix-4模乘单元中的映射。图8中虚线框中的CSA1、CPA3以及输入数据选择器一同完成“Z←X/2 mod p”、“Z←X/4 mod p”、“Z←(X+Y)/4 mod p”等运算。根据表6中对算术移位的路径分析可知，当Z←(X+Y)/n中的n为2时，X+Y的最后1 bit必为0；当n为4时，X+Y的最后2 bit必为00。因此该路径只需一个2输入CPA即可完成，如图8中右虚线框所示。
J-path与U-pathA的路径不在结构兼容考虑范围之内，在此不再详述。如图9所示为基于radix-4交错模乘算法的统一模单元结构图。下面以“X+Y”、“A1←4·A1 mod p”、“O←(O+E)/4 mod p”为例描述统一模运算单元的模加、模除、模乘功能。其中红色部分表示“X+Y”，通过“CSA1+CPA4”与“CPA5”分别实现是否“减p”的运算，而后通过数据选择器完成数据更新。绿色部分为“A1←4·A1 mod p”路径，其“CSA1+CPA1”、“CPA2”、“CPA3”分别完成A1←4·A1-3 p、A1←4·A1-2 p、A1←4·A1-p，而后根据三个CPA的进位确定正确输出结果。“O←(O+E)/4 mod p”的运算路径由“CPA4+CSA1”、“CPA5”以及输入端的数据选择器完成“-p”或“-0p”以及“右移2bit”的操作，其用到的结构与“X+Y”相同，只有输入选择器配置不同，在此不再进行额外标注。
文献[1]～文献[5]中对模运算单元进行了类似的模单元设计。为了性能对比的公平性和可靠性，本文将这些设计在相同的域长度下基于Xilinx Vitex-7 200T FPGA平台进行了逻辑综合，具体结果如表7所示。其中效能定义为：1/(Area×Time)，并对其进行了归一化。
本文提出的统一模运算单元可以实现576 bit以内任意位宽的双域有限域模运算，具有极高的灵活性。文献均有较高的灵活性，可以满足NIST提出的标准模式。而文献[6]、[2]、[4]、[7]为固定结构，不具可重构性，难以满足椭圆曲线密码体制多样化的应用需求。本文提出的统一模运算单元在Vitex-7 2000T的面积为5673 slices。文献[6]、[7]、[4]、[3]比之较小，但是前三者为固定的运算位宽，且不能完成双域运算，在灵活性上与本文不具有可比性。而对于文献[2]，本文无论是在运算频率还是模乘模除的运算时间上均比之优化。本文从算法和硬件设计层次对radix-4模乘算法进行了改进，将结构关键路径分解重新规划算法流程，并实现了全流水设计，在速度上具有一定的优势。本设计的运算频率在上述文献中是最高的，效能除文献[6]的模除外，为最高。但一方面文献[6]中的结构不具有可重构性，另一方面，模除运算的调用频数极低。所以在运算速度方面，本文提出的结构具有较大优势。综上所述，本文提出的统一模运算单元具有较高的运算速度、较好的灵活性，同时在面积资源消耗上进行了模单元兼容优化，并取得了一定的成效。而且该结构可以满足目前国际国内椭圆曲线体制任意标准的底层模运算，能够较好地移植到各种ECC处理器中，具有较好的适应性。前文已经在65 nm CMOS工艺下，通过DC对统一模单元进行了综合，改进的radix-4统一模单元面积为223 761 μm2，时钟周期为526 MHz。但相关研究实现方式大都在FPGA上进行实现，少有进行ASIC测试。目前相关的ECC处理器的ASIC设计时钟周期多在300～500 MHz，而这些ECC处理器的关键路径多由模单元决定。通过比较发现，本文设计的结构在速度和灵活性方面具有优势。通过将本文提出的结构替换到相关ECC处理器中大多能实现一定的工作频率优化。本文提出了一种基于改进的radix-4交错模乘算法的高速可重构统一模单元，该结构支持576 bit以内的任意长度双域可重构模乘、模除和加减运算。不同于传统统一模单元以模除单元为基础的设计，该结构以模乘单元为基础设计实现，具有较高的资源利用率，为统一模运算单元的设计提供了一定的参考。
参考文献
[1] LEE J W，CHUNG S C，CHANG H C，et al.Efficient power-analysis-resistant dual-field elliptic curve cryptographic processor using heterogeneous dual-processingelement architecture[J].IEEE Transactions on Very Large Scale Integration Systems，2013，22(1)：49-61.
[2] DALY A.An FPGA implementation of a GF(p) ALU for encryption processors[J].Microprocessors & Microsystems，2004，28(5)：253-260.
[3] SAKIYAMA K，PRENEEL B，VERBAUWHEDE I.A fast dual-field modular arithmetic logic unit and its hardware implementation[C].IEEE International Symposium on Circuits and Systems，2006.ISCAS 2006.Proceedings.IEEE，2006.
[4] GHOSH S，MUKHOPADHYAY D，ROYCHOWDHURY D.Petrel：power and timing attack resistant elliptic curve scalar multiplier based on programmable，GF(p) arithmetic unit[J].IEEE Transactions on Circuits & Systems I Regular Papers，2011，58(8)：1798-1812.
[5] LIU Z，LIU D，ZOU X.An efficient and flexible hardware implementation of the dual-field elliptic curve cryptographic processor[J].IEEE Transactions on Industrial Electronics，2017，PP(99)：1-1.
[6] MARZOUQI H，AL-QUTAYRI M，SALAH K，et al.A high-speed FPGA implementation of an RSD-based ECC processor[J].IEEE Transactions on Very Large Scale Integration Systems，2015，24(1)：151-164.
[7] MORALES-SANDOVAL M，FEREGRINO-URIBE C，ALGREDO-BADILLO I.An area/performance trade-off analysis of a GF(2m) multiplier architecture for elliptic curve cryptography[J].Computer & Electrical Engineering，2009，35(1)：54-58.
作者信息:
陈 琳，唐 俊，曲彤洲，尹安琪
(信息工程大学，河南 郑州450000)
原创声明：此内容为AET网站原创，未经授权禁止转载。
