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

2016-09-23 06:22:12李鵬飛李永強

網(wǎng)絡(luò)與信息安全學(xué)報 2016年6期

李鵬飛，李永強

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

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

李鵬飛1，2，李永強1

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

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

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

2　基本概念

2.1分支數(shù)

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

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

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

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

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

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

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

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

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

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

2.2線性碼

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

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

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

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

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

下面介紹幾個重要定理。

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

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

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

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

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

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

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

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

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

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

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

其行列式為

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

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

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

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

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

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

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

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

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

4　利用隨機檢測矩陣來構(gòu)造MDS矩陣

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

4.1 循環(huán)矩陣

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

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

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

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

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

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

4.2 Hadamard矩陣

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

4.3對合矩陣和正交矩陣

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

9　結(jié)束語

MDS矩陣廣泛應(yīng)用于分組密碼算法、Hash函數(shù)、認證加密算法，使用 MDS矩陣作為擴散層，可以保證分支數(shù)達到最大，從而可以最大限度地保證密碼算法在差分和線性分析下的安全性。本文比較系統(tǒng)地闡述了常見的構(gòu)造 MDS矩陣的方法：從線性碼中提取 MDS矩陣；采用隨機檢測矩陣構(gòu)造特殊MDS矩陣，如循環(huán)MDS矩陣、Hadamard MDS矩陣、對合MDS矩陣和正交MDS矩陣；使用數(shù)學(xué)上具有特殊性質(zhì)的矩陣，如Cauchy矩陣和Vandermonde矩陣構(gòu)造MDS矩陣。本文基于移位和異或構(gòu)造高效的 MDS矩陣和利用 LFSR構(gòu)造硬件實現(xiàn)友好的迭代型最優(yōu)擴散層，介紹了構(gòu)造 MDS矩陣的原理，并詳細給出了各種方法的研究現(xiàn)狀以及其中的優(yōu)缺點，最后，給出了 MDS矩陣的實現(xiàn)方法，設(shè)計者可以根據(jù)應(yīng)用場景的不同選用不同的實現(xià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ù)的擴散層分析及應(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］何凌云. 分組密碼擴散層的改進研究［D］. 杭州：杭州電子科技大學(xué)， 2011. HE L Y. Research on the improvement of block cipher diffusion layer［D］. Hangzhou： Hangzhou Dianzi University， 2011.

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

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

TP393

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

2016-04-27；

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

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