基为64的可扩展模乘法器设计*

刘建国,管文强,杨同杰,杨晓辉

(1.解放军信息工程大学 电子技术学院，河南 郑州 450004；2.72850部队，山东 济南 250031)

模乘运算在公钥密码系统中(例如RSA算法、椭圆曲线密码算法（ECC）以及 ElGamal算法等)有着广泛的应用。Montgomery模乘算法利用易于硬件实现的加法和移位操作来实现大整数的模乘运算，避免了复杂的除法运算，从而大大提高了模乘运算的效率[1]。

本文提出一种高速可扩展的Montgomery乘法器设计方案，该方案是在Tenca提出的Booth-8 Montgomery模乘法器的基础上，采用Booth-64编码进行改进，使速度平均提高了48%。同时对数据通路进行了优化，使得流水线数据通路的平均延迟大大降低。

1 MWR2kMM算法分析

Tenca等人在参考文献[2]中提出一种MWR2kMM算法，MWR2kMM算法如下：

其中，k表示基，X为模乘运算的乘数，Y是被乘数，M是模数。其中，操作数长度为N，部分积用为S表示，Y、M和S分成NW个BPW bit的字进行运算，xj表示 X的第 j bit，Sk(i)表示第 i个字的第 k 位，Ca、Cb表示进位，qYj、qMj分别是在计算部分积过程中Y和M的系数。

核心数据路径采用流水线组织结构，每一级之间用寄存器隔开。每个MMcell单元完成一轮外循环，每个时钟输入 Y、M、SS、SC的一个字参与运算，并把 Y、M和计算出来的SS、SC传递该下一级。为了能使数据路径可伸缩，加入了两个FIFO分别用来存储SS和SC。如图1所示，NS是流水线级数，由面积和时间需求来决定。

图1 数据路径结构

2 基为64的高速Montgomery乘法器设计

Tenca提出的模乘器设计中Booth编码采用的基为8，并且能够支持操作数长度可变的模乘运算，对操作数按字进行运算,缩短了关键路径的延迟，并且使用CSA(Carry Save Adder)提高了整体的系统性能。

通过分析,采用基为8的Booth编码可以将部分积数量减少为原来的1/3，而采用基为64的Booth编码则可以将部分积数量减少为原来的1/6。据此本文对Tenca提出的设计方案进行改进，因此提出基为64的高速Montgomery乘法器。

对于基为64的设计，乘数X每次扫描6 bit，经Booth编码后得到7 bit的输入数据，同时Y和M每次输入一个字。乘数X的Booth编码为：

xi-1是前一组扫描数据的最高位，qY的值表示为：

通过计算可知，qy的取值范围为[-32,32]，这样需要预先计算3Y、5Y、…、31Y的Y奇数倍的值，从而占用大量的存储空间，且电路复杂，显然难以直接应用到模乘器的硬件设计中。为了解决这个问题，可以将qy用一个线性表达式 qY=ha+b来表示，其中h为系数，a、b为变量。

为了确定系数h和变量a、b的取值范围，便于硬件实现，将 a、b 的取值范围限定在集合{±0,±1,±2,±3,±4}中。通过观察，要使qY=32，由于 a、b的值最大为 4，则要求 h≥7;同时，要使 qY=5， a取 1、b最小为-4，要求 h≤9。考虑到硬件的快速实现，系数h取8。则有：

通过对qY进行线性表示，可以将qYY运算转化为计算8(aY)+bY的值。为了进一步简化电路设计，a=3时，可以把3Y拆分成4Y与-Y的和；a=-3时，可以把-3Y拆分成Y与-4Y的和，这种方法同样适用于b。因此对a和b进行再编码，即a=qYa1+qYa2,b=qYb1+qYb2。qY可以分解为a和b，a和b又分解为 qYa1、qYa2、qYb1、qYb2，这样可以避免对3Y进行预计算，大大简化了电路的设计[3]。

对于qM,它取决于 S和 M的最低 6 bit的值，即 qM:=在 k=6时，qM的取值范围为[0,63]。为了进一步简化电路，对qM进行研究发现，当qM在[-32，32]范围取值时,同样可以使S的低 6 bit变为 0。系数 qM从[0,63]转换到 qM′[-32,32]的方法为：

本设计对于 qM′的解码采取与qy相同的办法,首先对 qM′采用线性表示，然后进行二次编码，输出 qMa1、qMa2和qMb1qMb2。处理单元MMcell的结构如图2所示，其中qY解码器用来根据Xj信号进行解码，产生部分积选择信号 qya1、qya2和 qyb1、qyb2,而 qM解码器根据 S和 M 的最低6 bit的值，产生部分积选择信号 qMa1、qMa2和 qMb1、qMb2。 对于部分积的求和运算，本文采用4～2的进位保留加法器，以减少关键路径的延迟，这样输出结果由SS和SC两部分组成。

图2 处理单元MMcell结构

3 性能分析与比较

对于基为64的Montgomery乘法器,计算一次模乘运算的总时钟周期数时，需要考虑NW≤2NS和NW＞2NS两种情况，NW代表操作数所含的字数。一个MMcell需要两个时钟周期的执行时间，因此一个字经过流水线的总时钟周期数是2NS+1。由于每次可处理6 bit，所以需要轮循环。完成一次模乘运算的时钟周期数为：

从表1可以看出，在不同条件下，本文的设计在性能上平均比Tenca的设计提高了48%。本文采用字长32 bit，级数 NS=8实现基为 64的 Montgomery乘法器，且使用Verilog HDL语言实现上述设计，并使用ModelSim对设计进行了仿真验证；基于SMIC 0.18 μm CMOS标准数字逻辑工艺，利用Design Compiler进行了综合设计，结果显示频率达到251 MHz，面积为37 381门。

表1 基为8和基为64的Montgomery乘法器在不同的NS和NW下的性能比较

顾叶华在参考文献[4]中对Tenca提出的流水线结构进行了优化，提出了一种基为4的Montgomery乘法器方案。面积和速度的比较如表2所示。从表中可以看出，本设计在512 bit和1 024 bit下具有最小的时间×面积的值，综合性能最优。

本文对Tenca提出的基为8的可扩展Montgomery模乘器进行改进，采用了更高的基为64的设计，进一步减少了部分积的个数，缩短了运算时间。与Tenca在参考文献[2]中的设计相比，时钟周期数平均减少了48%，并且缩短了关键路径的延迟相比，综合性能具有明显地提高。

表2 面积和速度性能比较

[1]KOC C K,ACAR T,KALISKI B.Analyzing and comparing Montgomery multiplication algorithms[C].IEEE Micro,1996:26-33.

[2]TENCA A F,TODOROV G,KOC C K.High-radix design of a scalable modular multiplier[A].Cryptography Hardware and Embedded System-CHES 2001.Springer Verlag,Berlin,Germany,2001:189-205.

[3]颜晓东，李树国.二次Booth编码的大数乘法器设计[J].清华大学学报（自然科学版），2007，47(10)：1681-1684.

[4]顾叶华，曾晓洋，赵佳，等.一种新型操作数长度可伸缩的模乘器 VLSI设计[J].计算机工程,2007，33(19)：227-229.