(中國船舶重工集團公司第七二二研究所 武漢 430079)

有限域GF(2n)上Hadamard型MDS矩陣研究*

劉麗輝徐林杰張祖平李艷萍

(中國船舶重工集團公司第七二二研究所 武漢 430079)

論文研究了有限域GF(2n)上Hadamard矩陣的性質(zhì),證明了Hadamard矩陣成為MDS矩陣及對合MDS矩陣的所需滿足的必要條件。特別地,當矩陣階數(shù)為4時,證明了充要條件。改進了4階及8階Hadamard型MDS矩陣的生成算法。

Hadamard矩陣;MDS矩陣;對合

ClassNumberTP301.6

1 引言

MDS矩陣作為一種最優(yōu)擴散映射,廣泛應用于AES、CLEFIA[1]、Twofish[2]及FOX[3]等算法的擴散層設(shè)計中。常見擴散層設(shè)計中的MDS矩陣一般是循環(huán)矩陣、Hadamard矩陣、Cauchy矩陣[4]等類型的矩陣。Cauchy矩陣因矩陣元素漢明重量較大,不利于算法在各種平臺上的實現(xiàn),因此在算法設(shè)計中并不常用;如果一個循環(huán)矩陣是MDS矩陣,則該矩陣一定不是對合的[5],因此,循環(huán)矩陣的應用具有局限性;Hadamard矩陣元素漢明重量較小,并且可以是對合的MDS矩陣,具有易于實現(xiàn)的特點。因此,深入研究Hadamard矩陣型MDS矩陣的性質(zhì)及產(chǎn)生方法,對密碼算法設(shè)計具有重要意義。隨機生成并檢驗的MDS矩陣生成方法效率較低。文獻[6]通過對有限域GF(2n)上Hadamard矩陣生成條件加以限制,提升了MDS矩陣的生成效率,但是效率提升有限。本文通過對Hadamard矩陣性質(zhì)的深入研究,極大地提升了Hadamard型MDS矩陣的生成效率。

2 預備知識

定義1[7]設(shè)A=(ai,j)2m×2m是GF(2n)上的2m×2m矩陣,如果當0≤i,j≤2m-1時,均有ai,j=a0,i⊕j,則稱A為有限域GF(2n)上的一個Hadamard矩陣,并簡記為A=Had(a0,0,a0,1,…,a0,2m-1)。

性質(zhì)1 有限域GF(2n)上的Hadamard矩陣是對稱矩陣。

證明:設(shè)A=Had(a0,0,a0,1,…,a0,2m-1),任取0≤i,j≤2m-1,則

ai,j=a0,i⊕j=a0,j⊕i=aj,i,所以矩陣A為對稱矩陣,證畢。

定義2[8]設(shè)f(x)=Ax,A是GF(2n)上的m×m矩陣,x={x1,x2,…,xm}為(GF(2n))m上的m維列向量,Wh(x)表示非零xi(1≤i≤m)的個數(shù)。則稱:

顯然f的差分分支數(shù)與線性分支數(shù)的最大值為m+1。

分支數(shù)可以衡量有限域上線性矩陣密碼學性質(zhì)好壞,當f的差分分支數(shù)與線性分支數(shù)都達到最大值時,則稱矩陣A為MDS矩陣。當矩陣A為MDS矩陣時,變換f為最優(yōu)的擴散變換。

由Hadamard矩陣的對稱性,結(jié)合差分分支數(shù)與線性分支數(shù)的定義可有如下推論:

推論1 有限域GF(2n)上Hadamard矩陣的差分分支數(shù)和線性分支數(shù)相等。

定理2 有限域GF(2n)上的MDS矩陣的逆矩陣也是MDS矩陣。

證明:設(shè)矩陣A是有限域上的MDS矩陣,A-1表示矩陣A的逆矩陣,則根據(jù)線性分支數(shù)的定義有min{Wh(x)+Wh(A-1x)}=min{Wh(A(A-1x))+Wh(A-1x)}=m+1,即A-1的線性分支數(shù)達到最大,同理可證A-1的差分分支數(shù)也達到最大,因此A-1是MDS矩陣。

性質(zhì)3 有限域GF(2n)上的Hadamard矩陣的逆矩陣仍是Hadamard矩陣。

根據(jù)定理3與Hadmard矩陣的性質(zhì)3有如下定理:

定理3 有限域GF(2n)上Hadamard型MDS矩陣的逆矩陣是Hadamard型MDS矩陣。

3 有限域GF(2n)上的Hadamard型MDS矩陣

有限域上Hadamard矩陣一般通過隨機方式生成,通過分支數(shù)的定義可以判定該矩陣是否為MDS矩陣。但該方法計算量較大,通常使用如下引理檢驗已知矩陣是否為MDS矩陣。

引理1[5]有限域GF(2n)上的矩陣是MDS矩陣的充要條件是該矩陣的所有子方陣都是非退化的。

定理4[6]有限域GF(2n)上的Hadamard矩陣Had(a0,0,a0,1,…,a0,2m-1)是MDS矩陣的必要條件是a0,0,a0,1,…,a0,2m-1兩兩不同且不為0。

根據(jù)定理4生成的Hadamard矩陣,第一行元素均不為零,則該Hadamard矩陣的矩陣元素均不為零,即矩陣的1階子陣均非退化;矩陣的第一行元素互不相同,則矩陣的一些2階方陣非退化。定理4通過限定Hadamard矩陣的生成條件,使得生成矩陣的非退化子方陣的個數(shù)增多。

本文研究了有限域的Hadamard矩陣的性質(zhì)后,在文獻[5]的基礎(chǔ)上進一步增加了在限定條件下生成矩陣的非退化子方陣的個數(shù)。

結(jié)合引理1與定理4有如下定理:

與定理4相比,定理6僅增加一個限制條件,即要求矩陣的第一行元素和不為零,則此時該Hadamard矩陣非退化,且該Hadamard矩陣的所有三階子方陣也均為非退化矩陣。

對于已知的n階方陣,所有子方陣的個數(shù)是確定的,如果需要判斷該矩陣是否為MDS矩陣,若非退化子方陣的個數(shù)越多,即非退化子方陣個數(shù)的下界越大,則需測試的子方陣個數(shù)越少,這就提高了判斷已知矩陣是否為MDS矩陣的效率。

表1列舉了四種2m(m=0,1,2,3)階矩陣的所有子方陣的個數(shù)和不同方法下非退化子方陣個數(shù)的下界。

表1 2m階矩陣非退化子方陣個數(shù)下界比較

3.1 有限域GF(2n)上4階Hadamard型MDS矩陣

以上討論了2m階Hadamard矩陣成為MDS矩陣的必要條件。根據(jù)定理6的限制條件生成的4階Hadamard矩陣,具有該矩陣,1階子方陣,3階子方陣及一些2階子方陣非退化的特點。補充以上條件,可得到4階Hadamard矩陣是MDS矩陣的充要條件。

證明:此時只需考慮2階子式。對任意的2階子式

上述定理指出了生成Hadamard型MDS矩陣的充要條件,實際的Hadamard型MDS生成算法中,判斷條件可以進一步減少。由于Hadamard矩陣的許多子矩陣是等價的,如:

=a0·a3⊕a1·a2

因此,Hadamard型MDS矩陣生成算法中只需判斷其中一個矩陣即可。更實用的篩選4階Hadamard型MDS矩陣的算法如下:

算法1

step1.定義有限域GF(2n)的運算,加法,乘法;

step2.選取4個互不相同且不為0的元素0

step3.如果a0⊕a1⊕a2⊕a3=0,返回step2;

step4.計算a0a3⊕a1a2,a0a1⊕a2a3或a0a2⊕a1a3,若有結(jié)果為0,返回step2;

step5.由a0,a1,a2,a3生成4階Hadamard矩陣;

step6.輸出矩陣A=Had(a0,a1,a2,a3)。

則輸出矩陣A即為Hadamard型MDS矩陣。

算法1是一種4階的Hadamard型MDS矩陣的生成方法,與引理1中需測試69個子方陣相比,通過定理6的限制條件產(chǎn)生Hadamard矩陣,僅需測試3個2階方陣是否非退化。極大地簡化了Hadamard型MDS矩陣生成的判定條件與計算過程,大大的提高了Hadamard型MDS矩陣的生成效率。

3.2 有限域GF(2n)上8階Hadamard型MDS矩陣

同4階Hadamard型MDS矩陣相比,8階Hadamard型MDS矩陣的生成需要測試的子式個數(shù)是驚人的,需要測試更多的矩陣才可能產(chǎn)生一個符合條件的矩陣。若能根據(jù)較小階的MDS矩陣生成一個高階的MDS矩陣是個一個很好的選擇。

可結(jié)合算法1中的4階Hadamard型MDS矩陣生成算法與定理8,構(gòu)造8階Hadamard型MDS矩陣生成算法。如下:

算法2

step1.定義有限域GF(2n)的運算,加法,乘法;

step2.根據(jù)算法1選取u0,u1,u2,u3,生成Hadamard型MDS矩陣U;

step3.根據(jù)算法1選取v0,v1,v2,v3(與u0,u1,u2,u3兩兩不同)生成Hadamard型MDS矩陣V;

step5.由U、V生成8階Hadamard矩陣;

step6.計算該Hadamard矩陣的k階子式2≤k≤2m-2,若有k階子式為零,返回step3;

則輸出矩陣即為8階Hadamard型MDS矩陣。

由算法1可知,生成若干個4階的Hadamard型MDS矩陣是容易的,根據(jù)Hadamard矩陣的性質(zhì),由任意矩陣元素互不相同的兩個4階的Hadamard型MDS矩陣生成8階的Hadamard是簡單的。通過定理8的限制條件產(chǎn)生的Hadamard矩陣的非退化子方陣的個數(shù)已經(jīng)達到340個,需判斷的子方陣的個數(shù)進一步減少,進一步提升了Hadamard型MDS矩陣的生成效率。

4 有限域GF(2n)上對合的Hadamard型MDS矩陣

SP結(jié)構(gòu)是目前廣泛適用的一種分組密碼整體結(jié)構(gòu),如AES、ARIA[10]、PRESRNT[11]等分組密碼都采用此種結(jié)構(gòu)。該種結(jié)構(gòu)可以得到更快速的擴散,使得密碼的輸入輸出更為復雜。但是,SP結(jié)構(gòu)的密碼算法需要對子模塊進行限制,才能保證算法的加解密相似,如AES算法的擴散層中使用了循環(huán)矩陣,雖然該矩陣是MDS矩陣,但是由于該矩陣不是對合的,所以該算法的解密過程中使用了與加密過程中不同的循環(huán)矩陣。如果擴散層的MDS矩陣是對合的,則可保證該算法的加解密相似。

文獻[5]指出,循環(huán)型MDS矩陣一定不是對合矩陣,循環(huán)矩陣的這一性質(zhì)限制了循環(huán)矩陣在SP結(jié)構(gòu)分組密碼算法中的廣泛應用。而由于有限域GF(2n)上Hadamard矩陣結(jié)構(gòu)與性質(zhì)的特殊性,存在很多對合的矩陣。

特別地,對4階Hadamard矩陣有:

5 結(jié)語

本文研究了有限域上Hadamard矩陣的一些性質(zhì),結(jié)合密碼學知識,研究了2m階Hadamard矩陣成為MDS矩陣,對合的MDS矩陣的必要條件。并針對4階MDS矩陣的特點,證明了4階Hadamard矩陣成為MDS矩陣、對合MDS矩陣的充要條件。當矩陣階越大,需判斷條件越多,限制了更高階MDS矩陣的生成,本文改進了8階Hadamard矩陣的生成方法,但能否找到8階Hadamard矩陣是MDS矩陣以及對合的MDS矩陣的充要條件是我們以后的研究工作。

[1]T. Shirai, K. Shibutani, T. Akishita, et al. The 128-bit Blockcipher CLEFIA[C]//FSE’07, LNCS 4593, Springer Verlag,2007:181-195.

[2]Schneier B, Kelsey J, Whiting D. The Twofish Encryption Algorithm:A 128-bit Block Cipher[M]. New York:John Wiley and Sons, Inc,1999:7-11.

[3]Junod, P., Vaudenay, S. FOX:A new family of block ciphers[C]//Handschuh, H., Hasan, M.A. (eds.)SAC 2004. LNCS, Springer, Heidelberg,2004,3357:114-129.

[4]A. Youssef, S. Mister, S. Tavares. On the Design of Linear Transformations for Substitution-Permutation Encryption Networks[C]//Workshop on Selected Areas in Cryptography-SAC’97, Ottawa,1997:164-171.

[5]王念平,金晨輝,余昭平.對合型列混合變換的研究[J].電子學報,2005,33(10):1917-1920.

[6]崔霆,金晨輝.對合Cauchy-Hadamard型MDS矩陣的構(gòu)造[J].電子與信息學報,2010,32(2):500-503.

[7]Xiao L, Heys H. Hardware design and analysis of block cipher components[C]//Proceedings of the 5th International. Conference on Information Security and Cryptology-ICISC’02,2003,2587:164-181.

[8]J Daemen. Cipher and Hash Function Design Strategies Based on Linear and Differential Cryptanalysis[D]. Leuven:K U Leuven,1995.

[9]Joan Daemen, Lars Knudsen, Vincent Rijmen. The Block Cipher Square[C]//Fast Software Encryption(FSE),1997:149-165.

[10]Kwon, D, Kim, J, Park, S, et al. New Block Cipher:ARIA[C]//Lim, J.-I., Lee, D.-H.(eds.)ICISC 2003. LNCS, Springer, Heidelberg,2004,2971:432-445.

[11]Bogdanov, A., Knudsen, L. R., Leander, G., et al. PRESENT:An ultra-lightweight block cipher[C]//Paillier, P., Verbauwhede, I. (eds.)CHES 2007. LNCS, Springer, Heidelberg,2007:450-466.

InvestigateforMDSMatrixofHadamardTypeonFiniteFields

LIU Lihui XU Linjie ZHANG Zuping LI Yanping

(No. 722 Research Institute of CSIC, Wuhan 430079)

In this paper, the character of Hadamard Matrices is investigated, and the necessary condition of Hadamard matrix being MDS matrix and involution MDS matrix is given. In special, the necessary and sufficient condition for 4-order matrix are illustrated. Additionally, the generating algorithms are improved for 4-order and 8-order MDS matrix of Hadamard type.

Hadamard matrix, MDS matrix, involution

2013年11月8日,

:2013年12月27日

劉麗輝,女,碩士,助理工程師,研究方向:信息安全。徐林杰,男,碩士,工程師,研究方向:信息安全。張祖平,男,碩士,工程師,研究方向:信息安全。李艷萍,女,工程師,研究方向:信息安全。

TP301.6DOI:10.3969/j.issn1672-9730.2014.05.012