一种可重构的有限域gf21km逆元结构

一种可重构的有限域gf21km逆元结构

在编码理论、通信理论和密码学等领域，有限域有广泛应用。在有限域的计算中，逆求正和消法是最复杂、最耗时的计算。目前，关于有限域反演算法的研究主要集中在固定有限区域。这种反演结构不能满足有限区域的要求。在实际应用中，需要根据特定的安全度选择有限区域的大小。例如，ksss提出了一种可变有限区域的乘法结构，但关于变有限区域反演结构的文献很少。主要原因是大乘逆元的解算方法本身非常复杂。对于反演结构，为了表示xm和x-1的值，需要添加两个ml值。可以重建每个反演，但对于每个反演，计算周期和油耗是固定的。例如，对于不可承受常数的193个逆元解的所需时间与非线性公共解的所需时间相同。因此，这种逆元结构缺乏灵活性。对于具体的不可边界项f（x），无法根据f（x）优化性能。本文在扩展欧几里德算法基础上,提出了一种可重构的有限域GF(2k)(1<k≤m)逆元结构,其中m是此结构支持的最大有限域的度.选择度为k的不可约多项式F(x),则每个逆元计算需要2k时钟周期,关键路径延迟复杂度为O(k).它的面积复杂度与最大有限域的度m成正比.采用门控时钟关闭未使用的触发器以减少电路功耗.逆元的计算周期和功耗均随不可约多项式的度k减小而减少,因此具有高灵活性.该逆元求解结构适合变有限域、低复杂度和低功耗的片上智能卡VLSI设计.1基于逆元算法的可重构性算法多项式有限域逆元通常采用原始欧几里德算法求解,该算法的时钟周期是可变的,同时它需要大量乘法运算,因此它的硬件实现复杂.Brunner等提出一种规则性的欧几里德算法,该算法逐比特地减少R和S的度,完成逆元计算需要2m次迭代运算,其中,R和S是度为m的多项式;U和V是m-1的多项式,分别表示如下:R=m∑i=0rixi,S=m∑i=0sixiU=m-1∑i=0uixi,V=m-1∑i=0vixi}(1)R=∑i=0mrixi,U=∑i=0m−1uixi,S=∑i=0msixiV=∑i=0m−1vixi⎫⎭⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪(1)关于R和U有如下关键运算:(1)R=xR移位操作,xR=m-1∑i=0rixi+1(2)xR=∑i=0m−1rixi+1(2)(2)U=xUmodF(x),由xmmodF(x)=fm-1xm-1+fm-2xm-2+⋯+f1x+f0xmmodF(x)=fm−1xm−1+fm−2xm−2+⋯+f1x+f0推导出xUmodF(x)=m-1∑i=0uixi+1=m-2∑i=0uixi+1+um-1xm=m-2∑i=0uixi+1+um-1(fm-1xm-1+fm-2xm-2+⋯+f1x+f0)(3)xUmodF(x)=∑i=0m−1uixi+1=∑i=0m−2uixi+1+um−1xm=∑i=0m−2uixi+1+um−1(fm−1xm−1+fm−2xm−2+⋯+f1x+f0)(3)(3)U=U/xmodF(x).由f0=1可推导出x-1modF(x)=xm-1+fm-1xm-2+…+f2x+f1(4)利用式(4)可得Ux=m-1∑i=1uixi-1+u0x=m-1∑i=1uixi-1+u0(xm-1+fm-1xm-2+⋯+f2x+f1)(5)基于逆元算法,本文提出了一种改进的可重构性算法,如算法1所示.令不可约多项式F(x)=xk+fk-1xk-1+⋯+f0k≤m,B(x)=k-1∑i=0bixi算法1其中,m为此逆元算法所支持的最大多项式的度.用一个寄存器deg2保存循环次数,其值等于2k.当循环的次数等于2k时,逆元计算完成.修改算法1的初始值U(x)=A(x)xm-k后,它支持有限域的除法.当A(x)=1时,计算逆元B(x)-1;当A(x)≠1时,计算除法A(x)/B(x).2门控信号相关电路表1给出了所有的操作.这些操作取决于rm、sm和计数器cnt零检测标志f.为了实现方便,引入2个额外的信号:Τ={Srm=0orsm=0S-Rrm=sm=1L={Vrm=0orsm=0V-Urm=sm=1}(6)把表1改写成表2.根据表2中的操作,引入3个控制信号:MultRU=(rm=0)or(f=0)Exchange=(rm=1)and(f=0)Reduce=(rm=1)and(sm=1)再引入另外一个信号,W={Urm=0orf=1Lrm=1andf=0(7)对于寄存器U的操作,可以简化为U={xWmodFΜultRU=1W/xmodFΜultRU=0(8)与文献中算法比较,算法1有如下不同点:(1)初始值不同.置寄存器R和S的高k+1位分别为B(x)和F(x),置R和S的低m-k位为0;置寄存器U的第m-k+1位为1,即um-k=1,置其他位为0;置寄存器V全部为0.(2)循环次数可变.在算法1中,迭代次数是2k(k是不可约多项式的度),由比较器控制.当循环的次数等于2k时,完成逆元计算.在算法中,迭代次数是一个固定值2m.比较电路由[lbm]个异或门和lbm个与门实现.(3)关键运算Wx和W/x.令W=wm-1xm-1+wm-2xm-2+⋯+wm-kxm-k+⋯+w0由于R、S、U和V的低m-k比特都不参与运算,且都等于0.因此可推导出W的低(m-k)bit也都为0.将W改写为W=wm-1xm-1+wm-2xm-2+…+wm-kxm-k(9)(1)定义Wx运算如下:Wx=[(wm-1xk-1+wm-2xk-2+⋯+wm-k)x]xm-k=[(wm-2xk-1+⋯+wm-kx+0)+wm-1xk]xm-k(10)由于xkmodF(x)=fk-1xk-1+fk-2xk-2+…+f1x+f0,代入式(10),得Wx=wm-2xm-1+⋯+wm-kxm-k+1+0xm-k+wm-1(fk-1xm-1+fk-2xm-2+⋯+f1xm-k+1+f0xm-k)(11)(2)定义W/x运算如下:W/x=[(wm-1xk-1+wm-2xk-2+⋯+wm-k)/x]xm-k=[(0xk-1+wm-1xk-2+wm-2xk-3+⋯+wm-k+1)+wm-k/x]xm-k(12)由于x-1modF(x)=(xk-1+fk-1xk-2+…+f2x+f1),代入式(12),得W/x=(0xm-1+wm-1xm-2+wm-2xm-3+⋯+wm-k+1xm-k)+wm-k(mm-1+fk-1xm-2+⋯+f2xm-k+1+f1xm-k)(13)由于xk和x-1随着不可约多项式F(x)的变化而变化,添加2个m-bit的寄存器P(x)和Q(x)分别保存xk和x-1的值,即Ρ(x)=m-1∑i=0pixi=fk-1xm-1+fk-2xm-2+⋯+f1xm-k+1+f0xm-kQ(x)=m-1∑i=1qixi=xm-1+fk-1xm-2+⋯+f2xm-k+1+f1xm-k}(14)在式(13)中,由于不可约多项式F(x)的度k是可变的,因此wm-k在W信号中的的位置也是可变的.为了确定wm-k的值,需添加m个配置信号cfg,定义:cfg(i)={10≤i≤m-k0m-k<i<m-1(15)令G是一组m维的信号,G(0)=cfg(0)andw0最后,G(m-1)等于wm-k的值.上面的电路由一组与门和或门实现.此电路形成逆元结构的主要关键路径延迟,其复杂度为O(k).为了实现Wx和W/x运算,添加另外一个信号Carry,Carry=(MultRUandwm-1)or(～MultRUandG(m-1))当不可约多项式F(x)的度为k(k<m)时,R,S,U,V的最低m-kbit都不参与运算.触发器在发生翻转时,会消耗能量.为了减少功耗,采用门控时钟将未使用的寄存器(即R,S,U,V的低m-k触发器)关闭.门控信号gate定义为gate(i)={00≤i<m-k1m-k≤i<m-1(16)gate由配置信号cfg左移一位后取反得到.图1给出了一种可重构性的逆元结构.由逻辑控制单元、计算单元、寄存器文件3部分组成.对于特定的不可约多项式F(x)=xk+fk-1xk-1+⋯+f0根据式(14),将相应的值装载到P和Q寄存器中,同时根据式(15)设定相应的配置信号cfg.这样完成了不可约多项式F(x)的逆元结构配置.3基于时间效率的逆元结构的可重构性分析表3给出了几种逆元结构的性能比较结果.Guo等提出的逆元结构是一种串行进/串行出的动脉结构,它的面积复杂度为O(m·lbm),该结构不适合小面积要求的电路实现.Araki等提出的逆元结构的计算时钟周期是可变的,对于不同的逆元,计算时钟周期在2m+3与3m+2之间变化.不确定时钟周期数导致计算性能不稳定.Brunner等提出的逆元结构的时间复杂度和面积复杂度都为O(m).通过添加2个mbit的寄存器保存xmandx-1的值,可以实现可重构性.它的计算时间为固定值2m时钟周期.当计算不可约多项式F(x)的度小于m的逆元时,所有的寄存器(触发器)都会翻转,这样耗费很多额外的电能.本文提出的逆元求解结构是可重构的,m是它支持的最大有限域的度.除了需要4个寄存器(R,S,U,V)外,还需要2个寄存器P和Q.它的计算时钟周期随着多项式度的变化而变化,且等于2k时钟周期(k为不可约多项式的度).在本结构中使用“门控时钟”关闭未使用的触发器以减少电路功耗.用verilog硬件描速语言编写了这种逆元结构,功能和时序仿真验证了电路的正确性.选择最大多项式度m=193,在Xilinx的FPGA(XCV2000E)上通过