摘 要： 有限域的运算是密码学的基础，而在有限域的运算中模乘运算是核心运算之一。为此，分析了模乘运算的原理及特点，使用Verilog HDL设计模乘电路，通过FPGA实现了基于有限域的模乘运算。电路应用双沿寄存器结构，并且规模小、速度快、功耗低能实现有限域通用模乘运算对加密算法的硬件实现具有实际价值。
关键词： 有限域； 模乘； 模2运算； 硬件设计
中图分类号：TP309 文献标识码：A 文章编号：1006-8228（2012）04-21-03
Design and implementation of a modular multiplication circuit of low power and high speed
Cheng Guihua1,2, Qi Xuemei1,2, Luo Yonglong1,2, Zuo Kaizhong1,2
（1. College of Mathematics and Computer Science， Anhui Normal University， Wuhu， Anhui 241000， China；
2. Research Center of Network and Information Security， Anhui Normal University， Anhui Normal University）
Abstract： The finite field arithmetic is the base of cryptography and modular multiplication is one of core operations. Based on analysis of finite field modular multiplication, the authors design a modular multiplication circuit in Verilog HDL, and its modular multiplication is realized by FPGA in finite fields. The circuit uses double-edge-triggered register, and realizes small-scale, low power consumption and high speed. It implements modular multiplication to reduce its scale and it has practical value for hardware implementation of encoding algorithm.
Key words： finite fields； modular multiplication； modular 2 arithmetic； hardware design
0 引言
加密是保证信息安全的主要途径之一，被广泛应用于信息技术的各个方面，如智能卡、手机银行、无线局域网和传感网等便携式设备中。因此设计快速、低功耗的硬件加密模块至关重要。加密算法基于有限域的运算，而模乘运算是有限域运算的核心运算之一，其运算速度对加密算法的实现起着重要作用，其功耗的高低会直接影响使用性能。
模乘运算是基于有限域的多项式乘法的模运算，一般通过移位和模2加运算代替多项式乘法和除法运算。文献[1-5]从算法的角度对如何提高模乘运算效率进行了讨论。本文分析了模乘运算的原理与特点，综合软硬件知识设计了一种小规模、快速、低功耗的模乘运算电路模乘电路使用Verilog HDL设计，在Quartus II开发软件中仿真，通过FPGA实现。电路引入双沿工作的寄存器，在系统工作时钟频率不变的情况下，不仅使模乘运算的速度加倍，还可使电路的功耗大大降低。
1 模乘算法
有限域GF(2n)上二进制多项式系数运算以2为模，运算时不考虑进位和借位。模2加减是按位执行“异或”运算，模2乘除则采用模2加减计算部分积和部分余数。若被乘数f(x)、乘数g(x)、模m(x)多项式定义如式⑴⑵⑶所示：
则有限域GF(2n)上模乘运算如公式⑷[6]所示。
若直接根据公式⑷在GF(2n)上执行多项模乘运算，需要用到多项式乘法和除法运算，时间开销较大，也难以用软件硬件实现[7-8]，因此我们将式⑷变换为式⑸[6]：
式⑸表明：xi×g(x)多项式模乘运算可以重复使用i次式⑸来实现。这样一来，在有限域GF(2n)上，式（4）定义的多项式模乘运算可以直接使用两个n位的二进制整数相乘，并通过多个中间结果作移位和模2加来实现。
2 模乘运算器电路设计与实现
2.1 电路设计
基于式⑸的模乘运算器的电路结构如图1所示。加电后电路按如下时序工作：
第一步，当Clr端收到负脉冲“ ”时，fxl、gxr和fgxm寄存器异步装入初值（如图1所示）。
第二步，当寄存器fxl的最高位为“1”，fxl mx →fxm，实现模乘运算；否则fxl→fxm。当寄存器gxr的最低位为1时，fgxm fxm→fxm1；否则fgxm→fxm1。
第三步，在时钟信号的作用下，电路同时完成如下三项工作：一是将fxm1存入fgxm寄存器；二是将fxm左移一位（低位补“0”）存入fxl寄存器；三是将gxr寄存器内容右移一位（高位补“0”）。重复第二、三步直到gxr寄存器为全“0”时，运算结束。fgxm寄存器的内容为所需的多项式模乘运算的乘积，通过fgx输出。
图1 模乘运算器电路结构示意图
模乘运算电路的规模取决于所采用的控制电路的规模。在图1中，将模运算（fxm）和左移操作合二为一，减少了电路的运算步骤与工作延时；利用乘数寄存器gxr右移时空出的高位补“0”，当gxr寄存器的值为全“0”时完成一次模乘运算。这样设计，一方面不需要额外增加控制电路，减少了模乘运算器电路的规模；另一方面加速了运算过程，完成一次模乘运算平均只需n/2个时钟边沿信号。
2.2 快速低功耗设计
模乘运算器的主要逻辑部件之一是寄存器，时钟信号是寄存器必备的输入信号之一。传统的寄存器仅对时钟的上升沿或下降沿敏感，十个单边沿触发器[9]，在另一方向上的时钟跳变成为一种冗余跳变，所对应的功耗也是多余的。如果能对时钟信号的两个边沿都能敏感，不仅可以降低电路的功耗，还可以使模乘运算器的运算速度加倍，从而提高系统的效率。依据文献[10]的设计思想和主从触发器的工作原理，我们利用“与非“门”组成双沿触发器的寄存器并用于模乘运算器器电路中（如图1中的fxl、gxr和fgxm寄存器），使模乘运算速度加倍、功耗减半。两种模乘运算器的工作波形如图2所示。
由图2可知，相对于单边沿寄存器组成的模乘运算器而言，在相同频率时钟的作用下，双边沿寄存器组成的模乘运算器运算速度加倍，同时避免了时钟冗余跳变，从而大幅降低了模乘运算器电路的功耗。
(a) 单边沿模乘运算器波形图
(b) 双边沿模乘运算器波形图
图2 单、双边沿乘法器时序对比图
3 仿真波形与实例分析
我们应用Verilog HDL语言设计基于有限域高速、低功耗的模乘运算器电路模型，并用Visual FoxPro语言进行了软件验证，证明所有运算结果完全正确。选择EP2C5Q208CN芯片，在Quartus II开发工具中配置、综合和优化后通过Quartus II中的Programmer工具下载到芯片中，可以快速稳定地实现模乘运算操作且占用面积小，达到预期设计目标。
图2是f(x) =x6+x4+x3+x2+x+1，g(x) =x5+x4+x2+1在有限域GF(28)中以m(x)=x8+x4+x3+x+1为模的多项式模乘运算仿真波形；模乘运算过程如表1所示。
在有限域中,每个多项式都可以表示为二进制整数，反之亦然，也就是说m(x)=x8+x4+x3+x+1等价于二进制数100011011B或十六进制数11BH，f(x)=x6+x4+x3+x2+x+1=5FH、g(x)=x5+x4+x2+1=35H。图2中的各数值为相应多项式系数的十六进制表示。
由表1可知，计算步骤1、2在单边沿模乘运算器中需要使用T1和T2两个时钟的上升沿，而在双边沿模乘运算器中只需要使用一个时钟T1的上升沿和下降沿完成，这不仅加速了运算过程，同时也减少了时钟的冗余跳变，降低了功耗。
表1中计算步骤1为初始化操作。计算步骤2中，首先因gxr(x)=x5+x4+x2+1=35H多项式系数的第0位为1，模乘部分积fgxm(x)=fgxm(x)+fxm(x)=0+x6+x4+x3+x2+x+1=x6+x4+x3+x2+x+1=5FH；其次fxm(x)、gxr(x)分别左移和右移一位得到fxl(x)=x7+x5+x4+x3+x2+x=0BEH、gxr(x)=x4+x3+x1=1AH、并因移位前fxm(x)多项式系数的最高位为0，fxm(x)=fxl(x)=x7+x5+x4+x3+x2+x，这为下一步骤中模乘部分积的计算准备好数据；重复上述操作，直到多项式gxr(x)=0，通过finsh输出正脉冲“ ”，表示完成一次模乘运算，运算结果通过fgx输出。
表1 模乘运算过程（f(x)=x6+x4+x3+x2+x+1、g(x)=x5+x4+x2+1、m(x)=x8+x4+x3+x+1）
[[步骤\&fxl(x)\&gxr(x)\&fxm(x)\&fgxm(x)\&时钟
（图2（a））\&时钟
（图2（b））\&1\&=x6+x4+x3+x2+x+1\&=x5+x4+x2+1\&=x6+x4+x3+x2+x+1\&=0\&T1↑\&T1↑\&2\&=21fxm(x)
=x7+x5+x4+x3+ x2+x\&=2-1gxr(x)
=x4+x3+x1\&=fxl(x)
=x7+x5+x4+x3+ x2+x\&=fgxm(x)+ fxm(x)
=x6+x4+x3+x2+x+1\&T2↑\&T1↓\&3\&=21fxm(x)
=x8+x6+x5+x4+ x3+ x2\&=2-1gxr(x)
=x3+x2+1\&=fxl(x) mod m(x)
=x6+x5+x2+x1+1\&=fgxm(x)
=x6+x4+x3+x2+x+1\&T31↑\&T2↑\&4\&=21fxm(x)
=x7+x6+x3+x2+x1\&=2-1gxr(x)
=x2+x1\&=fxl(x)
=x7+x6+x3+x2+x1\&=fgxm(x)+ fxm(x)
=x5+x4+x3\&T4↑\&T2↓\&5\&=21fxm(x)
=x8+x7+x4+x3+x2\&=2-1gxr(x)
=x1+1\&=fxl(x) mod m(x)
=x7+x2+x1+1\&=fgxm(x)
=x5+x4+x3\&T5↑\&T3↑\&6\&=21fxm(x)
=x8 +x3+x2+x1\&=2-1gxr(x)
=1\&=fxl(x) mod m(x)
=x4+x2+1\&=fgxm(x)+ fxm(x)
=x7+x5+x4+x3+ x2+x\&T6↑\&T3↓\&7\&=21fxm(x)
=x5+x3+ x1\&=2-1gxr(x)
=0\&=fxl(x)
=x5+x3+ x1\&=fgxm(x)+ fxm(x)
=x7+x5+x3+ x1\&T7↑\&T4↑\&8\&因gxr(x)=0，模乘运算完成，fgxm(x) = x7+x5+x3+ x1为模乘的乘积\&]]
4 结束语
通过“移位”和“异或”基本逻辑实现有限域模乘运算，电路规模小、运算效率高；电路引入双沿工作的寄存器，在系统工作时钟频率不变的情况下，不仅使模乘运算的速度加倍，还可避免时钟信号的冗余跳变，使电路的功耗大大降低。
参考文献：
[1] 丁宏,郭艳华.快速大数模乘算法及其应用[J].小型微型计算机系统,2003.24(7):1367~1370
[2] 雷明,叶新,张焕国.Montgomery算法及其快速实现[J]. 计算机工程,2003.29(14):44~46
[3] 孔凡玉,于佳,李大兴.一种改进的Montgomery模乘快速算法[J].计算机工程,2005.31(8):1~3
[4] 刘强,佟冬,程旭.一款RSA模乘幂运算器的设计与实现[J].电子学报,2005.33(5):923~927
[5] P L Montgomery.Modular multiplication without trial division[J].Mathematics of Computation.1985.44(170):519~521
[6] Stallings,W.密码编码学与网络安全:原理与实践(第四版)[M].孟庆树,王丽娜,傅建明等译.电子工业出版社,2006.
[7]GUO J H,WANG C L.Systolic array implementation of Euclid"s algorithm for inversion and division in GF(2m)[J].IEEE Trans Computers.1998,47(10):1161~1167
[8] Lu C C,Tseng S Y.Integrated Design of AES Encrypter and Decrypter[J].IEEE Transactions on Information Theory.1991.37(5):1241~1260
[9] 吴训威,韦健,M.Pedram.低功耗双边沿触发器的逻辑设计[J].电子学报,1999.27(5):129~131
[10] 吴训威,卢仰坚.CMOS可预置双边沿触发器的设计及其应用[J].电路与系统学报,2001.6(1):27~31