陳國(guó)源

（廣州大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，廣東 廣州 510006）

有限域F24上的四階MDS矩陣的計(jì)數(shù)

陳國(guó)源

（廣州大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，廣東 廣州 510006）

本文主要研究了有限域F24上的四階MDS矩陣的計(jì)數(shù). 在有無(wú)限制生成的四階矩陣互不相同的情況下，回歸分析了矩陣個(gè)數(shù)與MDS矩陣平均個(gè)數(shù)的線(xiàn)性關(guān)系，發(fā)現(xiàn)兩種情況下，二者均呈良好的線(xiàn)性關(guān)系，但不作限制可以節(jié)省搜索時(shí)間，使算法的擴(kuò)散性能最佳.

有限域；MDS矩陣；計(jì)數(shù)

隨著互聯(lián)網(wǎng)的普及，信息安全問(wèn)題也越來(lái)越受關(guān)注，現(xiàn)代密碼技術(shù)是解決互聯(lián)網(wǎng)信息安全的重要技術(shù)之一. Shannon在《保密系統(tǒng)的通信理論》[1]中提出：設(shè)計(jì)現(xiàn)代密碼算法需要包含混淆層和擴(kuò)散層這兩個(gè)重要的部件. 其中，通常使用幾個(gè)并置的非線(xiàn)性S盒來(lái)構(gòu)造混淆層. 對(duì)于擴(kuò)散層，則一般利用線(xiàn)性映射實(shí)現(xiàn). 安全性能良好的擴(kuò)散層可有效抵抗密碼分析（如線(xiàn)性分析[2]和差分分析[3]等）.而MDS矩陣[4-6]的分支數(shù)最大，擴(kuò)散性能最佳，可以最大限度地保證在線(xiàn)性和差分分析下的安全性，也因此常被用作對(duì)稱(chēng)密碼中的線(xiàn)性擴(kuò)散層，如Rijndael[7]和Square[8]等. 有限域是一種特殊的域，只含有有限個(gè)元素，但在密碼學(xué)領(lǐng)域有著廣泛應(yīng)用. 其中MDS矩陣的生成與檢驗(yàn)就可以在有限域中進(jìn)行. 在有限域中進(jìn)行運(yùn)算前，要先對(duì)有限域中的元素進(jìn)行表示. 矩陣的生成就是利用表示后的有限域中的元素構(gòu)成的矩陣；而矩陣的檢驗(yàn)過(guò)程就相當(dāng)于在有限域中的運(yùn)算. 通過(guò)對(duì)生成的矩陣進(jìn)行檢驗(yàn)，滿(mǎn)足條件的矩陣就是MDS矩陣. 令MDS矩陣作為對(duì)稱(chēng)密碼中擴(kuò)散層的線(xiàn)性映射，算法的擴(kuò)散性能達(dá)到最佳.

本文通過(guò)有限域[9-10]構(gòu)造了四階MDS矩陣，給出其運(yùn)算法則；進(jìn)而研究四階MDS矩陣的計(jì)數(shù)問(wèn)題[11-12]，并進(jìn)行相應(yīng)的實(shí)驗(yàn)統(tǒng)計(jì)分析[13].

1 有限域中元素的表示

根據(jù)有限域的定義，有限域F2n中只含有2n個(gè)元素. 下面使用多項(xiàng)式表示有限域F24中的元素，F(xiàn)24是F2的4次擴(kuò)張，f(x)=1+x+x4∈F2[x]是不可約的，若α是F2上的15次本原單位根，則其有限域的元素表示如表1所示，而F24中元素的加法為普通的多項(xiàng)式加法，乘法為模f(x)的多項(xiàng)式乘法.

表1 有限域的元素表示

2 四階MDS矩陣的個(gè)數(shù)

定理1[14]若矩陣A是一個(gè)MDS矩陣，當(dāng)且僅當(dāng)矩陣A的所有子方陣都是可逆的，即矩陣A的所有子方陣的行列式均不等于零.

由于樣本空間比較大，故沒(méi)有窮搜有限域F24上的所有四階矩陣，而是采用隨機(jī)生成四階矩陣的方法，再對(duì)隨機(jī)生成的矩陣進(jìn)行檢驗(yàn)，若滿(mǎn)足定理1的矩陣就是所求矩陣，即MDS矩陣. 因元素取自有限域F24上的四階矩陣規(guī)模比較大，而且由于隨機(jī)生成的矩陣的隨機(jī)性，若只進(jìn)行一次測(cè)試，實(shí)驗(yàn)結(jié)果誤差會(huì)比較大，所以這里進(jìn)行了多次試驗(yàn)（這里取試驗(yàn)次數(shù)為T(mén)=5），再求平均MDS矩陣的個(gè)數(shù)的方法，以保證數(shù)據(jù)結(jié)果的穩(wěn)定性.

2.1 隨機(jī)生成互不相同的矩陣

本實(shí)驗(yàn)對(duì)生成的矩陣做了一個(gè)小限制——生成的四階矩陣互不相同，實(shí)驗(yàn)數(shù)據(jù)如表2所示.

表2 MDS矩陣的實(shí)驗(yàn)個(gè)數(shù)統(tǒng)計(jì)

觀(guān)察表2可以發(fā)現(xiàn)，當(dāng)生成1 000個(gè)矩陣時(shí)，其中約有5個(gè)為MDS矩陣；當(dāng)生成10 000個(gè)矩陣時(shí)，其中約有42個(gè)矩陣是MDS矩陣；當(dāng)生成100 000個(gè)矩陣時(shí)，其中約有453個(gè)矩陣是MDS矩陣. 通過(guò)表2還可以知道：當(dāng)隨機(jī)生成的矩陣個(gè)數(shù)遞增時(shí)，對(duì)應(yīng)的MDS個(gè)數(shù)也呈現(xiàn)遞增的趨勢(shì). 因此對(duì)隨機(jī)生成的矩陣個(gè)數(shù)和相應(yīng)得到的平均MDS矩陣個(gè)數(shù)在進(jìn)行散點(diǎn)分析. 選取隨機(jī)生成的矩陣個(gè)數(shù)為自變量x，MDS矩陣的平均個(gè)數(shù)為y.利用Matlab軟件作散點(diǎn)圖，如圖1所示.

圖1 散點(diǎn)圖（要求生成互不相同的矩陣）

由散點(diǎn)圖可以發(fā)現(xiàn)，數(shù)據(jù)點(diǎn)成條狀分布，隨機(jī)生成的矩陣個(gè)數(shù)和相應(yīng)得到的平均MDS矩陣個(gè)數(shù)有較好的線(xiàn)性相關(guān)關(guān)系，因此可以用回歸直線(xiàn)來(lái)近似刻畫(huà)它們之間的關(guān)系. 而通過(guò)Matlab軟件進(jìn)行擬合可以得到如下回歸直線(xiàn)：

通過(guò)計(jì)算，R2=0.999 0.R2反映了回歸模型擬合數(shù)據(jù)的效果，R2越接近1，殘差平方和越小，表示回歸的效果越好. 即該回歸直線(xiàn)能很好地描述隨機(jī)生成的矩陣個(gè)數(shù)和相應(yīng)得到的平均MDS矩陣個(gè)數(shù)之間的關(guān)系，故可以用得到的直線(xiàn)進(jìn)行預(yù)測(cè)估計(jì)元素取自有限域F24上的四階MDS矩陣的個(gè)數(shù).

2.2 隨機(jī)生成可重復(fù)的矩陣

當(dāng)隨機(jī)生成互不相同的矩陣的個(gè)數(shù)較大時(shí)，不管是生成過(guò)程，還是檢驗(yàn)過(guò)程，需要付出的時(shí)間代價(jià)都是非常大的. 為了減少這種代價(jià)，需要對(duì)檢驗(yàn)隨機(jī)生成互不相同的矩陣作進(jìn)一步的調(diào)整，以尋求在不犧牲時(shí)間為代價(jià)的前提下而獲得較為可靠的結(jié)果. 下面將不再要求生成的矩陣互不相同（即隨機(jī)生成的矩陣是可重復(fù)的）的情況進(jìn)行討論分析. 通過(guò)隨機(jī)搜索得到的相關(guān)數(shù)據(jù)如表3所示.

表3 MDS矩陣的實(shí)驗(yàn)個(gè)數(shù)統(tǒng)計(jì)

對(duì)隨機(jī)生成的矩陣個(gè)數(shù)和相應(yīng)得到的平均MDS矩陣個(gè)數(shù)在進(jìn)行散點(diǎn)分析. 選取隨機(jī)生成的矩陣個(gè)數(shù)為自變量x，MDS矩陣的平均個(gè)數(shù)為y. 利用Matlab軟件作散點(diǎn)圖，如圖2所示.

由散點(diǎn)圖可以發(fā)現(xiàn)，數(shù)據(jù)點(diǎn)成條狀分布，隨機(jī)生成可重復(fù)的矩陣個(gè)數(shù)和相應(yīng)得到的平均MDS矩陣個(gè)數(shù)也有較好的線(xiàn)性相關(guān)關(guān)系，因此也可以用回歸直線(xiàn)來(lái)近似刻畫(huà)它們之間的關(guān)系. 同理可得，隨機(jī)生成可重復(fù)的矩陣個(gè)數(shù)和相應(yīng)得到的平均MDS矩陣個(gè)數(shù)的回歸直線(xiàn)為：

同時(shí)也可以得到相應(yīng)的相關(guān)指數(shù)R2=0.9998. 這表明了該回歸直線(xiàn)能很好地描述隨機(jī)生成可重復(fù)的矩陣個(gè)數(shù)和相應(yīng)得到的平均MDS矩陣個(gè)數(shù)之間的關(guān)系.

圖2 散點(diǎn)圖（隨機(jī)生成的矩陣可重復(fù)）

2.3 結(jié)果與討論

由2.1和2.2的分析可以對(duì)上述情況進(jìn)行數(shù)據(jù)的擬合，擬合結(jié)果如圖3.

圖3 擬合

通過(guò)上文和圖3分析可得，隨機(jī)生成的矩陣互不相同或矩陣可重復(fù)出現(xiàn)得到的擬合直線(xiàn)的回歸系數(shù)相等，而回歸截距相差并不大. 隨著實(shí)驗(yàn)數(shù)據(jù)的不斷增加時(shí)，兩條回歸直線(xiàn)近似相等，故對(duì)MDS矩陣的統(tǒng)計(jì)個(gè)數(shù)的影響不大. 同時(shí)可以得到以下結(jié)論：

結(jié)論1設(shè)矩陣A是有限域F24上隨機(jī)生成的一個(gè)四階矩陣，則矩陣A為MDS矩陣的概率為

結(jié)論2在有限域F24上，四階的MDS矩陣個(gè)數(shù)約為0.044*264個(gè).

例1若隨機(jī)生成106個(gè)四階矩陣，則其中大約會(huì)有4 400個(gè)為MDS矩陣.通過(guò)試驗(yàn)檢測(cè)的數(shù)據(jù)如表4所示.

表4 隨機(jī)生成106個(gè)矩陣中的MDS矩陣的個(gè)數(shù)

由表4，隨機(jī)生成106個(gè)四階矩陣，可得到4 307個(gè)矩陣是MDS矩陣，與理論4 400個(gè)相差并不是很大，因此，可利用本文得到的理論概率去估計(jì)有限域F24上的四階MDS矩陣的個(gè)數(shù).

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

本文研究了元素取自有限域F24的MDS矩陣的生成與檢驗(yàn)，通過(guò)使用Matlab軟件進(jìn)行試驗(yàn)檢驗(yàn)，統(tǒng)計(jì)滿(mǎn)足條件的四階MDS矩陣的個(gè)數(shù)，進(jìn)而解決有限域F24上的四階MDS矩陣的計(jì)數(shù)問(wèn)題. 本文是一個(gè)初步的探究，下一步研究可對(duì)統(tǒng)計(jì)概率的理論證明和算法的改進(jìn)等，從而提高結(jié)果的穩(wěn)定性和提升運(yùn)行效率.

[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 [C]//Advances in Cryptology—EUROCRYPT’93.Berlin Heidelberg∶ Springer, 1993∶ 386-397.

[4] RIJMEN V, DAEMEN J. The cipher SHARK [C]//Proceedings of the Third International Workshop on Fast Software Encryption. London∶ Springer-Ver log, 1996∶ 99-112.

[5] 劉麗輝，裴燾，張祖平. MDS矩陣的生成與應(yīng)用[J]. 現(xiàn)代通信技術(shù)，2014(1)∶ 26-29.

[6] 李鵬飛，李永強(qiáng). MDS矩陣的構(gòu)造方法[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào)，2016, 2(6)∶ 44-53.

[7] DAEMEN J, RIJMEN V. The design of Rijndael∶ AES，the advanced encryption standard [M]. Berlin Heidelberg∶ Springer, 2002.

[8] DAEMEN J, KNUDSEN L R, RIJMEN V. The block cipher square [C]//Pooceedings of the 4th International Workshop on Fast Software Encryption. London∶ Springer-Verlag, 1997∶149-165.

[9] 裴定一，徐祥. 信息安全數(shù)學(xué)基礎(chǔ)[M]. 北京：人民郵電出版社，2007.

[10] 林東岱. 代數(shù)學(xué)基礎(chǔ)與有限域[M]. 北京∶高等教育出版社，2006.

[11] 周旋，張欣，瞿成勤. MDS矩陣的比特變換性質(zhì)及計(jì)數(shù)研究[J]. 計(jì)算機(jī)工程與科學(xué)，2010, 32(4)∶ 33-35.

[12] 吳文玲，馮登國(guó)，張文濤. 分組密碼的設(shè)計(jì)與分析[M]. 2版. 北京：清華大學(xué)出版社，2009.

[13] 劉東華，向良軍. 信道編碼與MATLAB仿真[M]. 北京：電子工業(yè)出版社，2014.

[14] MACWILLIANS F J, SLOANE N J A. The theory of error correction codes [M]. New York∶ North-Holland Publishing Company, 1977.

[責(zé)任編輯：韋 韜]

Enumeration of Fourth Order MDS Matrices over the Finite Fields ofF24

CHEN Guo-yuan
(School of Mathematics and Information Sciences, Guangzhou University, Guangzhou 510006, China)

The paper mainly researches the enumeration of fourth order MDS matrices overF24. For the different four-order matrices generated under restricted conditions, a regression analysis of the linear relationship between the number of matrices and average number of MDS matrices reveals that the two are in a benign linear relationship, but dispensing with restrictions can save the search time and optimize the diffusion performance of the algorithm.

finite fields; MDS matrices; counting

O156.2；TN918.1

A

1006-7302（2017）04-0011-05

2017-07-10

陳國(guó)源（1992—），男，廣東珠海人，在讀碩士生，主要研究方向?yàn)閼?yīng)用數(shù)學(xué)（密碼學(xué)）