Camellia算法S盒的緊湊硬件實現*

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

1.中國科學院 信息工程研究所 信息安全國家重點實驗室,北京 100093

2.中國科學院大學 密碼學院,北京 100049

3.密碼科學技術國家重點實驗室,北京 100878

4.中國科學院大學 網絡空間安全學院,北京 100049

5.惠州學院 計算機科學與工程學院,惠州 516007

1 引言

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

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

本文結構如下:第2節簡單介紹塔域實現的基礎知識和通用方法;第3節將塔域實現和Camellia的具體結構相結合,根據該密碼算法的特點采用了針對性的優化方式;第4節匯總了實現方案的數據,并通過仿真實驗將它與以前的方案對比;第5節是對全文的總結,以及對未來工作的展望.

2 預備知識

2.1 塔域表現形式

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

圖1 兩種不同的域擴張方式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可由另一組系數向量(g7,g6,···,g0)T來表示.

由于塔域基中的每個基底分量都是F28中的元素,都可以用多項式基來表示,

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

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

b的兩組系數向量之間存在如下轉換關系

2.2 F28逆運算的塔域實現

γλ=(Γ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 三種工藝庫下常用電路元件的面積Table 1 Area of frequently-used gates in three CMOS technology libraries

3 實現方案

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

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

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

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

圖2 直觀地表示了兩種基下逆運算之間的聯系.

圖2 多項式基下求逆和塔域基下求逆之間的關系Figure 2 Relationship between inversion under polynomial basis and inversion under tower basis

進而S(b)可表示為

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

表2 三個不可約多項式的系數及其根Table 2 Values of coefficients and roots of three irreducible polynomials

我們使用5個模塊來完成S盒的功能,如圖3所示,每個部分的實現細節見下列各小節.

圖3 S盒整體結構Figure 3 S-box structure

3.1 頭部模塊實現方案

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

γ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.

設

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.

運用文獻[6-10]中的優化方法,最終表達式為

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

3.2 中部模塊實現方案

φ=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.

傳統方法利用了逆運算在塔域上的結構特點來實現,當我們舍棄這一特征,轉而應用文獻[9]中的方法時,可以得到一個面積更小的實現方案:

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個NAND門,1個NOR門,1個XNOR門和6個MUX元件.

通過觀察可知,

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

一般情況下,NANDN元件的面積小于MUX元件,當工藝庫支持NANDN元件時,我們可以進一步優化t4和t5:

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

3.3 尾部模塊實現方案

尾部模塊實現了等式(1)中λγ0和λγ1的部分表達式.設

λ=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.

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

3.4 輸入、輸出模塊實現方案

在有限域中,元素與常數的乘法運算以及元素的2β次冪運算均可轉化為對該元素的線性變換,即

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

優化方法在求逆運算過程產生的額外效果可以從圖4中看出來.

圖4 優化方法對逆運算的影響Figure 4 Influence of optimization

進而S(b)可以對應重寫為

這個優化只影響輸入、輸出模塊,對其他部分沒有影響.

實現輸入、輸出模塊的過程本質上是求解SLP(shortest linear straight-line programs)問題,而SLP問題已經被證明是NP-hard問題[7].目前已經存在多種方法來對其優化,如文獻[7-9,16-18],其中文獻[17]是將SLP問題轉換為SAT問題,利用SAT求解器來運算,對維數較小的矩陣能獲得可證明的最優解,而其他文獻則都是啟發式算法,只能得到較好的結果.針對當前規模較大的輸入、輸出模塊,我們使用了文獻[7]中的算法.

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

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

當我們取第一組最佳組合時,輸入模塊具體為:

一共使用了17個XOR/XNOR門和1個NOT門,實現方案如下:

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個XOR/XNOR門,實現方案如下:

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 實驗結果

我們將第3節各小節描述的數據匯總到表4中.利用Synopsys Design Compiler軟件,結合三種工藝庫的庫文件,可以對Camellia的各種實現方案做綜合仿真,結果見表5.

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

表5 不同論文下的實現方案綜合結果Table 5 Synthesis results of different implementations

5 總結

通過劃分AES密碼算法S盒輕量化實現時的優化方法,我們成功地將這些技術運用到Camellia中,在此基礎上當實際使用的工藝庫允許一些復合元件時,我們可以做更進一步的優化.實驗結果顯示,運用了新技術的方案比現有的最佳方案減少了從4.66 GE到8.25 GE不等的面積.

下一步的研究方向是針對深度做優化實現,以及在同時考慮面積和深度兩個維度的情況下,設計一種比較平衡的方案.