一种新的面向硬件轻量级near-MDS矩阵的构造算法  

New Hardware-oriented Lightweight Near-MDS Matrix Construction Algorithm

作　　者：张怡帆 任炯炯 陈少真[1,2] ZHANG Yi-Fan;REN Jiong-Jiong;CHEN Shao-Zhen(PLA Information Engineering University,Zhengzhou 450001,China;State Key Laboratory of Mathematical Engineering and Advanced Computing,Zhengzhou 450001,China)

机构地区：[1]解放军信息工程大学,郑州450001 [2]数学工程与先进计算国家重点实验室,郑州450001

出　　处：《密码学报》2019年第4期433-442,共10页Journal of Cryptologic Research

基　　金：信息保障技术重点实验室开放基金(KJ-17-002);国家密码发展基金(MMJJ20180203);数学工程与先进计算国家重点实验室开放基金(2018A03)~~

摘　　要：与maximal distance separable (MDS)矩阵相比, near-MDS矩阵更好地权衡了安全性和效率问题,因此在资源受限的环境下, near-MDS矩阵在面向硬件的轻量级密码算法设计中应用更广.而XORs(异或操作次数)的多少,刻画了硬件实现的效率.本文提出了一种新的面向硬件轻量级near-MDS矩阵的构造算法,研究如何获得XORs尽可能少的near-MDS矩阵.本文的关键之处在于将GL (m, F2), m=4, 8 (二元域上的m×m矩阵集, m代表S盒的比特数)中的矩阵作为扩散矩阵的元素来构造near-MDS矩阵,利用该方法构造出了较以往结果更多的异或操作次数最少的4×4循环对合near-MDS矩阵.本文利用特殊矩阵的性质给出循环对合形式的扩散矩阵其元素之间满足的条件引理,将其作为算法搜索的约束条件,可较大程度减少计算复杂度.结合near-MDS矩阵本身所具有的性质条件,借助Matlab软件对满足条件的矩阵进行搜索,在Windows 10系统、i5-6200U CPU处理器、4 G内存的机器条件下仅需要大概6分钟. m=4时,找到了48个满足XOR操作数最少的循环对合near-MDS矩阵,较以往最好结果10个更多.同时可以利"子域构造"方法给出m=8时达到最小XOR操作数的循环对合near-MDS矩阵.而且降低了搜索的时间复杂度.Compared with maximal distance separable(MDS) matrices, near-MDS matrices offer better tradeoff between security and efficiency, so it is more widely used in hardware-oriented lightweight cryptographic algorithm design under the resource-constrained environments. The number of XORs(XOR operations) describes the efficiency of the hardware implementation. This paper presents a new hardware-oriented lightweight near-MDS matrices construction algorithm, to construct the near-MDS matrices with as few XORs as possible. The key point of this paper is to construct near-MDS matrices by using the matrix in the GL(m, F2), m = 4, 8(m × m matrices set on the binary field, m represents the number of bits in the S box) as an element of the diffusion matrix, this method is used to construct a 4×4 cyclic involution near-MDS matrix with the least number of XOR operations compared with the previous results. This paper uses the properties of special matrices to give a conditional lemma among the elements of the diffusion matrix of the cyclic involution form, and use it as a constraint condition for the searching algorithm to reduce the computational complexity.Combining the properties of the near-MDS matrix itself, the Matlab software is used to search the matrix that satisfies the constrained condition. It takes about 6 minutes in a Windows 10 system,i5-6200 U CPU processor and 4 G memory. 48 cyclic involution near-MDS matrices are found that meet the conditions when m = 4, with 10 more best results than in the existing results. When m = 8,some cyclic involution near-MDS matrices that reach the lower bound of XORs are also given with the"subfield construction" method. And the time complexity of searching is decreased.

关 键 词：near-MDS矩阵 循环对合矩阵 XOR数 Matlab算法搜索 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]