基于复合域求逆的低电路面积s盒构造方法

基于复合域求逆的低电路面积s盒构造方法

0基于复合域求逆的s盒实现方法sms4算法是国家商业密码管理办公室于2006年1月发布的一套对称密码算法。这是中国第一个官方发布密码算法的算法。sms4算法的提出极大地促进了密码算法的研究和定制过程。S盒是SMS4算法中唯一的非线性运算,由于它作用于每一轮的加解密运算和密钥扩展,所以S盒的硬件实现性能在很大程度上决定了整个SMS4算法的硬件实现性能,如电路面积、吞吐量、功耗等.因此,当SMS4算法用于智能卡等产品时,它们有限的芯片面积就必须需要一种低电路面积开销的S盒实现,以减少SMS4算法硬件实现的电路面积,从而符合智能卡等产品对电路面积的要求.在SMS4算法硬件设计过程中,通常采用查找表方法构造S盒,硬件实现简单,但面积开销较大.Liu等提出了基于有限域求逆的S盒构造方法,但其在GF(28)域上的求逆运算非常复杂,难以用硬件实现.为了解决上述问题,本文根据SMS4算法的S盒和AES算法的S盒在结构上的相似性,参考AES算法S盒的研究方法,在Liu等的研究基础上,引入新的复合域,将GF(28)域上的求逆运算转化成GF(((22)2)2)复合域上的求逆运算,从而提出了一种易于硬件实现,基于复合域求逆的低硬件开销的S盒实现新方法.1加密轮密钥算法SMS4算法是一种分组密码算法,其分组长度和密钥长度均为128bit.加密算法与密钥扩展算法都采用32轮非线性迭代结构.解密算法与加密算法的结构相同,只是轮密钥的使用顺序相反,解密轮密钥是加密轮密钥的逆序.1.1sms4算法原理设明文输入为X=(X0,X1,X2,X3),Xi∈GF(2)32,i=0,1,2,3,密文输出分别为Y=(Y0,Y1,Y2,Y3),Yi∈GF(2)32,i=0,1,2,3,轮密钥为RKi∈GF(2)32,i=0,1,…,31,则算法的加密变换为Xi+4=F(Xi,Xi+1,Xi+2,Xi+3,RΚi)=Xi⊕Τ(Xi+1⊕Xi+2⊕Xi+3⊕RΚi),i=0,1,⋯,31(1)(Y0,Y1,Y2,Y3)=R(X32,X33,X34,X35)=(X35,X34,X33,X32)(2)式中,F为轮函数;T为合成置换;R为反序变换.合成置换T:GF(2)32→GF(2)32是一个可逆变换,由非线性变换τ和线性变换L复合而成,即T(·)=L(τ(·)).非线性变换τ由四个并行的S盒构成,每个S盒为固定的8bit输入8bit输出的置换,记为Sbox(·).设变换τ输入为A=(a0,a1,a2,a3),ai∈GF(2)8,i=0,1,2,3,输出为B=(b0,b1,b2,b3),bi∈GF(2)8,i=0,1,2,3,则B=(b0,b1,b2,b3)=τ(A)=(Sbox(a0),Sbox(a1),Sbox(a2),Sbox(a3))(3)非线性变换τ的输出即线性变换L的输入.设L的输入为B∈GF(2)32,输出为C∈GF(2)32,则C=L(B)=B⊕(B<<<2)⊕(B<<<10)⊕(B<<<18)⊕(B<<<24)(4)式中,<<<i表示32bit循环左移i位.SMS4算法加密流程如图1所示.算法的解密变换与加密变换结构相同,不同的仅是轮密钥的使用顺序:加密变换轮密钥使用顺序为(RK0,RK1,…,RK31);解密变换轮密钥使用顺序为(RK31,RK30,…,RK0).1.2轮密钥生成方法2,2,3.轮密钥由加密密钥通过密钥扩展算法生成,其结构与加密变换类似.设加密密钥为MK=(MK0,MK1,MK2,MK3),MK=(MK0,MK1,MK2,MK3),MKi∈GF(2)32,i=0,1,2,3.令Ki∈GF(2)32,i=0,1,…,35,轮密钥为RKi∈GF(2)32,i=0,1,…,31则轮密钥生成方法如下:(Κ0,Κ1,Κ2,Κ3)=(ΜΚ0⊕FΚ0,ΜΚ1⊕FΚ1,ΜΚ2⊕FΚ2,ΜΚ3⊕FΚ3)(5)RΚi=Κi+4=Κi⊕Τ′(Κi+1⊕Κi+2⊕Κi+3⊕CΚi)(6)式中,T′变换与加密变换中的T变换基本相同,只是其中的线性变换L修改为以下L′,即L′(B)=B⊕(B<<<13)⊕(B<<<23)(7)系统参数FKi(i=1,2,3)和固定参数CKi(i=1,2,3)均为常数,其取值方法参见算法标准文献.2s盒的sesf运算Liu等提出的基于有限域求逆构造的S盒由求逆变换和仿射变换组成,其代数结构为Sbos(a)=Ι(a⋅A1+C1)⋅A2+C2(8)式中,a为S盒的8bit输入;I为GF(28)上的乘法求逆;A1,A2∈GL(8,2),C1,C2∈GF(2)8.循环矩阵A1,A2和向量C1,C2分别为A1=A2=[1110010111110010011110011011110001011110001011111001011111001011]C1=C2=(1,1,0,0,1,0,1,1)式(8)中的仿射变换是线性运算,GF(28)域上的乘法求逆是非线性运算.其中,GF(28)上乘法求逆的八次不可约多项式为Μ(x)=x8+x7+x6+x5+x4+x3+x2+1(9)有限域GF(28)上的二进制多项式a(x)的乘法逆元是满足a-1(x)a(x)=1modΜ(x)(10)的二进制多项式a-1(x).式(8)所描述的S盒结构如图2所示.其中,ai和bi分别表示τ变换的第i个S盒的输入和输出字节(i=0,1,2,3).解密过程中的S盒运算方法与加密过程相同,只需将仿射变换改成仿射逆变换.3在复合区域中获得s盒结构的方法3.1复合域的二次数控扩张通过引入新的复合域,将GF(28)上的运算映射到GF(((22)2)2)复合域上进行,从而降低S盒的计算复杂度,S盒实现的算法流程如图3所示.具体的计算过程分为以下三步:(Ⅰ)使用同构映射T将有限域F的所有元素一一映射到复合域C中;(Ⅱ)在复合域C上求逆;(Ⅲ)使用同构映射T-1将复合域C上所有元素映射到有限域F中,完成计算.图3中,复合域C不是由GF(2)直接进行八次扩张得到的,而是由不可约多项式重复二次代数扩张得到.下面将介绍代数扩张所用到的不可约多项式的求解过程.设二元矩阵T(k×k)为域GF(2)的元素一一映射到复合域GF((2n)m)(mn=k)上的同构映射,T-1为反方向的同构映射.GF((2n)m)域上的所有运算都需要模两个域产生多项式Q(y)和P(x).其中Q(y)是产生子域GF(2n)的二进制多项式,P(x)是GF(2n)域上的多项式,产生复合域GF((2n)m),即Q(y)=yn+qn-1yn-1+⋯+q1y+1,qi∈GF(2),i=1,2,⋯,n-1(11)Ρ(x)=xm+pm-1xm-1+⋯+p1x+p0,pi∈GF(2n),i=0,1,⋯,m-1(12)由式(12)可以产生复合域C中用于二次代数扩张的各个不可约多项式如下GF(22):x2+μ0x+θGF((22)2):x2+μ1x+ΝGF(((22)2)2):x2+μ2x+ν}(13)为了简化计算,可令μ0=μ1=μ2=1;θ,N,ν选择不同的值,可产生432种不同的二元矩阵T.本文取θ={1},N={10},ν={1001}.在上述方法中,GF(28)域上的乘法求逆可以转换到复合域GF((24)2)上实现,GF(24)域上的乘法可以进一步转换到GF(22)域上并继而转换到GF(2)域上实现.GF(2)上的乘法其实是与操作,同构映射和仿射变换可以用较简单的组合逻辑实现,因此大大降低了整个S盒计算的复杂度,从而减少了硬件实现的电路面积.3.2源生长y型从整个S盒计算过程来看,步骤(Ⅱ)中的复合域求逆是难点也是重点.下面给出复合域GF((24)2)及其子域上乘法求逆的详细推导过程.设GF((24)2)域上的任意元素g=γ1y+γ0的乘法逆元为d=δ1y+δ0.其中,γ1,γ0,δ1,δ0∈GF(24).根据乘法逆元表达式(10)和不可约多项式(13),有gd=(γ1y+γ0)(δ1y+δ0)mod(y2+y+ν)=[(γ1δ1)y2+(γ1δ0+γ0δ1)y+(γ0δ0)]⋅mod(y2+y+ν)=(γ1δ0+γ0δ1+γ1δ1)y+(γ0δ0+γ1δ1ν)=1(14)由式(14)中对应项系数相等可得γ1δ0+γ0δ1+γ1δ1=0(15)γ0δ0+γ1δ1ν=1(16)从而求出δ1=(γ21ν+γ1γ0+γ20)-1γ1δ0=(γ21ν+γ1γ0+γ20)-1(γ0+γ1)}(17)从式(17)可以看出,GF((24)2)上的求逆运算主要包括GF((24)2)上的求逆运算和乘法运算.同理,设GF((22)2)域上的任意元素γ=Γ1z+Γ0的乘法逆元为δ=Δ1z+Δ0,Γ1,Γ0,Δ1,Δ0∈GF(22),,根据式(10)和式(13),可得γδ=(Γ1z+Γ0)(Δ1z+Δ0)mod(z2+z+Ν)=1(18)从而求出Δ1=(Γ21Ν+Γ1Γ0+Γ20)-1Γ1Δ0=(Γ21Ν+Γ1Γ0+Γ20)-1(Γ0+Γ1)}(19)类似地,设GF(22)域上的任意元素Γ=g1w+g0的乘法逆元为Δ=d1w+d0,g1,g0,d1,d0∈GF(2),根据式(10)和式(13),有下面的等式成立ΓΔ=(g1w+g0)(d1w+d0)mod(w2+w+1)=1(20)继而求出d1=(g21+g1g0+g20)-1g1d0=(g21+g1g0+g20)-1(g0+g1)}(21)由于g∈GF(2),故g2=g-1=g,化简式(21)可得d1=(g1+g1g0+g0)g1=g1d0=(g1+g1g0+g0)(g0+g1)=g1+g0}(22)3.3k-1.2gf2002域的映射在3.1节提到的方法中,同构映射将有限域的求逆转换到复合域中进行,对整个S盒实现方法至关重要.本文采用文献提出的计算同构映射的方法,具体描述如下:设GF((2n)m)域的素元α是式(12)所示P(x)的根,即P(α)=0;GF(2n)域上的素元ω是式(11)所示Q(y)的根,即Q(ω)=0.GF((2n)m)域的每一元素A都能表示为GF(2n)域上的m阶向量,而这m阶向量中的每个元素本身又是一个n阶向量,则A用mn=k阶的二元向量表示为A=(am-1,am-2,⋯,a0)=((am-1,n-1,am-1,n-2,⋯,am-1,0),(am-2,n-1,am-2,n-2,⋯,am-2,0),⋯,(a0,n-1,a0,n-2,⋯,a0,0)),ai∈GF(2n)‚ai,j∈GF(2)(23)GF(2k)域上的乘法运算的模M(z)可表示为Μ(z)=zk+rk-1zk-1+⋯+r1z+1,ri∈GF(2),i=1,2,⋯,k-1(24)设β是M(z)的根,B={βk-1,βk-2,…,β,1}是GF(2k)域的标准基.GF(2k)域的每一元素都可以表示为k阶向量,且都是基元素的线性组合.为了构造同构映射,用B中的k个基元表示GF((2n)m),则素基元β与素元αt一一对应,β2与α2t一一对应,以此类推则有Τβi=αit,i=0,1,⋯,k-1(25)为了确保两个域中的乘法运算也是一一映射的,还需满足Μ(αt)=0(modQ(y),Ρ(x))(26)根据有限域定理,恰好有k个素元满足上述条件构成T,即αt2j(j=0,1,…,k-1).其中,t2j运算模多项式2k-1,则计算T的步骤为(Ⅰ)初始化.设GF((2n)m)上的素元α满足P(α)=0;令t=1,矩阵T的右边第一列为向量(0,0,…,0,1),这样,完成了一个映射;(Ⅱ)计算M(α)(modQ(y),P(x)).如果结果为零,则元素找到,否则转向步骤(Ⅶ);(Ⅲ)αt2j(j=0,1,…,k-1)都不是β的映射元素;(Ⅳ)令t=t+1,重复此步骤直到t2j没被计算过;(Ⅴ)计算GCD(t,2k-1)判断αt是否为素元,若不是,转到步骤(Ⅳ);(Ⅵ)转到步骤(Ⅱ);(Ⅶ)将αt表示为式(23)的形式作为矩阵T的右边第二列,α2t的二元向量表示为其左边下一列,依次类推,α(k-1)t为矩阵T的左边第一列.在本文的3.1节,首先要确定GF(28)域到GF((24)2)域转换和GF(24)域到GF((22)2)域转换的同构映射.由于SMS4算法GF(28)的八次不可约多项式为式(9),即M(z)=z8+z7+z6+z5+z4+z2+1;根据式(11),可令Q(y)=y4+y+1;由于式(13)中的ν={1001},则P(x)=x2+x+ω14;令n=4,m=2,则k=8.采用上述方法计算得到的GF(28)域和GF((24)2)域的同构映射为Τ=[0101111001111100110100000101000000101110110011100000101000101101],Τ-1=[0011000010100100100110001011010001011010100100100101100001010001](27)同理,GF(24)域的生成多项式为M(x)=x4+x+1,取GF((22)2)域的生成多项式为P(x)=x2+x+ω,对应的GF(22)域的生成多项式为Q(x)=x2+x+1.其中,ν=ω,等于二进制数{10},ω∈GF(22).GF(24)域到GF(22)域的同构映射为Τ=[1000111011000001],Τ-1=[1000101001100001](28)这样,GF(28)域上的所有元素可以通过等式C=TF一一映射到GF((24)2)上,GF(24)上的元素可以进一步映射到GF((22)2).由图3还可以看出,同构映射可以和仿射变换结合到一起计算,进一步简化运算.4s盒硬件的实现4.1s盒的实验结果将GF(28)域上的求逆运算转换到其子域上进行,其复杂度比直接在GF(28)域上计算复杂度降低了很多.从式(17)和(19)可以看出,复合域求逆后结果的高位部分和低位部分存在公因子,如果重复计算将会增加整个电路设计面积和关键路径,降低运算效率.为了避免出现上述情况,在最大程度上减少电路面积,本文参照文献的优化方法,通过提取公因子,改变运算次序来优化S盒的计算过程.以下用⊕表示模加法,⨂表示乘法.式(17)和(19)的优化结构如图4和图5所示.图4和图5中的运算,除了求逆运算,还有加法运算和乘法运算.其中加法运算为异或操作,易于电路实现,乘法运算则可以采用专用电路来减少电路面积.图4和图5中的乘法运算的优化结构如图6和图7所示.为了更进一步优化电路,图4和图5中的任意数的平方乘以一个常量的乘法运算也可以用专用电路替代一般的乘法器.在图4中,ν={1001}可由同构函数T映射为复合域GF((22)2)的{1111},即ν=N2z+N2,则乘法ν⨂γ21的具体计算过程为ν⨂γ21=ν⨂(Γ1z+Γ0)2=ν⨂([Γ2z]z+[Γ20⊕N⨂Γ21]=(N2z+N2)⨂([Γ21]z+[Γ20⊕N⨂Γ21])=[Γ21⊕N2⨂Γ20]z+[N2⨂T20](29)在式(29)和图5中,由于N={10},即N=w,则有Ν⊗Γ21=(w)⊗(g1w+g0)2=[g0]w+[g1](30)Ν2⊗Γ20=(w2)⊗(g1w+g0)2=[g0⊕g1]w+[g0](31)通过使用以上优化方法,GF(28)上的求逆运算就转化成了GF(2)上的逻辑与和逻辑异或操作,大大简化了计算过程,从而减少了S盒硬件实现的电路面积.4.2种具有因子模型的sms4算法在SMIC0.18μmCMOS工艺和Chartered0.35μmCMOS工艺下,分别对用查找表和基于复合域求逆两种方法实现的S盒的RTL代码进行综合,综合后电路的面积对比如表1所示.用本文提出的方法构造S盒并用于SMS4加密算法,与原始的SMS4算法比较.其中,原始的SMS4加密算法的S盒采用查找表法.两种算法采用图1的算法结构,若令加密密钥为ΜΚ=(0x01234567,0x89,ABCDEF,0xFEDCBA98,0x76543210)(32)用2000组随机产生的数据作为两种SMS4算法的明文,则两种算法每