構(gòu)造分支數(shù)為4的對合線性變換

李 平， 孫 兵， 李瑞林， 李 超

（國防科技大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)系，湖南 長沙 410073）

0 引言

分組密碼的設(shè)計(jì)主要關(guān)注兩方面的性能，第一是算法本身的安全性，第二是算法的軟硬件實(shí)現(xiàn)效率。大多數(shù)分組密碼均采用SP輪函數(shù)的結(jié)構(gòu)，文獻(xiàn)[1]研究了分組密碼S盒輸出分量函數(shù)的密碼學(xué)性質(zhì)，文獻(xiàn)[2]研究了一類P置換的設(shè)計(jì)方法。P置換要實(shí)現(xiàn)盡可能高的擴(kuò)散性以抵抗差分線性等密碼攻擊手段，需要線性變換的分支數(shù)盡可能高。對合性質(zhì)能夠使得加解密完全一致，達(dá)到節(jié)省資源提高效率的目的。目前 AES，Camellia，F(xiàn)OX，SMS4等算法都使用了達(dá)到最優(yōu)分支數(shù)的線性變換，分支數(shù)均為5，但都不是對合的。為了能夠像Feistel型分組密碼一樣做到加解密一致，在擴(kuò)散層中采用對合型線性變換就非常必要，目前韓國密碼標(biāo)準(zhǔn)ARIA算法就采用了一個(gè)對合的線性變換作為其擴(kuò)散層，并且分支數(shù)達(dá)到了最優(yōu)。

基于以上優(yōu)點(diǎn)，設(shè)計(jì)盡可能好的分支數(shù)以及對合的線性變換是近來的熱點(diǎn)問題。由于異或運(yùn)算和循環(huán)移位易于實(shí)現(xiàn)，結(jié)合這兩種技巧來設(shè)計(jì)線性變換的方法逐漸得到廣泛的應(yīng)用。中國設(shè)計(jì)的無線局域網(wǎng)中使用的SMS4算法就是采用這種方法設(shè)計(jì)的擴(kuò)散層[3]?，F(xiàn)在已有的研究基礎(chǔ)上，給出了三類達(dá)到次最優(yōu)分支數(shù)的對合型線性變換的構(gòu)造。

1 基礎(chǔ)知識

下面給出給出線性變換分支數(shù)以及對合的定義：

B(L)=mX≠in0(W （X ) + W(L ( X)))。

根據(jù)分支數(shù)的定義，可知， B (L)≤ m+1。特別地，當(dāng)B ( L ) = m+1時(shí)，稱該線性變換為最優(yōu)線性變換；當(dāng) B ( L) = m時(shí)，稱該線性變換為次最優(yōu)線性變換。

現(xiàn)有的構(gòu)造最優(yōu)線性變換的方法包括如下一些方法：

①循環(huán)矩陣構(gòu)造[4]，AES算法擴(kuò)散層基于該方法設(shè)計(jì)。文獻(xiàn)[4]指出，與一般的隨機(jī)矩陣相比，循環(huán)矩陣所對應(yīng)的線性變換達(dá)到最優(yōu)的概率更大。文獻(xiàn)[2]進(jìn)一步指出，如果還要求變換為對合變換，則這樣的對合型線性變換的分支數(shù)最大只能達(dá)到4；

②組合方法構(gòu)造[5]，F(xiàn)OX算法擴(kuò)散層基于該方法設(shè)計(jì)；

③Hadamard矩陣構(gòu)造，NESSIE計(jì)劃中提交的分組密碼算法Khazad[6]與Anubis[7]的擴(kuò)散層基于該方法設(shè)計(jì)；

④Cauchy矩陣構(gòu)造[8]。

除這幾種常見的構(gòu)造方法之外，利用循環(huán)移位和異或運(yùn)算也可以構(gòu)造分支數(shù)達(dá)到最優(yōu)的線性變換。假設(shè)，用Xi表示將X循環(huán)左移i位，其中0 ≤ i≤ n m-1，則利用循環(huán)移位和異或運(yùn)算可以表示從的一類線性變換。文獻(xiàn)[9]給出了利用循環(huán)移位和異或運(yùn)算設(shè)計(jì)最優(yōu)線性變換時(shí)的一些條件這種方法特別適合于軟硬件的實(shí)現(xiàn)，效率高。但是，已有的基于該構(gòu)造方法給出的最優(yōu)線性變換均不是對合變換。

2 三種構(gòu)造次最優(yōu)對合線性變換的方法

上一節(jié)中基于循環(huán)移位結(jié)合異或運(yùn)算的方法均是將X視為整體進(jìn)行循環(huán)移位和異或運(yùn)算，對X的分量進(jìn)行考慮，當(dāng) 4m= 時(shí)，給出分支數(shù)達(dá)到4時(shí)的對合線性變換的三種構(gòu)造方法。

證明：根據(jù)分支數(shù)的定義，必要性顯然。

下面證明充分性，根據(jù)分支數(shù)的定義，只需按輸入X的重量來分別討論：

首先根據(jù)條件輸入向量滿足 W (X)= 1，則輸出向量滿足W(Y)≥ 3 ；

當(dāng)輸入向量滿足 W (X) = 2 時(shí)，假設(shè)此時(shí)輸出 Y =L(X)的重量 W (Y)= 1 。由于L是對合的，可考慮其逆變換L-1=L，由已知條件可知 X =L-1(Y)的重量 W (X)≥ 3。與W(X) = 2 矛盾，故輸出 Y =L( X)的重量 W (Y)≥ 2 ；

當(dāng)輸入向量滿足 W (X) = 3 時(shí)，由于輸出是非零的，那么必有 W (Y)≥ 1。

綜合以上3種情況，可知 B (L)≥ 4。

則線性變換L滿足對合性質(zhì)且分支數(shù)為 B ( L ) = 4。

證明：首先證明L的對合性，由L的定義：Y0⊕Y1⊕Y2⊕ Y3=X0⊕X1⊕X2⊕ X3， 故 T = ( X0⊕ X1⊕X2⊕ X3)i = (Y0⊕Y1⊕Y2⊕Y3)i ,又易知：

從而L為對合變換。

下面證明L的分支數(shù)為4，不妨設(shè)輸入 X = ( X0,0,0,0)，X0≠ 0 ，則容易計(jì)算：

可知， Y1≠0, Y2≠0, Y3≠ 0 ，故 W (Y)≥ 3；又由于L是對合的，由定理 1可知 B (L)≥ 4。另一方面，可設(shè)輸入X=(X0,0,0,0)中的 X0為全1向量，將其代入L的定義驗(yàn)證可知，輸出 Y =L( X)的重量 W (Y)= 3 ，由分支數(shù)定義，取所有可能的輸入輸出重量之和的最小值，故分支數(shù)為4。

則線性變換L滿足對合性質(zhì)且分支數(shù)為 B ( L) = 4。

證明：首先證明L的對合性，由L的定義，可做如下循環(huán)移位：并計(jì)算 Y0⊕(Y1i1) ⊕(Y2i2) ⊕ (Y3i3) ⊕ (Y0i4)可得:

X0= Y0⊕ ( Y1i1) ⊕ ( Y2i2) ⊕ ( Y33) ⊕ (Y0i4)，同理可得：

從而L為對合變換。類似構(gòu)造1的證明可知L的分支數(shù)為4。

則線性變換L的分支數(shù)為 B ( L) = 4，進(jìn)一步，當(dāng)n為偶數(shù)且i = n /2時(shí)，L是對合變換。

證明：首先證明L分支數(shù)為4，根據(jù)分支數(shù)的定義，只需按輸入X的重量來分別討論：

（1）當(dāng)輸入X的重量 W (X)= 1時(shí)，輸出 Y =L ( X)的重量 W (Y)≥ 3；

不妨設(shè)輸入 X = ( X0,0,0,0)， X0≠ 0 ，則容易計(jì)算：

可知， Y1≠ 0 , Y2≠0, Y3≠ 0 ，故 W (Y)≥ 3 。

（2）當(dāng)輸入X的重量 W (X) = 2 時(shí)，輸出 Y =L ( X)的重量 W (Y)≥ 2 ；

不妨設(shè)輸入 X = ( X0, X1,0,0), X0≠0, X1≠0,則容易計(jì)算:

若 X0⊕X1=0，則Y0≠0, Y1≠0，此時(shí)W(Y)= 2 ；若X0⊕X1≠0，則Y2≠0, Y3≠0，此時(shí)W(Y)≥ 2 。從而當(dāng)W(X) = 2 時(shí)， W (Y)≥ 2 。

當(dāng)輸入X的重量 W (X)= 3 時(shí)，輸出非零，所以必有W(Y)≥ 1；綜上并且注意到（2）中存在輸出 W (Y)=2的情況，由于分支數(shù)的定義，故 B ( L ) = 4。

下面證明當(dāng)n為偶數(shù)且 i = n /2時(shí)，L是對合的：由Y0⊕Y1⊕Y2⊕ Y3= ( X0⊕X1⊕ X2⊕X3)i ,故 T = X0⊕ X1⊕X2⊕ X3=( Y0⊕Y1⊕Y2⊕Y3)■ i ，則：

令T'= Y0⊕Y1⊕Y2⊕Y3，則 Ti =T '2 i，從而：

當(dāng)n為偶數(shù)且 /2i n= 時(shí)，有2i n= ，此時(shí)：

故：

這表明L為對合變換。

3 結(jié)語

介紹了分支數(shù)較好的對合型線性變換在密碼算法中的重要作用，以及主要的構(gòu)造方法。研究了如何利用循環(huán)移位和異或運(yùn)算構(gòu)造從的線性變換，使得分支數(shù)達(dá)到次最優(yōu)，并且是對合的。給出了三種具體的構(gòu)造方法，并分別給出了證明。進(jìn)一步需要研究，在利用這幾類線性變換作為擴(kuò)散層組件時(shí)，密碼算法是否能夠有效地抵抗各種密碼分析方法，尤其是截?cái)嗖罘置艽a分析。同時(shí)，利用提出的設(shè)計(jì)方法能否找到分支數(shù)達(dá)到最優(yōu)的線性變換也是下一步繼續(xù)研究的課題。

[1] 李強(qiáng),李超.Camellia算法中S盒輸出分量函數(shù)的等價(jià)表示[J].通信技術(shù),2008,41(11)：126-128．

[2] 王念平,金晨輝,余昭平.對合型列混合變換的研究[J].電子學(xué)報(bào),2005,33(10)：1917-1920．

[3] 國家商用密碼管理辦公室．無線局域網(wǎng)產(chǎn)品使用的 SMS4密碼算法[EB/OL].(2005-02-05).[2010-01-10].http：//www.oscca.gov.cn/UpFile/200621016423197990.pdf.

[4] DAEMEN J, KNUDSEN L R, RIJMEN V. The Block Cipher Square[C]//FSE 1997, LNCS 1267. Springer-Verlag, Berlin, 1997： 149-165.

[5] PASCAL J, SERGE V. Pergect Diffusion Primitives for Block Ciphers Building Efficient MDS Matrices[C]// SAC 2004, LNCS 3357. Berlin：Springer-Verlag,2005： 84-99.

[6] BARRETO P, RIJMEN V. The Khazad Legacy-level Block Cipher[EB/OL]. (2000-11-13) [2010-01-10]. http：//www.crypt onessie.org.

[7] BARRETO P, RIJMEN V.The Anubis Block Cipher[EB/OL].(2000-11-13).[2010-01-10]. http：//www.cryptonessie.org.

[8] WILLIAMS F M, SLOANE N. The Theory of Error-Correcting Codes[M].Holland：North-Holland Pub. Co.,1977.

[9] 王金波.基于循環(huán)移位構(gòu)造最優(yōu)線性變換[C]//密碼學(xué)進(jìn)展——中國密碼學(xué)會 2007年會論文集.成都：西南交通大學(xué)出版社,2007：306-307.