董新鋒，董新科，胡建勇

0 引 言

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

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

1 準備知識

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

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

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

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

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

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

2 基于循環(huán)移位和異或運算的線性MDS變換

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

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

2.1 最簡形式1與構(gòu)造方法1

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

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

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

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

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

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

其中 Xij(X＜＜＜ij)。

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

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

性質(zhì)1：設L(X)是通過構(gòu)造方法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的分支數(shù)達到最大值8。

2.2 最簡形式2與構(gòu)造方法2

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

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

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

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

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

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

若采用構(gòu)造方法2，需要遍歷的搜索量為(216-1)××15，約為 228.8。其中為 15選 3的組合數(shù)。性質(zhì)2：設L'(X)是通過構(gòu)造方法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的分支數(shù)達到最大值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的線性變換，其分支數(shù)達到最優(yōu)為8，即為MDS變換；

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

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

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

3 實例與分析

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

表1 輕量化線性MDS變換的計數(shù)結(jié)果

構(gòu)造實例1：

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

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

更進一步，通過測試發(fā)現(xiàn)L(X)滿足以下性質(zhì)：

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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

[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矩陣的構(gòu)造[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.