基于復(fù)合域求逆的低電路面積s盒構(gòu)造方法

基于復(fù)合域求逆的低電路面積s盒構(gòu)造方法

0基于復(fù)合域求逆的s盒實(shí)現(xiàn)方法sms4算法是國(guó)家商業(yè)密碼管理辦公室于2006年1月發(fā)布的一套對(duì)稱密碼算法。這是中國(guó)第一個(gè)官方發(fā)布密碼算法的算法。sms4算法的提出極大地促進(jìn)了密碼算法的研究和定制過(guò)程。S盒是SMS4算法中唯一的非線性運(yùn)算,由于它作用于每一輪的加解密運(yùn)算和密鑰擴(kuò)展,所以S盒的硬件實(shí)現(xiàn)性能在很大程度上決定了整個(gè)SMS4算法的硬件實(shí)現(xiàn)性能,如電路面積、吞吐量、功耗等.因此,當(dāng)SMS4算法用于智能卡等產(chǎn)品時(shí),它們有限的芯片面積就必須需要一種低電路面積開(kāi)銷的S盒實(shí)現(xiàn),以減少SMS4算法硬件實(shí)現(xiàn)的電路面積,從而符合智能卡等產(chǎn)品對(duì)電路面積的要求.在SMS4算法硬件設(shè)計(jì)過(guò)程中,通常采用查找表方法構(gòu)造S盒,硬件實(shí)現(xiàn)簡(jiǎn)單,但面積開(kāi)銷較大.Liu等提出了基于有限域求逆的S盒構(gòu)造方法,但其在GF(28)域上的求逆運(yùn)算非常復(fù)雜,難以用硬件實(shí)現(xiàn).為了解決上述問(wèn)題,本文根據(jù)SMS4算法的S盒和AES算法的S盒在結(jié)構(gòu)上的相似性,參考AES算法S盒的研究方法,在Liu等的研究基礎(chǔ)上,引入新的復(fù)合域,將GF(28)域上的求逆運(yùn)算轉(zhuǎn)化成GF(((22)2)2)復(fù)合域上的求逆運(yùn)算,從而提出了一種易于硬件實(shí)現(xiàn),基于復(fù)合域求逆的低硬件開(kāi)銷的S盒實(shí)現(xiàn)新方法.1加密輪密鑰算法SMS4算法是一種分組密碼算法,其分組長(zhǎng)度和密鑰長(zhǎng)度均為128bit.加密算法與密鑰擴(kuò)展算法都采用32輪非線性迭代結(jié)構(gòu).解密算法與加密算法的結(jié)構(gòu)相同,只是輪密鑰的使用順序相反,解密輪密鑰是加密輪密鑰的逆序.1.1sms4算法原理設(shè)明文輸入為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為輪函數(shù);T為合成置換;R為反序變換.合成置換T:GF(2)32→GF(2)32是一個(gè)可逆變換,由非線性變換τ和線性變換L復(fù)合而成,即T(·)=L(τ(·)).非線性變換τ由四個(gè)并行的S盒構(gòu)成,每個(gè)S盒為固定的8bit輸入8bit輸出的置換,記為Sbox(·).設(shè)變換τ輸入為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的輸入.設(shè)L的輸入為B∈GF(2)32,輸出為C∈GF(2)32,則C=L(B)=B⊕(B<<<2)⊕(B<<<10)⊕(B<<<18)⊕(B<<<24)(4)式中,<<<i表示32bit循環(huán)左移i位.SMS4算法加密流程如圖1所示.算法的解密變換與加密變換結(jié)構(gòu)相同,不同的僅是輪密鑰的使用順序:加密變換輪密鑰使用順序?yàn)?RK0,RK1,…,RK31);解密變換輪密鑰使用順序?yàn)?RK31,RK30,…,RK0).1.2輪密鑰生成方法2,2,3.輪密鑰由加密密鑰通過(guò)密鑰擴(kuò)展算法生成,其結(jié)構(gòu)與加密變換類似.設(shè)加密密鑰為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)系統(tǒng)參數(shù)FKi(i=1,2,3)和固定參數(shù)CKi(i=1,2,3)均為常數(shù),其取值方法參見(jiàn)算法標(biāo)準(zhǔn)文獻(xiàn).2s盒的sesf運(yùn)算Liu等提出的基于有限域求逆構(gòu)造的S盒由求逆變換和仿射變換組成,其代數(shù)結(jié)構(gòu)為Sbos(a)=Ι(a?A1+C1)?A2+C2(8)式中,a為S盒的8bit輸入;I為GF(28)上的乘法求逆;A1,A2∈GL(8,2),C1,C2∈GF(2)8.循環(huán)矩陣A1,A2和向量C1,C2分別為A1=A2=[1110010111110010011110011011110001011110001011111001011111001011]C1=C2=(1,1,0,0,1,0,1,1)式(8)中的仿射變換是線性運(yùn)算,GF(28)域上的乘法求逆是非線性運(yùn)算.其中,GF(28)上乘法求逆的八次不可約多項(xiàng)式為Μ(x)=x8+x7+x6+x5+x4+x3+x2+1(9)有限域GF(28)上的二進(jìn)制多項(xiàng)式a(x)的乘法逆元是滿足a-1(x)a(x)=1modΜ(x)(10)的二進(jìn)制多項(xiàng)式a-1(x).式(8)所描述的S盒結(jié)構(gòu)如圖2所示.其中,ai和bi分別表示τ變換的第i個(gè)S盒的輸入和輸出字節(jié)(i=0,1,2,3).解密過(guò)程中的S盒運(yùn)算方法與加密過(guò)程相同,只需將仿射變換改成仿射逆變換.3在復(fù)合區(qū)域中獲得s盒結(jié)構(gòu)的方法3.1復(fù)合域的二次數(shù)控?cái)U(kuò)張通過(guò)引入新的復(fù)合域,將GF(28)上的運(yùn)算映射到GF(((22)2)2)復(fù)合域上進(jìn)行,從而降低S盒的計(jì)算復(fù)雜度,S盒實(shí)現(xiàn)的算法流程如圖3所示.具體的計(jì)算過(guò)程分為以下三步:(Ⅰ)使用同構(gòu)映射T將有限域F的所有元素一一映射到復(fù)合域C中;(Ⅱ)在復(fù)合域C上求逆;(Ⅲ)使用同構(gòu)映射T-1將復(fù)合域C上所有元素映射到有限域F中,完成計(jì)算.圖3中,復(fù)合域C不是由GF(2)直接進(jìn)行八次擴(kuò)張得到的,而是由不可約多項(xiàng)式重復(fù)二次代數(shù)擴(kuò)張得到.下面將介紹代數(shù)擴(kuò)張所用到的不可約多項(xiàng)式的求解過(guò)程.設(shè)二元矩陣T(k×k)為域GF(2)的元素一一映射到復(fù)合域GF((2n)m)(mn=k)上的同構(gòu)映射,T-1為反方向的同構(gòu)映射.GF((2n)m)域上的所有運(yùn)算都需要模兩個(gè)域產(chǎn)生多項(xiàng)式Q(y)和P(x).其中Q(y)是產(chǎn)生子域GF(2n)的二進(jìn)制多項(xiàng)式,P(x)是GF(2n)域上的多項(xiàng)式,產(chǎn)生復(fù)合域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)可以產(chǎn)生復(fù)合域C中用于二次代數(shù)擴(kuò)張的各個(gè)不可約多項(xiàng)式如下GF(22):x2+μ0x+θGF((22)2):x2+μ1x+ΝGF(((22)2)2):x2+μ2x+ν}(13)為了簡(jiǎn)化計(jì)算,可令μ0=μ1=μ2=1;θ,N,ν選擇不同的值,可產(chǎn)生432種不同的二元矩陣T.本文取θ={1},N={10},ν={1001}.在上述方法中,GF(28)域上的乘法求逆可以轉(zhuǎn)換到復(fù)合域GF((24)2)上實(shí)現(xiàn),GF(24)域上的乘法可以進(jìn)一步轉(zhuǎn)換到GF(22)域上并繼而轉(zhuǎn)換到GF(2)域上實(shí)現(xiàn).GF(2)上的乘法其實(shí)是與操作,同構(gòu)映射和仿射變換可以用較簡(jiǎn)單的組合邏輯實(shí)現(xiàn),因此大大降低了整個(gè)S盒計(jì)算的復(fù)雜度,從而減少了硬件實(shí)現(xiàn)的電路面積.3.2源生長(zhǎng)y型從整個(gè)S盒計(jì)算過(guò)程來(lái)看,步驟(Ⅱ)中的復(fù)合域求逆是難點(diǎn)也是重點(diǎn).下面給出復(fù)合域GF((24)2)及其子域上乘法求逆的詳細(xì)推導(dǎo)過(guò)程.設(shè)GF((24)2)域上的任意元素g=γ1y+γ0的乘法逆元為d=δ1y+δ0.其中,γ1,γ0,δ1,δ0∈GF(24).根據(jù)乘法逆元表達(dá)式(10)和不可約多項(xiàng)式(13),有g(shù)d=(γ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)中對(duì)應(yīng)項(xiàng)系數(shù)相等可得γ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)上的求逆運(yùn)算主要包括GF((24)2)上的求逆運(yùn)算和乘法運(yùn)算.同理,設(shè)GF((22)2)域上的任意元素γ=Γ1z+Γ0的乘法逆元為δ=Δ1z+Δ0,Γ1,Γ0,Δ1,Δ0∈GF(22),,根據(jù)式(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)類似地,設(shè)GF(22)域上的任意元素Γ=g1w+g0的乘法逆元為Δ=d1w+d0,g1,g0,d1,d0∈GF(2),根據(jù)式(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,化簡(jiǎn)式(21)可得d1=(g1+g1g0+g0)g1=g1d0=(g1+g1g0+g0)(g0+g1)=g1+g0}(22)3.3k-1.2gf2002域的映射在3.1節(jié)提到的方法中,同構(gòu)映射將有限域的求逆轉(zhuǎn)換到復(fù)合域中進(jìn)行,對(duì)整個(gè)S盒實(shí)現(xiàn)方法至關(guān)重要.本文采用文獻(xiàn)提出的計(jì)算同構(gòu)映射的方法,具體描述如下:設(shè)GF((2n)m)域的素元α是式(12)所示P(x)的根,即P(α)=0;GF(2n)域上的素元ω是式(11)所示Q(y)的根,即Q(ω)=0.GF((2n)m)域的每一元素A都能表示為GF(2n)域上的m階向量,而這m階向量中的每個(gè)元素本身又是一個(gè)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)域上的乘法運(yùn)算的模M(z)可表示為Μ(z)=zk+rk-1zk-1+?+r1z+1,ri∈GF(2),i=1,2,?,k-1(24)設(shè)β是M(z)的根,B={βk-1,βk-2,…,β,1}是GF(2k)域的標(biāo)準(zhǔn)基.GF(2k)域的每一元素都可以表示為k階向量,且都是基元素的線性組合.為了構(gòu)造同構(gòu)映射,用B中的k個(gè)基元表示GF((2n)m),則素基元β與素元αt一一對(duì)應(yīng),β2與α2t一一對(duì)應(yīng),以此類推則有Τβi=αit,i=0,1,?,k-1(25)為了確保兩個(gè)域中的乘法運(yùn)算也是一一映射的,還需滿足Μ(αt)=0(modQ(y),Ρ(x))(26)根據(jù)有限域定理,恰好有k個(gè)素元滿足上述條件構(gòu)成T,即αt2j(j=0,1,…,k-1).其中,t2j運(yùn)算模多項(xiàng)式2k-1,則計(jì)算T的步驟為(Ⅰ)初始化.設(shè)GF((2n)m)上的素元α滿足P(α)=0;令t=1,矩陣T的右邊第一列為向量(0,0,…,0,1),這樣,完成了一個(gè)映射;(Ⅱ)計(jì)算M(α)(modQ(y),P(x)).如果結(jié)果為零,則元素找到,否則轉(zhuǎn)向步驟(Ⅶ);(Ⅲ)αt2j(j=0,1,…,k-1)都不是β的映射元素;(Ⅳ)令t=t+1,重復(fù)此步驟直到t2j沒(méi)被計(jì)算過(guò);(Ⅴ)計(jì)算GCD(t,2k-1)判斷αt是否為素元,若不是,轉(zhuǎn)到步驟(Ⅳ);(Ⅵ)轉(zhuǎn)到步驟(Ⅱ);(Ⅶ)將αt表示為式(23)的形式作為矩陣T的右邊第二列,α2t的二元向量表示為其左邊下一列,依次類推,α(k-1)t為矩陣T的左邊第一列.在本文的3.1節(jié),首先要確定GF(28)域到GF((24)2)域轉(zhuǎn)換和GF(24)域到GF((22)2)域轉(zhuǎn)換的同構(gòu)映射.由于SMS4算法GF(28)的八次不可約多項(xiàng)式為式(9),即M(z)=z8+z7+z6+z5+z4+z2+1;根據(jù)式(11),可令Q(y)=y4+y+1;由于式(13)中的ν={1001},則P(x)=x2+x+ω14;令n=4,m=2,則k=8.采用上述方法計(jì)算得到的GF(28)域和GF((24)2)域的同構(gòu)映射為Τ=[0101111001111100110100000101000000101110110011100000101000101101],Τ-1=[0011000010100100100110001011010001011010100100100101100001010001](27)同理,GF(24)域的生成多項(xiàng)式為M(x)=x4+x+1,取GF((22)2)域的生成多項(xiàng)式為P(x)=x2+x+ω,對(duì)應(yīng)的GF(22)域的生成多項(xiàng)式為Q(x)=x2+x+1.其中,ν=ω,等于二進(jìn)制數(shù){10},ω∈GF(22).GF(24)域到GF(22)域的同構(gòu)映射為Τ=[1000111011000001],Τ-1=[1000101001100001](28)這樣,GF(28)域上的所有元素可以通過(guò)等式C=TF一一映射到GF((24)2)上,GF(24)上的元素可以進(jìn)一步映射到GF((22)2).由圖3還可以看出,同構(gòu)映射可以和仿射變換結(jié)合到一起計(jì)算,進(jìn)一步簡(jiǎn)化運(yùn)算.4s盒硬件的實(shí)現(xiàn)4.1s盒的實(shí)驗(yàn)結(jié)果將GF(28)域上的求逆運(yùn)算轉(zhuǎn)換到其子域上進(jìn)行,其復(fù)雜度比直接在GF(28)域上計(jì)算復(fù)雜度降低了很多.從式(17)和(19)可以看出,復(fù)合域求逆后結(jié)果的高位部分和低位部分存在公因子,如果重復(fù)計(jì)算將會(huì)增加整個(gè)電路設(shè)計(jì)面積和關(guān)鍵路徑,降低運(yùn)算效率.為了避免出現(xiàn)上述情況,在最大程度上減少電路面積,本文參照文獻(xiàn)的優(yōu)化方法,通過(guò)提取公因子,改變運(yùn)算次序來(lái)優(yōu)化S盒的計(jì)算過(guò)程.以下用⊕表示模加法,?表示乘法.式(17)和(19)的優(yōu)化結(jié)構(gòu)如圖4和圖5所示.圖4和圖5中的運(yùn)算,除了求逆運(yùn)算,還有加法運(yùn)算和乘法運(yùn)算.其中加法運(yùn)算為異或操作,易于電路實(shí)現(xiàn),乘法運(yùn)算則可以采用專用電路來(lái)減少電路面積.圖4和圖5中的乘法運(yùn)算的優(yōu)化結(jié)構(gòu)如圖6和圖7所示.為了更進(jìn)一步優(yōu)化電路,圖4和圖5中的任意數(shù)的平方乘以一個(gè)常量的乘法運(yùn)算也可以用專用電路替代一般的乘法器.在圖4中,ν={1001}可由同構(gòu)函數(shù)T映射為復(fù)合域GF((22)2)的{1111},即ν=N2z+N2,則乘法ν?γ21的具體計(jì)算過(guò)程為ν?γ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)通過(guò)使用以上優(yōu)化方法,GF(28)上的求逆運(yùn)算就轉(zhuǎn)化成了GF(2)上的邏輯與和邏輯異或操作,大大簡(jiǎn)化了計(jì)算過(guò)程,從而減少了S盒硬件實(shí)現(xiàn)的電路面積.4.2種具有因子模型的sms4算法在SMIC0.18μmCMOS工藝和Chartered0.35μmCMOS工藝下,分別對(duì)用查找表和基于復(fù)合域求逆兩種方法實(shí)現(xiàn)的S盒的RTL代碼進(jìn)行綜合,綜合后電路的面積對(duì)比如表1所示.用本文提出的方法構(gòu)造S盒并用于SMS4加密算法,與原始的SMS4算法比較.其中,原始的SMS4加密算法的S盒采用查找表法.兩種算法采用圖1的算法結(jié)構(gòu),若令加密密鑰為ΜΚ=(0x01234567,0x89,ABCDEF,0xFEDCBA98,0x76543210)(32)用2000組隨機(jī)產(chǎn)生的數(shù)據(jù)作為兩種SMS4算法的明文,則兩種算法每