MDS矩陣構造方法

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

網絡與信息安全學報 2016年6期

李鵬飛，李永強

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

MDS矩陣構造方法

李鵬飛1，2，李永強1

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

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

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

2　基本概念

2.1分支數

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

圖1　混淆層和擴散層結構

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

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

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

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

其中，MT為矩陣M的轉置。

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

1）擴散層矩陣M的線性分支數等于轉置矩陣MT的差分分支數。2）擴散層的分支數等于其逆變換的分支數。3）擴散層差分分支數達到最大，當且僅當其線性分支數也達到最大。

定義4分支數達到最大的擴散層稱為最優擴散層，所對應的矩陣稱為MDS矩陣。

2.2線性碼

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

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

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

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

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

下面介紹幾個重要定理。

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

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

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

2.3構造MDS的相關矩陣

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

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

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

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

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

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

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

其行列式為

3　利用線性碼構造MDS矩陣

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

3.1 分支數與線性碼的關系

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

由此，將線性碼和擴散層聯系起來，結合差分分支數的定義 2，可以進一步得到擴散層差分分支數與線性碼的關系。

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

得到了擴散層和線性碼之間的關系，即可利用線性碼來構造MDS矩陣。

3.2 構造MDS矩陣的方法

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

4　利用隨機檢測矩陣來構造MDS矩陣

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

4.1 循環矩陣

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

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

其結果兩兩不等。

則循環矩陣D為MDS矩陣，即線性變換θ（x）分支數達到最大5。

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

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

4.2 Hadamard矩陣

由Hadamard矩陣的定義12可知，與循環矩陣類似，Hadamard矩陣的每一行均是第一行的置換，因此節省了軟硬件實現開銷，采用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），它也是作用在有限域上。關于Hadamard矩陣，有如下性質和定理［33，34］。

4.3對合矩陣和正交矩陣

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

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

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

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

5　利用數學方法構造MDS矩陣

Cauchy矩陣和Vandermonde矩陣由于具有數學上的特性，通常被用來構造大階MDS矩陣。

5.1利用Cauchy矩陣構造MDS矩陣

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

5.2利用Vandermonde矩陣構造MDS矩陣

根據Vandermonde矩陣的定義14，結合式（11）可知，當互不相同且不為0時，該類型矩陣的任意子式非零，由定理5可知，可以使用Vandermonde矩陣來構造MDS矩陣。

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

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

6　利用移位和異或構造MDS矩陣

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

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

7　利用LFSR構造迭代型最優擴散層

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

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

圖2　PHOTON中最優擴散層設計方式

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

狀態轉移矩陣（也稱為相伴矩陣）A的具體形式如下。

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

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

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

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

8　MDS矩陣的實現方法

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

9　結束語

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

［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］楊譜. 分組迭代密碼函數的擴散層分析及應用［D］. 西安：西安電子科技大學， 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］. 杭州：杭州電子科技大學， 2011. HE L Y. Research on the improvement of block cipher diffusion layer［D］. Hangzhou： Hangzhou Dianzi University， 2011.

［32］郭艷珍，韓文報，趙龍，等. AES列混合變換［J］. 解放軍理工大學學報（自然科學版）， 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矩陣的構造［J］.電子與信息學報， 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 擴散結構的幾點注記［J］. 電子學報， 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］. 計算機應用研究， 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］無線局域網產品中使用的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］王金波. 基于循環移位構造最優線性變換［C］. 中國密碼學會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］李瑞林，熊海，李超. 基于循環移位和異或運算的對合線性變換研究［J］. 國防科技大學學報， 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矩陣的實現方法效能分析［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　引言

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

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