椭圆曲线加密算法的FPGA实现

周维龙，欧阳洪波，李小宝

（湖南工业大学 电气与信息工程学院，湖南 株洲 412007）

0 引言

椭圆曲线加密算法（elliptic curve cryptography，ECC）是由N.Koblitz[1]和V.S.Miller[2]分别提出的一种加密体制。由于ECC 具有强抗攻击性、快加密速度以及低资源消耗等优点，已成为密码体制领域的研究热点[3-4]。加密算法实现的方式有很多种，根据算法实现的复杂程度、计算工作量大小等因素的不同，可将椭圆曲线加密算法分为硬件实现方式与软件实现方式两大类[5]。软件实现的方式虽然开发周期短，但其加密运算速度较慢、安全系数较低、无法较好地保证加密算法的安全性[6]。采用现场可编程门阵列（field-programmable gate array，FPGA）实现既可以保持软件实现的可移植性，又有硬件实现的安全性以及计算速度的优点，还可避免软件实现的缺点。

ECC 算法的关键运算包括点运算与模运算，运算位宽要求160～256 bits。所操作数均具有高数据长度特点，硬件实现方式可高效快速处理这类计算任务[7]。K.Javeed、Wang X.J.团队[8-10]先后提出了基于加法器的架构，分别采用Radix-4 parallel 模乘算法、Radix-4 booth encoded 交错模选乘法算法与Radi8-4 booth encoded 交错模乘法。其中文献[8]采用仿射-雅可比坐标体系完成算法设计，运算过程中不需要进行模逆运算，进一步提高了加密速度。本文采用硬件描述语言（hardware description language，HDL）实现椭圆曲线加密系统的设计与仿真。

1 相关理论分析

文献[11]提出标量乘法是ECC 算法中运用最多且最关键的运算，主要包括模加/减运算与求逆运算。设一个素数p，整数集合{0,1,…,p-1}构成了素数域GF(p)，也称为有限域Fp，那么素数域GF(p)中的元素有如下计算法则[12]。

1.1 模加法运算

若a,b∈GF(p) ，则(a+b)=c，其中c是a+b被p整除后的余数，并有0 ≤c≤p-1，把它叫为p的加法模。素数域上的这种运算称为模加运算，可表示为c=(a+b) modp。

算法1 为有限域Fp上的多精度模加法。

算法1输入：a,b,并且0 ≤a,b≤p-1。

输出：c=(a+b) modp。

第一步：(c,s[0])←a[0]+b[0]；

第二步：for(i=1；i

(c,s[i])←a[i]+b[i]+c;

得到(c,s)；

第三步：if (c==1)

s=(c,s)-p

else if(s>p)

s=s-p

else

s=s；

第四步：returns。

1.2 模减法运算

若a,b∈GF(p)，则(a-b)=c，其中c是a-b被p整除后的余数，并有0 ≤c≤p-1，把它叫为p的减法模。素数域上的这种运算称为模减运算，可表示为c=(a-b) modp。

算法2 为有限域Fp上的多精度模减法的计算。

算法2输入：a,b，并且0 ≤a,b≤p-1。

输出：c=(a-b) modp。

第一步：(c,s[0])←a[0]-b[0]；

第二步：for(i=1；i

(c,s[i])←a[i]+b[i]-c；

得到(c,s)；

第三步：ifc==1

s=s-p

else

s=s；

第四步：returns。

在计算过程中，由于每次数据的位宽不同，会导致资源使用率也不同。可以调整数据的位宽改变资源使用率。假定256 位的数据进行模加减运算，如果在计算过程中以256 位宽的数据直接进行加减运算，只需要循环一次，但这样会导致资源浪费。可以把256位宽的数据拆分成位宽相同等分的数据，这样虽然会增加循环次数，但是总的资源使用率会减少。

1.3 模乘法运算

若a,b∈GF(p)，则(a·b)=c，其 中c是a·b被p整除后的余数，并有0 ≤c≤p-1，将其称为p的乘法模。素数域上的这种运算称为模乘运算，可表示为c=(a·b) modp。

算法3 为布斯乘法算法的计算。

算法3第一步：先将被乘数a的最低位增加一位虚拟位，放入被乘数a中，a={a,0}，把被乘数循环右移；

第二步：ifa[1]==0 anda[0]==0 不需要进行运算，此时需要让乘积寄存器右移一位，a[1]、a[0]分别为最低位以及虚拟位；

ifa[1]==0 anda[0]==1，并且让乘积加上a，然后右移一位；

ifa[1]==1 anda[0]==0，让乘积减去a，然后右移一位；

ifa[1]==1 anda[0]==1，不需要进行运算，此时需要让乘积寄存器右移一位。

2 ECC 系统的FPGA 设计

2.1 椭圆曲线加密算法的总体框图

椭圆曲线加密算法系统总体框图如图1所示，椭圆曲线加密算法的设计。主要有算法实现和数据库实现两个部分在椭圆曲线加密算法框图之外，设定了数据输入和数据输出处的缓存区间，这两个区间是FPGA 内部存储块所生成的FIFO。

图1 椭圆曲线加密算法总体框图Fig.1 Block diagram of elliptic curve encryption algorithm

1）算法实现模块。算法实现模块将数据输入到数据缓存区间中的数据提取出，经过数据分流模块把数据递送到相应的算法运算子模块，等待算法运算子模块计算完成后，再经过数据合并模块将数据写到输出数据缓存区间。有限域上的计算以及椭圆曲线上的计算是公钥加密算法和密钥对生成算法两种算法的基石。通过把有限域上的模加减运算、模乘运算以及模逆运算和椭圆曲线上的点加以及倍点运算封装在数据库模块当中，不定时地被两种运算算法调用。考虑到FPGA 资源的使用率以及减少浪费，设定两种运算共同使用计算过程中的一些临时变量。

2）数据库模块。公钥加密算法以及密钥对生成算法主要使用有限域上的椭圆曲线相关计算。如果椭圆曲线的域在素域上面时，会根据安全性的高低来选择合适的曲线，因为非超奇异椭圆曲线的安全性高于超奇异椭圆曲线，基本上会选择用非超奇异椭圆曲线来实现椭圆曲线加密算法设计。经过前面章节椭圆曲线加密算法的理论基础，可知在有限域上的计算方法和在椭圆曲线上的计算方法是一致的，不同之处在于算法实现。因此，设计一个能够互通、资源使用少及在运行时间方面都合理的模块是值得研究的。

数据库模块包括了模加减运算、模乘运算、模逆运算以及在这3 个运算基础之上的点乘运算和点加运算，总计5 种运算。在这5 种运算之中，除了模加减运算消耗时长以及资源使用较少外，其他的模块使用都较多。有限域上椭圆曲线的点运算比模运算更为复杂，椭圆曲线上的运算是调用有限域上的模加减、模乘运算以及模逆运算。考虑到这些情况，为椭圆曲线上的点加运算以及倍点运算设定一个单独的模加减模块以及模乘模块供他调用。椭圆曲线上的运算在消耗时间以及资源占用等情况跟有限域上面的运算相比较，椭圆曲线上的运算消耗时间较长、资源占用较多。故可以通过占用资源以及消耗时长相结合，为椭圆曲线上的运算模块和有限域上的运算模块设计不同的实现方案。

2.2 椭圆曲线加密算法的层次结构

椭圆曲线加密算法主要有两种算法，一种是公钥加密算法，另一种是密钥对生成算法。采用自顶向下设计思想，将椭圆曲线加密算法分为3 层：加密层、群运算层以及算术运算层[13]，算法层次结构如图2所示。公钥加密算法和密钥对生成两种算法构成了加密层；点加运算和倍点运算构成了群运算层；有限域加法运算、有限域减法运算、有限域乘法运算及有限域求逆运算构成算术运算层。

图2 椭圆曲线加密算法层次结构图Fig.2 Hierarchical structure of elliptic curve encryption algorithm

加密层主要实现公钥加密算法和密钥对生成算法功能。其中有限域Fp上的运算和椭圆曲线上的运算是实现这两种不同算法的核心单元，但在具体的应用中，它们彼此独立，互不影响。在这些算法协议中，标量乘法运算是最重要的环节，其性能的优劣很大程度上对整个加密系统的性能起着决定性作用。因此，如何实现椭圆曲线上的标量乘法是实现加密算法的技术难点。而点加运算以及倍点运算又是由算术运算层上有限域Fp运算所构成。

群运算层主要实现标量乘法的运算，主要包括点加运算及倍点运算两个部分。它们针对的对象是不相同的，其中点加运算实现两个不同点的加法运算，而倍点运算针对的是两个相同点的加法运算。但是两种加法运算的结果均为圆曲线上的一个点[13]。

有限域运算层由模加运算、模减运算、模乘法和模逆运算等4 种不同运算模块构成。其中模逆运算的复杂度最大，资源占用最多，计算时间最长[14]；模加运算和模减运算的复杂度最小，占用资源最少。由于模逆运算在整个椭圆曲线加密算法中使用频率最低，完成一次加密算法只需要一次模逆运算；而模加运算、模减运算和模乘运算的使用频率基本都差不多，因此模乘运算是整个椭圆曲线加密算法中最为关键的底层运算模块，它很大程度上影响整个椭圆曲线加密算法的运算效率[15]。

2.3 EEC 系统算法的程序设计

完成FPGA 设计中，Verilog HDL 语言作为一种高级的硬件描述语言，因其精炼而易读的特点得到广泛应用。根据对信号描述方式的不同，可将HDL 建模分为数据流建模、行为建模与结构化建模3 种不同的建模方式。本设计采用行为建模的方式实现模加减、模乘运算以及模逆运算的程序设计。图3为模乘运算模块的程序设计界面图。

图3 模乘运算模块的程序设计界面图Fig.3 Programming design interface of modular multiplication module

经编译后可得到图4所示编译结果。

图4 模乘模块编译结果Fig.4 Compilation results of the modular multiplication module

由图4可知，本系统所用芯片型号为EP3SL340F1760C2，逻辑利用率为27%，管脚使用率为57%。程序设计正确。

3 EEC 系统的仿真与分析

3.1 模加模块

输入被加数ain、输入加数bin、输入模数pin以及输出仿真结果cout。

ain=5724_383A_42E6_7214_A512_B5E9_F478_BA87_CAB3_5A23_BC54_4862_0011_ABCD_8423_F783，

bin=C689_EB32_AB99_CC10_472_00EA_17BA_FF11_A2C7_1156_BF82_CE85_2578_45A6_AB26，

pin=FFFF_FFFF_FFFF_0000_0000_FFFF_0000_FFFF_A458_BFFA_B786_BE56_B4C2_BA12_AB21_5551，

cout=1DAE_236C_EE81_3E24_B983_B6D5_06BD_D243_256C_3CF0_1624_498E_19D4_1733_1EA9_4D58。

模加运算模块在Modelsim 中的时序仿真结果如图5所示。

图5 模加运算模块时序仿真结果Fig.5 Timing simulation results of the modular addition module

在验证模加模块时，输入的数据ain、bin以及pin要满足条件1

3.2 模减模块

输入被减数ain、输入减数bin、输入模数pin以及输出仿真结果cout。

ain=8564_AB23_25A4_1E12_5625_A123_B787_212F_BD89_147F_ABD9_EA56_63DA_B128_FF85_E25B，

bin=3BA8_AB78_35BA_4573_14B4_AB12_1487_AF96_6347_4D5A_175E_ABCF_1572_4A25_AE12_1453，

pin=FFFF_FFFF_FFFF_0000_0000_FFFF_0000_FFFF_A458_BFFA_B786_BE56_B4C2_BA12_AB21_5551，

cout=49BB_FFAA_EFE9_D89F_4170_F611_A2FF_7199_5A41_C725_947B_3E87_4E68_6703_5173_CE08。

模减运算模块在Modelsim 中的时序仿真结果如图6所示。

图6 模减运算模块时序仿真结果Fig.6 Timing simulation results of the modular subtraction module

在验证模减模块时，输入的数据ain、bin以及pin要满足条件0

3.3 模乘模块

输入被乘数ain、输入乘数bin、输入模数pin、输出仿真结果cout。为了方便检验计算的数据是否正确，设置输入的数据为低位二进制数，再把二进制数据转换成十进制数据。

输入3 组数据。首先输入第1 组数据：ain=2 545，bin=5 335，pin=8 795。再输入第2 组数据：ain=456 825，bin=686 877，pin=6 956 454。最后输入第3 组数据：ain=51 522 345，bin=12 879 353，pin=69 482 464。

模乘运算模块在Modelsim 中的时序仿真结果如图7所示。

图7 模乘运算模块时序仿真结果Fig.7 Timing simulation results of the modular multiplication module

在验证模乘模块时，输入数据ain、bin及pin。只有当时钟信号clk 上升沿、复位信号rst 处于低电平、选择模式信号select 为低电平，以及开始信号start 为高电平时，cout才会得到模乘运算的结果。当rst 处于高电平时，不会输出结果。通过计算检验第一组数据2 5455 335=8 795k+6 890，可以得出k=1 543，说明第一组计算结果正确。

456 825×686 877=956 454k+634 653，可以得出k=328 068，说明第二组计算结果正确。

51 522 345×12 879 353=69 482 464k+53 204 033，可以得出k=9 550 243，说明第三组计算结果正确。

4 结语

课题组采用FPGA 的自上而下（Top-Down）设计思想，将椭圆曲线加密算法分为加密层、群运算层与算术运算层三层结构。重点分析了模加/减运算与模乘法运算的计算原理与算法设计。完成了核心算法的FPGA 程序设计，并且结合Modelism 给出模加/减运算、模乘法运算的时序仿真结果，验证了算法设计的准确性。