椭圆曲线密码算法有限域上的求逆运算

椭圆曲线密码算法有限域上的求逆运算

1种双域上统一的有限域求逆算法随着震源（1986年）和koblitz（1987年）分离分离，采用椭圆曲线密码体系（ecc）以来，椭圆曲线算法引起了越来越多的研究人员的注意。有限域上的模逆运算是椭圆曲线密码体制中的重要运算之一,也是最耗时的有限域运算,它通常基于有限域GF(p)和GF(2n)。通过用硬件实现模逆运算可以显著改进椭圆曲线密码系统的性能。目前,有限域上的求逆算法主要分为以下3种类型:(1)基于Fermat小定理。(2)基于欧几里德定理。(3)Montgomery模逆算法。第(1)种类型虽然简单但速度较慢,并且不支持GF(2n)上任意的不可约多项式,第(2)种和第(3)种类型的求逆算法适合硬件实现且运算速率较高,但基于欧几里德定理的求逆算法每次循环需要对多种情况进行判断,若采用串行判断的方式,判断延迟较长,若采用并行判断的方式,电路中需要更多的中间变量寄存资源。基于以上3种方法设计的硬件电路只能支持GF(p)或GF(2n)一个域上的模逆运算,如果能在同一硬件电路上实现双域上的求逆运算,可以提高电路灵活性。因此,提出一种双域上统一的有限域求逆算法就显得尤为重要。Montgomery模逆算法由Kaliski借鉴Montgomery模乘的思想提出,该算法包括加法、减法、奇偶校验、求二倍值、偶数折半等便于硬件实现的运算,并且需要的中间变量较少,占用资源较小,运算时间更短。鉴于Montgomery模逆算法的上述优点,在对有限域GF(p)和GF(2n)上的Montgomery模逆算法进行分析的基础上,提出一种双域上统一的模逆算法,并根据算法实现了一种可扩展的统一Montgomery模逆硬件结构,这种硬件结构能够支持576比特以内双域上任意长度数据的求逆运算,并且在0.18μm工艺标准单元库下进行了综合,时钟频率可达250MHz,与其他设计相比具有灵活性好、性能高的特点。2n2n上的法定算法有限域GF(p)上的Montgomery模逆算法如算法1所示,算法分为两部分,第一部分为近似Montgomery模逆算法,求得近似逆元a-12kModp,第二部分对近似逆元作进一步转换,求得Montgomery逆元a-12nModp,其中n=「lbp骎。算法1GF(p)上的Montgomery模逆算法有限域GF(2n)上的Montgomery模逆算法如算法2所示,GF(2n)上的元素都采用多项式基形式表示。算法同样分为两部分,第一部分求得近似逆元a(x)-1xk(modp(x)),第二部分对近似逆元作进一步转换,求得Montgomery逆元a(x)-1xnModp(x),其中n=deg(p(x))+1。第一部分除了第13步以外,其余的加法运算都为异或运算,第二部分中的k-n是k和n的差。算法2GF(2n)上的Montgomery模逆算法对两个有限域上的求逆算法进行比较,可以看出,两个算法具有很大的相似性,算法2中除以x的操作等价于算法1中除以2的操作,都可以通过将一个二进制数右移一位实现,算法2中乘以x的操作等价于算法1中乘以2的操作,都可以通过将一个二进制数左移一位实现。差别主要在于算法1中需要对u和v大小进行比较,而算法2中需要对u(x)和v(x)阶数进行比较,两者在硬件上无法用统一的运算单元实现,对于r和p的比较同样存在硬件实现上的差异,因此,这一差异成为阻碍用统一硬件结构实现双域上求逆运算的关键。基于这一点提出一个双域上统一的Montgomery模逆算法。3算法在gf2n域上的叠加运算算法1和算法2在结构上具有相似性,由于比较两个数的阶数需要从高位到低位对两个数进行逐位比较,当两个数位数都比较大时,电路延迟就比较大,影响电路的整体速度。为了便于在硬件电路上统一实现双域上的求逆运算,也为了提高运算效率,将算法2中对两个数阶的比较替换为对大小的比较,据此提出双域上统一的Montgomery模逆算法,如算法3所示。算法3双域统一的Montgomery模逆算法算法3同样分为两个部分,第一部分求得近似逆元,第二部分对近似逆元作进一步转换求得Montgomery逆元。当计算GF(p)域上的逆元时,算法中的加减运算为普通的加减运算。当计算GF(2n)域上的逆元时,算法中的加减运算为GF(2)上的运算,即都为异或运算,其中u0、v0分别表示u、v的最低位,n=「lbp骎。算法在GF(p)域上的正确性参考文献可以很容易证明。下面重点说明算法在GF(2n)域上的正确性。k=0时,s=1、v=a,显然a≡a(modp)成立。假设k=t时,as≡v2t(modp)成立,那么k=t+1时,s=2s,由于p用多项式表示是不可约多项式,可得出2as≡v2t+1(modp)成立,根据归纳法得到as≡v2k(modp)成立。同理,k=0时,r=0、u=p,显然0≡p(modp)成立。假设k=t时,ar≡u2t(modp)成立,那么k=t+1时,r=2r或r=r+s且u=(u+v)/2,由于p是不可约多项式,有2ar≡u2t+1(modp)成立,由前文可知2as≡v2t+1(modp)成立,可得出2a(r+s)≡(u+v)2t+1(modp)成立,即a(r+s)≡((u+v)/2)2t+1(modp),根据归纳法得到ar≡u2k(modp)成立。当PhaseI最后一轮循环结束时,u=1,由ar≡u2k(modp)可得r≡a-12k(modp),得到近似逆元。算法3中第一部分在计算近似逆元的时候,每一轮循环结束时,p=us+vr始终成立,倒数第二轮结束时,u=1,v=1,因此r的阶数deg(r)小于等于p的阶数deg(p),最后一轮循环r左移一位,全部循环结束后r的阶数小于等于deg(p)+1。在10、11两步进行判断,r≥2n即deg(r)=deg(p)+1时,将p左移一位以后与r异或,然后判断r≥2n-1即deg(r)=deg(p)时,将p与r异或,经过这两步以后,可以得到deg(r)<deg(p)。4模逆运算数据路径双域模逆算法的硬件电路设计如图1所示,整个电路包括寄存器单元、模逆运算数据路径、状态机控制电路以及K计数器。设计采用可扩展设计,能够支持最高576位的任意长度下的求逆运算,寄存器单元包含u、v、r、s、p5个寄存器,每个寄存器的数据长度为192比特,数据深度为3,u、v、r、s寄存器用来存储每轮循环的中间值,p寄存器用来存储模数p。模逆运算数据路径是主要的运算单元,在状态机控制下完成模逆运算功能,其内部加减以及移位单元每次能够处理192比特的数据。状态机控制电路作为整个电路的核心控制器,协调整个模逆运算的操作。K计数器用来计算并存储k值。Start_inv为运算开始信号,Length为操作数长度信号,运算完成以后状态机给出完成信号done,结果rout由数据路径输出。寄存器单元在状态机写或读信号Write/Read_u、Write/Read_v、Write/Read_r、Write/Read_s、Read_p的控制下把数据送到模逆运算数据路径或把模逆运算数据路径输出的结果写入寄存器。模逆运算数据路径电路结构如图2所示,数据宽度w=192bit,包含2个双域减法器、1个双域加法器、1个左移单元、4个右移单元和13个数据选择器,所需的选择控制信号在图1中表示为select/control,完成算法3中的所有加、减、异或运算。算法中的比较操作都可以用减法器2来完成,通过减法器2的借位信号borrowbit来判断两个数的大小。数据选择器的选择信号由状态机生成。b是预计算的常数2n。双有限域加、减法器是数据路径的核心单元,可以计算两个有限域上的加、减法运算,它的速度直接影响到整个求逆运算的效率。为了提高运算速度,设计采用6个32比特的字加、减法器串接,即一次可以对192比特的数据进行计算。双有限域加法模块电路结构如图3所示。每个字加法器不必等待上一级字加法器产生的进位,而是预先针对两种进位情况分别进行计算,得到由两种不同进位值计算出的结果。当第一级的字加法器产生正确的进位时,由该进位信号对第二级字加法器的两个计算结果进行数据选择,再由第二级字加法器的正确进位值对第三级字加法器的两个计算结果进行数据选择,最后由第五级字加法器的正确进位值对第六级字加法器的两个计算结果进行数据选择。若要计算数据的长度超过192比特,则需要将第六级字加法器的正确进位返回第一级字加法器,进行第二轮的计算。双有限域字加法器的电路结构如图4所示。其中DFA为双有限域加法器。双有限域减法采用与双有限域加法模块相同的设计方式,不同之处仅在于双有限域字加法器换为双有限域字减法器。5性能的实现5.1ep2s293器件的实现设计用Verilog语言进行描述,用ModelSimSE6.0c进行功能仿真,然后,用Altera公司的QuartusII7.2进行综合以及布局布线,最后下载至StratixII的EP2S90F1508C3器件上得到了正确的验证。表1中列举了设计在FPGA上实现的性能参数。为了进一步准确地评估硬件电路的实现性能以及完成最终的ASIC实现,使用Synopsys公司的DesignCompilerforSolaris工具,采用0.18μmCMOS工艺标准单元库进行综合,综合报告如表2所示。5.2基于gfp和gf2n上的法定模式有限域内的求逆运算是最耗时的有限域运算,因此,执行一次模逆运算所使用的时间是衡量一个设计是否高效的重要参数。一次模逆运算的时间由一次运算的时钟周期数和时钟频率来共同决定,一个好的设计应该具有较少的时钟周期数和较高的时钟频率。E.Savas和C.K.Koc在文献中对GF(p)上的Montgomery模逆算法进行改进,并在同一硬件电路上实现了GF(p)和GF(2n)两个域上的Montgomery模逆算法。A.A.A.Gutub等人在文献中基于GF(p)和GF(2n)上的Montgomery模逆算法提出了一种可扩展统一硬件电路结构。在文献和文献中执行一次模逆运算使用的时钟周期数分别如表3所示,从表3中可以看出,设计的时钟周期数要明显小于前两者,与文献和文献相比,设计的时钟数分别减少了63%和75%。M.Naseer和E.Savas在文献中对双域上的Montgomery模逆算法进行改进提出双域统一的算法并给出了可扩展的硬件结构设计。E.Savas在文献中使用RSD(RedundantSignDigit)算法对Montgomery模逆算法进行改进,并给出了硬件实现的性能参数。图5给出了文献在不同长度数据下做一次模逆运算所需的总时间与该设计相比较的结果。其中,纵轴表示的是一次模逆运算的时间,横轴表示的是进行模逆运算的操作数的长度,可以看出该设计的运算时间具有明显的优势。在数据长度为576位时,该设计执行一次模逆运算的总时间比文献和文献分别减少了64%和44%,也说明设计在对大数进行模逆运算时具有更高的效率。6基于gf-p的统一模逆算法针对能