楊璐，蒲桃英，蒲鳳，蔡志丹

（長(zhǎng)春理工大學(xué) 理學(xué)院，長(zhǎng)春 130022）

一類十六階的MDS循環(huán)矩陣最小異或數(shù)的構(gòu)造

楊璐，蒲桃英，蒲鳳，蔡志丹

（長(zhǎng)春理工大學(xué) 理學(xué)院，長(zhǎng)春 130022）

MDS矩陣在密碼學(xué)中具有分支數(shù)大、擴(kuò)散性好及安全性高等優(yōu)點(diǎn)，并且MDS矩陣的異或數(shù)越小，實(shí)用性越強(qiáng)。以十六階二元MDS循環(huán)矩陣為例，為得到異或數(shù)最小的矩陣，首先，根據(jù)循環(huán)矩陣構(gòu)造MDS矩陣的充分條件，構(gòu)造出四階二元循環(huán)MDS矩陣；再由矩陣分塊原理，將矩陣的元素?cái)U(kuò)展到四階矩陣；最后構(gòu)造出若干異或數(shù)最小的十六階二元MDS循環(huán)矩陣，并給出其中一個(gè)異或數(shù)最小的最優(yōu)矩陣的具體形式。

MDS矩陣；異或數(shù)；循環(huán)矩陣；大數(shù)據(jù)處理

在實(shí)際應(yīng)用中，分組密碼需要在不同軟硬件平臺(tái)中高效實(shí)現(xiàn)，它的實(shí)現(xiàn)性能直接影響整個(gè)分組密碼的高效性能。其中，MDS矩陣在分組密碼的設(shè)計(jì)中地位尤為重要。

構(gòu)造MDS矩陣的方法多種多樣，但大多數(shù)構(gòu)造MDS矩陣的方法都有著對(duì)軟硬件的系統(tǒng)資源開(kāi)銷大、密碼算法速度慢等缺點(diǎn)。而循環(huán)矩陣是一類具有特殊結(jié)構(gòu)的矩陣，它不僅是應(yīng)用非常廣泛的一類矩陣，而且在構(gòu)造MDS矩陣的過(guò)程中能夠有效地克服上述缺點(diǎn)。此外，MDS矩陣的異或數(shù)越小，在分組密碼的應(yīng)用中擴(kuò)散性能越好，安全性越高，軟硬件實(shí)現(xiàn)性能就越好。于是，選擇在循環(huán)矩陣的基礎(chǔ)上構(gòu)造異或數(shù)最小的MDS矩陣。

1 基本定義及引理

定義1設(shè)A為一個(gè)m階二元矩陣，其異或數(shù)定義為直接計(jì)算

所需要的異或運(yùn)算次數(shù)。記A的異或數(shù)為#A，則有

定義2［1］只包含有限個(gè)元素的域，稱為有限域，記為GF(p)。

定 義 3［2，3］設(shè)則稱x1,…xm中非零元的個(gè)數(shù)為的漢明重量，簡(jiǎn)稱為重量，記為ω(x)。

引理 1［5，6］設(shè)c0，c1，c2，c3為有限域GF(28)上可逆多項(xiàng)式的系數(shù)：

c(x)對(duì)應(yīng)線性變換φ(x)=Bx。其中，B為4階循環(huán)矩陣

如果c0，c1，c2，c3滿足以下條件：

（1）c0=c1，且c0，c2，c3互不相等且不為零。

（2）c0，c2，c3任意兩個(gè)數(shù)的不等于第三個(gè)數(shù)的平方。即

（3）c0，c2，c3分別與(c0⊕c2)2，(c0⊕c3)2相乘，其結(jié)果兩兩不等。

則循環(huán)矩陣B為MDS矩陣。

定義4［7，8］數(shù)域P上的階矩陣A可以寫成m階分塊矩陣u,v=0,1,…,m-1，且有：

其中，Ai為n×n矩陣，則A成為準(zhǔn)循環(huán)矩陣。

2 MDS矩陣的構(gòu)造及異或數(shù)的求解

令引理1形成的循環(huán)矩陣B為：

其中，c0為一個(gè)四階二元矩陣的行列式的值，同理c1，c2，c3也分別為一個(gè)四階二元矩陣的行列式的值。通過(guò)計(jì)算，得到所有四階二元矩陣的行列式的取值為{-3，-2，-1，0，1，2，3}。由引理1，舍去行列式值為零的情況，即c0，c1，c2，c3的取值范圍是{-3，-2，-1，1，2，3}。

為了找到異或數(shù)最小的矩陣，利用遍歷算法得到四階二元矩陣行列式的值為±3,±2,±1時(shí)，矩陣的最小異或數(shù)，如表1：

表1 行列式值為±3,±2,±1的四階二元矩陣最小異或數(shù)

由上表可知，四階二元矩陣行列式值為±3時(shí)最小異或數(shù)為5。如果循環(huán)矩陣每一行至少有一個(gè)行列式的值為±3的四階二元矩陣時(shí)，得到的矩陣異或數(shù)將會(huì)變得很大。因此，將行列式取值為±3的情況舍去，即c0，c1，c2，c3最終的取值范圍是{-2，-1，1，2}。

為了找到滿足引理1中循環(huán)矩陣構(gòu)造MDS矩陣的條件，并且取值在{-2，-1，1，2}范圍內(nèi)的c0，c1，c2，c3組合，我們利用Eclipse設(shè)計(jì)了一個(gè)滿足上述條件的函數(shù)，現(xiàn)將滿足條件的c0，c1，c2，c3的組合和它們分別對(duì)應(yīng)的異或數(shù)總和結(jié)果整理如下：

表2 滿足條件的c0，c1，c2，c3的組合及對(duì)應(yīng)的異或數(shù)總和

表3 c0，c1，c2，c3對(duì)應(yīng)的十六階二元循環(huán)矩陣異或數(shù)統(tǒng)計(jì)

由引理1知，以表2中c0，c1，c2，c3作為元素的循環(huán)矩陣即為MDS矩陣。

為找到異或數(shù)最小的十六階二元MDS矩陣，首先從行列式值為-2，-1，1，2的矩陣中篩選出滿足表1異或數(shù)最小的四階二元方陣。其次，在篩選出的方陣中再次篩選出滿足引理1的四階二元方陣，舉例如下：

行列式值為-2：

行列式值為1：

將上述矩陣按照循環(huán)矩陣元素的排列順序，構(gòu)造出二十組十六階二元MDS矩陣，其矩陣異或數(shù)如表3。

由表3可知，十六階二元循環(huán)MDS矩陣的最小的異或數(shù)為12。得到對(duì)應(yīng)的矩陣L。

3 結(jié)論

十六階二元循環(huán)MDS矩陣L為：

其異或數(shù)為12，即十六階二元循環(huán)MDS矩陣最小異或數(shù)為12。

［1］楊子胥.近世代數(shù)（第三版）［M］.北京：高等教育出版社，2011：3-5.

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

［3］郭磊，鄭浩然，傅增強(qiáng)，等.MDS矩陣和對(duì)合MDS矩陣的新構(gòu)造方法［J］.計(jì)算機(jī)應(yīng)用研究，2014，31（1）：222-225.

［4］李鵬飛，李永強(qiáng).MDS矩陣構(gòu)建方法［J］.網(wǎng)絡(luò)與信息安全學(xué)報(bào)，2016，2（6）：45-52.

［5］Rao AR，Bhimasankaram P.Linear algebra：second edition［M］.Hindustan Book Agency，2000.

［6］何凌云.分組密碼擴(kuò)散層的改進(jìn)研究［D］.杭州：杭州電子科技大學(xué)，2011.

［7］李天增，王瑜.循環(huán)矩陣的性質(zhì)及求逆方法［J］，四川理工學(xué)院學(xué)報(bào)（自然科學(xué)版），2009，22（4）：47-49+55.

［8］齊登記.準(zhǔn)循環(huán)矩陣的行列式［J］.河南教育學(xué)院學(xué)報(bào)：自然科學(xué)報(bào)，2004，13（4）：9-10.

The Construction of Minimum Xor Number of Sixteen Order MDS Circulant Matrices

YANG Lu，PU Taoying，PU Feng，CAI Zhidan
（School of Science，Changchun University of Science and Technology，Changchun 130022）

MDS matrix has many advantages in cryptography，such as large branch number，good diffusion and high security.And the xor number of MDS matrix becomes more smaller，the practicability becomes more stronger.Taking the sixteen order of two element MDS circulant matrices as an example，in order to get the minimum number of XOR matrix，firstly，according to the sufficient conditions for constructing MDS matrix based on cyclic matrices，we constructed four order of two element MDS circulant matrices；Because of the principle of block matrix，the element in MDS circulant matrices can be extended to four order matrix；finally we constructed some the sixteen order of two element MDS circulant matrices with the minimum xor number，and gave the specific form of the optimal matrix which xor number is minimized.

MDS matrix；xor number；circulant matrices；bulk data handling

O153

A

1672-9870（2017）04-0112-03

2017-05-05

國(guó)家自然科學(xué)基金（11601039）

楊璐（1996-），女，本科，E-mail：501164176@qq.com

蔡志丹（1979-），女，副教授，E-mail：1261046008@qq.