基于GF（2m）的椭圆曲线求逆算法的改进研究

郭高峰+崔强强

摘 要： 针对二进制域上现有求逆算法计算量大、并行度小、速度慢的缺点进行改进，基于二元Euclidean算法提出了改进，设计了相应的乘法器硬件结构，并且分析了其运算效能和资源占用情况。将此求逆计算器的并行改进算法使用Verilog语言编程实现，利用Xilinx ISE 12.4对整个求逆算法综合仿真（行为级），在Xilinx Virtex?5 XC5VFX70T的硬件平台上验证求逆算法的运算效率，结果表明对求逆算法的改进有效地提高了求逆运算的速度。

关键词： 椭圆加密； 二进制域； 求逆； 扩展欧几里得算法

中图分类号： TN918?34； TP309.7 文献标识码： A 文章编号： 1004?373X（2014）18?0019?04

Improvement and research of inversion algorithm of elliptic curve based on GF （2m）

GUO Gao?feng1， CUI Qiang?qiang2

（1. Purchasing Center of Navy Equipments， Lianyungang 222000， China； 2. Jiangsu Automation Research Institute， Lianyungang 222000， China）

Abstract： Since the existing inversion operation algorithm based on GF（2m） has the following disadvantages： large amount of calculation， poor degree of parallelism and slow speed， an improved algorithm is proposed in this paper based on Extended Euclidean Algorithm. A corresponding multiplier hardware structure was designed. Its operation performance and the status of resource occupancy are analyzed. This parallel improved algorithm of inversion operation calculator was realized with the program based Verilog. The comprehensive simulation of the whole inversion algorithm was conducted with Xilinx ISE 12.4. The operation efficiency of the inversion algorithm was verified on hardware platform of Xilinx Virtex?5 xc5vfx70t. The experimental result and performance comparison show that the modification of the inversion algorithm has improved its speed.

Keywords： ECC； GF（2m）； inverse operation； expend Euclidean algorithm

0 引 言

椭圆密码算法ECC（Elliptic Curve Cryptography）[1]具有每bit 最高的安全性[2]，ECC算法的主要优点有[3]：安全性能高；计算量小且运算速度快；占用存储空间小；对数据运算带宽要求低。目前常用的定义椭圆曲线的有限域有两种：素数域GF（p） 和二进制域GF（2m）。在二进制域上元素可以直接用二进制位向量表示，这样元素的加、减、乘等操作在计算机中可以并行实现，所以二进制域的椭圆曲线加密通常被用于硬件实现的椭圆曲线加密系统中。GF（2m）上的非奇异椭圆曲线是Weierstrass 公式定义的：y2+xy=x3+ax2+b。其中a，b是GF（2m）中的元素，且b≠0。曲线E同时还包括一个无穷远点，通常用O 表示， 为曲线上点的加法单位元。有限域上的模逆运算是椭圆曲线密码系统中的关键性计算，但是其运算效率却是最低的，据M.Brown， D.Hankerson等人粗略估计[4]，求逆运算与乘法运算（带有快速取模运算）的资源占用比是80∶1，因此通过改进加速求逆运算减少其计算时间可以在很大程度上提高椭圆加密的运算效率和吞吐量。

GF（2m）上的求逆算法有两类：基于费尔玛小定理使用乘法的算法、扩展欧几里德算法及其变体。Scliroeppel等人在文献[5]中提出了Almost求逆算法。如果椭圆加密算法使用仿射坐标，那么求逆运算将是制约标量乘法性能提高的主要瓶颈。扩展欧几里德算法及其变体适合加密算法的软件实现；基于扩展欧几里德算法求逆电路会对核心电路和控制器并行性要求较高，所以硬件实现的研究还较少。

本文基于二元Euclidean算法提出了改进，根据资源和需求的不同，通过修改算法执行结构，将原算法中制约效能的步骤进行改进，并引入并行执行方式，实现了求逆运算的加速。

1 求逆运算的原理

域元素的求逆运算无论在软件和硬件实现上都有很大复杂度，相比于乘法运算其计算效率要低很多。单纯的求逆算法有两种：基于扩展Euclidean方法的算法、基于Fermat小定理的算法。基于Fermat小定理的算法是将求逆运算转化为升幂运算，算法中的模乘和模平方运算决定其运算速度，算法的评估软件得到结果是完成一次求逆运算需要「log2（m-l）」+w（m-1）-1次模乘和m+1次模平方，这种方法不但会增加软硬件设计的复杂度，算法中的运算需要反复执行，性能受到很大影响[7]。而扩展Euclidean方法便于硬件实现，没有大量的乘法，只涉及移位、判断和加法，可以方便并行化设计，因此，本文通过研究三种基于扩展Euclidean方法的算法，得到新的算法：对二元Euclidean方法进行并行优化和改进。

Euclidean算法本质是计算多项式的最大公因式。在多项式a1（x）和a2（x）的最大公因式gcd（（a1（x），a2（x））时，用a1（x）除a2（x）得到商p（x）和余数q（x），满足a2（x）=a1（x）p（x）+q（x），其中q（x）的次数低于a1（x）的次数，由Euclidean算法得gcd（a1（x），a2（x））=gcd（a1（x），q（x））。

定理1 设a1（x），a2（x）和a3（x）是GF（2m）上的任意多项式，求a1（x）和a2（x）的最大公因式有：gcd（a1（x），a2（x））=gcd（a1（x），a2（x）-a3（x）a1（x））。对于二元扩域上的逆元也可以使用该算法。二元扩域GF（2m）上的元素a，其多项式表示为a（x），那么a的逆元a-1可用a（x）的扩展Eucl idean算法求出。

使用传统的Euclidean算法计算正整数a，b的gcd原理就是当b≥a时，用a去除b得到商q和余数r，满足：b=qa+r，且0≤r

算法1 求二进制多项式的Euclidean算法

INPUT： 非零多项式a和b同时deg（a）≤deg（b）。

OUTPUT：d=gcd（a，b） 以及二进制多项式g，y满足 ag+bh=d。

1. u←a，v←b.

2. g1←1，g2←0，h1←0，h2←1.

3. While u≠0 do

3.1 j←deg（u）-deg（v）.

3.2 If j<0 then：u?v，g1?g2，h1?g2，j←-j.

3.3 u←u+zjv.

3.4 g1←g1 z j g2，h1←h1+zjh2.

4. d←v，g←g2，h←h2.

5.Return（d，g，h）.

假定f为一个m次二进制不可约多项式，非零多项式a的次数不超过m-1，这时gcd（a，f）=1，在算法中，如果输入是a和f，则在步骤3中，最后的非零的输入u=1，那么在步骤4中有ag1+fh1=1。所以ag1≡1（mod f）and so a-1=g1。说明：在求取g1的过程中，不需要求出h1和h2，基于此导出如下的求GF（2m）上的求逆的扩展Euclidean算法。

算法2 扩展Euclidean算法求逆[6]

INPUT： a∈GF（2m），a≠0，域的约减多项式f（x）

OUTPUT： a-1 mod f

1.B=1，C=0，U=A，V=F；

2.while deg（U）≠0 do

j=deg（U）-deg（V）；

if j<0 then U=V，B=C，j=-j；

U=U+xjV，B=B+xjC；

3.return B。

算法3 二元Euclidean算法[3]

INPUT： a∈GF（2m），a≠0，域的约减多项式f（x）

OUTPUT： a-1 mod f

1. u←a，v←f，g1←1，g1←0.

2. While（u≠1 and v≠1） do

2.1 While x divides u do

2.1.1 u←u/x.

2.1.2 If x divides g1 then g1←g1/x；else g1←（g1+f）/x.

2.2 While x divides v do

2.2.1 v←v/x.

2.2.2 If x divides g2 then g2←g2/x；else g2←（g2+f）/x.

2.3 If deg（u）>deg（v）then：u←u+v，g1←g1+g2；

Else：v←v+u，g2←g2+g1.

3. If u=1 then return（g1）； else return（g2）.

另外还有一种改进的二进制算法求逆方法叫殆逆算法，运算过程是先计算一个多项式h（x）以及一个正整数k，满足a（x）h（x）≡xk mod f（x），然后得到a-1（x） = h（x）x-k mod f（x）。如果多项式是某些特定的结构，其约减速度殆逆算法会比二元Euclidean算法快，如果多项式为任意结构，其约减速度比较的话二元Euclidean算法适应性更强。

2 求逆算法的改进及其硬件实现

2.1 改进求逆算法

在实现二元Euclidean算法时，总共需要四个m+1位的寄存器u，v，g1，g2，其中deg（u）和deg（v）分别表示u和v中域元素的多项式次数，在第2步中判断u和v是否能整除x，只要判断u和v的最低比特位是否为0，在整除时只要对应的寄存器进行逻辑右移，第3步是域元素的加法，因此制约二元Euclidean算法的执行效率的因素是对循环的判断，以及比较deg（u）和deg（v）。文献[8]给出了一种方案，这种算法能在一个时钟周期内比较deg（u）和deg（v）的函数，其硬件实现结构为优先级译码器，这种设计利用硬件资源换取了速度的提高，但是当选取域GF（2m）的m值较大的时候，其延迟也很大。因此，提出一种改进算法有效加速deg（u）和deg（v）的比较，能在很大程度上提高求逆速度。本文就是基于这一思想，增加了两个寄存器Count_u和Count_v，用于存储并检测u和v中元素次数的变化，设计了一种并行的硬件结构，同时执行循环中的判断和移位、加法操作。本文提出的改进的算法二元Euclidean算法描述如下：

算法4 改进的二元Euclidean算法

INPUT： a∈GF（2m），a≠0，域的约减多项式f（x）

OUTPUT： a-1 mod f

1.u←a，v←f，g1←1，g2←0. Count_u←m，Count_v←m+1

2. While（u≠1 and v≠1） do

利用设计的独立判断和移位元件并行执行2.1和2.2

2.1 While Count_u>1 and x divides u do

2.1.1 u←u/x.

2.1.2 Count_u←Count_u-1

2.1.3 If x divides g1 then g1←g1/x；else g1←（g1+f）/x.

2.2 While Count_v >1 and x divides v do

2.2.1 v←v/x.

2.2.2 Count_v←Count_v-1.

2.2.3 If x divides g2 then g2←g2/x；else g2←（g2+f）/x.

3. 并行判断部件

3.1 If Count_u=1 then return g1.

3.2 Elsif Count_v=1 then return g2.

3.3 Elsif Count_u >Count_v then

3.3.1 u←u+v，g1←g1+g2；

3.3.2 Goto step 2.1

Else：

3.3.1 v←v+u，g2←g2+g1.

3.3.2 Goto step 2.2

本文增加的两个寄存器Count_u和Count_v只需在初始化的时候赋予二进制项的系数，然后随着移位的进行检测u和v的次数的变化，也就是在步骤2.1和2.2中根据相应的跳转条件减1计数，在硬件中比较两个（log2（m+1））位的寄存器Count_u和Count_v是容易实现的。程序状态图如图1所示。

图1 程序运行状态图

在循环的判断、移位、域加法的操作执行时增加的两个并行部件，这两个部件同时执行，而且他们的出口都是连接到并行判断元件上去，一旦跳出条件满足，两个部件同时终止，这就避免了串行循环带来的大延迟，以增加了很小的硬件资源的代价换来了求逆速度的极大的提升。

2.2 改进求逆算法的结构图

根据2.1节的改进算法，运算流程图如图2所示。

图2 改进算法的运算流程图

参数初始化之后进入并行执行模块，在并行执行模块内部，首先判断执行条件， 当条件满足时，在两个运算部件中分别判断Count_u和Count_v以及u或者v次数大于1的条件满足时，分别单独执行。在并行执行的同时，并行判断部件也在运行，当Count_u或Count_v的跳转条件满足时，Count_u>Count_v或者Count_u

由于改进的求逆算法在计算没有太多的I/O限制，而且计算密集，判决条件具有并行性，运算步骤可以流水处理和并行处理，根据上述的运算流程，本文基于FPGA设计了高效的执行结构，利用FPGA内部丰富的逻辑布线资源和算法功能块实现结构图如图3所示。

图3 改进算法的运算结构图

2.3 硬件仿真与实现

根据2.2节改进原理以及实现结构图，本文选取有限域GF（2192），编写相应的Verilog代码，Xilinx Virtex?5 XC5VFX70T的硬件开发板上对改进算法进行板级验证。本文设计的求逆代码仿真结果如图4所示。

图4 改进求逆算法一次仿真图

针对一次求逆所需的时间，与现有的实现效果进行了对比，比较如表1所示，数据表明：在使用资源规模相当的情况下，本文提出的改进算法运算效率提高约20.9%。

3 结 语

椭圆曲线密码进行实现时，有限域上的求逆运算占有很大比例。由于求逆运算是标量乘法的重要组成部分，提高求逆算法效率可以在很大程度上提高点乘的运算速度，进而提高整个椭圆加密的吞吐率，本文提出的改进二元Euclidean算法，简化了其中的耗时运算，并且引入了并行化操作机制，在此基础上设计了一套适合FPGA实现的求逆运算器结构。采用Verilog语言，将此求逆算法进行并行优化，并且编程实现，使用Xilinx ISE 12.4对整个算法仿真、综合，在Xilinx Virtex?5 XC5VFX70T的开发板上实现了域内标量乘法的验证，比较结果表明该改进算法有效地提高了椭圆曲线加密算法的硬件运算速度。

表1 求逆运算实现对比

参考文献

[1] W.DIFFIE H M. New direction in cryptography [J]. IEEE Tran?

sactions on information Theory， 1976， 22（6）： 644?654.

[2] 王峰.GF（2163）上椭圆曲线密码体制的FPGA实现[D].广州：广州大学，2006.

[3] HANKERSON Darrel， MENEZES Alfred， VANSTONE Scott.， Guide to Elliptic Curve Cryptography[M].张焕国，译.北京：电子工业出版社，2005.

[4] BROWN M， HANKERSON D， LOPEZ J， et al. Software implementation of the NIST elliptic curves over prime fields [C]// Topics in Cryptology?CT?RSA. [S.l.]： Springer， 2002： 250?265.

[5] SEHROEPPEL R， ORMAN H， O′MALLEY S， et al. Fast key exchange with elliptic curve systems [C]// Advances in Cryptology?CRYPTO. [S.l.]： [s.n.]， 1995： 43?56.

[6] IEEE. IEEEP1363?2000 IEEE standard specifications for public?key cryptography [S]. USA： IEEE， 2000.

[7] ZHANG Yu， CHEN Dong?dong， CHOI Younhee， et al. A high performance ECC hardware implementation with instruction?level parallelism over GF（2163） [J]. Microprocessors and Microsystems， 2010， 34： 228?236.

[8] 高献伟，欧海文，董秀则，等.基于FPGA的GF（2）域求逆算法的设计研究[J].计算机工程与应用，2005（9）：135?137.

[9] 秦帆，戴紫衫.有限素域上椭圆曲线模逆运算的设计与实现[J].计算机工程与应用，2008，44（23）：117?119.

[10] 蔡振国，陈韬，郁滨.基于GF（2n）的ECC乘法逆元的快速实现[J].微处理机，2006（3）：59?62.

[3] HANKERSON Darrel， MENEZES Alfred， VANSTONE Scott.， Guide to Elliptic Curve Cryptography[M].张焕国，译.北京：电子工业出版社，2005.

[4] BROWN M， HANKERSON D， LOPEZ J， et al. Software implementation of the NIST elliptic curves over prime fields [C]// Topics in Cryptology?CT?RSA. [S.l.]： Springer， 2002： 250?265.

[5] SEHROEPPEL R， ORMAN H， O′MALLEY S， et al. Fast key exchange with elliptic curve systems [C]// Advances in Cryptology?CRYPTO. [S.l.]： [s.n.]， 1995： 43?56.

[6] IEEE. IEEEP1363?2000 IEEE standard specifications for public?key cryptography [S]. USA： IEEE， 2000.

[7] ZHANG Yu， CHEN Dong?dong， CHOI Younhee， et al. A high performance ECC hardware implementation with instruction?level parallelism over GF（2163） [J]. Microprocessors and Microsystems， 2010， 34： 228?236.

[8] 高献伟，欧海文，董秀则，等.基于FPGA的GF（2）域求逆算法的设计研究[J].计算机工程与应用，2005（9）：135?137.

[9] 秦帆，戴紫衫.有限素域上椭圆曲线模逆运算的设计与实现[J].计算机工程与应用，2008，44（23）：117?119.

[10] 蔡振国，陈韬，郁滨.基于GF（2n）的ECC乘法逆元的快速实现[J].微处理机，2006（3）：59?62.

[3] HANKERSON Darrel， MENEZES Alfred， VANSTONE Scott.， Guide to Elliptic Curve Cryptography[M].张焕国，译.北京：电子工业出版社，2005.

[4] BROWN M， HANKERSON D， LOPEZ J， et al. Software implementation of the NIST elliptic curves over prime fields [C]// Topics in Cryptology?CT?RSA. [S.l.]： Springer， 2002： 250?265.

[5] SEHROEPPEL R， ORMAN H， O′MALLEY S， et al. Fast key exchange with elliptic curve systems [C]// Advances in Cryptology?CRYPTO. [S.l.]： [s.n.]， 1995： 43?56.

[6] IEEE. IEEEP1363?2000 IEEE standard specifications for public?key cryptography [S]. USA： IEEE， 2000.

[7] ZHANG Yu， CHEN Dong?dong， CHOI Younhee， et al. A high performance ECC hardware implementation with instruction?level parallelism over GF（2163） [J]. Microprocessors and Microsystems， 2010， 34： 228?236.

[8] 高献伟，欧海文，董秀则，等.基于FPGA的GF（2）域求逆算法的设计研究[J].计算机工程与应用，2005（9）：135?137.

[9] 秦帆，戴紫衫.有限素域上椭圆曲线模逆运算的设计与实现[J].计算机工程与应用，2008，44（23）：117?119.

[10] 蔡振国，陈韬，郁滨.基于GF（2n）的ECC乘法逆元的快速实现[J].微处理机，2006（3）：59?62.