王 石, 李云青, 徐运阁, 曾祥勇

湖北大学数学与统计学学院应用数学湖北省重点实验室, 武汉 430062

1 引言

扩散和混淆是Shannon 提出的设计对称密码体制的两种基本方法[1], 其目的是为了抵抗攻击者对密码体制的统计分析. 扩散层可以通过线性扩散矩阵实现, 而矩阵的扩散能力通常由其分支数量化. 当分支数达到最大时, 将该矩阵称为MDS 矩阵. 由于MDS 矩阵具有最大的分支数可以有效的抵抗差分分析[2]和线性分析[3]. 因此, 1998 年Rijmen 等人首次将MDS 矩阵应用到Rijndael 算法中, 即高级加密标准(AES)[4]. 此后, MDS 矩阵被广泛的应用到线性层的设计中.

构造MDS 矩阵的方法主要有两种. 文献[5–7]中, 作者利用线性操作, 以字为单位直接构造具有高效实现电路的MDS 矩阵. 此外, 在特殊的子类中构造也是MDS 矩阵的常见构造方法, 如利用循环矩阵[8–11]和Hadamard 矩阵[12–14]. 文献[10]指出, 循环矩阵可以通过迭代的方式实现, 在资源受限的环境中能有效地提高硬件效率. 而Hadamard 矩阵不仅可以通过迭代的方式实现, 同时也容易构造具有对合性质的MDS 矩阵[6,11,15,16]. 因此, 在设计密码算法时, 研究者们经常会考虑使用Hadamard MDS 矩阵作为扩散层.

检验MDS 性质是构造MDS 矩阵的关键步骤之一. 文献[17]给出了MDS 矩阵的等价定义, 即一个矩阵为MDS 矩阵当且仅当其任意阶的子方阵满秩. 因此, 可以通过判断矩阵所有子方阵的行列式是否非零来确定MDS 性质. 高斯消元法是计算行列式最常用的方法, 利用高斯消元法计算一个n阶矩阵的行列式的复杂度为O(n3). 随着矩阵的阶数的增加, 计算单个子方阵的行列式的复杂度也会随之上升. 而文献[18]给出了一种新的MDS 矩阵的判别方法, 将一个矩阵所有子矩阵行列式的乘积分解为若干个不可约多项式, 不可约多项式的集合即为判别MDS 矩阵的条件集. 若集合中任意元素均可逆, 则可判定该矩阵为MDS 矩阵.

本文主要研究Hadamard MDS 矩阵的搜索方法. 首先给出了一种新的MDS 矩阵的判定方法称为链式判别法, 其主要思想是按阶数由低到高的顺序计算子方阵行列式, 将获得的k阶子方阵的行列式存放在一张表中, 在计算k+1 阶子方阵行列式时直接从存储表中调用k阶子方阵的行列式进行计算. 由此, 单个子方阵行列式的计算复杂度为O(n). 相比较之前的方法, 判定矩阵MDS 性质的速度有了很大提升. 其次, 对于4 阶Hadamard 矩阵M, 利用对称多项式基本定理, 证明出了M任意子方阵的行列式均可用初等对称多项式表示. 基于此, 给出了4 阶Hadamard MDS 矩阵的判定定理. 此外, 利用代数余子式, 本文给出了8 阶Hadamard MDS 矩阵的判定方法. 只需证明其i(i ≤4) 阶子方阵均满秩即可判定该矩阵为MDS 矩阵. 利用上述判别方法, 搜索出了有限域F24和F26所有4 阶及8 阶的Hadamard MDS 矩阵,并且找到了有限域F2n(n ≤16) 上实现代价最低的Hadamard MDS 矩阵. 最后, 为了进一步提高搜索的效率, 本文建立了有限交换环上4 阶Hadamard 矩阵和有限域上8 阶Hadamard 矩阵之间的联系, 利用该联系可以快速过滤不满足MDS 性质的Hadamard 矩阵.

2 预备知识

本节主要介绍MDS 矩阵以及Hadamard 矩阵的相关概念. 首先给出本文中常用的符号, 见表1.

表1 符号说明Table 1 Notations

定义1[19]设M是一个m阶非奇异方阵,M的伴随矩阵定义为

根据该定理,M的行列式可由其m −1 阶子方阵的行列式计算得到. 下面介绍MDS 矩阵的概念.

定义2[4]M为MDS 矩阵当且仅当M的任意阶子方阵都是可逆的.

根据该定义, 若一个矩阵的所有子方阵行列式均不为0, 则该矩阵为MDS 矩阵.

定义3[10]设矩阵P是一个m阶方阵, 若P的每一行每一列都恰有一个1 且其余元素均为0, 则称P为置换矩阵.

命题1[10,11]设P1,P2是两个置换矩阵, 矩阵M是MDS 矩阵当且仅当P1MP2是MDS 矩阵.

置换矩阵仅改变矩阵行列的位置, 不改变子矩阵的可逆性. 因此, 将M与置换矩阵相乘不改变其MDS 性质.

定义4[15]若H为有限域F2n上的2s阶Hadamard 矩阵, 它可以由两个Hadamard 子方阵表示:

该矩阵可记作H=Had(a1,a2,··· ,a2s), 其中a1,a2,··· ,a2s为Hadamard 矩阵的首行元素.

关于Hadamard 矩阵, 有如下性质.

命题2[20]设H=Had(a1,a2,··· ,a2s) 为有限域F2n上的一个2s阶Hadamard 矩阵, 则

下面引入Hadamard 等价矩阵的概念.

定义5[10,14]设P1,P2是两个置换矩阵, 若矩阵M和P1MP2是两个Hadamard 矩阵, 则称P1MP2是M的Hadamard 等价矩阵, 记作M ∼H P1MP2.

命题3设P1,P2是两个置换矩阵,M是F2n上的m阶Hadamard 矩阵. 若M和P1MP2是Hadamard 等价矩阵, 则M和P1MP2有相同的i阶子方阵, 其中1≤i ≤m −1.

因此, 根据Hadamard 矩阵的首行元素的个数, 我们即可确定Hadamard 等价类的个数.

注1设S是一个由2s个非零元素构成的集合, 其中S={a1,a2,··· ,a2s}.

(1) 当2s=4 时, 根据命题4可知由集合S中的元素构成的Hadamard 矩阵仅有1 个等价类;

(2) 当2s=8 时, 根据命题4可知由集合S中的元素构成的Hadamard 矩阵可分为30 个等价类;

(3) 设S是由8 个非零元构成的集合,H为Hadamard 矩阵, 其中S={a1,a2,··· ,a8}且H=Had(a1,a2,··· ,a8). 对于集合S中任意三个元素ai1,ai2,ai3, 总存在一个Hadamard 矩阵H′=Had(ai1,ai2,··· ,αi8) 使得H ∼H H′, 其中{ai1,ai2,··· ,αi8}={a1,a2,··· ,a8}.

命题5[21]若A,B,C,D均为同阶方阵, 则

3 MDS 矩阵的链式判别法

由定义2可知, 判定MDS 矩阵时, 需要检验其所有子方阵是否满秩. 最常见的方法是利用高斯消元计算矩阵的行列式, 若所有子方阵行列式均不为0, 则该矩阵为MDS 矩阵. 然而, 随着矩阵阶数增大, 待计算的行列式的个数会急剧增加. 因此, 判定过程将更加耗时. 我们提出了一种更高效的判别方法, 根据定理1 中行列式的计算方法, 将低阶矩阵的行列式的值储存用于计算高阶矩阵的行列式, 实现资源的重复利用, 从而减小计算量.

3.1 建立链式表

设M为有限域F2n上的m阶方阵,表示M的一个k阶子方阵. 由定理1 知k阶矩阵的行列式可以通过k −1 阶行列式计算, 其中1≤k ≤m. 若k −1 阶行列式已知, 则k阶行列式的计算过程将被有效地简化. 因此, 我们按照阶数由低到高的顺序计算子方阵的行列式, 将阶数相同的子方阵行列式的值存储到同一表中, 并在后续计算阶数更大的矩阵时调用表中行列式的值.

令S(k,m)表示元素小于等于m的k维向量构成的集合, 其中向量元素按由小到大的顺序排列:

下面介绍建表过程:

注意, 我们研究的是特征为2 的有限域上MDS 矩阵的判定. 此时, 矩阵的代数余子式与余子式相同,故可直接代入低阶行列式的值计算阶数更大的行列式. 当特征不为2 时, 还需考虑行列式的符号.

下面我们给出一个例子具体说明如何通过建表来判断矩阵的MDS 性质.

例1M为有限域F24/(x4+x+1) 上的4 阶方阵,

其中1 表示为有限域上的单位元,α为多项式x4+x+1 的一个根. 由于M为4 阶方阵, 我们可以确定其2 阶和3 阶子方阵行(列) 指标的向量集合.

显然,M的1 阶子方阵均不为0. 下面建立2 阶行列式存储表T2. 首先令r=1,c=1 计算T2[1,1].由于f2(1)−1=[1,2], 对应行指标为[1,2] 列指标也为[1,2]. 因此,

利用上述方法遍历r,c(1≤r,c ≤6), 依次计算T3[r,c] 的值, 结果见图1.

图1 2 阶行列式存储表Figure 1 Storage table of 2-order determinants

利用上述方法遍历r,c(1≤r,c ≤4), 依次计算T3[r,c] 的值, 结果见图2.

图2 3 阶行列式存储表Figure 2 Storage table of 3-order determinants

最后, 利用表T3中3 阶行列式的值计算矩阵M的行列式.r3=f3([1,2,3])=1,c1=f3([1,2,3])=1,c2=f3([1,2,4])=2,c3=f3([1,3,4])=3,c4=f3([2,3,4])=4. 由定理1 可得

综上,M所有子方阵行列式均不为零, 故为MDS 矩阵.

3.2 MDS 矩阵的判定方法

由行列式储存表, 我们给出MDS 矩阵的链式判别法. 设矩阵M是一个m阶方阵, 首先判断M是否存在零元素. 若元素全为非零元, 则建立2 阶行列式存储表T2. 若T2中元素均不为0, 则利用表T2中的结果建立3 阶行列式存储表T3. 类似地, 依次由k −1 阶行列式存储表, 计算Tk, 直至求得m阶方阵行列式的值. 若在建表过程中存在某子方阵行列式为0, 则判定结束, 该矩阵不是MDS 矩阵. 具体过程见算法1.

算法1 MDS 矩阵的链式判别法Input: m×m 矩阵M.Output: 若返回值为1 则M 是MDS 矩阵, 否则不是MDS 矩阵.1 初始化: 集合S(k,m) 及对应函数fk, k 阶行列式存储表Tk ←0, k = 2,3,··· ,m;2 for 1 阶行列式Mij(1 ≤i,j ≤m) do return 0;5end 6 end 7 for 2 阶行列式1 ≤r,c ≤C2m do 3if 1 阶行列式Mij == 0 then 4 8计算r,c 所对应的行列指标f−1 2 (r) = [i1,i2],f−1 2 (c) = [j1,j2];9计算2 阶行列式T2[r,c] =■■■M[i1,i2][j1,j2]■■■= Mi1 j1 Mi2 j2 +Mi1j2 Mi2 j1;10if 2 阶行列式T2[r,c] == 0 then 11return 0;12end 13 end 14 for k 阶行列式存储表3 ≤k ≤m do 15for k 阶行列式1 ≤r,c ≤Ckm do k (r) = [i1,i2,··· ,ik],f−1k (c) = [j1,j2,··· ,jk];17计算rk−1 = fk−1([i1,i2,··· ,ik−1]), cs = fk−1([j1,j2,··· ,jk]/[js]), s = 1,2,··· ,k;18计算k 阶行列式Tk[r,c] = ∑k s=1 Mikjs Tk−1[rk−1,cs];19if k 阶行列式Tk[r,c] == 0 then 16计算r,c 所对应的行列指标f−1 20return 0;21end 22end 23 end 24 return 1;

我们将链式判别法与高斯消元法判断MDS 矩阵所需的计算量进行对比. 由表2 可知, 随着矩阵阶数增大, 两种方法所需计算量差异也逐渐增大. 以8×8 矩阵为例, 使用高斯消元法所需乘法运算数是链式判别法的6.8 倍, 所需加法运算数是链式判别法的8 倍. 显然, 使用链式判别法来判定MDS 矩阵能够有效地提升计算效率.

表2 计算量对比Table 2 Comparisons of computational complexity

4 Hadamard MDS 矩阵的判定方法

在对称密码算法中, 通常会使用一些特殊类型的矩阵作为扩散层. 结合矩阵自身的特殊性质, MDS 性质的判别方法会更加简单. 本节将介绍有限域中Hadamard MDS 矩阵的判定方法.

4.1 有限域中4 阶Hadamard MDS 矩阵的判定方法

本小节给出了有限域F2n上4 阶Hadamard MDS 矩阵的判定方法. 我们引入对称多项式的概念.

定义6[24]设多项式f ∈R[a1,a2,··· ,an]. 若对于整数1,2,··· ,n的任意置换i1,i2,··· ,in都有多项式f(ai1,ai2,··· ,ain)=f(a1,a2,··· ,an), 则称f为对称多项式. 其中

称为R[a1,a2,··· ,an] 上的k次初等对称多项式.

下面介绍对称多项式基本定理.

定理 2[24]对于任意对称多项式f ∈ R[a1,a2,··· ,an], 存在唯一确定的多项式h ∈R[a1,a2,··· ,an] 使得f(a1,a2,··· ,an)=h(σ1,σ2,··· ,σn).

我们可以将4 阶Hadamard 矩阵子方阵行列式的乘积表示为置换多项式.

例2设M=Had(1,a,a+1,((a+1)a)−1) 是有限域F2n上的4×4 Hadamard 矩阵, 其中1,a,a+1,((a+1)a)−1是有限域中的4 个互不相同的非零元并且n是一个奇数, 则M是MDS 矩阵.

4.2 交换环上4 阶Hadamard MDS 矩阵的判定方法

这一小节, 我们将有限域中的4 阶Hadamard MDS 矩阵判定定理3 推广到特征为2 的交换环上. 首先定义交换环上的MDS 矩阵.

定义7[22]设M是偶特征交换环上的4 阶矩阵. 若M任意阶子方阵行列式的值都是可逆矩阵, 则称M是4 阶MDS 矩阵.

类似命题6 的证明方法, 可以得到如下结论:

则M 是一个特征为2 的交换环.

证明:集合M 中的元素为2 阶Hadamard 矩阵且矩阵元素属于有限域F2n. 有限域F2n上2 阶Hadamard 矩阵关于加法运算可交换, 关于乘法运算封闭, 且满足结合律和分配律, 由此可知M 是一个环. 根据命题2, 对于任意两个2 阶Hadamard 矩阵H1,H2∈M 均满足H1H2=H2H1. 因此, 环M 对乘法满足交换性. 对于M 中任意元素H=Had(a1,a2),

即M 的特征为2. 综上可得集合M 是一个特征为2 的交换环.

4.3 8 阶Hadamard MDS 矩阵的判定方法

本节将利用Hadamard 矩阵的性质, 给出8 阶Hadamard MDS 矩阵的判定方法.

命题8设M= Had(a1,a2,··· ,a8) 是一个8 阶非奇异Hadamard 矩阵, 其中ai(1≤i ≤8) 为有限域F2n中的非零元, 则M的所有7 阶子方阵均为非奇异矩阵.

下面介绍8 阶Hadamard 矩阵的2 阶子方阵与6 阶子方阵的关系.

命题9设M= Had(a1,a2,··· ,a8) 是一个8 阶非奇异Hadamard 矩阵, 其中ai(1≤i ≤8) 为有限域F2n中的非零元素. 若M的任一2 阶子方阵非奇异, 则M的任一6 阶子方阵也为非奇异矩阵.

证明:对于矩阵M, 2 阶子方阵的余子式为6 阶子方阵的行列式. 因此, 我们可以将判定6 阶子方阵的满秩问题转化为判定2 阶子方阵余子式是否为0 的问题.

其中A,B,C,D均为有限域F2n上的4 阶方阵且B,D为Hadamard 矩阵. 由Hadamard 矩阵的交换性得BD=DB. 根据命题2, 利用公式|M3|=|DA −BC| 计算分块矩阵行列式得

对该行列式进行列变换(第1 列加到第4 列, 第2 列加到第3 列)得

下面给出8 阶Hadamard 矩阵3 阶子方阵与5 阶子方阵的关系.

命题10设M=Had(a1,a2,··· ,a8) 是一个8 阶非奇异Hadamard 矩阵, 其中ai(1≤i ≤8) 为有限域F2n中的非零元素. 若M的任一3 阶子方阵非奇异, 则M的任一5 阶子方阵也为非奇异矩阵.

计算该矩阵的行列式得

因为C,D是Hadamard 矩阵满足CD=DC, 由命题2可得|M2|=|AD −BC|, 即

根据上述结论, 我们可以给出判定8 阶Hadamard MDS 矩阵的充要条件.

定理5设M= Had(a1,a2,··· ,a8) 是一个8 阶非奇异Hadamard 矩阵, 其中ai(1≤i ≤8) 是有限域F2n中的非零元素. 若M的i(i ≤4) 阶子方阵均为非奇异矩阵, 则M是一个Hadamard MDS 矩阵.

证明:由命题8可得, 当M的所有元素均不为0 时,M的所有7 阶子方阵也都是非奇异矩阵. 若M的所有2 阶子方阵均为非奇异矩阵, 由命题9知M的所有6 阶子方阵也为非奇异矩阵. 若M的所有3 阶子方阵均为非奇异矩阵, 由命题10知M的所有5 阶子方阵均为非奇异矩阵. 综上, 若M的i(i ≤4)阶子方阵均为非奇异矩阵, 则M的任意阶子方阵均为非奇异矩阵, 可得M是一个Hadamard MDS 矩阵.

因此, 若要判断一个8 阶Hadamard 矩阵的MDS 性质, 只需计算所有i(i ≤4) 阶子方阵行列式是否为0, 若均不为0, 则该Hadamard 是MDS 矩阵, 反之不是.

5 Hadamard MDS 矩阵的搜索

基于上述Hadamard MDS 矩阵的判定方法, 我们可以对Hadamard MDS 矩阵进行搜索. 本节首先给出有限域F2n上4 阶和8 阶Hadamard MDS 矩阵的搜索方法. 然后, 利用有限域和有限交换环的关系, 进一步优化8 阶Hadamard MDS 矩阵的搜索方法.

5.1 4 阶Hadamard MDS 矩阵的搜索

首先给出有限域F2n上4 阶Hadamard MDS 矩阵的搜索算法. 由定理3 可知, 判定一个4阶Hadamard 矩阵Had(a1,a2,a3,a4)是否为MDS 矩阵需计算σ1,σ21σ4+σ23, 其中σ1,σ3,σ4为F2n[a1,a2,a3,a4] 上的初等对称多项式. 下面给出σ1,σ3,σ4的计算过程:

利用上述判定方法, 只需在有限域F2n{0}上遍历首行元素a1,a2,a3,a4再判断MDS 性质, 即可搜索4 阶Hadamard MDS 矩阵. 我们使用文献[23] 中的度量方法计算矩阵的实现代价, 在不同的有限域中搜索并找到了该度量方法下代价最低的4 阶Hadamard MDS 矩阵, 结果见表3.

之前的研究者也尝试寻找在不同的有限域中获得的异或数最低的4 阶Hadamard MDS 矩阵. 我们也将其罗列在表3 并给出相应的参考文献.

表3 不同有限域中的异或数最低的4 × 4 Hadamard MDS 矩阵Table 3 4 × 4 Hadamard MDS Matrices with lowest xor in different finite fields

5.2 8 阶Hadamard MDS 矩阵的搜索

由命题1易知, 同一Hadamard 等价类的矩阵有相同的MDS 性质. 因此, 我们只需要从每个等价类中选择1 个矩阵检验它是否为MDS 矩阵即可确定对应Hadamard 等价类的MDS 性质. 8 阶Hadamard矩阵一共有30 个等价类, 代表矩阵如表4 所示. 下面我们给出有限域F2n上8 阶Hadamard MDS 矩阵的搜索方法.

表4 30 个Hadamard 矩阵的等价类Table 4 30 equivalent representations of Hadamard matrices

首先, 从有限域F2n的2n −1 个非零元素中选择8 个互不相同的元素a1,a2,··· ,a8. 此时一共有种选择. 对于每一次选择的8 个元素, 都有30 个不同的等价类. 我们利用4.3 节给出的8 阶Hadamard MDS 矩阵判定方法, 来验证每一个等价代表矩阵是否为MDS 矩阵. 若判定对合HadamardMDS 矩阵则需要判断8 个元素之和是否为1. 如果不为1 则需要重新选择元素. 最终, 我们在有限域F24中搜索到15 个8 阶Hadamard MDS 矩阵, 在有限域F26中搜索到约20 万个对合Hadamard MDS 矩阵.该方法还可以在更大的有限域F2n(n ≤16) 中寻找实现代价最低的Hadamard MDS 矩阵, 结果见表5.

表5 不同有限域中异或数最低的8×8 Hadamard MDS 矩阵Table 5 8 × 8 Hadamard MDS Matrices with lowest xor in different finite fields

5.3 优化8 阶Hadamard MDS 矩阵的搜索算法

最后, 我们对有限域中8 阶Hadamard MDS 矩阵的搜索算法进一步优化.

首先利用交换环中4 阶Hadamard 矩阵的判定方法. 由第4.2 节可知, 若M= Had(a1,a2,··· ,a8)是有限域F2n上的Hadamard MDS 矩阵,则M可以表示为Had(A1,A2,A3,A4),Ai=Had(a2i−1,a2i).该矩阵为交换环M 上的4 阶Hadamard MDS 矩阵. 因此,σ1,σ4σ21+σ3σ2σ1+σ23,σ21σ4+σ23均为可逆元, 其中σk为交换环M 上的初等对称多项式. 我们首先判断σ1,σ4σ21+σ3σ2σ1+σ23,σ21σ4+σ23是否可逆. 若其中存在某个元素不可逆, 则该8 阶Hadamard 矩阵不是MDS 矩阵. 通过此方法可以快速过滤掉大量不是MDS 矩阵的候选矩阵. 然而直接计算这3 个元素, 过程依然比较繁琐. 易知, 如果一个元素A可逆当且仅当A2可逆. 于是我们尝试判定这3 个元素平方的可逆性. 令αi=a2i−1+a2i, 则有

其中,

综上, 在交换环上判断一个4 阶Hadamard 矩阵的MDS 性质需要进行12 次加法和11 次乘法运算.若M是一个对合矩阵则需要进行4 次加法和9 次乘法运算. 令集合S为{a1,a2,··· ,a8}, 其中ai是有限域F2n中的8 个互不相同的非零代表元. 利用集合S可以获得8!个8 阶Hadamard 矩阵. 将这些矩阵划分为30 个等价类, 因此每一个等价类含有1344 个8 阶Hadamard 矩阵. 由这1344 个8 阶Hadamard矩阵, 同样可以获得交换环M 上的1344 个4 阶Hadamard 矩阵. 由命题7知, Had(A1,A2,A3,A4) 和Had(Ai1,Ai2,Ai3,Ai4) 在交换环M 上具有相同的MDS 矩阵的性质, 其中i1,i2,i3,i4是1,2,3,4 的置换. 因此, 又可以将这些矩阵分成= 56 类. 最后, 将这56 个矩阵全部列出, 最终排除相同的矩阵后只剩下7 个交换环上的4 阶Hadamard 矩阵, 具体见表6. 若这7 个矩阵中存在矩阵不是交换环上4 阶MDS 矩阵, 则这1344 个矩阵均不是有限域上的8 阶Hadamard MDS 矩阵. 已知在交换环上判定一个4阶对合Hadamard MDS 矩阵需要进行4 次加法和9 次乘法运算, 那么判断这7 个矩阵则需要进行28 次加法和63 次乘法运算.

表6 用于第一步优化搜索的7 个矩阵Table 6 7 matrices for optimizing search algorithm

其次, 我们发现对于8 阶Hadamard 矩阵中存在4 阶Hadamard 子矩阵. 当8 阶Hadamard 矩阵是一个MDS 矩阵, 则它所有4 阶Hadamard 子矩阵也是MDS 矩阵. 因此我们可以利用5.1 的方法先对所有4 阶Hadamard 子矩阵进行判定. 若M=Had(a1,a2,··· ,a8) 是有限域F2n上的Hadamard MDS矩阵, 则M可以表示为Had(B1,B2), 其中B1=Had(a1,a2,a3,a4),B2=Had(a5,a6,a7,a8). 当M是一个MDS 矩阵时B1和B2都必须是4 阶Hadamard MDS. 除了B1和B2之外, 我们一共能找到14个关于M的4 阶Hadamard 矩阵, 具体见表7. 最终由5.1 可知, 验证一个4 阶的子方阵需要5 次加法和6 次乘法. 因此, 那么判断这14 个矩阵则需要进行70 次加法和84 次乘法运算.

表7 用于第二步优化搜索的14 个矩阵Table 7 14 matrices for optimizing search algorithm

算法2 有限域中8 阶对合Hadamard MDS 矩阵优化搜索算法Input: F2n 的生成多项式f(x).Output: 8 阶对合Hadamard MDS 矩阵.1 从F2n 中选择8 个互不相同的非零代表元S1 = {a1,a2,··· ,a8};2 计算∑4 i=1 αi;3 if ∑4 i=1 αi = 1 then 6利用S1 中元素对应给出表6 的7 个矩阵Hj,j = 1,2,··· ,7;4利用S1 中元素对应给出表4 的30 个矩阵Mi,i = 1,2,··· ,30;5for i = 1 to 30 do 7 temp = 0;8 for j = 1 to 7 do进行4 次加法和9 次乘法计算α,β;10if αβ == 0 then 9 11temp=1;12break;13end 14end 15if temp == 0 then 16利用S1 中元素对应给出表7 的14 个矩阵Gj,j = 1,2,··· ,14;17for j = 1 to 14 do 18if 4 阶Hadamard 矩阵不是MDS 矩阵then 19temp=1;20break;21end 22end 23if temp == 0 then 24if Mi是MDS 矩阵then 25print Mi;26end 27end 28end 29end 30 end

综上所述, 我们可以对5.2 节给出的8 阶Hadamard MDS 矩阵搜索方法进行优化, 即在对一个矩阵使用链式判别法之前先检验对应的7 个矩阵是否是交换环上的4 阶MDS 矩阵然后检验14 个4 阶Hadamard 矩阵是否为MDS 矩阵. 若存在非MDS 矩阵, 则该矩阵必然不是有限域上的8 阶Hadamard MDS 矩阵, 无需再使用链式判别法, 从而达到减少搜索空间的目的. 最后我们给出优化后的8 阶对合Hadamard MDS 矩阵的搜索算法2. 根据上述搜索策略, 我们在有限域F26中进行搜索, 在相同的计算条件下, 使用该优化算法计算量减少了3 倍.

6 总结

在资源受限的环境中, 轻量级密码算法的设计会更加注重硬件效率. Hadamard MDS 矩阵因其本身的良好性质, 被广泛的应用在线性层的设计中. 本文设计了一种Hadamard MDS 矩阵的快速搜索算法.

首先, 提出了MDS 矩阵的链式判别法. 与高斯消元法相比, 该方法将子方阵行列式的计算复杂度从O(n3) 减小到O(n), 从而可以快速的验证矩阵的MDS 性质. 随着矩阵阶数增大, 计算效率的提升也更加显著.

其次,给出了有限域上m(m=4,8)阶Hadamard MDS 矩阵的判定方法. 对于4 阶Hadamard 矩阵,只需要验证3 个元素是否为0 即可判断该矩阵是否为MDS 矩阵. 该方法有效地提升了4 阶Hadamard MDS 矩阵的搜索效率, 并且还可以被推广到有限交换环上. 对于8 阶Hadamard 矩阵, 只需要判定不小于4 阶子方阵均满秩, 即可判定该矩阵为Hadamard MDS 矩阵. 该方法将待计算的子方阵行列式的个数减少了一半, 因此可以更加快速的判定8 阶Hadamard MDS 矩阵.

最后, 结合上述方法, 本文给出了有限域上m(m= 4,8) 阶Hadamard MDS 矩阵的快速搜索算法.对于一个给定的4 阶Hadamard 矩阵, 只需要计算6 次乘法和5 次加法即可确定该矩阵是否为MDS矩阵. 利用该判定方法可以穷搜有限域F2n(n ≤8) 上的4 阶Hadamard MDS 矩阵, 并且搜索到了F2n(n ≤16) 上异或数最低的4 阶Hadamard MDS 矩阵. 对于有限域上8 阶Hadamard 矩阵, 我们利用有限交换环上4 阶Hadamard 矩阵和有限域上8 阶Hadamard 矩阵的联系减小搜索范围. 最终, 实现了对有限域F2n(n ≤6) 上8 阶Hadamard MDS 矩阵的穷搜, 并且搜索到了F2n(n ≤16) 上异或数最低的Hadamard MDS 矩阵.