基于Rotation-XOR的MDS线性变换的研究

Research of MDS Linear Transformation Based on Rotation-XOR

在分组密码的扩散层中构造MDS线性变换可实现良好的扩散性.构造MDS线性变换的方法有很多种,其中基于Rotational-XOR的MDS线性变换软硬件实现效率高,能够增强密码算法抵抗各种密码分析的能力,适用于对称密码算法设计,例如SMS4算法、ZUC算法等.本文研究构造MDS线性变换的必要条件,探寻分组规模为64、分块规模为8时基于Rotational-XOR的MDS线性变换.首先通过分析首行矩阵的性质,给出MDS矩阵的一个必要条件为矩阵中不可能有连续三个矩阵块相同,根据该条件证明此规模下异或项数取最小值9项时不存在MDS线性变换,并利用Magma软件验证该结论.进而研究异或项数为11项时的MDS线性变换,将此情况下的所有线性变换分为三种情况,分别是一个矩阵中至多有一个自由项、存在两个自由项落在同一矩阵中和三个自由项恰好落在同一矩阵中.这三种情况将该规模下的8^8×56×55×54个线性变换等价划分为15种形式,设计15个算法分别搜索后得到此规模下异或项数取11项时也不存在MDS线性变换.本文的结论和搜索方法对研究分块规模为8的MDS扩散层具有启示作用.

In the diffusion layer of a block cipher,the construction of MDS linear transformation can achieve good diffusivity,and several kinds of methods can be used to achieve it.The MDS linear transformation based on Rotation-XOR is efficient to implement in hardware and software,it can enhance the resistance of a cryptographic algorithm against various cryptographic analyses,and it has been adopted by many symmetric cryptographic algorithms,such as SMS4 and ZUC.This paper studies the necessary conditions of constructing MDS linear transformations and constructs MDS linear transformations based on Rotation-XOR,where the group size is 64 and the block size is 8.By analyzing the first row of matrix,a necessary condition of MDS matrix is found to be that there does not exist three consecutive identical matrix blocks.Then it is proved that MDS linear transformations do not exist when the number of XOR terms is 9,which can be verified using Magma.Furthermore,the MDS linear transformations when the terms of XOR is 11 are studied.All such linear transformations are divided into three cases,including the cases when there is at most one free term in a matrix,there are two free terms falling in the same matrix and three free terms falling in the same matrix.In these three cases,8~8×56×55×54 linear transformations can be divided into 15 equivalent classes.For all these 15 classes,it was found by computation that MDS linear transformations do not exist when the number of XOR terms is 11.The conclusion and the search method in this paper are instructive to the study of MDS diffusion layer with block size of 8.