Camellia算法S盒的緊湊硬件實(shí)現(xiàn)*

魏子豪,張英杰,胡 磊,孫思維,史丹萍,羅宜元

1.中國(guó)科學(xué)院 信息工程研究所 信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室,北京 100093

2.中國(guó)科學(xué)院大學(xué) 密碼學(xué)院,北京 100049

3.密碼科學(xué)技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,北京 100878

4.中國(guó)科學(xué)院大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院,北京 100049

5.惠州學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院,惠州 516007

1 引言

Camellia分組密碼算法由三菱公司和日本電信電話公司在2000年共同設(shè)計(jì)[1].由于其較高的安全性以及在軟、硬件平臺(tái)上高效的實(shí)現(xiàn)性能,該算法在2003年歐洲NESSIE項(xiàng)目中被評(píng)選為獲勝算法,同年在日本CRYPTREC計(jì)劃中被評(píng)選為推薦算法,2004年成為IETF標(biāo)準(zhǔn)算法,2005年成為ISO/IEC標(biāo)準(zhǔn)算法,2006年成為PKCS#11認(rèn)證密碼.

在硬件平臺(tái)上實(shí)現(xiàn)時(shí),存在這樣一種應(yīng)用場(chǎng)景:由于環(huán)境約束,電路芯片的面積必須比較小,因此能使用的電路資源也相對(duì)有限,除了滿足正常運(yùn)行功能之外,設(shè)計(jì)者還需要提供安全加解密能力,例如銀行卡芯片、無(wú)線傳感器節(jié)點(diǎn)等.在這種情況下,密碼算法實(shí)現(xiàn)者對(duì)資源面積這一參數(shù)更敏感.在Camellia算法中,S盒作為唯一的非線性部件,需要消耗的資源最多,可以優(yōu)化的空間也比線性部件大,因此通常我們會(huì)研究S盒的實(shí)現(xiàn)方法.

本文結(jié)構(gòu)如下:第2節(jié)簡(jiǎn)單介紹塔域?qū)崿F(xiàn)的基礎(chǔ)知識(shí)和通用方法;第3節(jié)將塔域?qū)崿F(xiàn)和Camellia的具體結(jié)構(gòu)相結(jié)合,根據(jù)該密碼算法的特點(diǎn)采用了針對(duì)性的優(yōu)化方式;第4節(jié)匯總了實(shí)現(xiàn)方案的數(shù)據(jù),并通過(guò)仿真實(shí)驗(yàn)將它與以前的方案對(duì)比;第5節(jié)是對(duì)全文的總結(jié),以及對(duì)未來(lái)工作的展望.

2 預(yù)備知識(shí)

2.1 塔域表現(xiàn)形式

我們可以用其系數(shù)組成的向量(b7,b6,···,b0)T來(lái)表示b.

圖1 兩種不同的域擴(kuò)張方式Figure 1 Two different ways of field extensions

b=γ1Y16+γ0Y,

γ1=Γ3Z4+Γ2Z,γ0=Γ1Z4+Γ0Z,

Γ3=g7W2+g6W,Γ2=g5W2+g4W,Γ1=g3W2+g2W,Γ0=g1W2+g0W,

其中,γ1,γ0∈F24,Γ3,Γ2,Γ1,Γ0∈F22,g i∈F2,0≤i≤7,即

b=g7W2Z4Y16+g6W Z4Y16+g5W2Z Y16+g4W Z Y16+g3W2Z4Y+g2W Z4Y+g1W2Z Y+g0W Z Y.

我們將這組由W,Z和Y組成的基叫做塔域基,記為T B,

T B=[W2Z4Y16,W Z4Y16,W2Z Y16,W Z Y16,W2Z4Y,W Z4Y,W2Z Y,W Z Y],

在T B下,b可由另一組系數(shù)向量(g7,g6,···,g0)T來(lái)表示.

由于塔域基中的每個(gè)基底分量都是F28中的元素,都可以用多項(xiàng)式基來(lái)表示,

T B[i]=W h Z j Y k=(X7,X6,···,X0)V i,i=7,6,···,0,

其中T B[i]表示塔域基的第i個(gè)分量,V i表示它在多項(xiàng)式基下的系數(shù)列向量,因此塔域基整體也可以用多項(xiàng)式基表示為

b的兩組系數(shù)向量之間存在如下轉(zhuǎn)換關(guān)系

2.2 F28逆運(yùn)算的塔域?qū)崿F(xiàn)

γλ=(Γ1Z4+Γ0Z)(Λ1Z4+Λ0Z)

=[Γ1Λ1T+(Γ1+Γ0)(Λ1+Λ0)N T2]Z4+[Γ0Λ0T+(Γ1+Γ0)(Λ1+Λ0)N T2]Z.

ΓΔ=(u1W2+u0W)(v1W2+v0W)

=[u1·v1⊕(u1⊕u0)·(v1⊕v0)]W2+[u0·v0⊕(u1⊕u0)·(v1⊕v0)]W.

2.3 常用電路元件

表1 三種工藝庫(kù)下常用電路元件的面積Table 1 Area of frequently-used gates in three CMOS technology libraries

3 實(shí)現(xiàn)方案

Camellia算法一共使用了4個(gè)不同的S盒s1,s2,s3,s4,其中

s2(x)=s1(x)?1,

s3(x)=s1(x)?1,

s4(x)=s1(x?1),

圖2 直觀地表示了兩種基下逆運(yùn)算之間的聯(lián)系.

圖2 多項(xiàng)式基下求逆和塔域基下求逆之間的關(guān)系Figure 2 Relationship between inversion under polynomial basis and inversion under tower basis

進(jìn)而S(b)可表示為

第2.2節(jié)的運(yùn)算表達(dá)式顯示,I T B的計(jì)算過(guò)程受r(y),s(z),t(w)三個(gè)不可約多項(xiàng)式影響,參考文獻(xiàn)[10]可知,三個(gè)多項(xiàng)式共會(huì)產(chǎn)生720種有效情況.我們運(yùn)用文獻(xiàn)[6-10]中的知識(shí),對(duì)所有有效情況進(jìn)行了搜索,得到了一種和文獻(xiàn)[10]不同,并且效果更好的實(shí)現(xiàn)方案,其中多項(xiàng)式的系數(shù)和它們的根如表2所示,它們的值均是基于多項(xiàng)式基的表示.

表2 三個(gè)不可約多項(xiàng)式的系數(shù)及其根Table 2 Values of coefficients and roots of three irreducible polynomials

我們使用5個(gè)模塊來(lái)完成S盒的功能,如圖3所示,每個(gè)部分的實(shí)現(xiàn)細(xì)節(jié)見下列各小節(jié).

圖3 S盒整體結(jié)構(gòu)Figure 3 S-box structure

3.1 頭部模塊實(shí)現(xiàn)方案

頭部模塊實(shí)現(xiàn)了等式(1)中的γ1γ0τ2+(γ1+γ0)2ν部分,記結(jié)果為φ.用2.1節(jié)的塔域表示符號(hào)將γ1γ0τ2和(γ1+γ0)2ν展開到比特級(jí),可得表達(dá)式

γ1γ0τ2=(Γ3Z4+Γ2Z)(Γ1Z4+Γ0Z)·(N·Z4+N·Z)2

=g6g2⊕(g7⊕g6)(g3⊕g2)⊕(g7⊕g5)(g3⊕g1)⊕(g7⊕g6⊕g5⊕g4)(g3⊕g2⊕g1⊕g0)]W2Z4+[g7g3⊕g6g2⊕(g6⊕g4)(g2⊕g0)⊕(g7⊕g6⊕g5⊕g4)(g3⊕g2⊕g1⊕g0)]W Z4+[g4g0⊕(g5⊕g4)(g1⊕g0)⊕(g7⊕g5)(g3⊕g1)⊕(g7⊕g6⊕g5⊕g4)(g3⊕g2⊕g1⊕g0)]W2Z+[g5g1⊕g4g0⊕(g6⊕g4)(g2⊕g0)⊕(g7⊕g6⊕g5⊕g4)(g3⊕g2⊕g1⊕g0)]W Z

(γ1+γ0)2ν=[(Γ3+Γ1)Z4+(Γ2+Γ0)Z]2·(N·Z4+0·Z)

=(g7⊕g6⊕g3⊕g2)W2Z4+(g6⊕g2)W Z4+(g7⊕g5⊕g3⊕g1)W2Z+(g7⊕g6⊕g5⊕g4⊕g3⊕g2⊕g1⊕g0)W Z.

設(shè)

m9=g7⊕g6m8=g3⊕g2m7=g7⊕g5m6=g3⊕g1

m5=g6⊕g4m4=g2⊕g0m3=g7⊕g6⊕g5⊕g4m2=g3⊕g2⊕g1⊕g0

m1=g5⊕g4m0=g1⊕g0,

則

φ=(g6g2⊕m9m8⊕m7m6⊕m3m2⊕m9⊕m8)W2Z4+(g7g3⊕g6g2⊕m5m4⊕m3m2⊕g6⊕g2)W Z4+(g4g0⊕m1m0⊕m7m6⊕m3m2⊕m7⊕m6)W2Z+(g5g1⊕g4g0⊕m5m4⊕m3m2⊕m3⊕m2)W Z.

運(yùn)用文獻(xiàn)[6-10]中的優(yōu)化方法,最終表達(dá)式為

在不考慮m9,m8,···,m0實(shí)現(xiàn)方式(即假設(shè)比特序列g(shù)和m均已知)的情況下,實(shí)現(xiàn)該表達(dá)式需要8個(gè)NAND門、4個(gè)NOR門和12個(gè)XOR門.

3.2 中部模塊實(shí)現(xiàn)方案

φ=p3W2Z4+p2W Z4+p1W2Z+p0W Z

λ=(p2p1p0⊕p3p1⊕p2p1⊕p1⊕p0)W2Z4+(p3p1p0⊕p3p1⊕p2p1⊕p2p0⊕p0)W Z4+(p3p2p0⊕p3p1⊕p3p0⊕p3⊕p2)W2Z+(p3p2p1⊕p3p1⊕p3p0⊕p2p0⊕p2)W Z.

傳統(tǒng)方法利用了逆運(yùn)算在塔域上的結(jié)構(gòu)特點(diǎn)來(lái)實(shí)現(xiàn),當(dāng)我們舍棄這一特征,轉(zhuǎn)而應(yīng)用文獻(xiàn)[9]中的方法時(shí),可以得到一個(gè)面積更小的實(shí)現(xiàn)方案:

t1=NAND(p2,p0)t2=NOR(p3,p1)t3=XNOR(t1,t2)t4=MUX(p3,p0,1)

t5=MUX(p1,p2,1)t6=MUX(p0,t3,p1)t7=MUX(t3,p1,t4)t8=MUX(p2,t3,p3)

t9=MUX(t3,p3,t5),

λ=(t7,t6,t9,t8),

共使用1個(gè)NAND門,1個(gè)NOR門,1個(gè)XNOR門和6個(gè)MUX元件.

通過(guò)觀察可知,

MUX(s,a,1)=s·a⊕s⊕1=NANDN(a,s),

一般情況下,NANDN元件的面積小于MUX元件,當(dāng)工藝庫(kù)支持NANDN元件時(shí),我們可以進(jìn)一步優(yōu)化t4和t5:

t4=NANDN(p0,p3),t5=NANDN(p2,p1).

3.3 尾部模塊實(shí)現(xiàn)方案

尾部模塊實(shí)現(xiàn)了等式(1)中λγ0和λγ1的部分表達(dá)式.設(shè)

λ=l3W2Z4+l2W Z4+l1W2Z+l0W Z,

k4=l3⊕l2,k3=l3⊕l1,k2=l2⊕l0,k1=l3⊕l2⊕l1⊕l0,k0=l1⊕l0,

e17=NAND(g3,l3)e16=NAND(m8,k4)e15=NAND(g2,l2)e14=NAND(m4,k2)

e13=NAND(m6,k3)e12=NAND(m2,k1)e11=NAND(g1,l1)e10=NAND(m0,k0)

e9=NAND(g0,l0)e8=NAND(g7,l3)e7=NAND(m9,k4)e6=NAND(g6,l2)

e5=NAND(m5,k2)e4=NAND(m7,k3)e3=NAND(m3,k1)e2=NAND(g5,l1)

e1=NAND(m1,k0)e0=NAND(g4,l0),

則

λγ0=(e17⊕e16⊕e14⊕e13)W2Z4+(e15⊕e16⊕e12⊕e13)W Z4+(e11⊕e10⊕e14⊕e13)W2Z+(e9⊕e10⊕e12⊕e13)W Z,

λγ1=(e8⊕e7⊕e5⊕e4)W2Z4+(e6⊕e7⊕e3⊕e4)W Z4+(e2⊕e1⊕e5⊕e4)W2Z+(e0⊕e1⊕e3⊕e4)W Z.

從表達(dá)式中可以看到,最后的結(jié)果是從18個(gè)NAND門的輸出中分別抽取4個(gè)異或在一起,形成的8個(gè)組合.參考文獻(xiàn)[7]中的優(yōu)化方式,在尾部模塊中,我們只實(shí)現(xiàn)比特序列k和e,將更進(jìn)一步的異或操作留到之后的模塊中去完成.這樣尾部模塊一共使用了5個(gè)XOR門和18個(gè)NAND門.

3.4 輸入、輸出模塊實(shí)現(xiàn)方案

在有限域中,元素與常數(shù)的乘法運(yùn)算以及元素的2β次冪運(yùn)算均可轉(zhuǎn)化為對(duì)該元素的線性變換,即

其中Mα,Mβ分別表示常數(shù)α和2β次冪運(yùn)算對(duì)應(yīng)的矩陣,因此等式(2)可以重寫為

優(yōu)化方法在求逆運(yùn)算過(guò)程產(chǎn)生的額外效果可以從圖4中看出來(lái).

圖4 優(yōu)化方法對(duì)逆運(yùn)算的影響Figure 4 Influence of optimization

進(jìn)而S(b)可以對(duì)應(yīng)重寫為

這個(gè)優(yōu)化只影響輸入、輸出模塊,對(duì)其他部分沒有影響.

實(shí)現(xiàn)輸入、輸出模塊的過(guò)程本質(zhì)上是求解SLP(shortest linear straight-line programs)問(wèn)題,而SLP問(wèn)題已經(jīng)被證明是NP-hard問(wèn)題[7].目前已經(jīng)存在多種方法來(lái)對(duì)其優(yōu)化,如文獻(xiàn)[7-9,16-18],其中文獻(xiàn)[17]是將SLP問(wèn)題轉(zhuǎn)換為SAT問(wèn)題,利用SAT求解器來(lái)運(yùn)算,對(duì)維數(shù)較小的矩陣能獲得可證明的最優(yōu)解,而其他文獻(xiàn)則都是啟發(fā)式算法,只能得到較好的結(jié)果.針對(duì)當(dāng)前規(guī)模較大的輸入、輸出模塊,我們使用了文獻(xiàn)[7]中的算法.

α有255種取值,β有8種取值,因此(α,β)共有2040種組合情況.在嘗試了所有組合對(duì)應(yīng)的矩陣后,我們發(fā)現(xiàn)其中6種組合能使輸入、輸出模塊的實(shí)現(xiàn)代價(jià)之和最小,其取值和實(shí)現(xiàn)代價(jià)總和的情況見表3,其中α的值是多項(xiàng)式基下的表達(dá)式.而其他組合則會(huì)使用更多的XOR/XNOR門電路,通常會(huì)增加1-16個(gè).

表3 α、β的最佳取值和矩陣實(shí)現(xiàn)情況Table 3 Best values ofαandβ,and sum of implementations of their corresponding matrices

當(dāng)我們?nèi)〉谝唤M最佳組合時(shí),輸入模塊具體為:

一共使用了17個(gè)XOR/XNOR門和1個(gè)NOT門,實(shí)現(xiàn)方案如下:

t1=XOR(b4,b1)t2=XNOR(b4,b2)t3=XNOR(b6,b1)t4=XOR(b7,b0)

t5=XOR(b6,b3t6=XNOR(t4,t5)t7=XOR(t1,t6)t8=XNOR(b0,t7)

t9=XOR(b1,t8)t10=XNOR(t2,t5)t11=XOR(t1,t10)t12=XOR(t4,t10)

t13=XOR(t4,t7)t14=XOR(b5,t13)t15=XOR(t9,t14)t16=XNOR(b6,t15)

t17=XOR(t8,t16),

g=(t1,t6,t11,t2,t9,b1,t14,t3)

m=(t7,t8,t10,t15,t12,NOT(b6),t4,t16,t13,t17).

輸出模塊具體為:

一共使用了28個(gè)XOR/XNOR門,實(shí)現(xiàn)方案如下:

t1=XOR(e8,e5)t2=XOR(e6,e0)t3=XOR(e6,e3)t4=XNOR(t1,t3)

t5=XOR(e1,t2)t6=XNOR(e7,t5)t7=XOR(e4,t1)t8=XNOR(t5,t7)

t9=XNOR(e10,t6)t10=XNOR(e9,t4)t11=XOR(e16,t9)t12=XOR(t10,t11)

t13=XNOR(e15,t12)t14=XOR(e17,e11)t15=XOR(e13,e12)t16=XOR(t12,t15)

t17=XOR(e10,e8)t18=XOR(e2,t2)t19=XOR(t17,t18)t20=XNOR(e16,t8)

t21=XOR(t16,t20)t22=XNOR(t8,t11)t23=XNOR(t14,t22)t24=XOR(t14,t16)

t25=XOR(t19,t24)t26=XOR(e14,e13)t27=XOR(e11,t19)t28=XOR(t26,t27),

S(b)=(t28,t8,t23,t25,t6,t13,t4,t21).

4 實(shí)驗(yàn)結(jié)果

我們將第3節(jié)各小節(jié)描述的數(shù)據(jù)匯總到表4中.利用Synopsys Design Compiler軟件,結(jié)合三種工藝庫(kù)的庫(kù)文件,可以對(duì)Camellia的各種實(shí)現(xiàn)方案做綜合仿真,結(jié)果見表5.

表4 各模塊所用電路元件數(shù)量Table 4 Gate number for each module

表5 不同論文下的實(shí)現(xiàn)方案綜合結(jié)果Table 5 Synthesis results of different implementations

5 總結(jié)

通過(guò)劃分AES密碼算法S盒輕量化實(shí)現(xiàn)時(shí)的優(yōu)化方法,我們成功地將這些技術(shù)運(yùn)用到Camellia中,在此基礎(chǔ)上當(dāng)實(shí)際使用的工藝庫(kù)允許一些復(fù)合元件時(shí),我們可以做更進(jìn)一步的優(yōu)化.實(shí)驗(yàn)結(jié)果顯示,運(yùn)用了新技術(shù)的方案比現(xiàn)有的最佳方案減少了從4.66 GE到8.25 GE不等的面積.

下一步的研究方向是針對(duì)深度做優(yōu)化實(shí)現(xiàn),以及在同時(shí)考慮面積和深度兩個(gè)維度的情況下,設(shè)計(jì)一種比較平衡的方案.