陳國源

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

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

陳國源

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

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

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

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

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

1 有限域中元素的表示

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

表1 有限域的元素表示

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

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

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

2.1 隨機生成互不相同的矩陣

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

表2 MDS矩陣的實驗個數(shù)統(tǒng)計

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

圖1 散點圖（要求生成互不相同的矩陣）

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

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

2.2 隨機生成可重復的矩陣

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

表3 MDS矩陣的實驗個數(shù)統(tǒng)計

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

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

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

圖2 散點圖（隨機生成的矩陣可重復）

2.3 結(jié)果與討論

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

圖3 擬合

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

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

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

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

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

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

3 結(jié)束語

本文研究了元素取自有限域F24的MDS矩陣的生成與檢驗，通過使用Matlab軟件進行試驗檢驗，統(tǒng)計滿足條件的四階MDS矩陣的個數(shù)，進而解決有限域F24上的四階MDS矩陣的計數(shù)問題. 本文是一個初步的探究，下一步研究可對統(tǒng)計概率的理論證明和算法的改進等，從而提高結(jié)果的穩(wě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矩陣的生成與應用[J]. 現(xiàn)代通信技術(shù)，2014(1)∶ 26-29.

[6] 李鵬飛，李永強. MDS矩陣的構(gòu)造方法[J]. 網(wǎng)絡與信息安全學報，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ù)學基礎[M]. 北京：人民郵電出版社，2007.

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

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

[12] 吳文玲，馮登國，張文濤. 分組密碼的設計與分析[M]. 2版. 北京：清華大學出版社，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.

[責任編輯：韋 韜]

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

陳國源（1992—），男，廣東珠海人，在讀碩士生，主要研究方向為應用數(shù)學（密碼學）