MDS矩陣構(gòu)造方法

李鵬飛，李永強(qiáng)

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

MDS矩陣構(gòu)造方法

李鵬飛1，2，李永強(qiáng)1

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

針對(duì)MDS矩陣的設(shè)計(jì)策略做了綜述。闡述了MDS矩陣構(gòu)造中的關(guān)鍵問(wèn)題，并對(duì)當(dāng)前典型和常見MDS矩陣的構(gòu)造方法從原理、實(shí)現(xiàn)機(jī)制等方面進(jìn)行了分析和討論。另外，調(diào)研了最近幾年關(guān)于輕量級(jí)MDS矩陣的研究成果。關(guān)鍵詞：分組密碼；最優(yōu)擴(kuò)散層；分支數(shù)；MDS矩陣；線性變換

本文針對(duì)MDS矩陣的設(shè)計(jì)策略做了綜述。歸納總結(jié)了常見的構(gòu)造MDS矩陣的方法，分別為利用線性碼構(gòu)造 MDS矩陣；采用隨機(jī)檢測(cè)矩陣的方法來(lái)構(gòu)造 MDS矩陣，通過(guò)檢測(cè)特殊矩陣來(lái)構(gòu)造MDS矩陣，如循環(huán)矩陣、Hadamard矩陣、對(duì)合矩陣和正交矩陣等，以節(jié)省軟硬件實(shí)現(xiàn)開銷；利用一些數(shù)學(xué)上具有特殊性質(zhì)的矩陣，如Cauchy矩陣、Vandermonde矩陣構(gòu)造MDS矩陣；基于簡(jiǎn)單的移位和異或構(gòu)造高效的 MDS矩陣；基于線性反饋移位寄存器（LFSR， linear feedback shift register）構(gòu)造硬件實(shí)現(xiàn)友好的迭代型最優(yōu)擴(kuò)散層。本文闡述了這些MDS矩陣構(gòu)造方法中的關(guān)鍵問(wèn)題，并對(duì)當(dāng)前典型的構(gòu)造方法從原理、實(shí)現(xiàn)機(jī)制等方面進(jìn)行了分析和討論，另外，隨著物聯(lián)網(wǎng)技術(shù)的快速發(fā)展，設(shè)計(jì)和構(gòu)造輕量級(jí)的MDS矩陣受到了越來(lái)越多研究人員的關(guān)注，本文也對(duì)近幾年輕量級(jí) MDS矩陣的研究成果進(jìn)行了調(diào)研。

2　基本概念

2.1分支數(shù)

在迭代型密碼結(jié)構(gòu)中，將輸入差分或者輸出掩碼非零的S盒稱為活躍S盒。一般情況下，如果混淆層是由n個(gè)mm×的 S盒并置而成，則擴(kuò)散層一般設(shè)計(jì)成的一個(gè)置換，其中如圖1所示。

圖1　混淆層和擴(kuò)散層結(jié)構(gòu)

分支數(shù)又分為差分分支數(shù)和線性分支數(shù)，具體定義如下。

定義2擴(kuò)散層θ的差分分支數(shù)定義為［4］

類似于差分分支數(shù)，可以給出擴(kuò)散層線性分支數(shù)的定義。

定義3擴(kuò)散層θ的線性分支數(shù)定義為［4］

其中，MT為矩陣M的轉(zhuǎn)置。

差分（線性）分支數(shù)即連續(xù)兩輪的差分（線性）特征中活躍S盒的最小數(shù)目，設(shè)計(jì)者可以根據(jù)差分（線性）分支數(shù)的大小給出理論上最大差分特征概率（最佳線性逼近偏差）的界，由此可以分析密碼算法抵抗差分和線性分析的能力。關(guān)于分支數(shù)有如下性質(zhì)［19］。

1）擴(kuò)散層矩陣M的線性分支數(shù)等于轉(zhuǎn)置矩陣MT的差分分支數(shù)。2）擴(kuò)散層的分支數(shù)等于其逆變換的分支數(shù)。3）擴(kuò)散層差分分支數(shù)達(dá)到最大，當(dāng)且僅當(dāng)其線性分支數(shù)也達(dá)到最大。

定義4分支數(shù)達(dá)到最大的擴(kuò)散層稱為最優(yōu)擴(kuò)散層，所對(duì)應(yīng)的矩陣稱為MDS矩陣。

2.2線性碼

線性碼理論對(duì)于研究擴(kuò)散層的分支數(shù)很重要，本節(jié)結(jié)合文獻(xiàn)［4，5］，給出線性碼的一些重要性質(zhì)和定理。

定義5域GF（2p）上的線性碼C=［n，k，d］是指向量空間GF（2p）n上任意 2個(gè)不同向量之間漢明距離至少為d的一個(gè)k維子空間，空間的元素稱為一個(gè)碼字。線性碼C的最小漢明距離d等于線性碼C中非零碼字的最小漢明重量。

由定義7可知，若假設(shè)線性碼C的生成矩陣為G，校驗(yàn)矩陣為H，則有，而且，如果是碼C的生成矩陣，則是碼C的校驗(yàn)矩陣。

定義8將與線性碼C中所有向量都正交的向量集合稱為C的對(duì)偶碼C⊥，具體定義為

由此可以看出，線性碼C的校驗(yàn)矩陣就是C⊥的生成矩陣。

下面介紹幾個(gè)重要定理。

定理1設(shè)C是一個(gè)［n，k，d］線性碼，H是它的校驗(yàn)矩陣，如果H的任意d?1列線性無(wú)關(guān)，且存在d列線性相關(guān)，則線性碼C的最小漢明距離等于d。

定理5 （MDS矩陣的判定定理）設(shè)矩陣M是與擴(kuò)散層θ對(duì)應(yīng)的n階矩陣，則M為MDS矩陣（即的充要條件是M的任意k階子式都不為零（1≤k≤n）。

定理6 （MDS矩陣的判定定理）設(shè)矩陣M是與擴(kuò)散層θ對(duì)應(yīng)的n階矩陣，則M為MDS矩陣（即的充要條件是M的任意k階子方陣均滿秩1≤k≤n）。

2.3構(gòu)造MDS的相關(guān)矩陣

定義 9［20］具有以下形式的n階方陣A稱為循環(huán)矩陣。

顯然，矩陣A的每一行向量的每一個(gè)元素由前一行向量各元素依次循環(huán)右移一個(gè)位置得到，循環(huán)矩陣A可簡(jiǎn)記為

定義 10［21］一個(gè)n階方陣A稱為對(duì)合矩陣當(dāng)且僅當(dāng)該矩陣滿足即，其中，I表示n階單位陣。

定義 11［21］一個(gè)n階方陣A稱為正交矩陣當(dāng)且僅當(dāng)該矩陣滿足，其中，I表示n階單位陣，表示矩陣A的轉(zhuǎn)置矩陣。

定義12［9］一個(gè)2n×2n矩陣H稱為Hadamard矩陣，則它具有如下形式。

定義13［22，23］給定令且則將n階方陣稱為柯西矩陣，其行列式為

定義14［23，24］給定，則滿足以下形式的n階方陣A稱為范德蒙（Vandermonde）矩陣。

其行列式為

3　利用線性碼構(gòu)造MDS矩陣

一直以來(lái)，MDS碼是構(gòu)造密碼算法最優(yōu)擴(kuò)散層的主要工具，通過(guò) MDS碼構(gòu)造的擴(kuò)散層分支數(shù)達(dá)到最大，具有良好的擴(kuò)散能力，能夠更好地抵抗差分分析、線性分析和其他未知的密碼分析。許多分組密碼算法如 AES、Khazad、SHARK、Square等擴(kuò)散層中所使用的 MDS矩陣就是從MDS碼中提取出來(lái)的。Reed-Solomon碼［23，25］是一種 MDS碼，它的最小漢明距離達(dá)到了最大，可以用來(lái)構(gòu)造MDS矩陣。另外，BCH碼［23，26］、Goppa碼［27］這2種線性碼的最小距離都是可以設(shè)計(jì)的，通過(guò)控制這2種線性碼的最小漢明距離，使其達(dá)到最大值，即可從它們的生成矩陣提取MDS矩陣。另外，文獻(xiàn)［28］提出通過(guò) Gabidulin碼來(lái)構(gòu)造MDS碼的新方法。

3.1 分支數(shù)與線性碼的關(guān)系

根據(jù)線性碼的一些重要性質(zhì)和定理，可利用GF（2）p上的線性碼來(lái)進(jìn)一步分析擴(kuò)散層的分支數(shù)，以得到線性碼和擴(kuò)散層分支數(shù)間的關(guān)系，以下定義參考文獻(xiàn)［29］。

由此，將線性碼和擴(kuò)散層聯(lián)系起來(lái)，結(jié)合差分分支數(shù)的定義 2，可以進(jìn)一步得到擴(kuò)散層差分分支數(shù)與線性碼的關(guān)系。

定理 7 擴(kuò)散層θ的差分分支數(shù)等于它的相關(guān)線性碼中2個(gè)不同碼字之間的最小漢明距離。這是因?yàn)?，根?jù)擴(kuò)散層θ的差分分支數(shù)定義2有

得到了擴(kuò)散層和線性碼之間的關(guān)系，即可利用線性碼來(lái)構(gòu)造MDS矩陣。

3.2 構(gòu)造MDS矩陣的方法

定理8［5］令C是有限域上的一個(gè)［2m， m，m+1］線性碼是C的生成矩陣的梯次形，則C定義了如下置換。

4　利用隨機(jī)檢測(cè)矩陣來(lái)構(gòu)造MDS矩陣

為了節(jié)省軟硬件實(shí)現(xiàn)的系統(tǒng)資源，減少開銷，提高密碼算法運(yùn)行速度，通常根據(jù)定理5和定理6通過(guò)檢測(cè)特殊矩陣來(lái)構(gòu)造MDS矩陣，如循環(huán)矩陣、Hadamard矩陣、對(duì)合矩陣和正交矩陣等。循環(huán)矩陣和 Hadamard矩陣可使矩陣中不同元素的數(shù)量極其少，對(duì)合矩陣可使密碼算法加解密一致，節(jié)省解密的開銷，正交矩陣同樣可以使用幾乎相同的電路實(shí)現(xiàn)加解密操作。

4.1 循環(huán)矩陣

由循環(huán)矩陣的定義9可知，循環(huán)矩陣的元素基本相同，只用實(shí)現(xiàn)一行，然后通過(guò)不斷更新輸入向量，便可以得到全部的輸出向量，另外，與一般的隨機(jī)矩陣相比，循環(huán)矩陣所對(duì)應(yīng)的擴(kuò)散層達(dá)到最優(yōu)的概率更大［8］。采用循環(huán)矩陣作為擴(kuò)散層的密碼算法很多，典型的是AES算法中列混淆部分所使用的MDS矩陣另外，還有基于分組密碼的Hash函數(shù)Whirlpool擴(kuò)散層中使用的MDS矩陣它們均作用在有限域）上。實(shí)際中，還可以根據(jù)下面2個(gè)定理構(gòu)造循環(huán)MDS矩陣。

定理9［31］設(shè)為上可逆多項(xiàng)式的系數(shù)，c（ x）對(duì)應(yīng)的線性變換其中，D為4階循環(huán)矩陣如果滿足以下條件。

其結(jié)果兩兩不等。

則循環(huán)矩陣D為MDS矩陣，即線性變換θ（x）分支數(shù)達(dá)到最大5。

定理10［32］設(shè)是上的一個(gè)可逆多項(xiàng)式，設(shè)其逆多項(xiàng)式為對(duì)應(yīng)的線性變換為其中，D為4階循環(huán)矩陣，如果滿足如下條件。

則4階循環(huán)矩陣D為MDS矩陣，線性變換θ（x）分支數(shù)達(dá)到最大5。

4.2 Hadamard矩陣

由Hadamard矩陣的定義12可知，與循環(huán)矩陣類似，Hadamard矩陣的每一行均是第一行的置換，因此節(jié)省了軟硬件實(shí)現(xiàn)開銷，采用Hadamard矩陣的典型算法是CLEFIA、Anubis和Khazad。輕量級(jí)分組密碼算法 CLEFIA中所使用的 2個(gè)Hadamard MDS矩陣為H=Had（01，02，04，06）和H=Had（01，08，02，0a），它們均作用在有限域上。Anubis算法中使用的 MDS矩陣和CLEFIA算法中的第一個(gè)矩陣相同。Khazad算法中所使用的 MDS矩陣為H=Had（01，03，04，05，06，08，0b，07），它也是作用在有限域上。關(guān)于Hadamard矩陣，有如下性質(zhì)和定理［33，34］。

4.3對(duì)合矩陣和正交矩陣

對(duì)合矩陣的優(yōu)點(diǎn)在于可以使用相同的電路實(shí)現(xiàn)加解密操作，節(jié)省了密碼算法加解密的實(shí)現(xiàn)開銷，典型的是Anubis和Khazad算法擴(kuò)散層中使用的對(duì)合 MDS矩陣。正交矩陣的優(yōu)點(diǎn)是可以通過(guò)實(shí)現(xiàn)矩陣的轉(zhuǎn)置來(lái)得到逆變換，可以使用幾乎相同的電路實(shí)現(xiàn)加解密操作，所以，正交矩陣同對(duì)合矩陣一樣，簡(jiǎn)化了逆矩陣的實(shí)現(xiàn)，使解密實(shí)現(xiàn)效率更高。

利用特殊矩陣來(lái)構(gòu)造MDS矩陣的研究成果很多，文獻(xiàn)［22］利用MDS碼來(lái)構(gòu)造對(duì)合MDS矩陣，Sajadieh等［24］提出一種基于有限域GF（2）q構(gòu)造對(duì)合Hadamard MDS矩陣的方法。文獻(xiàn)［35］提出了一種構(gòu)造擁有低漢明重量的對(duì)合MDS矩陣。早在2009年，Nakahara等［36］就證明4階循環(huán)MDS矩陣不可能是對(duì)合的。ISPEC 2014上，Gupta等［21］又證明了基于有限域的n×n循環(huán)對(duì)合MDS矩陣是不存在的，同時(shí)也證明了基于有限域的2d×2d的循環(huán)正交 MDS矩陣也是不存在的。文獻(xiàn)［37］從數(shù)學(xué)角度通過(guò)分解循環(huán)矩陣，構(gòu)造出一種新型的循環(huán)MDS矩陣。

FSE 2015上，Sim等［38］通過(guò)證明一些有關(guān)循環(huán)矩陣、Hadamard矩陣、Cauchy矩陣和Hadamard-Cauchy矩陣的等價(jià)類，提出一個(gè)新的算法來(lái)搜索具有更少異或數(shù)的輕量級(jí)對(duì)合 MDS矩陣，該算法減少了搜索空間，使MDS矩陣的搜索變得更容易，并且找到了更大維數(shù)的 MDS矩陣。FSE 2016上，Liu等［39］通過(guò)分析循環(huán)矩陣的一些新的等價(jià)類性質(zhì)，縮小了搜索空間，得到了一系列的循環(huán) MDS矩陣，另外，他們提出一種新型的具有類似于循環(huán)矩陣性質(zhì)且具有潛在自逆性的cyclic矩陣，構(gòu)造出對(duì)合left-circulant MDS矩陣。FSE 2016上，Li等［40］直接基于向量空間F2m構(gòu)造 MDS矩陣，采用非交換元素首次構(gòu)造了作用在4 bit和8 bit S盒上的4階和5階輕量級(jí)循環(huán)對(duì)合 MDS矩陣（這一類型的基于有限域的矩陣之前在文獻(xiàn)［21，36］中被證明是不存在的），并且構(gòu)造了一系列循環(huán)非對(duì)合 MDS矩陣，循環(huán)正交MDS矩陣，Hadamard對(duì)合MDS矩陣和Hadamard非對(duì)合MDS矩陣，這些輕量級(jí)MDS矩陣硬件實(shí)現(xiàn)所需的異或數(shù)均極少。

由于循環(huán)矩陣、Hadamard矩陣、對(duì)合矩陣和正交矩陣等特殊矩陣相對(duì)于普通矩陣具有更低的軟硬件實(shí)現(xiàn)代價(jià)，所以受到研究人員的青睞，一般來(lái)說(shuō)，利用隨機(jī)檢測(cè)矩陣來(lái)構(gòu)造 MDS矩陣，可以找到足夠輕量的 MDS矩陣，但由于需要搜索的空間非常大，需要搜索所有可能的置換，所以一般從理論上分析它們的一些等價(jià)類特征和自身所具有的一些性質(zhì)，以此來(lái)縮小搜索空間，但當(dāng)矩陣的維數(shù)較大時(shí)，直接進(jìn)行窮舉搜索也顯得不太現(xiàn)實(shí)，此時(shí)，一般在具有特定結(jié)構(gòu)的矩陣中搜索MDS矩陣，這樣的好處是搜索的空間比較小，可以得到這種特定結(jié)構(gòu)中最輕量的MDS矩陣，但可能會(huì)漏失一些更加輕量的其他MDS矩陣。

5　利用數(shù)學(xué)方法構(gòu)造MDS矩陣

Cauchy矩陣和Vandermonde矩陣由于具有數(shù)學(xué)上的特性，通常被用來(lái)構(gòu)造大階MDS矩陣。

5.1利用Cauchy矩陣構(gòu)造MDS矩陣

根據(jù)Cauchy矩陣的定義13，結(jié)合式（9）可知，如果對(duì)于任意的i ，j均滿足xi各不相同，yi各不相同，且，那么該類型矩陣的任意子方陣均非奇異，由定理5可知，可以很容易地通過(guò)Cauchy矩陣來(lái)構(gòu)造MDS矩陣。有不少學(xué)者利用Cauchy矩陣來(lái)構(gòu)造MDS矩陣，文獻(xiàn)［34］證明了Cauchy-Hadamard型MDS矩陣等效于對(duì)合Cauchy-Hadamard型MDS矩陣，并且給出了由 Cauchy-Hadamard型 MDS矩陣構(gòu)造對(duì)合Cauchy-Hadamard型MDS矩陣的方法。文獻(xiàn)［41］證明了有限域上 Cauchy矩陣的個(gè)數(shù)，也證明了Cauchy矩陣一定不是循環(huán)移位矩陣。文獻(xiàn)［42］提出一種緊湊型的 Cauchy矩陣（CCM， compact cauchy matrices），它們擁有最少的不同元素?cái)?shù)目，更加利于軟硬件實(shí)現(xiàn)，他們還證明所有的緊湊型Cauchy矩陣可以轉(zhuǎn)化為對(duì)合緊湊型Cauchy矩陣。文獻(xiàn)［43］對(duì) Cauchy矩陣和 MDS矩陣分別從Hadamard矩陣和循環(huán)移位矩陣以相互結(jié)合的方式構(gòu)造最優(yōu)擴(kuò)散層的方法進(jìn)行了研究。文獻(xiàn)［22］利用Cauchy矩陣的性質(zhì)構(gòu)造了新型的對(duì)合MDS矩陣。文獻(xiàn)［35］提出一種基于Cauchy矩陣構(gòu)造有效MDS矩陣的一般方法。

5.2利用Vandermonde矩陣構(gòu)造MDS矩陣

根據(jù)Vandermonde矩陣的定義14，結(jié)合式（11）可知，當(dāng)互不相同且不為0時(shí)，該類型矩陣的任意子式非零，由定理5可知，可以使用Vandermonde矩陣來(lái)構(gòu)造MDS矩陣。

文獻(xiàn)［44］介紹了2個(gè)利用Vandermonde矩陣構(gòu)造 MDS矩陣的方法。文獻(xiàn)［24］提出一種使用Vandermonde矩陣構(gòu)造任意階對(duì)合 MDS矩陣的方法。文獻(xiàn)［35］基于Vandermonde和Cauchy矩陣構(gòu)造了對(duì)合Hadamard MDS矩陣。

采用隨機(jī)檢測(cè)特殊矩陣來(lái)構(gòu)造MDS矩陣的方法通常只適用于矩陣維數(shù)較小時(shí)，當(dāng)需要構(gòu)造更大維數(shù)的 MDS矩陣時(shí)，這種方法不適用，此時(shí)，可以利用數(shù)學(xué)上具有某些特性的矩陣來(lái)構(gòu)造MDS矩陣，Cauchy矩陣和Vandermonde矩陣因其獨(dú)特的結(jié)構(gòu)可用來(lái)構(gòu)造任意階的MDS矩陣。但由于這類MDS矩陣中元素漢明重量通常較大，實(shí)現(xiàn)過(guò)程需要消耗很大的軟硬件資源，因此，在密碼算法設(shè)計(jì)中不常用。

6　利用移位和異或構(gòu)造MDS矩陣

基于簡(jiǎn)單移位和異或構(gòu)造的擴(kuò)散層由于具有軟硬件實(shí)現(xiàn)效率高，能夠增強(qiáng)密碼算法抵抗時(shí)間、能量等密碼分析能力的特點(diǎn)，已被很多對(duì)稱密碼算法所使用，比如，我國(guó)無(wú)線局域網(wǎng)產(chǎn)品中使用的密碼算法SM4［45］、3GPP LTE國(guó)際加密標(biāo)準(zhǔn)ZUC算法［46］、HIGHT［47］、SHA-256［48］、MD6［49］等，其中，SM4和ZUC中所使用的就是這種類型的最優(yōu)擴(kuò)散層，其分支數(shù)達(dá)到了最大。SM4中的擴(kuò)散層為中使用了2個(gè)最優(yōu)擴(kuò)散層，其中一個(gè)和SM4中的相同，另外一個(gè)是

近幾年，有一些利用移位和異或構(gòu)造 MDS矩陣的研究，文獻(xiàn)［50］研究了基于循環(huán)移位和異或構(gòu)造的擴(kuò)散層分支數(shù)達(dá)到最優(yōu)時(shí)需要滿足的一些必要條件，文獻(xiàn)［51］研究了SM4型的擴(kuò)散層，指出在一定的等價(jià)意義下，這樣的最優(yōu)擴(kuò)散層僅有 2個(gè)，文獻(xiàn)［52］研究了基于循環(huán)移位和異或運(yùn)算設(shè)計(jì)的對(duì)合線性變換，給出了這類線性變換的計(jì)數(shù)公式，指出它們的分支數(shù)上界為4。

7　利用LFSR構(gòu)造迭代型最優(yōu)擴(kuò)散層

近幾年，隨著物聯(lián)網(wǎng)（IoT， Internet of things）技術(shù)的發(fā)展，射頻識(shí)別（RFID， radio frequency identification）標(biāo)簽、無(wú)線傳感器網(wǎng)絡(luò)（WSN，wireless sensor network）、個(gè)人數(shù)字助理終端（PDA，personal digital assistant）等微型嵌入式設(shè)備越來(lái)越發(fā)達(dá)，由于這些微型嵌入式計(jì)算設(shè)備在面積、通信能力、電源能量、計(jì)算速度和存儲(chǔ)空間等方面嚴(yán)峻的資源限制，要保護(hù)數(shù)據(jù)安全和用戶隱私就必須設(shè)計(jì)更加輕量的密碼算法，于是，設(shè)計(jì)更加輕量、安全的部件，特別是擴(kuò)散層成為研究焦點(diǎn)。

為了滿足資源受限設(shè)備加解密的需求，節(jié)省軟硬件實(shí)現(xiàn)開銷，除了上述利用隨機(jī)檢測(cè)矩陣和基于移位和異或構(gòu)造輕量級(jí) MDS矩陣外，PHOTON輕量級(jí)Hash函數(shù)族的設(shè)計(jì)者們［18］還提出一種新的最優(yōu)擴(kuò)散層設(shè)計(jì)策略——迭代型擴(kuò)散層設(shè)計(jì)。這種設(shè)計(jì)方式借用流密碼算法中的LFSR的設(shè)計(jì)思想，如圖2所示，每次只更新一個(gè)元素，其余元素則通過(guò)移位得到。

圖2　PHOTON中最優(yōu)擴(kuò)散層設(shè)計(jì)方式

圖2中每個(gè) Li選自有限域GF（2n），迭代s步后的最終狀態(tài)作為擴(kuò)散層的輸出。假設(shè)A是LFSR的狀態(tài)轉(zhuǎn)移矩陣，則這種方式構(gòu)造的擴(kuò)散層矩陣是GF（2n）上的n×n矩陣As。此外，輕量級(jí)分組密碼算法 LED和認(rèn)證加密算法PRIMATEs［53］的最優(yōu)擴(kuò)散層也采用這種方式設(shè)計(jì)。

狀態(tài)轉(zhuǎn)移矩陣（也稱為相伴矩陣）A的具體形式如下。

迭代型擴(kuò)散層的設(shè)計(jì)在得到MDS矩陣的同時(shí)，也具有很高的硬件實(shí)現(xiàn)效率，只需實(shí)現(xiàn)LFSR且能在不需要增加額外邏輯控制電路的情形下重用已有的存儲(chǔ)，因此，十分適合硬件實(shí)現(xiàn)，但是，軟件需要使用類似于 AES中的查表過(guò)程實(shí)現(xiàn)該擴(kuò)散層，矩陣需要用表來(lái)存儲(chǔ)，消耗一定的存儲(chǔ)空間，另外，這種設(shè)計(jì)方式在節(jié)省硬件實(shí)現(xiàn)面積的同時(shí)，增加了時(shí)鐘周期，具有一定的延遲，因此，它不適合在延遲性要求比較高的場(chǎng)景下使用。

受到PHOTON擴(kuò)散層的啟發(fā)，越來(lái)越多的學(xué)者把關(guān)注點(diǎn)放在了迭代型擴(kuò)散層的設(shè)計(jì)上，涌現(xiàn)出了一大批研究成果。FSE 2012上，Sajadieh等［54］對(duì)該設(shè)計(jì)方式進(jìn)行了擴(kuò)展，并給出了一系列最優(yōu)擴(kuò)散層。他們將圖2中線性變換i的選取從有限域GF）擴(kuò)展到了向量空間上，得到的MDS矩陣可以表示成上的sn×sn矩陣或者GF（2）n上的s×s分塊矩陣。由于有限域GF（2）n上的乘法運(yùn)算是向量空間F2n上的特殊線性變換，因此，Sajadieh等的工作擴(kuò)展了擴(kuò)散層的選擇空間，這使設(shè)計(jì)者可能構(gòu)造出硬件實(shí)現(xiàn)代價(jià)更低的擴(kuò)散層。

SAC 2012上，Wu等［55］在Sajadieh等基礎(chǔ)上，通過(guò)改變線性變換的選擇范圍，得到了一系列最優(yōu)分支數(shù)為5～9的輕量級(jí)擴(kuò)散層。Augot等［56］擺脫以上方法中復(fù)雜的符號(hào)計(jì)算，構(gòu)造出了階數(shù)更大的迭代型MDS矩陣。另外，迭代型的MDS矩陣構(gòu)造還與碼理論有關(guān)。Berger［57］利用Gabidulin碼構(gòu)造了迭代型MDS矩陣。FSE 2014上，Augot等［26］直接采用BCH碼來(lái)構(gòu)造迭代型MDS矩陣。

由于迭代型MDS矩陣具有高延遲的缺點(diǎn)，LFSR需要進(jìn)行好多拍才能得到輸出向量，于是，研究如何構(gòu)造非迭代型的輕量級(jí) MDS矩陣成為接下來(lái)的研究重點(diǎn)。一些學(xué)者重新基于有限域來(lái)構(gòu)造輕量級(jí) MDS矩陣，經(jīng)過(guò)精心選擇有限域上元素，可以使軟硬件實(shí)現(xiàn)代價(jià)降低。最近，CHES 2014上，Khoo等［58］指出不可約多項(xiàng)式的選取對(duì)有限域上元素乘法實(shí)現(xiàn)有很大影響，這意味著可以選擇有效的不可約多項(xiàng)式來(lái)構(gòu)造 MDS矩陣，節(jié)省軟硬件實(shí)現(xiàn)開銷。文獻(xiàn)［38］對(duì)該性質(zhì)進(jìn)行了進(jìn)一步的研究。

8　MDS矩陣的實(shí)現(xiàn)方法

在實(shí)際應(yīng)用中，密碼算法需要在不同軟硬件平臺(tái)上高效實(shí)現(xiàn)，而擴(kuò)散層作為密碼算法一個(gè)很重要的部分，它的實(shí)現(xiàn)性能直接影響整個(gè)密碼算法的高效性能。一般來(lái)說(shuō)，實(shí)現(xiàn) MDS矩陣的常用方法有基于xtime（）乘法［4］、基于字的乘法、查小表、查大表，后2種是通過(guò)預(yù)置乘法表的方法，利用空間換取時(shí)間來(lái)提高運(yùn)行速度。為了節(jié)省軟硬件資源，提高密碼算法運(yùn)行速度，需要根據(jù)不同的應(yīng)用場(chǎng)景，選用不同的實(shí)現(xiàn)方式，在資源空間受限的情況下，適宜采用基于字的乘法實(shí)現(xiàn)方式；在資源空間充足的情況下，宜采用查大表的方法實(shí)現(xiàn)MDS矩陣［36，59］。

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

MDS矩陣廣泛應(yīng)用于分組密碼算法、Hash函數(shù)、認(rèn)證加密算法，使用 MDS矩陣作為擴(kuò)散層，可以保證分支數(shù)達(dá)到最大，從而可以最大限度地保證密碼算法在差分和線性分析下的安全性。本文比較系統(tǒng)地闡述了常見的構(gòu)造 MDS矩陣的方法：從線性碼中提取 MDS矩陣；采用隨機(jī)檢測(cè)矩陣構(gòu)造特殊MDS矩陣，如循環(huán)MDS矩陣、Hadamard MDS矩陣、對(duì)合MDS矩陣和正交MDS矩陣；使用數(shù)學(xué)上具有特殊性質(zhì)的矩陣，如Cauchy矩陣和Vandermonde矩陣構(gòu)造MDS矩陣。本文基于移位和異或構(gòu)造高效的 MDS矩陣和利用 LFSR構(gòu)造硬件實(shí)現(xiàn)友好的迭代型最優(yōu)擴(kuò)散層，介紹了構(gòu)造 MDS矩陣的原理，并詳細(xì)給出了各種方法的研究現(xiàn)狀以及其中的優(yōu)缺點(diǎn)，最后，給出了 MDS矩陣的實(shí)現(xiàn)方法，設(shè)計(jì)者可以根據(jù)應(yīng)用場(chǎng)景的不同選用不同的實(shí)現(xiàn)方式以提高算法運(yùn)行速度，節(jié)省軟硬件資源。

［1］SHANNON C E. Communication theory of secrecy systems［J］. Bell System Technical Journal， 2015， 28（4）：656-715.

［2］BIHAM E， SHAMIR A. Differential cryptanalysis of DES-like cryptosystems［J］. Journal of Cryptology， 1991， 4（1）： 3-72.

［3］MATSUI M. Linear cryptanalysis method for DES cipher［M］// Advances in Cryptology — EUROCRYPT. Berlin Heidelberg：Springer， 1993：386-397.

［4］DAEMEN J， RIJMEN V. The design of rijndael， AES—the advanced encryption standard［M］. Berlin Heidelberg：Springer， 2002.

［5］RIJMEN V， DAEMEN J. The cipher SHARK［C］//Fast Software Encryption. c1996：99-112.

［6］SCHNEIER B， KELSEY J， WHITING D， et al. Twofish： a 128 bit block cipher［C］// The 1st AES Candidate Conference on National Institute for Standards and Technology. c1998.

［7］SCHNEIER B， KELSEY J， WHITING D， et al. The twofish encryption algorithm［M］.1999.

［8］DAEMEN J， KNUDSEN L R， RIJMEN V. The block cipher square［C］//The 4th fast software encryption workshop. c1997：149-165.

［9］BARRETO P， RIJMEN V. The anubis block cipher［EB/OL］. http：//www.larc.usp.br/～pbarreto/AnubisPage.html.

［10］BARRETO P， RIJMEN V. The khazad legacy-level block cipher［J］. Primitive Submitted to NESSIE， 2000.

［11］JUNOD P， VAUDENAY S. FOX： a new family of block ciphers［C］//Selected Areas in Cryptography. c2004：114-119.

［12］SHIRAI T， SHIBUTANI K， AKISHITA T， et al. The 128 bit block cipher CLEFIA［C］//International Workshop on Fast Software Encryption. c2007： 181-195.

［13］GUO J， PEYRIN T， POSCHMANN A， et al. The LED block cipher［C］//International Workshop on Cryptographic Hardware and Embedded Systems. c2011： 326-341.

［14］WATANABE D， FURUYA S， YOSHIDA H， et al. A new keystream generator MUGI［C］//FSE 2002. c2002：179-194.

［15］FILHO G D， BARRETO P， RIJMEN V. The maelstrom-0 Hash function［C］//The 6th Brazilian Symposium on Information and Computer Systems Security. c2006.

［16］GAURAVARAM P， KNUDSEN L R， MATUSIEWICZ K， et al. Gr?stl a SHA-3 candidate［EB/OL］. http：//www.groestl.info.

［17］BARRETO P S L M， RIJMEN V. Encyclopedia of cryptography and security［C］//2nd Edn. c2011：1384-1385.

［18］GUO J， PEYRIN T， POSCHMANN A. The PHOTON family of lightweight hash functions［C］// Rogaway-CRYPTO 2011. c2011：222-239.

［19］DAMG?RD I B. A design principle for hash functions［C］// Advances in Cryptology-CRYPTO'89. c1990： 416-427.

［20］RAO A R， BHIMASANKARAM P.Linear algebra［M］. Hindustan Book Agency.

［21］KISHAN C G， INDRANIL G R. On constructions of circulant MDS matrices for lightweight cryptography［C］// ISPEC. c2014：564-576.

［22］YOUSSEF A M， MISTER S， TAVARES S E. On the design of linear transformations for substitution permutation encryption networks［C］//Workshop On Selected Areas in Cryptography（SAC）. c1997：40-48.

［23］WILLIAMS F J M， SLOANE N J A. The theory of error correcting codes［M］. Elsevier， 1977.

［24］SAJADIEH M， DAKHILALIAN M， MAL H， et al. On construction of involutory MDS matrices from vandermonde matrices in ［C］// Design， Codes Cryptography. c2012：1-22.

［25］LINT J H V. Algebraic geometric codes［M］//Coding theory and design theory. New York ：Springer， 1990： 137-162.

［26］AUGOT D， FINIASZ M. Direct construction of recursive MDS diffusion layers using shortened BCH codes［C］//International Workshop on Fast Software Encryption. c2014： 3-17.

［27］GOPPA V D. A new class of linear correcting codes［J］. Problemy Peredachi Informatsii， 1970， 6（3）： 24-30.

［28］BERGER T P， OURIVSKI A. Construction of new MDS codes from gabidulin codes［C］// ACCT. c2009： 40-47.

［29］楊譜. 分組迭代密碼函數(shù)的擴(kuò)散層分析及應(yīng)用［D］. 西安：西安電子科技大學(xué)， 2013. YANG P. Cryptanalysis and applications for diffusion layer of iterated block function［D］. Xi'an： Xidian University， 2013.

［30］JUNOD P， VAUDENAY S. Perfect diffusion primitives for block ciphers［C］//International Workshop on Selected Areas in Cryptography. c2004： 84-99.

［31］何凌云. 分組密碼擴(kuò)散層的改進(jìn)研究［D］. 杭州： 杭州電子科技大學(xué)， 2011. HE L Y. Research on the improvement of block cipher diffusion layer［D］. Hangzhou： Hangzhou Dianzi University， 2011.

［32］郭艷珍， 韓文報(bào)， 趙龍， 等. AES列混合變換［J］. 解放軍理工大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2009 （3）： 232-236. GUO Y Z， HAN W B， ZHAO L， et al. AES mixColumns transfor-mation［J］. Journal of PLA University of Science and Technology（ Natural Science Edition）， 2009（3）： 232-236.

［33］劉麗輝， 徐林杰， 張祖平， 等. 有限域上Hadamard型MDS矩陣研究［J］. 艦船電子工程， 2014（5）：41-45. LIU L H， XU L J， ZHANG Z P， et al. Investigate for MDS matrix of hadamard type on finite fields［J］. Ship Electronic Engineering，2014（5）：41-45.

［34］崔霆， 金晨輝. 對(duì)合Cauchy-Hadamard型 MDS矩陣的構(gòu)造［J］.電子與信息學(xué)報(bào)， 2010， 32（2）：500-503. CUI T， JIN C H. Construction of involution cauchy-hadamard type MDS matrices［J］. Journal of Electronics & Information Technology，2010， 32（2）： 500-503.

［35］GUPTA K C， RAY I G. On constructions of involutory MDS matrices［C］//International Conference on Cryptology in Africa. c2013：43-60.

［36］NAKAHARA J R， éLcio A. A new involutory mds matrix for the AES［J］. Network Security， 2009，9（2）：109-116.

［37］DEHNAVI S M， SHAMSABAD M R M， RISHAKANI A M， et al. Efficient MDS diffusion layers through decomposition of matrices［M］// IACR Cryptology. ePrint Archive， 2015.

［38］SIM S M， KHOO K， OGGIER F， et al. Lightweight MDS Involution Matrices［C］//FSE 2015. c2015.

［39］LIU M， SIM S M. Lightweight MDS generalized circulant matrices［C］//Fast Software Encryption. c2016.

［40］LI Y， WANG M. On the construction of lightweight circulant involutory MDS matrices［C］//Fast Software Encryption. c2016.

［41］崔霆， 金晨輝. 分組密碼 Cauchy 型 MDS 擴(kuò)散結(jié)構(gòu)的幾點(diǎn)注記［J］. 電子學(xué)報(bào)， 2011， 39（7）： 1603-1607. CUI T， JIN C H. Several remarks of Cauchy type MDS diffusion layer for block cipher［J］. Acta Electronica Sinica， 2011， 39（7）：1603-1607.

［42］CUI T， JIN C， KONG Z. On compact cauchy matrices for substitution-permutation networks［J］. IEEE Transactions on Computers，2015， 64（7）： 2098-2102.

［43］馬慶祿， 魏悅川， 潘曉中. 基于 Cauchy 矩陣的線性變換的研究［J］. 計(jì)算機(jī)應(yīng)用研究， 2015， 32（7）： 2144-2146. MA Q L， WEI Y C， PAN X Z. Research on linear transformations based on Cauchy matrix［J］. Application Research of Computers，2015， 32（7）， 2144-2146.

［44］LACAN J， FIMES J. Systematic MDS erasure codes based on vandermonde matrices［J］. IEEE Communications Letters， 2004，8（9）： 570-572.

［45］無(wú)線局域網(wǎng)產(chǎn)品中使用的SMS4算法［EB/OL］. http：//www.oscca. gov.cn/UpFile/200621016423197990.pdf. SMS4 algorithm used in wireless LAN products［EB/OL］. http：//www.oscca.gov.cn/UpFile/200621016423197990.pdf.

［46］ETSI/SAGE TS 35.222-2011， specification of the 3GPP confidentiality and integrity algorithms 128-EEA3 & 128-EIA3； document 2：ZUC Specification［S］.

［47］HONG D， SUNG J， HONG S， et al. HIGHT： a new block cipher suitable for low-resource device［M］//Cryptographic Hardware and Embedded Systems-CHES 2006. Berlin Heidelberg： Springer， 2006：46-59.

［48］National institute of standards and technology［S］. The Secure Hash Standard， 2002.

［49］RIVEST R L， AGRE B， BAILEY D V， et al. The MD6 hash function［J］. Invited Talk at CRYPTO， 2008.

［50］ZHANG W， WU W， FENG D， et al. Some new observations on the SMS4 block cipher in the Chinese WAPI standard［M］//Information Security Practice and Experience. Berlin Heidelberg： Springer，2009： 324-335.

［51］王金波. 基于循環(huán)移位構(gòu)造最優(yōu)線性變換［C］. 中國(guó)密碼學(xué)會(huì)2007年會(huì)，成都. c2007：306-307. WANG J B. The optimal permutation in cryptography based on cyclic-shift linear transform［C］//China Crypt'2007，Chengdu. c2007： 306-307.

［52］李瑞林， 熊海， 李超. 基于循環(huán)移位和異或運(yùn)算的對(duì)合線性變換研究［J］. 國(guó)防科技大學(xué)學(xué)報(bào)， 2012， 34（2）： 46-50. LI R， XIONG H， LI C. Research on involutional linear transformations based on rotation and XOR［J］. Journal of National University of Defense Technology， 2012， 34（2）： 46-50.

［53］ANDREEVA E， BILGIN B， BOGDANOV A， et al. PRIMATEs v1.02 submission to the CAESAR competition［EB/OL］. http：// competitions.cr.yp.to/round2/primatesv102.pdf.

［54］SAJADIEH M， DAKHILALIAN M， MALA H， et al. Recursive diffusion layers for block ciphers and Hash functions［C］// FSE 2012. c2012：385-401.

［55］WU S， WANG M， WU W.Recursive diffusion layers for （lightweight）block ciphers and Hash functions［C］//SAC 2012. c2012： 355-371.

［56］AUGOT D， FINIASZ M. Exhaustive search for small dimension recursive MDS diffusion layers for block ciphers and hash functions［C］// 2013 IEEE International Symposium on Information Theory （ISIT）. c2013：1551-1555.

［57］BERGER T P. Construction of recursive MDS diffusion layers from gabidulin codes［C］//Indocrypt. c2013：274-285.

［58］KHOO K， PEYRIN T， POSCHMANN A， et al. FOAM： searching for hardware optimal spn structures and components with a fair comparison［C］//Cryptographic Hardware and Embedded Systems （CHES）. c2014： 433-450.

［59］劉鴻博， 金曉剛， 段俊紅. 分組密碼中 MDS矩陣的實(shí)現(xiàn)方法效能分析［J］. 信息安全與通信保密，2013（10）：77-78. LIU H B， JIN X G， DUAN J H. Efficiency analysis of MDS matrix applied in block cipher［J］. Information Security and Communications Privacy， 2013（10）：77-78.

Construction of MDS matrices

LI Peng-fei1，2， LI Yong-qiang1

（1. The State Key Lab of Information Security， Institute of Information Engineering， Chinese Academy of Sciences， Beijing 100093， China；2. University of Chinese Academy of Sciences， Beijing 100049， China）

A survey for MDS matrices design strategy was made. Design strategies and the key issues during the design were elaborated， and many aspects such as principle and implementation mechanisms of some typical and common construction of MDS matrices were analyzed and discussed. In addition， the research results on lightweight MDS matrices in recent years were investigated.

block cipher， optimal diffusion layer， branch number， MDS matrix， linear transformation

1　引言

隨著信息技術(shù)的快速發(fā)展，互聯(lián)網(wǎng)已經(jīng)融入人們生活的方方面面，然而，人們?cè)谙硎芑ヂ?lián)網(wǎng)帶來(lái)便利的同時(shí)，信息安全問(wèn)題也越來(lái)越突出?，F(xiàn)代密碼學(xué)作為信息安全的核心和關(guān)鍵技術(shù)，在保護(hù)數(shù)據(jù)安全和用戶隱私上發(fā)揮著巨大的作用。分組密碼因其加、解密速度快，便于軟硬件實(shí)現(xiàn)和易于標(biāo)準(zhǔn)化等特點(diǎn)，受到廣泛關(guān)注且成為密碼學(xué)研究的熱點(diǎn)課題。分組密碼在對(duì)大批量數(shù)據(jù)加密的應(yīng)用中扮演著舉足輕重的作用，它們以硬件、軟件等不同的實(shí)現(xiàn)方式廣泛應(yīng)用在個(gè)人通信、電子支付、數(shù)據(jù)庫(kù)加密等諸多領(lǐng)域。早在1949年，香農(nóng)（Shannon）在他的《保密系統(tǒng)的通信理論》中就提到密碼系統(tǒng)設(shè)計(jì)的2種基本方法：混淆和擴(kuò)散［1］，這是現(xiàn)今密碼算法設(shè)計(jì)和分析的基礎(chǔ)。現(xiàn)在廣泛使用的分組密碼算法通常采用迭代型結(jié)構(gòu)，迭代型是指所有輪（除第一輪和最后一輪外）均采用相同輪變換。迭代型分組密碼設(shè)計(jì)中最重要的2個(gè)基本部件是混淆層（confusion layer）和擴(kuò)散層（diffusion layer）?；煜龑油ǔＪ褂梅蔷€性的幾個(gè)并置S盒來(lái)構(gòu)造，擴(kuò)散層由線性的變換函數(shù)構(gòu)成。擴(kuò)散層作為迭代型分組密碼的一個(gè)很重要的部件，它的設(shè)計(jì)不但影響分組密碼算法的安全性，而且影響分組密碼在軟硬件中的實(shí)現(xiàn)效率。性能良好的擴(kuò)散層可以有效地抵抗一些著名的密碼攻擊，如差分密碼分析［2］和線性密碼分析［3］。擴(kuò)散層的安全性能主要由Daemen提出來(lái)的分支數(shù)［4］概念來(lái)衡量，擴(kuò)散層的分支數(shù)越小，分組密碼越容易遭受差分分析、線性分析以及一些未知分析方法的攻擊；反之，分支數(shù)越大，擴(kuò)散層的擴(kuò)散效果越好，安全性越好。在實(shí)際設(shè)計(jì)中，最受矚目的是那些分支數(shù)達(dá)到最大時(shí)的擴(kuò)散層，簡(jiǎn)稱最優(yōu)擴(kuò)散層，所對(duì)應(yīng)的矩陣稱為 MDS（maximum distance separable）矩陣。MDS矩陣首次被使用在分組密碼SHARK［5］的設(shè)計(jì)中，隨后，越來(lái)越多的分組密碼算法將 MDS矩陣用于擴(kuò)散層的設(shè)計(jì)中，如Rijndael［4］、Twofish［6，7］、Square［8］、Anubis［9］、Khazad［10］、FOX［11］、CLEFIA［12］、LED［13］等。流密碼算法也使用 MDS矩陣作為擴(kuò)散層，如MUGI［14］。另外，散列函數(shù)，如 Maelstrom［15］、Gr?stl［16］、Whirlpool［17］和PHOTON輕量級(jí)散列函數(shù)族［18］等都將MDS矩陣作為擴(kuò)散層使用。

The National Natural Science Foundation of China （No.61379142， No.61303255）

TP393

A

10.11959/j.issn.2096-109x.2016.00063

2016-04-27；

2016-05-30。通信作者：李鵬飛，lipengfei@iie.ac.cn

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61379142， No.61303255）

李鵬飛（1991-），男，陜西渭南人，中國(guó)科學(xué)院信息工程研究所碩士生，主要研究方向?yàn)槊艽a學(xué)。

李永強(qiáng)（1982-），男，吉林集安人，博士，中國(guó)科學(xué)院信息工程研究所副研究員，主要研究方向?yàn)閷?duì)稱密碼算法關(guān)鍵部件的構(gòu)造、對(duì)稱密碼算法分析。