一类十六阶的MDS循环矩阵最小异或数的构造

杨璐，蒲桃英，蒲凤，蔡志丹

（长春理工大学 理学院，长春 130022）

一类十六阶的MDS循环矩阵最小异或数的构造

杨璐，蒲桃英，蒲凤，蔡志丹

（长春理工大学 理学院，长春 130022）

MDS矩阵在密码学中具有分支数大、扩散性好及安全性高等优点，并且MDS矩阵的异或数越小，实用性越强。以十六阶二元MDS循环矩阵为例，为得到异或数最小的矩阵，首先，根据循环矩阵构造MDS矩阵的充分条件，构造出四阶二元循环MDS矩阵；再由矩阵分块原理，将矩阵的元素扩展到四阶矩阵；最后构造出若干异或数最小的十六阶二元MDS循环矩阵，并给出其中一个异或数最小的最优矩阵的具体形式。

MDS矩阵；异或数；循环矩阵；大数据处理

在实际应用中，分组密码需要在不同软硬件平台中高效实现，它的实现性能直接影响整个分组密码的高效性能。其中，MDS矩阵在分组密码的设计中地位尤为重要。

构造MDS矩阵的方法多种多样，但大多数构造MDS矩阵的方法都有着对软硬件的系统资源开销大、密码算法速度慢等缺点。而循环矩阵是一类具有特殊结构的矩阵，它不仅是应用非常广泛的一类矩阵，而且在构造MDS矩阵的过程中能够有效地克服上述缺点。此外，MDS矩阵的异或数越小，在分组密码的应用中扩散性能越好，安全性越高，软硬件实现性能就越好。于是，选择在循环矩阵的基础上构造异或数最小的MDS矩阵。

1 基本定义及引理

定义1设A为一个m阶二元矩阵，其异或数定义为直接计算

所需要的异或运算次数。记A的异或数为#A，则有

定义2［1］只包含有限个元素的域，称为有限域，记为GF(p)。

定 义 3［2，3］设则称x1,…xm中非零元的个数为的汉明重量，简称为重量，记为ω(x)。

引理 1［5，6］设c0，c1，c2，c3为有限域GF(28)上可逆多项式的系数：

c(x)对应线性变换φ(x)=Bx。其中，B为4阶循环矩阵

如果c0，c1，c2，c3满足以下条件：

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

（2）c0，c2，c3任意两个数的不等于第三个数的平方。即

（3）c0，c2，c3分别与(c0⊕c2)2，(c0⊕c3)2相乘，其结果两两不等。

则循环矩阵B为MDS矩阵。

定义4［7，8］数域P上的阶矩阵A可以写成m阶分块矩阵u,v=0,1,…,m-1，且有：

其中，Ai为n×n矩阵，则A成为准循环矩阵。

2 MDS矩阵的构造及异或数的求解

令引理1形成的循环矩阵B为：

其中，c0为一个四阶二元矩阵的行列式的值，同理c1，c2，c3也分别为一个四阶二元矩阵的行列式的值。通过计算，得到所有四阶二元矩阵的行列式的取值为{-3，-2，-1，0，1，2，3}。由引理1，舍去行列式值为零的情况，即c0，c1，c2，c3的取值范围是{-3，-2，-1，1，2，3}。

为了找到异或数最小的矩阵，利用遍历算法得到四阶二元矩阵行列式的值为±3,±2,±1时，矩阵的最小异或数，如表1：

表1 行列式值为±3,±2,±1的四阶二元矩阵最小异或数

由上表可知，四阶二元矩阵行列式值为±3时最小异或数为5。如果循环矩阵每一行至少有一个行列式的值为±3的四阶二元矩阵时，得到的矩阵异或数将会变得很大。因此，将行列式取值为±3的情况舍去，即c0，c1，c2，c3最终的取值范围是{-2，-1，1，2}。

为了找到满足引理1中循环矩阵构造MDS矩阵的条件，并且取值在{-2，-1，1，2}范围内的c0，c1，c2，c3组合，我们利用Eclipse设计了一个满足上述条件的函数，现将满足条件的c0，c1，c2，c3的组合和它们分别对应的异或数总和结果整理如下：

表2 满足条件的c0，c1，c2，c3的组合及对应的异或数总和

表3 c0，c1，c2，c3对应的十六阶二元循环矩阵异或数统计

由引理1知，以表2中c0，c1，c2，c3作为元素的循环矩阵即为MDS矩阵。

为找到异或数最小的十六阶二元MDS矩阵，首先从行列式值为-2，-1，1，2的矩阵中筛选出满足表1异或数最小的四阶二元方阵。其次，在筛选出的方阵中再次筛选出满足引理1的四阶二元方阵，举例如下：

行列式值为-2：

行列式值为1：

将上述矩阵按照循环矩阵元素的排列顺序，构造出二十组十六阶二元MDS矩阵，其矩阵异或数如表3。

由表3可知，十六阶二元循环MDS矩阵的最小的异或数为12。得到对应的矩阵L。

3 结论

十六阶二元循环MDS矩阵L为：

其异或数为12，即十六阶二元循环MDS矩阵最小异或数为12。

［1］杨子胥.近世代数（第三版）［M］.北京：高等教育出版社，2011：3-5.

［2］吴文玲，冯登国，张文涛.分组密码的设计与分析［M］.北京：清华大学出版社，2009：20-35.

［3］郭磊，郑浩然，傅增强，等.MDS矩阵和对合MDS矩阵的新构造方法［J］.计算机应用研究，2014，31（1）：222-225.

［4］李鹏飞，李永强.MDS矩阵构建方法［J］.网络与信息安全学报，2016，2（6）：45-52.

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

［6］何凌云.分组密码扩散层的改进研究［D］.杭州：杭州电子科技大学，2011.

［7］李天增，王瑜.循环矩阵的性质及求逆方法［J］，四川理工学院学报（自然科学版），2009，22（4）：47-49+55.

［8］齐登记.准循环矩阵的行列式［J］.河南教育学院学报：自然科学报，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

国家自然科学基金（11601039）

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

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