一類循環(huán)MDS矩陣的構(gòu)造及計(jì)數(shù)

董新鋒 董新科 李 楓

(1.保密通信重點(diǎn)實(shí)驗(yàn)室 四川成都 610041； 2.西南科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 四川綿陽(yáng) 621010)

擴(kuò)散部件的設(shè)計(jì)是密碼算法設(shè)計(jì)的重要組成部分，目前的擴(kuò)散部件主要有MDS矩陣、基于循環(huán)移位和異或運(yùn)算的線性變換、比特置換、二元矩陣等。擴(kuò)散部件設(shè)計(jì)的好壞直接影響著密碼算法的安全性和效率[1-3]，采用差分分支數(shù)和線性分支數(shù)較大的擴(kuò)散結(jié)構(gòu)可以使密碼算法更好地抵抗差分攻擊和線性攻擊，采用結(jié)構(gòu)簡(jiǎn)單的擴(kuò)散部件，有利于密碼算法的快速實(shí)現(xiàn)。

MDS(最大距離可分碼)矩陣的差分分支數(shù)和線性分支數(shù)相等，且達(dá)到最大[4]，故利用MDS矩陣設(shè)計(jì)分組密碼的擴(kuò)散結(jié)構(gòu)是一種常用的方法。目前，MDS矩陣作為擴(kuò)散部件被廣泛應(yīng)用于密碼算法的設(shè)計(jì)中，如AES算法、CLEFIA算法、SMS4算法等都采用MDS矩陣，設(shè)計(jì)擴(kuò)散結(jié)構(gòu)。此外，為了保證密碼算法的快速有效實(shí)現(xiàn)，MDS矩陣應(yīng)具有較少的元素且元素的數(shù)值較小，例如AES算法中使用的MDS矩陣為循環(huán)移位矩陣，且只含有GF(28)上的3個(gè)不同的數(shù)值{1,2,3}，CLEFIA算法中使用的MDS矩陣為Hadamard矩陣，只含有GF(28)上的4個(gè)不同的數(shù)值{1,2,4,6}和{1,2,8,10}。

如何構(gòu)造能夠快速實(shí)現(xiàn)的MDS矩陣一直是人們關(guān)心的重要問(wèn)題。文獻(xiàn)[5]提出可以分別從循環(huán)移位矩陣、Cauchy矩陣以及Hadamard矩陣等特殊的矩陣中搜索出便于實(shí)現(xiàn)的MDS矩陣。文獻(xiàn)[6]與文獻(xiàn)[7]提出了利用Cauchy型矩陣設(shè)計(jì)MDS矩陣的思想和構(gòu)造方法，但能構(gòu)造出的MDS矩陣的個(gè)數(shù)不多，即當(dāng)矩陣的級(jí)數(shù)給定時(shí)，這兩種方法都只能構(gòu)造出一個(gè)或少數(shù)幾個(gè)MDS矩陣。文獻(xiàn)[8]基于Cauchy矩陣以及Hadamard矩陣的構(gòu)造方法給出了一類Cauchy-Hadamard矩陣的構(gòu)造方法。文獻(xiàn)[9-14]研究了通常情形下MDS矩陣的構(gòu)造方法。文獻(xiàn)[15-19]研究了輕量級(jí)MDS變換的構(gòu)造方法。

本文將在Cauchy矩陣構(gòu)造方法的基礎(chǔ)上，提出一種循環(huán)移位MDS矩陣，并給出了這類矩陣的結(jié)構(gòu)、構(gòu)造方法和個(gè)數(shù)，是循環(huán)移位MDS矩陣的一種新的構(gòu)造方法。由于這類MDS矩陣的結(jié)構(gòu)非常簡(jiǎn)明，且構(gòu)造方法簡(jiǎn)單，包含較少的不同元素，因而能夠快速有效實(shí)現(xiàn)。

1 準(zhǔn)備知識(shí)

本文用?表示逐位模2加，用+表示實(shí)數(shù)加或?qū)崝?shù)模2m加，用a-1表示有限域GF(2n)中元素a的乘法逆元。

對(duì)于y=(y1,y2,…,ym)∈GF(2n)m，本文均用W(y)表示y=(y1,y2,…,ym)中非0元的個(gè)數(shù)。

對(duì)于GF(wn)上m×m矩陣A定義的線性變換f(x)=Ax，其差分分支數(shù)達(dá)到最大值m+1等價(jià)于其線性分支數(shù)達(dá)到最大值m+1。當(dāng)其差分分支數(shù)達(dá)到最大值時(shí)，則稱A為MDS矩陣。

下面首先介紹線性變換的差分分支數(shù)Bd和線性分支數(shù)Bl的定義。

定義1 設(shè)f(x)=Ax且A是GF(2n)上的m×m矩陣，則

Bd=min{W(α)+W(Aα)|α∈GF(2n)m{0}}

Bl=min{W(ATα)+W(α)|α∈GF(2n)m{0}}

其中矩陣AT為矩陣A的轉(zhuǎn)置矩陣。此處用+表示實(shí)數(shù)加。

本文以下部分均使用+表示實(shí)數(shù)模2m加。

定義2 設(shè)A=(aij)2m×2m是GF(2n)上的2m×2m矩陣，如果當(dāng)0≤i,j≤2m-1時(shí)，均有aij=a0(i+j)，則稱A為有限域上的一個(gè)循環(huán)(Cyclic)移位矩陣，并簡(jiǎn)記為A=Cyc(a00,a01,…,a0(2m-1)).

定義3[6]設(shè)x0,x1,…,xm-1,y0,y1,…,ym-1是GF(2n)中的互異元，對(duì)0≤i,j≤m-1，令aij=(xi,yj)-1，則稱矩陣(aij)m×m為有限域GF(2n)上由X={x0,x1,…,xm-1}和Y={y0,y1,…,ym-1}生成的Cauchy矩陣。

文獻(xiàn)[6]證明了有限域GF(2n)上的Cauchy矩陣都是MDS矩陣，因而也稱Cauchy矩陣為Cauchy型MDS矩陣。

下面給出Cauchy-Cyclic型MDS矩陣的定義。

定義4 如果有限域GF(2n)上的2m×2m矩陣同時(shí)是Cyclic矩陣和Cauchy矩陣，則稱該矩陣為Cauchy-Cyclic型MDS矩陣，簡(jiǎn)稱為C-C矩陣。

2 C-C型MDS矩陣的構(gòu)造及計(jì)數(shù)

定理1 設(shè)x0,x1,…,x2m-1∈GF(2n)且互不相同，則存在Y∈GF(2n)m，使得由X={x0,x1,…,x2m-1}和Y能夠決定一個(gè)C-C矩陣的充要條件是xi?xj=x0?xi+j對(duì)0≤i,j<2m都成立，且存在GF(2n)中的非零元δ，使得xi?x0≠δ對(duì)0≤i<2m都成立。

證明：

由A是C-C矩陣知a00=aii=(xi?yi)-1，從而

由y0≠xi和y0=x0?δ知xi?x0≠δ，

再由aij=a0(i+j)以及aij=(xi?yj)-1和a0(i+j)=(x0?y(i+j))-1知xi?yj=x0?yi,j，從而有xi?x0=yj?yi+j=(xi,j?δ)?(xj?δ)=xi,j?xj.

這說(shuō)明必要性成立。

設(shè)i≠j，則xi?xj=x0?xi,j≠0，故x0,x1,…,x2m-1是GF(2n)上互不相同的元素。

令yi=xi?δ，則y0,y1,…,y2m-1也是GF(2n)上互不相同的元素。

由于xi?yj=xi?xj?δ=xi(j?x0?δ≠0，故x0,x1,…,x2m-1,y0,y1,…,y2m-1互不相同，因?yàn)橛蒟和(0,y1,…,y2m-1)能夠生成一個(gè)Cauchy矩陣(aij)2m×2m，其中aij=(xi?yi)-1.

再由aii=(xi?yi)-1=(xi?xj?δ)-1=(xi+j?x0?δ)-1=(yi+j?x0)-1=a0(i+j)，即知(aij)2m×2m是循環(huán)矩陣，因而是C-C矩陣。

這說(shuō)明充分性成立。

定理1解決了利用有限域GF(2n)中2m個(gè)不同元{x0,x1,…,x2m-1}通過(guò)構(gòu)造C-C矩陣的方法構(gòu)造MDS矩陣時(shí){x0,x1,…,x2m-1}應(yīng)當(dāng)滿足的條件，其證明過(guò)程給出了C-C矩陣的構(gòu)造結(jié)構(gòu)。

定理1說(shuō)明構(gòu)造C-C矩陣等價(jià)于構(gòu)造GF(2n)中滿足xi?xj=x0?xi+j不同元{x0,x1,…,x2m-1}，并從GF(2n){0,x1?x0,x2?x0,…,x2m-1}中選取一個(gè)元作為δ，因此，也稱C-C矩陣為基于{δ,x0,x1,…,x2m-1}構(gòu)造的C-C矩陣。

下面解決C-C矩陣的計(jì)數(shù)問(wèn)題。

定理2 設(shè)A=(aij)2m×2m和B=(bij)2m×2m是GF(2n)上基于{δ,x0,x1,…,x2m-1}和{δ",y0,y1,…,y2m-1}構(gòu)造的C-C矩陣，則A=B的充要條件是δ=δ"且存在ε∈GF(2n)，使得當(dāng)0≤i≤2m-1時(shí)都有xi?yi=ε.

證明：

由aij=(xi?xj?δ)-1=[(yi?ε)?(yj?ε)?δn]-1=(yi?yj?δ")-1=bij,易知充分性成立。

由aij=(x0?xi,j?δ)-1知a00=δ-1，

同理知b00=δ"-1，

故由A=B可知δ=δ".

設(shè)x0?y0=ε，則由(x0?xi?δ)-1=ai0=bi0=(y0?yi?δ")-1可知xi?yi=ε.

即必要性成立。

定理2說(shuō)明，基于{δ,x0,x1,…,x2m-1}構(gòu)造的C-C矩陣與基于{δ,0,x1?x0,x2?x0,…,x2m-1}構(gòu)造的C-C矩陣相等，因而只需基于{δ,0,x1?x0,x2?x0,…,x2m-1?x0}構(gòu)造C-C矩陣即可。

下面考慮基于{δ,0,x1?x0,x2?x0,…,x2m-1?x0}構(gòu)造的C-C矩陣的計(jì)數(shù)情形。

證明：

3 構(gòu)造方法及實(shí)例

由上節(jié)的相關(guān)結(jié)果可知，C-C矩陣的構(gòu)造可以采用下述的步驟完成。

Step 4 對(duì)0≤i,j<2m-1，令aij=(xi+j?δ)-1,則矩陣A=(aij)2m×2m是GF(2n)上的一個(gè)2m階的C-C矩陣。

下面給出構(gòu)造GF(28)上的一個(gè)4階MDS矩陣的實(shí)例。

選取的8次不可約多項(xiàng)式：f(x)=x8+x4+x3+x2+1。

選取{δ,x0,x1,x2,x3}={δ,0,1,x,x+1}，其中x為GF(28)上的本原元，δ=x2。

根據(jù)aij=(xi+j?δ)-1得到的4階MDS矩陣(0x表示16進(jìn)制前綴)：

測(cè)試結(jié)果表明，上述的4階矩陣具有最大的分支數(shù)5，是循環(huán)MDS矩陣。

4 結(jié)束語(yǔ)

本文研究了Cauchy矩陣的構(gòu)造方法，在此基礎(chǔ)上構(gòu)造了一類循環(huán)移位MDS矩陣(C-C矩陣)，并解決了C-C矩陣的構(gòu)造方法和計(jì)數(shù)問(wèn)題。

本文的研究結(jié)果為循環(huán)移位MDS矩陣的構(gòu)造方法提供了一種新的途徑，豐富了密碼算法擴(kuò)散部件的選擇，對(duì)密碼算法的設(shè)計(jì)具有實(shí)際的應(yīng)用價(jià)值。

如何快速構(gòu)造元素?cái)?shù)值較小的循環(huán)移位矩陣或Hadamard矩陣是進(jìn)一步需要解決的問(wèn)題。

[1] SCHNEIER B,KELSEY J, WHITING D,et al.Twofish:A 128-bit block cipher[OL].Available at http://www.schneier.com/,2007-2-2.

[2] WANG M Q.Differential cryptanalysis of present[OL]. http://eprint.iacr.org/2007/408.

[3] WU W L,ZHANG W T, FENG D G.Impossible differential cryptanalysis of reduce round ARIA and camellia[J].Journal of Computer Science and Technology,2007,22(3):449-456.

[4] KANG J S,HONG S, LEE S J,et al.Practical and provable security against differential and linear cryptanalysis for substitution-permutation networks[J].ETRI Journal,2001,23(4):158-167.

[5] XIAO L, HEYS H.Hardware design and analysis of block cipher omponents[C].Proceedings of the 5th International Conference on Information Security and Cryptology-ICISC’02,2003 LNCS 2587:164-181.

[6] YOUSSEF A,MISTER S, TAVARES S.On the design of linear transformations for substitution permutation encryption networks[C].Workshop on Selected Areas in Cryptography-SAC’97,Ottawa,Workshop record,1997:40-48.

[7] BLOMER J,KALFANE M, KARPINSKI M,et al.An xor-based erasure-resilient coding scheme[R/OL].Technical Report TR-95-048.International Computer Science Institute,August 1995.ftp://ftp.icsi.berkeley.edu/pub/techreports/1995/tr-95-048.ps.gz.

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

[9] MALIK M Y, NO J S. Dynamic MDS Matrices for Substantial Cryptographic Strength[OL]. http://eprint.iacr.org/2011/177.

[10] GUPTA K C, RAY I G. On constructions of MDS matrices from companion matrices for lightweight cryptography[OL]. http://eprint.iacr.org/2013/056.

[11] DEHNAVI S M, MAHMOODI A, MIRZAEE M R, et al. Construction of new families of MDS diffusion layers[OL]. http://eprint.iacr.org/2014/011.

[12] KOLAY S, MUKHOPADHYAY D. Lightweight diffusion layer from thekthroot of the MDS matrix[OL]. http://eprint.iacr.org/2014/498.

[13] SIM S M, KHOO K, OGGIER F, et al. Lightweight MDS inrolution matrices[M]//Fast Software Encryption. Springer Berlin Heidelberg.2015:471-493.

[14] ZHAO R, ZHANG R, LI Y Q, et al. On constructions of a sort of MDS block diffusion matrices for block ciphers and hash functions[OL]. http://eprint.iacr.org/2015/449.

[15] SUMANTA S, SIANG M S. A deeper understanding of the XOR count distribution in the context of lightweight cryptography[OL]. http://eprint.iacr.org/2016/422.

[16] SUMANTA S, HABEEB S. Lightweight diffusion layer importance of toeplitz matrices[OL]. http://eprint.iacr.org/2016/835.

[17] SUMANTA S, HABEEB S. Analysis of toeplitz MDS matrices[OL]. http://eprint.iacr.org/2017/368.

[18] SUMANTA S, HABEEB S, RAJAT S, et al. Lightweight design choices for LED-like block ciphers[OL]. http://eprint.iacr.org/2017/1031.

[19] SUMANTA S, HABEEB S. Bounds on the differential branch number of permutations[OL]. http://eprint.iacr.org/2017/990.