董新锋，董新科，胡建勇

0 引 言

扩散部件的设计是密码算法设计的重要组成部分。目前，扩散部件主要有MDS矩阵、基于循环移位和异或运算的线性MDS变换、比特置换和二元矩阵等。扩散部件设计的好坏直接影响密码算法的安全性和效率[1-3]。采用差分分支数和线性分支数较大的扩散部件，可以使密码算法更好地抵抗差分攻击和线性攻击。采用结构简单的扩散部件，有利于密码算法的快速实现。线性MDS变换的差分分支数和线性分支数相等且达到最大[4]，故利用线性MDS变换设计分组密码的扩散部件是一种常用的方法。线性MDS变换作为扩散部件被广泛应用于密码算法设计中，如AES算法、Twofish算法、SMS4算法、AIRA算法、HIEROCRYPT算法等。为了保证密码算法的快速有效实现，线性MDS变换对应的MDS矩阵应具有较少的元素和较小的数值。例如，AES算法使用有限域GF(28)上的MDS矩阵为循环移位矩阵；Twofish算法使用GF(28)上的MDS矩阵为Hadamard矩阵；AIRA算法使用GF(2)上的0/1矩阵为对合矩阵，等等。如何设计有限域GF(2n)上快速实现MDS矩阵，一直是人们关心的重要问题，具有较好的理论基础和丰富的研究成果。例如，文献[5-7]等提出可以基于循环移位矩阵、Cauchy矩阵以及Hadamard矩阵等特殊矩阵来设计MDS矩阵的思想和构造方法，并搜索出大量便于实现的MDS矩阵。但是，由于有限域GF(2n)上的乘法运算较为复杂，导致有限域上的MDS矩阵无法满足移动互联网、物联网中诸多资源受限应用场景下的密码算法扩散部件的设计要求。此外，文献[8-14]研究了通常情形下MDS矩阵的构造方法，文献[15-19]研究了轻量级MDS变换的构造方法。……