可扩展高基蒙哥马利模乘算法及其电路结构

摘要

本发明属集成电路技术领域，具体为一种可扩展高基蒙哥马利模乘算法及其电路结构。本发明是对多字高基蒙哥马利模乘器的改进，其中，每一步对模数N和被乘数B进行左移位操作，对中结果S不作移位操作，使数据通路的流水线级间的延迟从二个时钟周期缩短为一个时钟周期。其电路结构包括用于存放模乘运算3个操作数A、B和N的3个存储器、由第1－第P级处理单元组成的流水线形式的数据通路模块、用于控制整个模乘器运算过程的控制模块和一个先进先出的存储器等。本发明大大提高了模乘运算速度，同时对中间结果的存储单元进行了改进，使其硬件开销减小。

说明书

技术领域

本发明属集成电路技术领域，具体涉及一种改进的可扩展高基蒙哥马利(Montgomery)模乘算法及其电路结构。

背景技术

随着电子通讯技术的飞速发展，信息安全越来越受到人们的关注。为了保障传输数据的安全，人们提出了很多密码算法与协议。因为用软件实现加密算法既耗时又存在安全隐患，所以近年来RSA等密码算法的硬件实现成为信息安全技术研究的一个热点，众多的国内外学者在这方面已经取得很多研究成果，并且已有很多成果应用于各种信息安全产品中。

有限域的乘法运算广泛应用于各种加密算法中，如RSA算法，椭圆曲线密码算法(ECC)等。因为随着密钥长度的增加和需要大量的模乘运算来实现模幂运算，加密运算越来越耗时，所以如何用硬件实现高效率的模乘器成为密码处理器设计的关键。Montgomery算法仅仅通过加法运算和移位操作实现模乘运算，避免了除法运算，因此很适合硬件实现。

Montgomery模乘是一种利用整数的余数表示系统(Residue Number System，RNS)来求模乘的方法，通过操作数到RNS的变换，在RNS除法求模转化为每次扫描乘数后的移位操作，最后再从RNS变换回整数，实现模乘运算。下面对Montgomery模乘算法进行介绍。

算法1.Montgomery模乘算法

Montgomery模乘：MM(A，B，N)＝A×B×R^-1(mod N)，式中，N为n位，A、B也是n位且小于N，R＝2ⁿ，其算法如下：

输入：A，B，N

输出：S

MM Algorithm：

S＝0

for i＝0 to n-1

q_i＝(S+A_i×B)mod 2

S＝(S+q_i×N+A_i×B)/2

end for

if S≥N then S＝S-N

算法中q_i＝(S+A_iB)mod 2，由S、A_i和B三者的最低位决定，它的引入是为了使得累加结果的最低位为0，从而在进行运算S＝(S+q_i×N+A_iB)/2时，也就是要右移一位的时候不会带来误差。从上面的算法可以看出只需要做加法和移位运算就可以得到模乘结果，非常适合硬件实现。

加密算法的模乘运算的操作数都比较大，目前对于ECC算法，密钥长度从128位到256位，对于RSA算法，密钥长度则从512位到2048位，甚至更高位数。目前大部分模乘运算器的硬件设计都是针对固定的密钥长度，也就是说模乘操作数不能超出一个固定位数。为了使同一个电路结构可以根据需要完成任意位宽要求的模乘运算，有参考文献提出了一种采用基于字操作的Montgomery模乘算法。同时为了提高模乘运算的速度，有文献提出了高基的Montgomery模乘算法，即对于被扫描的乘数A每次扫描一位以上，运用布思编码(Booth encoding)进行计算。下面算法是采用多字操作的高基Montgomery模乘算法。

算法2.多字高基的Montgomery模乘算法

输入：A，B，N

输出：S

MWR2^kMM Algorithm：

S＝0

a_-1＝0

for j＝0 to n-1 STEP k

q_Bj＝Booth(a_j+k-1..j-1)

(C_a，.S⁽⁰⁾)＝S⁽⁰⁾+(q_Bj*B)⁽⁰⁾

q_Nj＝S⁽⁰⁾_k-1..0*(2^k-N^(0)-1_K-1..0)mod 2^k

(C_b，S⁽⁰⁾)＝S⁽⁰⁾+(q_Nj*N)⁽⁰⁾

for i＝1 to e-1

(C_a，S⁽ⁱ⁾)＝C_a+S⁽ⁱ⁾+(q_Bj*B)⁽ⁱ⁾

(C_b，S⁽ⁱ⁾)＝C_b+S⁽ⁱ⁾+(q_Nj*N)⁽ⁱ⁾

S^(i-1)＝(S⁽ⁱ⁾_k-1..0，S^(i-1)_w-1..k)

end for

C_a＝C_a or C_b

S^(e-1)＝sign ext(C_a，S^(e-1)_w-1..K)

end for

if S≥N then  S＝S-N

其中模数N的位数为n位，w为处理单元的数据宽度，n＝e*w。有关多字高基Montgomery模乘算法详细内容可参考A.F.Tenca，G.Todorov，and C.K.Koc，“High-radix design of ascalable modular multiplier”in Cryptographic Hardware and Embedded Systems-CHES 2001，C.K.Koc and C.Paar，Eds.2001，Lecture Notes in Computer Science，No.1717，pp.189-206，Springer，Berlin，Germany。

上述的多字高基Montgomery模乘算法的问题在于，如果采用多级处理单元的流水线电路结构，因为S^(i-1)传递到下一级运算必须等到S⁽ⁱ⁾_k-1..0计算出来，因此数据从上一级流水线传递到下一级流水线需要经过两个时钟周期的延迟，这导致模乘运算的速度降低。

发明内容

本发明的目的是提出一种改进的多字高基的可扩展Montgomery模乘算法及其电路结构，使流水线间的延迟只有一个时钟周期，从而提高模乘运算的速度，同时对中间结果的存储单元进行改进使其硬件开销减小。

上文提到的A.F.Tenca设计的模乘器结构是每次对中间结果S进行右移操作，这样上一级流水线的一组结果S^(i-1)要等到S⁽ⁱ⁾_k-1..0计算出来以后才可以传递到下一级参与运算，因此这样设计的流水线之间的延迟为两个时钟周期。当流水线级数较多时这种结构的模乘运算速度会大大降低。本发明提出的可扩展高基蒙哥马利模乘算法，是对上述多字高基蒙哥马利模乘算法(算法2)的改进，其作法是每一步对模数N和被乘数B进行左移位操作，对中间结果S不作移位操作，这样改进了流水线组织形式，使数据通路的流水线级间的延迟只有一个时钟周期，因此可以大大提高运算速度。

有关A.F.Tenca和本发明的流水线算法设计的比较如附图1所示。由图1可以看出，由于本发明的流水线的组织是左移B和N，因此前一级流水线计算得到的S^(i-1)直接进入下一级流水线进行运算而不再需要等待移位，所以本发明的流水线的组织形式可以大大提高模乘运算速度。

本发明提出的模乘乘法器的电路结构如附图2所示，主要包括：3个存储器(RAM)模块：存储器5、存储器6和存储器7，用来存放模乘运算的3个操作数A、N和B；第1-第P级处理单元(PE)组成的流水线形式的数据通路(Datapath)模块1；控制模块10(Controlunit)以及一个先进先出的存储器(FIFO)9。存储器6存放模数N，存储器7存储被乘数B，存储器5存储乘数A。模乘运算时，模数N和被乘数B分别以w位宽的N⁽ⁱ⁾和B⁽ⁱ⁾进入数据通路参与运算，同时乘数A以k+1位的宽度进入各个处理单元。第p级处理单元2输出的中间结果进入FIFO9。FIFO9的输出结果和2w位的零通过一个选择器8进入第一级处理单元4。控制模块10控制整个模乘器的运算过程，包括三个存储器5、6、7的读写、数据通路中数据的流向、FIFO9中的数据读写。

为了减小关键路径延时，运算单元内采用进位保留加法器(CSA)，所以计算中间结果都是冗余形式表示，即加法的结果以和结果(SS)和进位结果(SC)存在。为了减小存储中间结果的FIFO，本发明将最后一级运算单元计算输出的和结果SS和进位结果SC通过一个提前进位加法器(CLA)16加和后再存入FIFO9，这样FIFO9的大小可以减小一半，从而减小了硬件开销。FIFO电路结构如附图3所示，其组成包括：一个提前进位加法器16、一个寄存器15、一个寄存堆14、一个选择器13、一个两输入与门12和一个输出寄存器11。

当bypass信号为高时，进位结果SC通过选择器13直接输出到输出寄存器11，和结果SS通过一个两输入与门12输出到输出寄存器11。当bypass信号为低时，和结果SS和进位结果SC进入提前进位加法器16相加后再通过寄存器15进入寄存器堆14，然后寄存器堆的输出再通过两输入选择器13输出到输出寄存器11。

以基4为例的处理单元(PE)如图4所示，其中取运算位宽为32位。处理单元主要包括Aj编码器模块31和N编码器模块28，两个进位保留加法器27和34，两个反相器模块21和32，若干寄存器、选择器和触发器。被乘数B和模数N通过触发器17和18左移两位，再通过寄存器19输出到下一级处理单元。乘数Aj通过Aj编码模块31后产生信号double、zero和neg，由double、zero和neg控制三输入选择器30和反相器32产生相应的被乘数的倍数。输入SC、SS与反相器32的输出通过进位保留加法器(CSA)34加和，CSA34的输出SS和SC的其中两位通过加法器37求和的结果和N[1]一起控制N编码单元产生信号double、zero和neg，double、zero和neg控制选择器20和反相器21产生相应N的倍数。上一级的CSA的输出SS、SC和反相器的输出通过CSA27加和，同时其结果经过寄存器24后输出给下一级处理单元。

从图4中可以看出，本级处理单元包括4个w位的寄存器，它们用来存储模乘被乘数B⁽ⁱ⁾、模数N⁽ⁱ⁾以及中间运算结果SS⁽ⁱ⁾和SC⁽ⁱ⁾。其中B⁽ⁱ⁾和N⁽ⁱ⁾各左移两位再传递到下一级运算，而中间运算结果SS⁽ⁱ⁾和SC⁽ⁱ⁾则直接经过寄存器进入下一级流水线。

附图说明

图1为本发明和其他参考文献的流水线结构比较。其中，(a)为A.F.Tenca设计的流水线结构，(b)为本发明设计的流水线结构。

图2为可扩展的Montgomery模乘器结构。

图3先进先出存储器结构图。

图4基为4的处理单元(PE)结构图。

图中标号：1为模乘器的数据通路模块，2为第p级处理单元，3为第2级处理单元，4为第1级处理单元，5、6和7为存储器，8为两输入选择器，9为先进先出存储器模块(FIFO)，10为模乘控制模块，11和15为寄存器，12为两输入与门，13为两输入选择器，14为寄存器堆，16为提前进位加法器(CLA)，17、18、23、26、33、36、38和39为D触发器，19和24为寄存器，20和30为三输入选择器，21和32为反相器模块，22、25、29、35、40和41为两输入选择器，28为N编码模块，31为Aj编码模块，27和34为进位保留加法(CSA)，37为加法器。

具体实施方式

下面结合附图进一步描述本发明。

本发明的可扩展高基模乘器的结构可以应用于任何加密强度要求，可以处理任意长位数的有限域的模乘运算。并且可以根据实际应用需要的运算速度和硬件开销调节运算单元的流水线级数，从而达到模乘运算速度和面积的折衷。如附图1的结构所示，如果需要运算速度较快，可以增加流水线的级数、提高处理单元的位宽w，或者采用更高基(如基为2³、2⁴)。反之，如果需要较少的硬件来实现一个对速度要求不高的模乘器，则可以通过减小流水线的级数、减小处理单元的位宽w或采用较低的基。同时对于已经设计好的模乘运算单元，只需要增加用来存储中间运算结果的FIFO，增加运算流水线循环的次数就可以处理更高位数的模乘运算。

附图1所示的流水线结构中，每一竖列代表流水线的一级(即一个PE)，横行每一行代表一个时钟周期。进行模乘运算时，首先N⁽⁰⁾、B⁽⁰⁾以及a0(k+1位)进入第一级流水线，经过一个时钟周期运算得到SS⁽⁰⁾和SC⁽⁰⁾。第二个时钟周期将N⁽⁰⁾和B⁽⁰⁾左移k位，还有SS⁽⁰⁾和SC⁽⁰⁾传递到第二级进行运算，同时N⁽¹⁾、B⁽¹⁾进入第一级进行运算。这样经过p级PE的流水线运算，中间运算结果从第p级的PE输出。下面分两种情况，如果e＞p，中间结果从第p级PE输出时，第1级PE仍然在运算高位的N⁽ⁱ⁾和B⁽ⁱ⁾，所以将输出的中间结果通过CLA加和后存入FIFO，直到N^(e-1)和B^(e-1)通过第1级PE运算后，再将FIFO中的中间结果依次读入流水线第1级PE开始运算。如果e≤p，则当中间结果从第p级PE输出时，第1级PE已经空闲，所以输出的中间结果SS⁽⁰⁾和SC⁽⁰⁾可以通过移位处理后直接进入第1级PE进行运算。

以基4为例的处理单元PE的具体结构如附图4所示，Aj[2:0]通过布思编码后输出三个信号用于选择需要加的B的倍数，其中double为1代表加2倍的B，neg为1代表加负数，zero为1表示加0。同样，当firstcycle＝1时，即N⁽⁰⁾和B⁽⁰⁾运算时，CSA运算的结果的最低2位加和的结果和N[1]通过编码产生所需加N的倍数的选择信号，其中double为1代表加2倍的N，neg为1代表加负数，zero为1表示加0。运算结束后SS⁽ⁱ⁾和SC⁽ⁱ⁾经过寄存器进入下一级PE进行运算，同时B⁽ⁱ⁾和N⁽ⁱ⁾左移2位后进入下一级PE进行运算。

本发明的多字Montgomery模乘器的流水线组织结构可以使每级流水线之间的延迟只有一个时钟周期，对于e≤p时，可以大大提高模乘运算速度，对于e＞p时，由于省去级间寄存器可以减小硬件开销，两种情况下模乘器的速度面积比都提高了将近2倍。