一种多乘法器结合的dsps乘法器逆元计算的新思路

一种多乘法器结合的dsps乘法器逆元计算的新思路

0高效乘子法逆元计算方法的优化设计有限区域gf（2n）是一个包含2n个元素的区域。在密码学中，基于该区域的乘法逆元计算广泛应用于公钥通算系统中的sra算法和椭圆曲线算法，以及对称密码系统中的asa算法s盒的计算。对于乘法逆元的计算,传统方法主要为扩展欧几里德算法和费尔马小定理。从纯粹计算角度上来考虑,扩展欧几里德算法的计算复杂度要小于费尔马小定理,所以前者的应用范围更加广泛。现代数字信号处理器(DSPs)的性能发展得相当迅速,在最新的TMS320C6400系列DSPs中,包含了Galois域乘法器,这使得有限域上的乘法计算变得相当容易,同时也使费尔马小定理有了更大的应用空间。本文根据费尔马小定理的求逆方法,结合C64x系列DSPs的流水线特点及其Galois域乘法器,对算法进行调整,设计了一个高速的乘法逆元计算方案。这一结果使得DSPs在进行智能信息处理时,加快了可能用到的加密算法的运算速度。1扩展欧几里德算法扩展欧几里德算法:令F(x)为最高项n的不可约多项式,A(x)是一个不为0的在有限域GF(2n)中的元素,表示为A(x)=axi(i=0,…,n-1),因为F(x)和A(x)互质,其最大公约数为:gcd(F(x),A(x))=1.因此存在一个次数小于n的多项式B(x)和一个多项式C(x),满足:A(x)B(x)+F(x)A(x)=gcd(F(x),A(x))=1,所以有A(x)B(x)=1modF(x).这样B(x)是A(x)的乘法逆元,B(x)就是通过扩展欧几里德算法得到的。算法描述如下:输入:F(x)和A(x)<>0输出:B(x)满足A(x)B(x)=1modF(x)。第一步:R(-1)(x)=F(x),R(0)(x)=A(x),U(-1)(x)=0,U(0)(x)=1,i=0第二步:do{i=i+1Q(i)(x)=R(i-2)(x)/R(i-1)(x)R(i)(x)=R(i-2)(x)+Q(i)(x)/R(i-1)(x)U(i)(x)=U(i-2)(x)+Q(i)(x)U(i-1)(x)}while(R(i)(x)<>0)第三步:B(x)=U(i-1)(x)=A(-1)(x)费尔马小定理的求逆方法:令A(x)为有限域GF(2n)中的元素,B(x)是A(x)的乘法逆元,有A(2n)(x)=A(x)因此A(-1)(x)=A(2n-2)(x)又因为A(2n-2)(x)=A2(x)*A(22)(x)*…*A2n-1(x)这样由A(x)就可以求出B(x)。上述两种算法中,扩展欧几里德算法主要用到了求商和加减法运算,对于有限域GF(2n)上的元素,加减法运算等同于位上的异或运算,求商也只有用笔算除法一样的步骤。采用移位异或的方法,可以说这种方法没有很复杂的运算,但对于微处理器运算也还是需要花费很多的时间;费尔马小定理的算法在普通微处理器上运行绝对比扩展欧几里德算法要慢,且有限域上的乘法在一般微处理上的实现相当麻烦,但对于C64X系列的DSPs,由于其特有的Galois域乘法器及高性能的流水线,我们有理由认为用费尔马小定理的算法可以轻松的实现求逆运算。2突破不约函数的有限元转化C64x包含的Galois域乘法器硬件由C64x特有的Galois域多项式生成函数寄存器(GFPGFR)控制。GFPGFR属于CPU的控制寄存器,只能由MVC指令访问。Galois域乘法器对域形式为GF(2n)的所有的有限域乘法都可以编程执行,但n的数值范围是1～8,可以用任何的不可约多项式。GFPGFR各个数位定义格式如图1所示。其中SIZE定义n的值,POLY定义不可约多项式。GMPY4指令的汇编格式:GMPY4(.unit)src1,src2,dst。它把src1、src2看做4个打包的无符号数,同时对4个字节分别执行4个有限域乘法运算,结果存入dst。下面举例说明有限域GF(28)上的乘法运算。假设乘数为0x57,0x83,用多项式表示分别为x6+x4+x2+x+1,x7+x+1,取不可约多项式为x8+x4+x3+x+1,即0x11b,这也是AES算法中进行有限域运算时用到的不可约多项式。做有限域乘法如下:(x6+x4+x2+x+1)(x7+x+1)=x13+x11+x9+x8+x7+x7+x5+x3+x2+x+x6+x4+x2+x+1=x13+x11+x9+x8+x6+x5+x4+x3+1x13+x11+x9+x8+x6+x5+x4+x3+1modx8+x4+x3+x+1=x7+x6+1最终得到的结果为0xc1。在用GMPY4指令时,先用MVC指令对GFPGFR赋值,n取8,不可约多项式设为0x11b,两个乘数0x57,0x83分别存放在A0,A1的低8位,执行GMPY4.M1A0,A1,A2指令后,结果0xc1存放到A2的低8位。3a-1运算我们以有限域GF(28)为例进行设计,设a是有限域GF(28)中的一个元素,根据上述费尔马小定理的求逆方法,求a-1就等于求a254。我们首先假设a存放在通用寄存器A0中,src1与src2都设为A0,dst设为A1,用.M1作为运算单元,指令为:GMPY4.M1A0,A0,A1运算一次后,求得a2,再下一步得到a4,这样一直运行若干次后,最终目的是得到a254。这个过程中有一个怎样计算效率最高的问题,我们结合C64x系列DSPs的流水线结构进行了设计。4多数同时求逆运算现代微处理器是用结构的复杂性来换取提高速度的。它把指令处理分为几个子操作,每个子操作在微处理器内由不同的部件来完成。对于微处理器的每个部件来说,每隔一个时钟周期就可以进入一条新指令,这样在同一时间内就有多条指令交迭的在不同的部件内处理,这种工作方式叫做流水线的工作方式。C64x具有两个.M单元(.M1,.M2),可以同时进行有限域乘法运算。C64x中的所有指令都按照取指(Fetch)、译码(Decode)和执行(Execute)3级流水线运行,其中每一级流水线又包括几个节拍。取指包含PG,PS,PW,PR四个节拍,译码包含DP,DC两个节拍,然后执行级的节拍跟指令的具体情况有关。对于GMPY4为E1,E2,E3,E4的四个节拍,每一个节拍为一个时钟周期,也就是说每执行一条GMPY4指令至少需要10个时钟周期。C64x的每个取指包(FP)可以包含8条指令,每个取指包中的指令又分为1～8个执行包(EP),每个执行包中的指令都可以并行执行,对于GMPY4指令来说,由于运算单元的限制,每次最多只能有两条并行。对一个元素进行求逆运算时,可以同时采用两个乘法器对计算方式加快速度,计算结果最快需要18个时钟周期。在实际的系统中,往往需要求逆的数为多个,比如AES算法S盒中用到的求逆运算,如果取明文为128位的方式,则需要对32个数进行求逆,所以需要重点考虑同时对多个数求逆的运算。下面对8个数同时求逆的方案进行说明。我们采用了两个乘法器分别对4个数进行运算:先假设a,b,c,d,e,f,g,h分别保存在A0,B0中,然后用两个有限域乘法器分别对A0,B0中的数进行操作。这样可以保证两个乘法器之间始终保持并行,不会浪费一个时钟周期。根据这种思想设计的流水线如图2所示。实现这个过程的代码如下:最终a-1,b-1,c-1,d-1,e-1,f-1,g-1,h-1分别保存在寄存器A12,B12中,处理8个数共用21个时钟周期,运算效率为21/8=2.625时钟周期/数。5教育上的求逆运行机制综上所述,用费尔马小定理的算法来计算有限域GF(2n)上的乘法逆元在C64x系列DSPs中的实现