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

作者：张怡帆; 任炯炯; 陈少真^*

来源：密码学报, 2019, 6(04): 433-442.

DOI：10.13868/j.cnki.jcr.000312

• near-MDS矩阵
• 循环对合矩阵
• XOR数
• Matlab算法搜索

与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矩阵.而且降低了搜索的时间复杂度.

• 单位
  中国人民解放军信息工程大学