GF(2m)域Montgomery模乘器的高效设计及FPGA实现

张 丽 董秀则 明娇娇 高献伟,

1(西安电子科技大学通信工程学院 陕西 西安 710071)2(北京电子科技学院 北京 100070)

0 引 言

随着物联网(IOT)的发展，通信安全的重要性日益增加，其安全问题引起了人们的广泛关注。1949年，香农发表了著名论文—《保密系统的通信理论》，密码学作为一门独立的科学从此形成。1976年，W.Diffie和M.E.Hellman提出了公钥密码的概念，从此密码学的发展进入了一个新的时代。公钥密码体制解决了传统对称密码中密钥分配的难题，不仅满足计算机网络应用，而且易于实现数字签名，所以迅速成为研究的焦点[1-2]。Neal Koblitz和Victor Miller于1985年提出椭圆曲线密码体制(ECC)，其中，椭圆曲线离散对数问题(ECDLP)的困难性是保证ECC安全的基础[3]，现在求解ECLDP的最佳算法仍然具有全指数时间复杂度。而应用颇为广泛的RSA公钥密码体制是基于整数因子分解的困难问题，目前该问题已出现亚指数时间算法。这说明在相同的安全水平下，椭圆曲线密码使用的密钥长度要比RSA密码短得多。例如普遍认为，160位椭圆曲线密码可以提供相当于1 024位RSA密码的安全强度[4]。由于密钥短，带宽占用少，所以工程实现的加解密速度较快，并且可以节省能源、存储空间，使得ECC特别适合在航空、航天、卫星及其智能卡等体系中应用[5-6]。

椭圆曲线密码体制自顶向下依次是算法协议层、ECC点运算模块层和底层有限域模运算层。其中点乘运算是整个密码算法的核心模块，其运算速度更是决定着整个系统加解密的效率，而点乘的实现则是采取自下而上的调用结构[7]，所以底层各有限域模运算的效率就成为椭圆曲线加密的关键[8]。底层有限域运算主要包括模加减、模乘和模逆等。其中，模逆运算最为复杂耗时，在点运算的调用过程中，通常通过转换运算坐标系来降低模除法的出现频次，或者将其转换为相对易于进行的模乘、模加/减和移位等操作，因此如何高效率、低成本快速地实现模乘是当前的一个研究热点。目前最为高效、研究较为广泛的模乘算法是Montgomery模乘算法[9]。文献[10]提出了一种Montgomery模乘算法在高基阵列上的优化算法，显著减少了时钟周期数，但消耗资源较大，对于模乘基本处理单元的结构还有待改进。文献[11]简化原始Montgomery算法的求商过程，设计模乘流水化阵列结构，提高了Montgomery模乘的性能。文献[12]结合Karatsuba算法提出一种基于全字的Montgomery模乘方案，降低了计算复杂度，但是硬件实现中占用了FPGA内部大量DSP单元，使得该方案的可移植性与灵活性较差。

针对以上问题，本文结合FPGA硬件结构的特点，提出一种基于k步长迭代的串并结合Montgomery模乘器，不仅显著减少了执行一次模乘所需的时钟数，还在速度与资源上取得最佳的折衷。

1 GF(2m)Montgomery模乘运算

应用在密码学中的椭圆曲线按其奇偶性质可分为两大类，它们分别对应于GF(p)和GF(2m)多项式，其中GF(p)中的椭圆曲线由于更适合硬件实现而被选作常用曲线。在椭圆曲线加密过程中，标量乘是整个系统的核心运算，而模乘又是其中的关键运算。Montgomery模乘是目前计算模乘较快的算法。为了提高模乘的计算效率，本设计选择GF(2m)域对Montgomery模乘器进行FPGA设计与实现。

1.1 GF(2m)基本模乘运算

h(x)=a(x)b(x)modf(x)

(1)

由式(1)可以看出，传统的计算模乘方法可分多项式相乘和对不可约多项式取模约化两步进行。即首先计算得到阶为2m-2的d(x)=a(x)·b(x)，然后计算d(x)modf(x)，如Karatsuba-Ofman多项式乘法方案、Matrix-Vector乘法等，但计算速度都有待提高。因此，边乘边约化的Montgomery模乘算法补足了传统模乘方案的短板，能够达到较高的实现速度。

1.2 基本的Montgomery模乘算法

Montgomery模乘算法利用完全剩余系的性质，采用简单移位代替求模过程中耗时的除法运算，提高了模乘的计算效率[13]。设f(x)是GF(2)上的不可约多项式，选定多项式r(x)使得gcd(r(x),f(x))=1，则Montgomery模乘乘积的计算如下：

c(x)=a(x)b(x)r-1(x)modf(x)

(2)

式中：r-1(x)是r(x)对f(x)取模得到的逆。即：

r(x)r-1(x)+f(x)f′(x)=1

(3)

具体的Montgomery模乘的计算过程如算法1所示。

算法1GF(2m)上Montgomery模乘结构

输入：a(x),b(x),r(x),f′(x)

输出：c(x)=a(x)b(x)r-1(x)modf(x)

1.t(x)=a(x)b(x)

2.u(x)=t(x)f′(x)modr(x)

3.c(x)=[t(x)+u(x)f(x)]/r(x)

由以上算法可知，为了得到计算结果c(x)，需要经历步骤1中的多项式乘法、步骤2中的取模运算、最后还需要一次加法、多项式乘法和除法的操作。但是当选取r(x)为单项式r(x)=xm时，由于f(x)是GF(2)上的不可约多项式，所以gcd(r(x),f(x))=1依然成立。此时结合硬件实现的特点，步骤2、步骤3中的乘法和除法操作便可以快速实现，任意多项式除以r(x)=xm的除法操作可转变为右移m位的移位运算。而且当逐比特扫描因子a(x)的系数时，预计f′(x)计算也可以避免，大大减少运算的时间。改进后的快速Montgomery模乘如算法2所示。

算法2GF(2m)上Montgomery模乘快速实现

输入：a(x),b(x)，f(x)

输出：c(x)=a(x)b(x)x-mmodf(x)

1.c(x)←0

2.i从0增加到m-1循环执行：

3.c(x)←c(x)+aib(x)

4.c(x)←c(x)+c0f

按照硬件实现的结构分，多项式乘法运算可以分为全串行结构、全并行结构和串并混合结构。观察算法2中的步骤2可知，该方案是逐比特的处理数据，至少需要m个时钟才可以完成。对应到硬件实现时，即为全串行结构。全串行结构比较简洁，对于处理较小的数据速度很快，但是随着密钥长度的增加，对于超长位操作数，必然消耗大量的时钟数。若采用串并混合结构，算法2的效率将会得到有效提高。

2 Montgomery模乘器的优化设计

为了达到较高的安全性要求，目前的密码算法所使用的密钥长度越来越大，对硬件实现方式的要求也越来越高[14]。串行结构简洁直观，适合于小操作数运算，而对于超长位大数运算，必然耗费大量的时钟数，无法满足速度的要求。全并行结构可以在一个时钟内完成全部的运算，但是资源开销巨大，对于资源受限的网络设备，并没有实际的使用价值。所以，为了提高Montgomery模乘的计算效率，找到基于全串行结构与全并行结构模乘器性能的平衡点，设计在一个时钟内进行多步运算的模乘算法，即可以在资源没有增加太多的情况下大大减少时钟的个数，从而提高Montgomery模乘器的性能。

为了详细说明改进后的Montgomery模乘结构，首先引入k、t、r三个参数。其中，k表示一个时钟内执行模乘核心运算的步数，为了增加改进后模乘器的灵活性，k可以选取大于0小于m的任意值。t表示执行完一次模乘所需要的迭代次数，r表示m位操作数在执行t个周期后剩余步数。显然三个参数之间的关系可以表示如下:

m=k·t+r

(4)

算法3根据式(3)中的关系，对改进后的GF(2m)域Montgomery模乘算法进行具体描述：

所谓西学之用，实为清廷应对日趋严峻的外交局面，有限度地变更旧制势在必行，被压抑的入侵文化的声音也因此得以显现于译文，现代法律意识的雏形伴随着殖民权力的扩张悄然扎根。尽管如此，中学为体的理念根深蒂固。洋务运动的中坚两江总督张之洞在《劝学篇》中甚至将三纲五常提升到国家民族生死存亡的高度：“保种必先保教，保教必先保国”(2002：1)。即便到了十九世纪末，维新变法的代表康有为依然鼓吹：“必有宋学义理之体，而讲西学政艺之用，然后收其用也。”

算法3改进后的域Montgomery模乘运算

输入：a(x),b(x)，f(x),k,t,r,m

输出：c(x)=a(x)b(x)x-mmodf(x)

1c(x)←0

2 for(i=0tot-1) loopi从0增加到t-1循环执行：

for(j=0 tok-1) loop

2.1c(x)←c(x)+aib(x)

2.2c(x)←c(x)+c0f(x)

2.3c(x)←c(x)/x

3 如果r>0,则

3.1c(x)←c(x)+aib(x)

3.2c(x)←c(x)+c0f(x)

3.3c(x)←c(x)/x

否则，跳转

3 高效Montgomery乘法器的硬件实现

为了进一步详细说明基于可变步长的串并混合硬件结构设计原理，给出基本结构说明如图1所示。其中Core是该Montgomery模乘器的核心运算模块，步骤1-步骤k表示一个时钟周期内进行的k次迭代，PE表示单次迭代的数据通路结构，其详细电路设计如图2所示[15]。将GF(2m)域中不可约多项式f(x)和乘因子b(x)对应的二进制串分别存入两个循环移位寄存器中，然后控制中心在时钟信号的作用下，周期性的存取数据以驱动Core电路周期性执行模乘运算。由式(3)不难得出，该Montgomery模乘器计算一次模乘的周期数即为└m/k┘，与上面的讨论一致，之所以对m/k向上取整，是因为r>0时，需要再执行一次剩余的迭代运算。此处k>1,所以时钟周期数定然小于m,进而大大减少了计算Montgomery模乘的时间。

图1 改进后的Montgomery模乘结构图

图2 Montgomery模乘单次迭代的关键路径图

由图2可知，Montgomery模乘电路图仅仅使用了简单的与门、异或门以及寄存器资源，并没有使用任何的芯片内部的DSP单元，便于移植，所以本方案不仅仅追求速度的提高，也注重灵活性和资源功耗的问题。

4 结果分析

为了公平合理的与文献[1]、文献[16-18]比较该模乘器的性能，本设计选择NIST推荐的5个二进制有限域F2163,F2233,F2283,F2409,F2571中的GF(2233)和GF(2163)分别进行功能仿真验证,选取的GF(2)域上的不可约多项式分别是f(x)=x233+x74+1和f(x)=x163+x7+x6+x3+1。改进后的Montgomery模乘器采用Verilog HDL硬件描述语言进行代码描述，并使用Modelsime 10.2a进行功能仿真，有限域F2233上的一组数据仿真结果如图3所示。其中一组测试矢量如下(十六进制)：

a=233′H0FA C9DFCBAC 8313BB21 39F1BB75

5FEF65BC 391F8B36 F8F8EB73 71FD558B

b=233′H100 6A08A419 03350678 E58528BE

BF8A0BEF F876A7CA 36716F7E 01F81052

c=233′H169 4FAF37D6 04D3F2F5 6727F419

356344CB 90C4BC1C 51BCBE66 2A18E0E6

图3 modelsime测试仿真图

在功能仿真验证正确后，又使用Synopsys公司的Synplify Pro编译器进行综合，综合实现是基于FPGA硬件实现平台，选用Xilinx Virtex2系列的xc2v3000芯片。当单次迭代步数为k=14时，该模乘器的速度与资源取得最佳折衷，如图4所示，此时仅仅用了17个时钟周期。表1依据计算一次模乘所需要的时钟周期数、最高时钟频率、时间作为比较要素和相关文献进行对比。

表1 GF(2m)域不同Montgomery模乘器的性能比较

表1给出文献[1]、文献[16]、文献[17]、文献[18]中各模乘器性能与本文优化后的Montgomery模乘器性能的比较结果。由表中不难看出，文献[16]中的模乘器频率在各设计中是最高的，文献[18]的资源占用在各模乘器中是最少的。但速度与资源的矛盾问题使得只考虑追求速度快或者资源占用少的方案是不可取的。所以，为了取得最佳的模乘器性能，所设计方案需平衡速度与资源，以取得两者的最佳折衷。鉴于相关设计的实现平台不同，比如文献[16]使用Synopsys公司的Design Complier在SMIC 0.18 μm工艺库下进行的综合，而文献[17]选用了Xilinx Virtex2系列的xc2v3000芯片，文献[18]选用Altera Stratix EP1S25F1020C5器件，本设计则是用Xilinx Virtex2系列的xc2v3000芯片，所以综合工艺库的不同使得直接比较并不合理。为了解决这一问题，引入参数C=A×T,其中A表示面积，T表示计算一次模乘的所需的时间。之所以选择该参数，是因为它能够综合考虑执行一次模乘时所需要的时钟数、最大频率以及占用面积这三个关键因素。参数C的具体含义如下所示：

(5)

式中：t为时钟数目，f为最高频率。由式(3)不难看出，当C的值越大，也就标志着消耗资源越多或者执行模乘所需要的时钟越多，而频率f越小，即该模乘器的性能越低。反之，则表示模乘器的性能较高。据此得出各模乘器的C参数对比结果如图4所示。

图4 各Montgomery模乘器性能比较图

由图4不难看出，虽然文献[16]的频率最大，但是C参数的取值却并不理想。文献[18]中根据芯片的资源情况采用全局串行局部并行的结构设计乘法器，可以看出该模乘器的效率是相对不错的。而本文的Montgomery模乘方案综合考虑芯片资源与延时问题，依据算法设计中在单位时钟周期内所进行的不定次循环迭代，对应到硬件实现中的串并混合结构，最终取得速度与面积的最佳折衷。所以本设计的Montgomery模乘器的效率在GF(2233)域和GF(2163)域都有很大提升。

5 结 语

为了提高椭圆曲线密码体制中模乘运算的效率，改进后的Montgomery模乘算法将原算法中的逐位扫描运算改为在单位时钟内进行k步移位来计算模乘，大大减少了时钟周期数。同时考虑资源占用情况，针对不同的操作数长度选取特定步数k，以取得速度与资源的最佳折衷。然后根据硬件实现的特点，设计一种基于FPGA的串并混合结构的Montgomery模乘器。通过与相关文献的对比分析，本方案的模乘器不仅在速度与资源上有平衡的优势，而且更适合硬件实现，具有较高的灵活性与可移植性。