ABSTRACT

MDS Matrix has important applications in cryptography and it can be used to construct block ciphers. The number of XOR of a MDS Matrix is an important index to measure the validity of cipher algorithm. In this paper, we study the properties of MDS matrix and consider the ideas of cycle, block matrix and so on. The MDS matrix is constructed for several special properties, including cyclic MDS matrix, Hadamard MDS matrix and iterative MDS matrix etc. When the number m = 4, 8, we use the program to search the MDS matrix that satisfies the condition. The number of MDS matrix with the minimum number of XOR and examples are given and we get many MDS matrices with the minimum number of XOR; when m = 4, we have given the circulating MDS Matrix with the number of XOR with 12, when m = 8 we have given the best MDS Matrix with the number of XOR with 10.

Keywords:MDS Matrix, Linear Diffusion Layer, Cyclic Matrix, Hadamard Matrix, Number of XOR

轻量级MDS矩阵的构造

周敏¹，顾执²

¹西华大学数学研究所，四川 成都

²西南交通大学数学学院，四川 成都

收稿日期：2018年4月11日；录用日期：2018年4月21日；发布日期：2018年4月28日

摘 要

MDS矩阵在密码学中有重要的应用，可以用来构造分组密码。MDS矩阵的异或数是衡量密码算法的有效性的一个重要指标。本文研究MDS矩阵的性质，考虑循环、矩阵分块和迭代等思想，分别针对几类特殊性质的MDS矩阵构造，包括循环MDS矩阵、Hadar MDS矩阵和迭代MDS矩阵等。在m = 4, 8情况下，使用程序来搜索满足条件的MDS矩阵，给出了具有最小异或数的MDS矩阵的数目和例子，得到m = 4, 8情况下许多具有已知最小异或数的MDS矩阵，得到了m = 4时具有异或数12的循环MDS矩阵，也构造了m = 8时具有异或数10的最佳MDS矩阵。

关键词 :MDS矩阵，线性扩散层，循环矩阵，Hadamard矩阵，异或数

Copyright © 2018 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 绪论

1.1. 引言

混乱原则和扩散原则是保证分组密码安全性的重要原则，线性扩散层是分组对称密码算法的重要组成部分，其扩散特性是通过特定的内部结构来实现的。扩散结构的设计十分重要，直接关系到分组密码的安全性能和实现性能 [1] 。在轻量级加密过程中，通过有限的资源环境保证信息安全，线性扩散层发挥着重要作用。

分支数是分组密码设计中的一个重要组成成分，可以根据分支数的大小从理论上给出差分和线性攻击的抵抗界限。线性扩散层是一个线性变换，可以通过一个n阶矩阵表示，若这个n阶矩阵的最大分支数是n + 1，则这个扩散层就称为完美扩散层。MDS矩阵的分支数达到最大，在分组密码的扩散结构中得到广泛应用，比如Advanced Encryption Standard (AES) [2] 、Shark [3] 以及Twofish [4] 和Khazad [5] 分组密码算法等。此外，为了保证解密结构和加密结构的一致性，通常采用对合MDS矩阵，因此，如何构造良好性质的对合MDS矩阵成为了研究的目标。

构造MDS矩阵的方法通常利用有限域及MDS码。为提高运算效率，通常考虑有限域上具有较少非零元素的矩阵。循环矩阵以及Hadamard矩阵是主要选取的对象，AES扩散层就是使用此类矩阵。为了适用于轻量密码算法，目前主要使用递归扩散层构造最优扩散层，具体是首先构造一个简单的矩阵，然后该矩阵复合若干次(通常大于等于矩阵的阶数)，得到MDS矩阵。在轻量级的Hash函数设计中，比如PHOTON，以及分组密码LED [6] ，均是通过此类MDS矩阵构造。利用上述想法并用具有较少异或操作的线性变换替换有限域上的乘法，实现效率得以提高。如何构造轻量级MDS矩阵，既能减少矩阵乘法运算中出现的困难又能避免迭代构造出现的问题，是进一步需要研究的问题。

本文考虑m = 4, 8时具有小异或数的MDS矩阵，首先给出了MDS矩阵异或数的性质，然后使用直接搜索满足性质的特殊循环MDS矩阵，并分析MDS矩阵的异或数最小值和数目，为了改进MDS矩阵的构造方法和效率，使用循环、分块和迭代等思想，来考虑特殊MDS矩阵，并分析这些MDS矩阵的异或数最小值和数目。

本文的主要结构是：第二节给出了一些基本概念和MDS矩阵性质；第三节使用循环、分块和迭代等思想，给出几种特殊类型MDS矩阵的构造，并分析这些MDS矩阵的最小异或数和数目。

1.2. 预备知识

记为一个有个元素的有限域，当m = 1时，值为0或1，可以看成上的m维线性空间，记为上的m维线性空间。一个矩阵成为二元矩阵，若矩阵的每个元素都在有限域中，即每个元素都是0或1。

一个映射L被称为是线性的，若，其中。确定上的一个基，上的线性映射可以用的二元矩阵L表示，即，其中为一个列向量。

记为所有的的非奇异二元矩阵的集合，其中。取一个二元矩阵

其中为中一个二元矩阵。定义L的一个t阶子方阵为，其中，是两个长度为t的序列，并且，。二元矩阵L称为MDS矩阵，若L的任意阶数为t的子方阵都是满秩矩阵。

对任意的二元矩阵L，记L的异或数为，其中，m为L的阶数，为L的第i行中1的个数。对任意的，通过提取L中每一行不为零元素的位置而将L的简化形式给出，例如矩阵[[1,3], 2, 3, [1,4]]表示如下矩阵

线性扩散层是一个线性变换，每一个线性变换都可以用一个m阶矩阵表示。所以每一个线性扩散层都可以有一个m阶矩阵表示，众所周知，m阶矩阵的最大分支数是m + 1。具有最大分支数的线性扩散层是一个完美扩散层或者是一个MDS矩阵。

一个矩阵被称为循环矩阵，若这个矩阵每一行的最后一个分块被旋转到下一行的最左边。四阶循环矩阵如下

,

其中

一个的矩阵被称为Hadamard矩阵，若它具有如下形式

,

其中是两个的Hadamard矩阵。四阶Hadamard矩阵如下

其中。

文献 [7] 给出了循环MDS矩阵和Hadamard MDS矩阵的一个下界，提出一种利用非对合矩阵，建构出异或数较小的MDS矩阵，主要的思想是对构造的非对合MDS矩阵，通过不同矩阵的性质的研究，借助搜索，得到最终异或数最小的MDS矩阵。

2. 构造轻量级MDS矩阵

本节主要使用循环、分块和迭代等思想，在m = 4, 8情况下，考虑特殊二元MDS矩阵的构造，分别考虑循环MDS矩阵、Hadmard MDS矩阵、最佳MDS矩阵和迭代MDS矩阵的构造，分析这些矩阵的性质，使用程序搜索具有最小异或数的MDS矩阵，并给出了矩阵对应的最小异或数以及这些矩阵的数目，得到了m = 4时具有异或数12的循环MDS矩阵(2.1节)，也构造了m = 8时具有异或数10的最佳MDS矩阵(2.4节)。

2.1. 轻量级循环MDS矩阵的构造

对于循环型矩阵

若是MDS矩阵，则都必须是可逆矩阵。4阶可逆矩阵有20,160个，而8阶可逆矩阵超过了2⁶²个。需要构造轻量级MDS矩阵，直观看应该包含异或数为0的矩阵(置换矩阵)，特别地，我们可将中某些矩阵取为单位阵。因此，首先考虑如下矩阵：

其中I为单位矩阵。首先给出如下基本引理(证明由高等代数基本知识可得证)。

引理1：假设均是二元域上的m阶满秩矩阵，则有下述结论：

1)是满秩矩阵当且仅当为满秩矩阵。

2)是满秩矩阵当且仅当为满秩矩阵。

3)是满秩矩阵当且仅当为满秩矩阵。

4)是满秩矩阵当且仅当为满秩矩阵。

对于型矩阵，若L为MDS矩阵，则必定有以下几个矩阵均为满秩矩阵：

下面针对m = 4和m = 8，分别讨论MDS矩阵。

2.1.1. 4阶矩阵环上的循环型MDS矩阵

考虑在上的所有满秩矩阵，令集合

为了满足MDS矩阵的相关条件，记集合

记满足上述条件的有序矩阵对，其中

令

最后依照MDS矩阵的定义，依次验证，其中

使用程序4总共搜索到156,387个这种形式的MDS矩阵，其中异或总数最低的MDS矩阵共有48个，其异或数为12。并且，经过验证，A、B满足关系：

或。

例1：

例2：

2.1.2. 8阶矩阵环上的循环型MDS矩阵

当m = 8时，若依照m = 4的程序搜索方法，面临搜索数据量极大的问题。为缩小搜索范围，考虑特殊情形下的这类MDS矩阵，分别在两种具体情形下讨论。

1) 基于低异或数子类搜索：

利用分块构造矩阵的思想，具体考虑这样形式的集合：

考虑mzjz2中的矩阵A的限定条件：

a) 取，

即

考虑所有此类有序矩阵对，其中，再通过MDS矩阵的定义，使用程序5依次验证，其中，最终得到2690个这种形式的MDS矩阵，其中MDS阵的一行异或数最低为7，且能够取得17个这样的MDS矩阵。

例3：

b) 取，即

考虑所有此类有序矩阵对，其中，再通过MDS矩阵的定义，使用类似程序5的程序依次验证：，其中最终得到200,072个这种类型的MDS矩阵，其中异或总数最低的MDS矩阵共有12个，其中MDS阵的一行异或数最低为22。

例4：

c) 矩阵A满足

即：

考虑所有此类有序矩阵对，其中，再通过MDS矩阵的定义，依次验证，其中，最终得到1444个这种形式的MDS矩阵，并且每一个MDS矩阵一行的异或数均为4。

例5：

m = 8时，基于低异或数构造的循环MDS矩阵总结如表1。

2) 基于4阶情形的启发式搜索：

通过对4阶循环MDS矩阵的分析，我们知道形如这样的异或数最低的MDS矩阵满足关系或。为此，考虑如下形式8阶矩阵环上的循环型MDS矩阵：

表1. 循环MDS矩阵

为了得到低异或数的矩阵，我们只搜索了A是异或数等于1的满秩矩阵的情况：记所有八阶异或数为零的满秩矩阵集合为：

将矩阵中的零元素依次用1进行替换，得到一个新矩阵，记此变换后的全体矩阵集合为，集合中所有矩阵的异或数均为1，即：

满足条件的矩阵可从选取。现检验如下矩阵是否为MDS矩阵：

，其中

使用程序6检验，共96,093个MDS矩阵，其中矩阵异或总数最小为12，共80,640个矩阵满足异或数最小。

例6：

下面给出一些二元矩阵的性质。

引理2 [7] ：已知，，如果L的秩为2m，则。

证明：假设，。则的每一行每一列都有一个元素为1其中。所以L是非奇异的，即，矛盾。证毕。

定理1：1) 若是一个循环的MDS矩阵，其中，则；2) 若是一个Hadamard MDS矩阵，其中，则。

证明：1) 设是一个循环的MDS矩阵。

若，则在第一行中至少含有三个异或数为0，不妨假设，有，因L是一个MDS矩阵，所以这与假设矛盾。其他情况同样可以被证明。

若，则对某一行至少有两个元素异或数为零，其余两个元素异或数之和为2。

当m = 4时：

a) 不妨设。采用如下搜索策略：当m = 4时，首先得到一个包含所有异或数为1的满秩矩阵的集合One以及包含所有异或数为0的满秩矩阵的集合，然后对每一个数组，带入检验是否为MDS矩阵，通过运行程序1，并未检测到任何满足条件的矩阵；

b) 不妨设，记异或数为零的矩阵集合为，则

,

显见L存在一个子方阵，

，此时的L一定不是MDS矩阵。

当m = 8时，同理可证，详见附件程序2。

由矩阵的初等行列变换知，交换上述A B C D的位置不会影响的MDS性，故该证明具有一般性。

综上可得，满足

2)是一个Hadamard MDS矩阵。

若，则在第一行中至少含有两个异或数为0，不失普遍性，这里假设，据引理2，有，因L是一个MDS矩阵，所以这与假设矛盾。其他情况同样可以被证明。

若，则对某一行至少有一个元素异或数为零，其余三个元素异或数之和为3。

当m = 4时：

1) 不妨设，采用如下搜索策略：首先可记一个包含所有异或数为1的满秩矩阵的集合One和包含所有异或数为0的满秩矩阵。然后对每一个数组，带入程序3的findMDS1.m检验是否为MDS矩阵的程序中，通过运行程序，并未检测到任何满足条件的矩阵。

2) 不妨假设，搜索策略如下：记一个包含所有异或数为1的矩阵的集合One，一个包含所有异或数为2的矩阵的集合Two。然后对每一个数组，带入程序3中的findMDS2.m检验是否为MDS矩阵的程序中，通过运行程序，并未检测到任何满足条件的矩阵。

3) 假设，，。

显见L存在一个子方阵，显然，所以此时的L一定不是MDS矩阵。

当m = 8时，同理可证。

由矩阵的初等行列变换知，交换上述A B C D的位置不会影响的MDS性，故该证明具有一般性。

综上，是一个MDS矩阵，则。证毕。

利用上述定理知4阶或8阶矩阵环上的循环型MDS矩阵异或数不小于12。前面构造说明异或数12是可以达到的，并已经取得。

2.2. 循环MDS矩阵的改进

此节继续考虑特殊分块矩阵，尝试构造类似循环矩阵的MDS矩阵，记循环矩阵为，考虑类似循环矩阵的矩阵：

，其中

对这类矩阵，期望得到异或数低于12的MDS矩阵。

对已知异或总数为12的循环MDS矩阵的分析，发现总是可以表示成或者其中的异或数为1，的异或数为2。现在对24对矩阵序对中异或数为2的矩阵进行替换，即将某一个替换为集合One中的元素。其中：

考虑。

很遗憾，使用程序7搜索并没有异或数小的MDS矩阵的出现。

2.3. 轻量级Hadamard型 MDS矩阵的构造

记为Hadamard循环矩阵：

要想为MDS矩阵，则至少要求下列矩阵是满秩矩阵：

通过分析，若是采用全局程序搜索，当m = 4和8时程序运算量太大，故不实际，由此需要对进行特殊处理。

当m = 4时考虑如下三种特殊Hadamad矩阵：

1) 令。要使得为MDS矩阵，则下列矩阵一定为满秩矩阵：

使用程序8来搜索满足条件的此类MDS矩阵，发现此类MDS矩阵不存在。

2) 令，即，其二阶子方阵中

存在。程序发现不存在此类MDS矩阵。

3) 令。若为MDS矩阵，则要求下列矩阵一定为满秩矩阵：

使用程序得到型的MDS矩阵共有7917个，其中矩阵一行的最低异或数为4，并且，给出了48组这样的矩阵对使得为MDS矩阵，且满足。

例7：

将这几种情形Hadamard矩阵总结如表2。

显见，此时得到的MDS矩阵异或总数并不是所有矩阵中最小的，与目标还有一定的距离。为此，考虑如何改进我们的矩阵，从而得到更优结果，还有待进一步的研究。

当m = 8时，考虑满足如下条件的Hadamard矩阵：

将中所有非单位元的元素均拆分为如下形式：

再次对矩阵A的异或数做限定，令集合

构造这样的，满足，使用类似程序搜索得到了形如的MDS矩阵有6693个，且矩阵异或总数最小为32，共有48个矩阵能够取得最小异或总数。

例8：

令集合，先取定。检验此时的是否为MDS矩阵，没有任何结果返回。这说明当时，根本不存在型MDS矩阵。由此有如下定理。

定理2：已知，如果矩阵是MDS矩阵，则一定有。

2.4. 最佳MDS矩阵的构造

文献 [8] 构造了一类MDS矩阵：

表2. Hadamard MDS矩阵

文献 [8] 中被称为最佳矩阵。基于这个思想，本小节研究如下矩阵：

要求L为MDS矩阵，则必有以下矩阵是满秩矩阵：

当m = 4时，考虑满足条件的，使用程序9得到共48878个最佳MDS矩阵，其中存在43组满足条件的矩阵对，使得最佳MDS矩阵的异或数达到最小为13，即，经观察，这些矩阵中的矩阵对均满足，其中。

例9：

当m = 8时，考虑中满足条件的，基于m = 4时得到的结论，为找到异或数较低的MDS矩阵，不妨尝试令，考虑二元域上所有异或数等于1的满秩矩阵，使用程序10，检验得到61,528个MDS矩阵，其中40320个异或数为10的最佳MDS矩阵。

例10：

2.5. 利用迭代寻找轻量级MDS矩阵

构造MDS矩阵可以利用有限域以及MDS码，除此以外，最常用的方法还有迭代法。迭代法的主要思想是通过利用较小分支数的扩散层重复作用，最终得到具有最大分支数的扩散层。实施此方法的第一步并不是构造一个MDS矩阵，这种新的设计策略在轻量级的哈希函数中被提出 [9] ，例如PHOTON算法，在LED轻量分组密码的设计中被大量应用 [10] 。典型的代表是利用线性反馈移位寄存器的构造。使用此方法，本小节中构造一些具有低异或数的MDS矩阵。

记LFSR MDS矩阵L具有如下形式：

表3. 轻量级MDS矩阵

其中。由矩阵L迭代生成MDS矩阵时，迭代次数不超过100次。为了减少程序搜索量，考虑矩阵中每一行的元素至多有两个不相关的变量。文献 [9] 考虑矩阵，其中，可通过合适的线性变换得到一个MDS矩阵。不妨就取定，其中

当时，考虑上的所有二元矩阵，然后将矩阵L带入进行运算，得到所有的矩阵(注意：此处假设迭代100次)。利用MDS矩阵的定义，使用程序11找出迭代后的所有MDS矩阵，总共得到18,882个MDS矩阵，其中具有最小异或数的矩阵有24个，这些矩阵的异或总数为42。此时的迭代次数d可以取到82。

例11：

此时通过该形式迭代得到的MDS矩阵异或数不是很理想。虽然在中我们并没有找到轻量级的MDS矩阵，但是通过修改生成元及其形式，有望得到异或数较小的MDS矩阵。使用以上的搜索策略，尝试了多种形式，均有MDS矩阵的返回，现将结果列于表3。

3. 总结

本文考虑具有小的异或数MDS矩阵的构造，使用循环、分块和迭代等思想来考虑MDS矩阵，分析MDS矩阵的性质，考虑特殊情况下的矩阵，分别对几种情况的特殊矩阵，在m = 4和8下，使用程序搜索，得到这些MDS矩阵的异或数最小的情况，并计数和给出相关例子。如何构造最小的异或数的MDS矩阵是一个有趣和实际应用的问题，需要进一步研究。

基金项目

本文得到四川省科技厅2015年第一批科技计划项目(基本科研-重点研发) (2015JY0245)、四川省教育厅自然科学重点项目(15ZA0135)，在此表示感谢！

文章引用

周 敏,顾 执. 轻量级MDS矩阵的构造
The Construction of Lightweight MDS Matrix[J]. 应用数学进展, 2018, 07(04): 429-445. https://doi.org/10.12677/AAM.2018.74054

参考文献