一類輕量化線性MDS變換的設計與分析*

董新鋒，董新科，胡建勇

0 引 言

擴散部件的設計是密碼算法設計的重要組成部分。目前，擴散部件主要有MDS矩陣、基于循環移位和異或運算的線性MDS變換、比特置換和二元矩陣等。擴散部件設計的好壞直接影響密碼算法的安全性和效率[1-3]。采用差分分支數和線性分支數較大的擴散部件，可以使密碼算法更好地抵抗差分攻擊和線性攻擊。采用結構簡單的擴散部件，有利于密碼算法的快速實現。線性MDS變換的差分分支數和線性分支數相等且達到最大[4]，故利用線性MDS變換設計分組密碼的擴散部件是一種常用的方法。線性MDS變換作為擴散部件被廣泛應用于密碼算法設計中，如AES算法、Twofish算法、SMS4算法、AIRA算法、HIEROCRYPT算法等。為了保證密碼算法的快速有效實現，線性MDS變換對應的MDS矩陣應具有較少的元素和較小的數值。例如，AES算法使用有限域GF(28)上的MDS矩陣為循環移位矩陣；Twofish算法使用GF(28)上的MDS矩陣為Hadamard矩陣；AIRA算法使用GF(2)上的0/1矩陣為對合矩陣，等等。如何設計有限域GF(2n)上快速實現MDS矩陣，一直是人們關心的重要問題，具有較好的理論基礎和豐富的研究成果。例如，文獻[5-7]等提出可以基于循環移位矩陣、Cauchy矩陣以及Hadamard矩陣等特殊矩陣來設計MDS矩陣的思想和構造方法，并搜索出大量便于實現的MDS矩陣。但是，由于有限域GF(2n)上的乘法運算較為復雜，導致有限域上的MDS矩陣無法滿足移動互聯網、物聯網中諸多資源受限應用場景下的密碼算法擴散部件的設計要求。此外，文獻[8-14]研究了通常情形下MDS矩陣的構造方法，文獻[15-19]研究了輕量級MDS變換的構造方法。

本文將基于循環移位和異或運算，提出一種新的輕量化的線性MDS變換的構造方法，給出該類線性MDS變換的計數結果和相應實例，能夠為算法設計提供大量輕量化的線性MDS變換。通過與公開算法中擴散部件的比較分析，說明本文提出的最簡形式線性MDS變換具有時延低、運算快、計算資源小等輕量化特性，可以滿足移動互聯網、物聯網中諸多資源受限應用場景下的擴散部件的設計要求。

1 準備知識

本文用⊕表示逐位模2加，用+表示實數加或實數模2m加。對于y=(y1, y2,…, ym)∈GF(2n)m，本文均用W(y)表示y=(y1, y2,…, ym)中非0元的個數。

對于GF(2n)上m×m矩陣A定義的線性變換f(x)=Ax，其差分分支數達到最大值m+1等價于其線性分支數達到最大值m+1。當它的差分分支數達到最大值時，則稱A為MDS矩陣。

下面介紹線性變換的差分分支數Bd和線性分支數Bl的定義。

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

其中矩陣At為矩陣A的轉置矩陣。此處用+表示實數加。

定義 2：設A=(aij)2m×2m是GF(2n)上的 2m×2m矩陣，如果當0≤i, j≤2m-1時，均有aij=a0(i+j)，則稱A為有限域上的一個循環（Cyclic）移位矩陣，簡記為A=Cyc(a00,a01,…,a0(2m-1))。此處，用+表示實數模2m加。

2 基于循環移位和異或運算的線性MDS變換

基于循環移位、異或等簡單邏輯運算設計的線性MDS變換，具有結構簡單、運算快速、計算資源消耗低等輕量化特征，特別適用于移動互聯網、物聯網等應用場景下的輕量級密碼算法設計。通常情形下，衡量一個密碼算法部件的資源占用情況，可以通過基本運算數目的多少來大致刻畫。本文的主要目標是尋找具有最少異或數、最少循環移位數和最優分支數等輕量化特征的最簡形式MDS變換的設計方法。

目前，主流的密碼算法設計中采用的MDS變換擴散部件主要有兩類：一類是有限域GF(2n)上分支數為5的4階或8階矩陣變換（一般地，n=4、8、16、32等）；另一類是GF(2)上分支數為4、5或8的0/1矩陣變換（對應的矩陣階數分別為4階、8階或16階）。考慮到密碼部件在算法設計等實際應用中的普適性，以下章節均以GF(2)16→GF(2)16的線性MDS變換為例來闡述相關結果，但本文的構造方法及思路適用于設計任意的GF(2n)m→GF(2n)m上的線性MDS變換。

2.1 最簡形式1與構造方法1

由線性MDS碼的相關結論易知，GF(2)16→GF(2)16的線性變換其比特分支數最優為8。因此，若要使基于循環移位和異或等邏輯運算構造的線性變換L(X)：GF(2)16→GF(2)16為比特分支數為8的MDS變換，則L(X)的表達式中應至少包含7個單項式（即包含6個循環移位和6個異或運算）。此外，考慮到L(X)與L(X＜＜＜i)具有相同的分支數，則對L(X)變換整體做循環移位不會影響其MDS變換的性質，稱L(X)與L(X＜＜＜i)為兩個等價線性MDS變換。

定義具有如下形式的L(X)為GF(2)16→GF(2)16的基于循環移位和異或等邏輯運算構造的線性MDS變換的最簡形式1。

設L(X)是GF(2)16→GF(2)16的線性變換，如果L(X)具有如下形式：

其中Xij(X＜＜＜ij)，且L(X)為MDS變換（即L(X)的分支數達到8），則稱L(X)為GF(2)16→GF(2)16具有最簡形式1的線性MDS變換。

具有最簡形式1的L(X)包含6個循環移位和6個異或運算。其中，6個循環移位運算可以并行計算，具有時延低、運算快、計算資源小等特性，滿足諸多輕量化密碼算法擴散部件的設計需求。

構造方法1：設L(X)是GF(2)16→GF(2)16的線性變換，且具有如下形式（其中i0、i2、…、i5均為1～15之間互不相同的非零整數）：

其中 Xij(X＜＜＜ij)。

X通過遍歷GF(2)16的216-1個16比特值（全0除外），i0、i2、…、i5（互不相同）通過分別遍歷1～15的15個整數值，計算min{W(X)+W(L(X))|X∈GF(2)16{0}}并判斷取值是否等于8，即可得到GF(2)16→GF(2)16的所有具有最簡形式1的線性MDS變換。

若采用構造方法1，需要遍歷的搜索量為(216-，約為228.3。其中為15選6的組合數。

性質1：設L(X)是通過構造方法1得到的GF(2)16→GF(2)16的線性MDS變換，形如式（4），定義Ln(X)為GF(2n)16→GF(2n)16的線性變換，且具有下面的形式：

其中Ln(X)。

那么Ln(X)為GF(2n)16→GF(2n)16的線性MDS變換，即驗證Ln(X)的等價形式Ln(X)=M·X，其中M為16階0/1矩陣，M的分支數達到最大值8。

2.2 最簡形式2與構造方法2

在密碼算法的某些資源受限應用場景下，可以考慮犧牲擴散部件運算的并行性，使得擴散部件占用的資源最少。這種情形下需要通過級聯迭代等形式設計擴散部件。下面的構造方法2給出了一種適用于這種資源受限應用場景的GF(2)16→GF(2)16的線性MDS變換設計方法，僅包含4個循環移位和4個異或運算。

設L'(X)是GF(2)16→GF(2)16的線性變換，如果L'(X)具有如下形式：

且L'(X)為MDS變換，即L'(X)的分支數達到8，則稱L'(X)為GF(2)16→GF(2)16具有最簡形式2的MDS變換。

具有最簡形式2的L'(X)僅包含4個循環移位和4個異或運算，相對最簡形式1具有更低的時延和更小的計算資源占用，但4個循環移位和4個異或運算只能依次串行計算。

構造方法2：設L'(X)是GF(2)16→GF(2)16上的線性變換，且通過如下形式得到（其中a、c、d均為1～15之間互不相同的非零整數，b為1～15之間的非零整數）：

X通過遍歷GF(2)16的216-1個16比特值（全0除外），a、c、d（互不相同）通過分別遍歷1～15的15個整數值，b通過遍歷1～15的15個整數值，計算min{W(X)+W(L'(X))|X∈GF(2)16{0}}，并判斷取值是否等于8，即可獲得GF(2)16→GF(2)16上的所有具有最簡形式2的MDS變換。

若采用構造方法2，需要遍歷的搜索量為(216-1)××15，約為 228.8。其中為 15選 3的組合數。性質2：設L'(X)是通過構造方法2得到的GF(2)16→GF(2)16的線性MDS變換，形如式（9）、式（10）、式（11），定義Ln'(X)為GF(2n)16→GF(2n)16上的線性變換，且具有下面的形式：

那么Ln'(X)為GF(2n)16→GF(2n)16的線性MDS變換，即驗證Ln'(X)的等價形式為Ln'(X)=M·X，其中M為16階0/1矩陣，M的分支數達到最大值8。

2.3 最簡形式1與最簡形式2之間的關系

對最簡形式2中的L'(X)展開、化簡、合并后，得到如下形式（注：此處“+”為模16加）：

其中 Xi＜＜＜i。

說明最簡形式2得到的MDS變換也具有最簡形式1的形式，即通過最簡形式2得到的MDS變換為通過最簡形式1得到的MDS變換的子集。

在有些特殊場景下，可能會對密碼算法的擴散部件MDS變換提出更多要求，如要求GF(2n)16→GF(2n)16上的線性MDS變換同時滿足上述的最簡形式1或最簡形式2，此外還滿足為GF(24n)4→GF(24n)4上的線性MDS變換，即要求L''(X)滿足以下三點：

（1）作為GF(2n)16→GF(2n)16的線性變換，同時滿足最簡形式1或最簡形式2；

（2）作為GF(2n)16→GF(2n)16的線性變換，其分支數達到最優為8，即為MDS變換；

（3）作為GF(24n)4→GF(24n)4的線性變換，其分支數達到最優為5，即為MDS變換。

將滿足上述三點性質的L''(X)稱為具有特殊形式的MDS變換。

在本文的第3部分，將說明滿足上述最簡形式的線性MDS變換L(X)、L'(X)、L''(X)的存在性、計數結果等。

3 實例與分析

根據第2部分的構造方法1、構造方法2，通過編程計算，可以得到具有最簡形式1、最簡形式2和特殊形式的輕量化線性MDS變換的計數結果，如表1所示，并給出了1個構造實例。

表1 輕量化線性MDS變換的計數結果

構造實例1：

通過構造方法1可以得到如下的L(X)：

通過構造方法2可以得到如下的L'(X)：

更進一步，通過測試發現L(X)滿足以下性質：

（1）作為GF(2)16→GF(2)16的線性變換，其分支數為8，達到最優，即為MDS變換L''(X)；

（2）作為GF(24n)4→GF(24n)4的線性變換，其分支數為5，達到最優，即為MDS變換L''(X)；

表明L(X)同時滿足最簡形式1和特殊形式，在實際密碼算法設計中具有非常明顯的實現優勢。通過計算機搜索沒有發現同時滿足最簡形式2和特殊形式的L'(X)。

線性MDS變換L(X)對應的0/1矩陣M為：

AIRA算法和HIEROCRYPT算法均為128 bit分組長度的分組密碼算法，分別使用了1個16階0/1矩陣M0和M1，分支數均達到最優為8。

AIRA算法中使用的16階0/1矩陣M0為：

HIEROCRYPT算法中使用的16階0/1矩陣M1為式（22）。

通過分析比較容易發現：M與M1相比具有更少的1（M中含有112個1，M1中含有176個1），即M所包含的比特異或數更少，消耗的計算資源更少；M與M0相比具有相同數量的1（均含有112個1），即M與M0包含的比特異或數相同，但由于M是循環矩陣，所以在實現上具有更多的優勢和靈活性。

綜上所述，本文設計的這類具有最簡形式的MDS變換，具有更優良的密碼性能和更靈活的實現方式，在諸多資源受限應用場景下的密碼算法擴散部件設計中具有極大優勢。事實上，還存在其他最簡形式的MDS變換，研究方法類似。

4 結 語

本文研究了線性MDS變換的構造方法，在此基礎上構造了一類新的輕量化的循環移位線性MDS變換，并給出了該類MDS變換的計數和構造實例。本文的研究結果為循環移位MDS變換的構造方法提供了一種新的途徑，豐富了密碼算法擴散部件的選擇，對密碼算法的設計具有實際的應用價值。值得一提的是，這類線性MDS變換構造方法簡單，能夠快速有效實現。

[1] Schneier B,Kelsey J,Whiting D,et al.Twofish:A 128-bit Block Cipher[EB/OL].(2007-02-02)[2017-11-22].http://www.schneier.com/.

[2] WANG Mei-qin.Differential Cryptanalysis of Present[EB/OL].(2008-01-09)[2017-11-22].https://eprint.iacr.org/2007/408.

[3] WU Wen-ling,ZHANG Wen-tao,FENG Deng-guo.Impossible Differential Cryptanalysis of Reduce Round ARIA and Camellia[J].Journal of Computer Science and Technology,2007,22(03):449-456.

[4] KANG Ju-sung,Hong S,Lee S,et al.Practical and Provable Security Against Differential and Linear Cryptanalysis for Substitution-permutation Networks[J].ETRI Journal,2001,23(04):158-167.

[5] 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 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,1997:40-48.

[7] Blomer J,Kalfane M,Karpinski M,et al.An Xor-based Erasure-resilient Coding Scheme[EB/OL].(1999-10-12)[2017-11-22].https://www.researchgate.net/publication/2643899.

[8] 崔霆,金晨輝.對合Cauchy-Hadamard型MDS矩陣的構造[J].電子與信息學報,2010,32(02):500-503.CUI Ting,JIN Chen-hui.Construction of Cauchy Cauchy-Hadamard MDS Matrix[J].Journal of Electronics &Information Technology,2010,32(02):500-503.

[9] Malik M Y,No J S.Dynamic MDS Matrices for Substantial Cryptographic Strength[EB/OL].(2011-04-05)[2017-11-22].http://eprint.iacr.org/2011/177.

[10]Gupta K C,Ray I G.On Constructions of MDS Matrices from Companion Matrices for Lightweight Cryptography[EB/OL].(2013-02-04)[2017-11-22].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[EB/OL].(2014-12-09)[2017-11-22].http://eprint.iacr.org/2014/011.

[12] Souvik K,Debdeep M.Lightweight Diffusion Layer from the k^th root of the MDS Matrix[EB/OL].(2014-06-22)[2017-11-22].http://eprint.iacr.org/2014/498.

[13] Siang M S,Khoongming K.Lightweight MDS Involution Matrices[EB/OL].(2015-05-19)[2017-11-22].http://eprint.iacr.org/2015/258.

[14] ZHAO Ruo-xin,ZHANG Rui,LI Yong-qiang,et al.On Constructions of a Sort of MDS Block Diffusion Matrices for Block Ciphers and Hash Functions[EB/OL].(2015-05-11)[2017-11-22].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[EB/OL].(2016-04-29)[2017-11-22].http://eprint.iacr.org/2016/422.

[16] Sumanta S,Habeeb S.Lightweight Diffusion Layer Importance of Toeplitz Matrices[EB/OL].(2016-09-30)[2017-11-22].http://eprint.iacr.org/2016/835.

[17] Sumanta S,Habeeb S.Analysis of Toeplitz MDS Matrices[EB/OL].(2017-04-23)[2017-11-22].http://eprint.iacr.org/2017/368.

[18] Sumanta S,Habeeb S.Bounds on the Differential Branch Number of Permutations[EB/OL].(2017-10-08)[2017-11-22].http://eprint.iacr.org/2017/990.

[19] Sumanta S,Habeeb S,Rajat S,et al.Lightweight Design Choices for LED-like Block Ciphers[EB/OL].(2017-10-18)[2017-11-22].http://eprint.iacr.org/2017/1031.