Edwards 曲线快速标量乘算法的改进与FPGA 实现*

高献伟 明娇娇 张 磊 董秀则 张青川

1. 北京电子科技学院，北京市 100070；

2. 农产品质量安全追溯技术及应用国家工程实验室(北京工商大学)，北京市 100048

引言

公钥密码思想是由W.Diffie 和M.E.Hellman在1976 年提出的，随着社会信息化的快速发展，人们对系统安全性要求越来越高，这点使得公钥密码的应用也越来越广泛。 RSA 是公钥密码体系中应用最广的一种公钥密码体制，但是，现在计算机的计算能力越来越高，RSA 变得越来越不安全，很容易就被第三方攻 破。 所以，对于RSA 密码体制来说，若想要增强其安全强度，就必须不断地增加密钥长度，但是密钥长度的增加所带来的问题就是加解密速度特别慢，而且占用的存储空间也比较大，这不但使得密码体制效率低下，资源利用率也很低。

椭圆曲线密码(Elliptic Curves Cryptography，ECC)体制是在1985 年由Miller[1]和Koblitz[2]分别提出来的。 研究表明，在安全性相同的情况下，ECC 的密钥长度较短[3]。 例如，160 位密钥的ECC 相当于1024 位的RSA 的安全性[4]。 因为ECC 的密钥的长度比较短，所以ECC 在工程实现加密和解密时的速度比较快，并且节省资源，适合用在移动通信、智能卡等系统中。 因此，密码学中热衷于研究椭圆曲线的学者越来越多。Edwards[5]在2007 年为椭圆曲线引入了一种新的形式:x2＋y2＝c2(1 ＋dx2y2)，并且提出，如果一个域的特征不等于2，则该域上的椭圆曲线与该域或其扩域上的Edwards 曲线等价。 Edwards曲线最大的优点是点加运算和倍点运算的公式相同，所以其运算规则比较简单。 这个特点使得Edwards 曲线能够天然有效地抵抗侧信道攻击[6]，进而使得加密系统更加安全。 文献[7]全面分析了Edwards 曲线上的点运算规则，结果表明，Edwards 曲线上的运算效率比其他形式的椭圆曲线效率更高。 如今对Edwards 曲线的研究也取得了一些优秀的成果，例如，文献[8]设计了一款加密处理器，该处理器是基于Edwards 曲线的，然后将该处理器设计于无源射频识别(Radio Frequency Identification，RFID)标签，能够很好的到达RFID 标签的要求。 文献[9]对于标量乘法的研究中提出马尔科夫点加-倍点链能够抵抗简单能量攻击。 文献[10]采用串行和并行两种算法，分别对标量乘法进行了测试，还有一些学者对二进制Edwards 曲线的硬件设计进行了测试[11][12]。 研究发现，Edwards 曲线是椭圆曲线中实现效率更好的一种曲线，而且其安全性也比其他曲线更高。 因此，Edwards 曲线成为椭圆曲线领域的研究热点。

标量乘是椭圆曲线密码体制中的核心运算，其运算速度严重制约着整个密码体系的实现效率。 Edwards 曲线作为一种新型椭圆曲线，其上的标量乘算法研究较少，最常见的是采用二进制计算方法，如文献[10]中工程实现采用从左向右算法和从右向左算法。 该方法将标量k 表示为二进制形式，通过判断每一位上的数值执行相应的点加和倍点运算，此算法虽然比较简单，但是运算效率并不高。 文献[13]中通过对倍点公式进行变形设计了一种连续倍点算法，采用该算法来计算标量乘能够有效降低模逆运算的次数。但是该算法是在仿射坐标下设计的，不能用于其他坐标系中，而且模逆运算是模运算中最耗时的运算，算法最后一步仍然需要计算模逆运算，因此，标量乘运算速度仍然受到制约。 为了提高Edwards 曲线上标量乘的计算效率，本文针对标量乘算法进行研究，主要通过研究标量k 的有效表示来减少点运算的调用次数，从而提高标量乘的运算速度。

本文首先详细地介绍了仿射坐标系下和标准射影坐标系下的Edwards 曲线上的点运算规则以及一种Edwards 曲线上快速标量乘(scalar multiplication on Edwards curve， EDSM)算法[14]，然后从标量k 的表示形式上对该算法进行了改进，经过计算得出改进算法运算效率优于原算法，最后，将设计的算法在现场可编程门阵列(Field Programmable Gate Array， FPGA)上仿真实现，结果表明本文所提出的标量乘算法能够取得较好的运算效率。

1 Edwards 曲线及其基本运算

1.1 仿射坐标下的Edwards 曲线

2007 年，Edwards 提出了特征不为2 的域K上椭圆曲线的一种新形式，定义如下:

其中，c，d ∈K，c，d ≠0，且cd4≠1，称(1)式为Edwards 曲线，该曲线上的运算规则简单。研究表明，如果域的特征不等于2，那么其上的椭圆曲线双有理等价于该域或者其扩域上的Edwards 曲线。

更深一步研究发现:任何特征不为2 的域上的椭圆曲线都能够转换为该域上c ＝1 的曲线，即(1)式简化为

Edwards 曲线上的点对于加法运算构成加法群。 其中单位元为(0，1)， - P1＝(- x1，y1)，令P1＝(x1，y1) 和P2＝(x2，y2)，P1＋P2＝P3＝(x3，y3)，点加公式为:

当P1＝P2时，公式(3)仍然成立，此时只要将其中的x2和y2分别替换为x1和y1，即为倍点公式:

令I，M，S 分别域K 上的求逆、乘法与平方运算，则根据文献[15]可知，I，M，S 之间的等价关系为I ＝10M，S ＝0.8M；令D 表示乘以d 的运算，加法和减法运算可以忽略不计，则点加公式(3)的计算量为2I ＋5M ＋1D ＝25M ＋1D，倍点公式(4)的计算量为2I ＋1M ＋3S ＋1D ＝23.4M＋1D。

1.2 标准射影坐标下的Edwards 曲线

为了避免Edwards 曲线加法公式中耗时的求逆运算，采用标准射影坐标形式，将曲线方程表示为:

其上的(X1:Y1:Z1) 对应于仿射坐标下的点(X1/Z1，Y1/Z1)，Z1≠0。 单位元是(0:c:1)，(X1:Y1:Z1) 的逆是(-X1:Y1:Z1)。 令P1＝( X1:Y1:Z1) ，P1＝ ( X2:Y2:Z2) ，P3＝P1＋P2＝( X3:Y3:Z3) ，则点加公式为:

设有寄存器R1，R2，R3存储X1，Y1，Z1，寄存器R4，R5，R6存储X2，Y2，Z2，仅使用两个临时的寄存器R7，R8。 最终结果X3，Y3，Z3放在寄存器R1，R2，R3中，上述点加计算过程如下:

R3←R3·R6；R7←R1＋R2；R8←R4＋R5；R1←R1·R4；R2←R2·R5；R7←R7·R8；R7←R7-R1；R7←R7- R2；R7←R7·R3；R8←R1·R2；R8←d·R8；R2←R2-R1；R2←R2·R3；R3←R23；R1←R3-R8；R3←R3＋R8；R2←R2·R3；R3←R3·R1；R1←R1·R7；R3←cR3.

同样地，设有寄存器R1，R2，R3存储X1，Y1，Z1，寄存器R4，R5，R6存储X2，Y2，Z2， 仅使用两个临时的寄存器R7，R8。 最终结果X3，Y3，Z3放在寄存器R1，R2，R3中，则倍点公式的计算过程如下所示:

由此可以看出，使用该倍点公式来计算X3，Y3，Z3的计算量为3M ＋4S ＋3C ＋6a。

1.3 Edwards 曲线上的快速标量乘算法

标量乘法是椭圆曲线上的关键运算，其运算速度影响着整个ECC 的运算效率。 因此，研究如何加快标量乘法的运算速度对于ECC 来说很重要。

标量乘kP 是指计算k 个P 相加的结果，其中k 为整数，P 为椭圆曲线上的一个点，则计算标量乘法kP 的过程为:

根据公式(8)，如果要计算5P，则先计算两次倍点运算得到4P，然后再计算4P ＋P， 即由点加运算得出5P 的结果。 椭圆曲线密码算法结构图如图1 所示，按照不同的层次来划分椭圆曲线系统，可以分为4 层，分别为协议层、椭圆曲线层、点运算层和有限域运算层，由图中可以看出，标量乘法调用群运算层中的点加运算和倍点运算，而点加运算和倍点运算调用底层有限域上的模加、模减、模乘和模逆运算。 若要提高标量乘法的运算速度，第一个方面是提高底层有限域上的基本运算，第二个方面是提高群运算层上的点运算速度，标量乘法是通过调用点加和倍点运算实现的，因此，减少点加和倍点的运算次数可以有效提高标量乘法的运算速度。 众所周知标量k 的长度越短，点加和倍点的调用次数越少，本文首先引入了一种新的标量乘运算算法EDSM[14]，然后针对该算法进行了改进，改进方案是将标量k 表示为四进制形式，并且给出了在四进制下标量乘法的实现算法，最后用Verilog HDL 语言对算法进行描述，通过FPGA 仿真实现，给出改进后算法的运算速度。

首先介绍一种Edwards 曲线上的快速标量乘算法EDSM 算法[14]。 计算标量乘kP，k 是域K 上的任意一个整数， P 为Edwards 曲线上的点， 将 k 表 示 成 三 进 制 形 式， 即 k ＝(kl-1kl-2…k1k0)，其中ki∈{0，1，2}。

算法1:EDSM 算法

输入:k 和P，l 为k 的三进制表示位数

输出:kP

在算法1 中，循环语句执行一次时，只需要计算一次倍点和一次点加，若忽略加减法运算且c ＝1，则倍点的运算量是3M ＋4S，点加的运算量是10M ＋1S ＋1D。 因此，执行一次循环语句总共需要的运算量是13M ＋5S ＋1D，如果假定标量k 的二进制长度l′ ＝256，则由计算可以得出标量k 的三进制表示长度为l ＝(log2/log3)·l′≈162， 因此可得，算法1 中计算标量乘法的EDSM 算法平均每比特的运算量为[(9M ＋1S ＋1D) ＋(3M ＋4S) ＋(162 - 2)(13M ＋5S ＋1D)]/256 ≈8.17M ＋3.15S ＋0.63D。 其中，算法1 中步骤1 计算初始值时，点加运算可以采用混合点加运算，其运算量为9M ＋1S ＋1D，而在循环体内采用标准射影坐标下的运算，因此采用普通点加运算即可，倍点运算的计算量是3M ＋4S，因此倍点运算相比点加运算来说，计算量少一些。

2 标量乘算法的改进

一个整数用三进制表示和四进制表示时，它们的位数是不同的，如果用四进制来表示标量k，那么相比于三进制来说， k 的长度会缩短20%左右。 在椭圆曲线标量乘法中，标量k 的长度决定着调用ECC 上点加运算和倍点运算的次数，如果k 的长度越短，则调用次数越少，相应的标量乘法的计算量就会减少。

2.1 Edwards 曲线上快速标量乘算法的改进

为了提高ECC 上标量乘法的运算速度，将k表示成四进制形式，即k ＝(kl-1kl-2…k1k0)， 其中ki∈{0，1，2，3}。 改进算法如下所示。

算法2:EDSM 算法改进

输入:k 和P，l 为k 的四进制表示位数输出:kP

因此，当算法2 中输入标量k 和Edwards 曲线上的点P 后，其输出的Q0即为标量乘法kP 的值。 下面给出算法的正确性证明:

当l ＝1 时，Q0＝k0P，for 循环语句不执行，结论显然成立。

当l ＝2 时，即k ＝k1k0＝k1×4 ＋k0，初值Q0＝k1P，Q1＝(k1＋1)P。 for 循环语句执行一次，此时i ＝0，ki＝k0，有以下四种情况。

执行parallel do 语句，由k0＝0 有: Q0＝2(Q0＋Q2)＝2(k1P ＋k1P)＝4 ×k1P，Q1＝4Q1＋P ＝4 × k1P ＋P；最后输出Q0＝4 × k1P 成立；

执行parallel do 语句，由k0＝1 有:Q0＝4Q0＋P ＝4 × k1P ＋P，Q1＝2(Q1＋Q3) ＝2((k1＋1)P ＋k1P)＝4 × k1P ＋2P；最后输出Q0＝4 ×k1P ＋P，成立；

执行parallel do 语句，由k0＝2 有: Q0＝2(Q0＋Q2)＝2((k1＋1)P ＋k1P) ＝4 × k1P ＋2P，Q1＝4Q1-P ＝4(k1＋1)P-P ＝4×k1P ＋3P；最后输出Q0＝4 × k1P ＋2P，成立；

执行parallel do 语句，由k0＝3 有:Q0＝4Q0- P ＝4(k1＋1)P -P ＝4 ×k1P ＋3P，Q1＝4Q1＝4(k1＋1)P ＝4 × k1P ＋4P；最后输出Q0＝4 ×k1P ＋3P，成立。

对于l ＞2 的情况，同样可以用数学归纳法来证明。 假设当l ＝n 时成立，证明l ＝n ＋1 时是否成立。 当l ＝n ＋1 时，即k ＝knkn-1…k1，根据假设，for 循环执行n 次后输出Q0＝knkn-1…k1P，Q1＝(knkn-1…k1＋1)P。 同理，当i ＝0，k0有四种取值，即等于0、1、2 或3，根据上述办法可知，无论k0为何值，最后算法求出的Q0就是Q0＝knkn-1…k0P 的值，所以，当l ＝n ＋1 时成立。

综上，根据数学归纳法可知，算法是正确的。

2.2 效率分析

在算法2 中，第一步计算初值时， ki的取值有四种，分别为0，1，2，3。 当ki取0 时，初值不用计算；当ki取1 时，Q0＝P，Q1＝2P，需要进行一次倍点运算；当ki取2 时，Q0＝2P，Q1＝3P，需要计算一次倍点和一次点加；当ki取3 时，Q0＝3P，Q1＝4P，需要计算两次倍点和一次点加。在循环体内，当ki取不同值时，Q0和Q1之间互不相关，可以在FPGA 中并行计算。 因此，执行一次循环运算最多需要计算两次倍点运算和一次点加运算。

下面分析当ki取不同值时，算法中计算Q0和Q1的平均运算量。

ki＝0 时，Q0和Q1平均运算量为[(13M＋5S＋1D)＋2(3M＋4S)＋10M＋1S＋1D]/2≈14.5M＋7S＋1D。 同样地，当分别计算ki＝1，2，3 时，计算Q0和Q1的平均运算量分别为14.5M＋7S＋1D，14.5M＋7S＋1D，11M＋8.5S＋0.5D。 设ki＝0，1，2，3 出现概率相同，并且随机出现，则算法2 中计算Q0和Q1的平均运算量为[3(14.5M＋7S＋1D)＋(11M＋8.5S＋0.5D)]/4≈13.62M＋7.37S＋0.88D。 假定k的二进制长度l′＝256，那么其四进制表示长度l ＝(log2/log4)·l′＝128，由于在算法2 中，步骤1 计算初值时，ki＝0，1，2，3，因此需要计算两次倍点运算和一次点加运算。 虽然在单次循环中比算法1多计算了一次倍点运算，但是算法2 中标量k 的长度变短了。 通过上述分析可以得出，算法2 中改进的EDSM 算法平均每比特的运算量为[(9M＋1S＋1D)＋2(3M＋4S)＋(128-2)(13.62M＋7.37S＋0.88D)]/256≈6.76M＋3.66S＋0.44D。

2.3 算法比较

表1 给出Edwards 曲线中不同算法的平均每比特的计算量比较，前三种算法的计算量参考文献[14]。 使用基本二进制算法计算标量乘法时，无论是采用从左向右计算还是从右向左计算，在标量k(假设k 是t 比特的数)中0 和1 均衡情况下，两种算法都需要进行t/2 次点加运算和t 次倍点运算。 因此，当标量k 为256 位数时，平均每比特的计算量为[(256/2)(10M ＋1S ＋1D) ＋256(3M ＋4S)]/256 ＝8M ＋4.5S ＋0.5D。

文献[16]利用连续倍点算法给出仿射坐标系下标量乘法的计算算法， 由于仿射坐标系下需要计算复杂的模逆运算，因此计算量较大，通过计算可得，其每比特的计算量为12.42M ＋1.89S ＋0.32D。 文献[17]中也是采用四进制来表示标量k，然后根据k 的形式给出计算标量乘法的算法。 但是标量乘算法中计算Q0和Q1不能并行计算，Q1的值依赖于Q0。 而本文标量乘算法中计算Q0和Q1时互相独立，可以并行计算，从而提高标量乘法的运算效率。 算法中的点加都采用混合点加，表中(S，D) 表示相对于M的比例，即(1，1) 表示1S ＝1M，1D ＝1M；(0.8，0.5) 表示1S ＝0.8M，1D ＝0.5M；(0.8，0) 表示1S ＝0.8M，1D ＝0M。

表1 Edwards 曲线上各种标量乘算法每比特计算量比较Table 1 Comparison of calculation amount per bit of various scalar multiplication algorithms on Edwards curve

通过表1 中不同算法的计算量可以看出，本文改进后的算法每比特计算量比其他算法的计算量都低，在(S，D)比例分别为(1，1)、(0.8，0.5)、(0.8，0)的情况下，改进后的算法比改进的蒙哥马利方法计算速度提高了35.8%、28.4%、21.5%，比EDSM 算法的计算速度提高了9.1%、10.0%、9.4%。

2.4 不同进制效率分析

标量乘法是ECC 上的核心运算，本文对于标量乘法的研究主要通过缩短标量k 的长度来减少点运算的调用次数，进而提高标量乘法的运算速度。 用不同的进制数表示标量k 时，其长度是不一样的，当采用三进制表示标量k 时，其长度为162，当采用四进制表示标量k 时，其长度为128，长度缩短了约20%。 根据上述计算结果可知，标量k 采用四进制后的运算速度比三进制仅提高了10%左右。 虽然四进制长度比三进制短，但是在四进制形式标量乘算法中计算Q0和Q1时，相比三进制形式需要多做一次倍点运算。也就是说，如果采用五进制或者其他进制，虽然标量k 的长度会变短，但同时也会需要计算更多的点加或倍点运算，导致计算量增加。 而且标量k 表示的进制数越多，需要的存储空间会越大，效率反而会降低。

3 标量乘的FPGA 实现与分析

为了更好地验证本文所设计标量乘算法的实现效率，利用FPGA 并行计算的特点对设计的算法进行仿真实现，下面给出具体分析。

3.1 标量乘算法的FPGA 实现

模加/减法器用于计算两个整数相加或者相减，然后对运算结果进行取模，即计算z ＝(x ±y)modp。 为了方便顶层文件调用，本文对于模加运算和模减运算的FPGA 实现采用可以同时具备模加/减的结构[18]。 如果要在电路中实现既能进行模加运算又可以进行模减运算，就需要在算法中设置一个控制位，然后根据该控制位的取值来决定进行模加运算还是模减运算。

模乘器采用文献[19]中基于进位存储加法(Carry-Save Adder，CSA)的Montgomery 模乘器，该模乘器将传统的串行结构改进为串并混合结构，改进后的Montgomery 模乘器能够在一个时钟周期内进行多次CSA 迭代运算，这样就可以降低一次模乘的时钟个数，从而提高了模乘的运算速度。 以256 比特的数据为例，当选取一个周期进行16 次迭代时，完成一次模乘仅仅需要0.22μs。

模逆运算采用二进制下的扩展欧几里德算法[18]，该算法可以计算z ＝xy-1modp。 欧几里德模逆算法中除法运算不能被FPGA 综合，但是，二进制下的扩展欧几里德算法对欧几里得模逆算法进行了扩充，并且避免了除法运算，因此，采用该算法进行模逆运算在时间上有很大的优势。

标量乘算法的FPGA 实现时，本文选取Edwards 曲线x2＋y2＝1 ＋(121665/121666)x2y2，p＝2255- 19。 曲线上的点为P ＝(xp，yp)。 采用Verilog HDL 硬件语言对算法进行代码描述，并使用Modelsime 10.2c 进行功能仿真。 仿真验证成功后，使用Synopsys 公司的Synplify Pro 编译器进行综合，综合实现是基于FPGA 硬件实现平台，选用Xilinx Virtex5 XC5VLX20T 芯片。 选取素域上256 位的数据进行测试，测试数据如下所示:

d ＝256′D37095705934669439343138083508754565189542113879843219016388785533085940283555；

k ＝256′HFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551；

先将k 表示为四进制形式，如下所示:

k ＝33333333333333330000000000000000333333333333333333333333333333332330321233222 231221301132132201033032321302230023330120302111101；

x1＝256′H216936D3CD6E53FEC0A4E231FDD6DC5C692CC7609525A7B2C9562D608F25D51A；

y1＝256H′6666666666666666666666666666666666666666666666666666666666666658.

仿真结果和综合后的器件频率分别如图2 和3 所示:

在仿真图2 中，当start ＝1 时对应的时间为80ns，当done ＝1 时对应的时间为1456780ns，所以，采用改进后的EDSM 算法计算一次标量乘需要的时钟个数为「1456780-80■/40 ＝36418。 由图3 中可知，标量乘综合后的器件频率为98.1MHz，因此，通过计算可得，完成一次标量乘需要的时间为0.37ms。

3.2 性能对比分析

为了说明本文设计的标量乘算法能取得比较好的效率，下面从完成一次256 位标量乘所需要的时钟个数、器件的时钟频率、运算时间和资源消耗进行分析。 表2 列举了不同文献的标量乘运算比较，如下所示:

在表2 中，为了公平合理地进行对比，所有文献都是选用Xilinx FPGA 作为仿真实现的硬件平台，并且都是针对256 位数据的标量乘运算进行研究。 文献[20]采用的是基于Karatsuba-Ofman 算法的两级流水线。 通过提出的乘法结构，设计了一种基于改进的Barret 模块化乘法算法的256 位模块化乘法器。 在模块化乘法器上，完成了标量乘法的调度。 文献[20]的时钟频率最低，资源占用中还使用了芯片内部的64 个18×18 的乘法器。 明显本文设计的算法在运算时间上更短，且本文不占用芯片内部任何乘法器。文献[21]中采用新型并行模块化乘法算法，通过合并四个并行乘法器单元可以在电路级别进行优化，文中仿真平台选用了两种，分别为Xilinx Virtex4 和Xilinx Virtex6，为了公平合理的对比，本文选用Xilinx Virtex4 芯片进行综合，结果表明，本文在计算标量乘运算中，不仅资源占用较少，运算时间也比文献[21]降低了60%。文献[22]中标量乘法中采用全字乘法器，该乘法器所需的时钟周期比较少，仿真是在Xilinx Virtex2 中进行实现的，和本文进行对比，其运算速度不如本文的的高，占用资源上不仅使用了63020 个查找表，还额外使用了128 个18×18 的乘法器。 文献[23]对于标量乘的研究是基于高基Montgomery 模乘流水化阵列结构，然后给出计算标量乘法的硬件结构。 为了便于比较，本文选用和文献[23]一样的仿真平台Xilinx Virtex5，虽然本文的时钟频率不如文献[23]高，使用的查找表数量也比文献[23]多，但是本文运算时间少，速度提高了一倍左右，而且文献[23]中还用到了芯片内部38 个DSP 模块，本文并没有占用芯片内部的DSP 模块，因此，本文具有更好的可移植性，对于其他硬件平台也适用。

表2 本文标量乘运算性能与其他文献性能的对比Table 2 Comparison of performance of scalar multiplication operation in this paper with that of other literatures

4 结语

Edwards 曲线是一种新型椭圆曲线，相比于传统的曲线来说，目前针对Edwards 曲线的研究很少，尤其在硬件实现方面寥寥无几。 但是，Edwards 曲线自身特点比其他曲线有很好的优势，研究Edwards 曲线对于椭圆曲线密码体制来说有重大的意义。 本文针对EDSM 算法进行了改进，将标量k 表示为四进制的形式来减少k 的长度，从而降低点加运算和倍点运算的调用次数，以此来减少标量乘法的运算量，通过FPGA 仿真实现得出，本文算法不但能够提高标量乘法的运算速度，而且具有良好的可移植性。