輕量級(jí)迭代MDS 矩陣的構(gòu)造*

王 麗, 陳 媛, 王 石, 曾祥勇

湖北大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院 應(yīng)用數(shù)學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室, 武漢 430062

1 引言

隨著信息技術(shù)的快速發(fā)展, 微型嵌入式設(shè)備越來越發(fā)達(dá). 由于微型設(shè)備在面積、通信能力、計(jì)算速度和儲(chǔ)存空間等方面有著一定限制, 所以設(shè)計(jì)更加安全并且輕量的擴(kuò)散層成為焦點(diǎn). 與直接使用MDS 矩陣實(shí)現(xiàn)最優(yōu)擴(kuò)散的擴(kuò)散層相比, 迭代擴(kuò)散層有著更小的硬件實(shí)現(xiàn), 因此適用于資源受限環(huán)境的迭代MDS 矩陣引起了廣泛關(guān)注. 迭代MDS 矩陣, 即其本身并不具備MDS 性質(zhì), 而將其迭代特定次數(shù)后是MDS 矩陣. 更具體地說, 如果At是MDS 矩陣, 則可以通過A而不是At來實(shí)現(xiàn)MDS 性質(zhì), 但是這種方法往往需要增加t時(shí)鐘周期, 因此在使用的過程中會(huì)有更高的延遲.

矩陣的異或數(shù)是衡量線性層實(shí)現(xiàn)的另一個(gè)重要指標(biāo), 異或數(shù)越小意味著矩陣的實(shí)現(xiàn)代價(jià)越低. 而矩陣中非零元的個(gè)數(shù)越小, 獲得較小異或數(shù)的可能性越大. 文獻(xiàn)[1] 給出了迭代MDS 矩陣的非零元數(shù)目的下界和達(dá)到該下界時(shí)迭代次數(shù)的下界, 這使得搜索異或數(shù)低且延遲低的迭代MDS 矩陣更加容易. 文獻(xiàn)[2]提出一類具有特殊結(jié)構(gòu)的稀疏DSI 矩陣來構(gòu)造迭代型MDS 矩陣, 該類矩陣的固定異或數(shù)僅是友矩陣固定異或數(shù)的一半, 在迭代實(shí)現(xiàn)中比友矩陣構(gòu)造的擴(kuò)散矩陣更輕; 而且對(duì)于4 階矩陣, 稀疏DSI 矩陣可以實(shí)現(xiàn)最低的固定成本, 這意味著不存在其他迭代型的MDS 矩陣結(jié)構(gòu)輕于稀疏DSI 結(jié)構(gòu). 但由于搜索空間過大, 并沒有得到8 階的稀疏DSI 矩陣. 隨后文獻(xiàn)[3] 證明了F28上的8 階稀疏DSI 矩陣是不存在的.

關(guān)于迭代MDS 矩陣的構(gòu)造, 在過去的工作中, 迭代次數(shù)一般都大于等于矩陣的階數(shù)[1–7]. 在迭代次數(shù)等于階數(shù)的情況下, 文獻(xiàn)[5,8] 利用友矩陣, 在有限域F24和F28上得到非零元個(gè)數(shù)為7, 異或數(shù)最低分別為15 和33 的4 階迭代MDS 矩陣. 文獻(xiàn)[9] 中構(gòu)造出了有限域F24上非零元個(gè)數(shù)為7, 異或數(shù)為13的4 階迭代MDS 矩陣, 但此時(shí)矩陣要迭代8 次才能實(shí)現(xiàn)最優(yōu)擴(kuò)散. 2018 年提出的稀疏DSI 矩陣, 也是在迭代次數(shù)等于階數(shù)的情況下構(gòu)造迭代MDS 矩陣, 在F24和F28上分別得到非零元個(gè)數(shù)為6, 異或數(shù)最低分別為10 和22 的4 階迭代MDS 矩陣[2].

為減少因時(shí)鐘周期增加而產(chǎn)生的延遲, 本文研究了迭代次數(shù)小于等于階數(shù)時(shí)4 階迭代MDS 矩陣的構(gòu)造. 在迭代次數(shù)分別為2、3、4 時(shí), 證明了4 階迭代MDS 矩陣所含非零元個(gè)數(shù)的下界, 并通過矩陣的置換相似分類和MDS 條件, 實(shí)現(xiàn)了非零元個(gè)數(shù)達(dá)到下界的4 階迭代MDS 矩陣的窮搜. 在迭代次數(shù)為3 時(shí),我們?cè)贔24上找到了非零元個(gè)數(shù)達(dá)到最小值7, 異或數(shù)為15 的4 階迭代MDS 矩陣, 這是迭代次數(shù)為3時(shí), 4 階迭代MDS 矩陣異或數(shù)所能達(dá)到的最小值; 而在F28上, 我們得到了非零元個(gè)數(shù)達(dá)到最小值7, 異或數(shù)為30 的4 階迭代MDS 矩陣, 不僅實(shí)現(xiàn)了迭代次數(shù)的降低, 同時(shí)有著更低的異或數(shù). 在迭代次數(shù)等于4 時(shí), 在F24和F28上我們得到了同文獻(xiàn)[2] 中稀疏DSI 矩陣具有相同異或數(shù)的一般類型輕量4 階迭代MDS 矩陣, 其非零元個(gè)數(shù)達(dá)到最小值為6, 異或數(shù)分別達(dá)到最小值為10 和22.

2 預(yù)備知識(shí)

本節(jié)主要介紹迭代MDS 矩陣相關(guān)定義、性質(zhì)和度量. 首先給出本文中常用的符號(hào), 見表1.

表1 符號(hào)說明Table 1 Notations

2.1 迭代MDS 矩陣及MDS 條件

定義1[10]設(shè)M ∈Mn(F2m). 若矩陣M的分支數(shù)

則稱M為MDS 矩陣.

注1M為MDS 矩陣當(dāng)且僅當(dāng)M的任意階子方陣都是可逆的[11]. 這個(gè)等價(jià)條件常用來判斷一個(gè)矩陣是否是MDS 矩陣.

矩陣分支數(shù)是度量矩陣擴(kuò)散能力的重要標(biāo)準(zhǔn). MDS 矩陣是矩陣分支數(shù)達(dá)到上界的矩陣, 它可以有效抵抗差分攻擊和線性攻擊, 同時(shí)提供最優(yōu)的擴(kuò)散能力, 這在密碼應(yīng)用中得到廣泛應(yīng)用. 但是因?yàn)镸DS 矩陣不含有零元, 且大多數(shù)元素互不相等, 在資源受限的環(huán)境下實(shí)現(xiàn)MDS 矩陣很困難. 因此在此基礎(chǔ)上, 提出了更適合輕量級(jí)應(yīng)用的迭代MDS 矩陣.

定義2[12]設(shè)M ∈Mn(F2m). 若存在正整數(shù)t, 使得Mt為MDS 矩陣, 則稱矩陣M為迭代MDS矩陣, 稱Mt為迭代型MDS 矩陣, 其中正整數(shù)t稱為迭代次數(shù).

顯然, MDS 矩陣是滿秩矩陣, 從而迭代MDS 矩陣也是滿秩陣, 其每行每列至少含有一個(gè)非零元. 因此本文只考慮形如P(D+B′)=PD+B形式的矩陣, 其中P是置換矩陣(即每行和每列有且僅有一個(gè)元素為1 而其余元素都為0 的矩陣),D是非奇異對(duì)角陣,B′是在非對(duì)角位置包含k(k ≥1) 個(gè)非零元的矩陣, 即B包含k個(gè)非零元且非零元位置與P均不相同. 稱能被寫成PD+B形式的矩陣為k-XOR 矩陣[3].

例1 3-XOR 矩陣的例子:

如果有x=(a,b,c,d)?, 那么Mx=(X1a+X2d,X3d,X4b+X5c,X1a+X7c)?.Mx中的加法總數(shù)等于B的非零元個(gè)數(shù). 在特征為2 的域中, 這些加法是通過異或來實(shí)現(xiàn)的, 因此形如PD+B的矩陣被稱為k-XOR 矩陣, 這些異或被稱為固定異或數(shù)或固定成本. 若M ∈Mn(F2m), 則θ(B) =θ(M)-n=k.M的固定成本為m·k. 非零元素的個(gè)數(shù)k越小, 越容易構(gòu)造出實(shí)現(xiàn)代價(jià)較低的矩陣.

下面我們引入(k,t) 迭代MDS 矩陣的概念.

定義3 設(shè)M ∈Mn(F2m). 如果M是k-XOR 矩陣且Mt是MDS 矩陣(t為正整數(shù)), 則稱M是(k,t) 迭代MDS 矩陣.

注2M ∈Mn(F2m) 是(k,t) 迭代MDS 矩陣當(dāng)且僅當(dāng)M?是(k,t) 迭代MDS 矩陣.

設(shè)M=PD+B ∈Mn(F2m) 是k-XOR 矩陣, 則θ(M) =k+n, 非零元分別用X1,X2,··· ,Xk+n表示. 若M是(k,t) 迭代MDS 矩陣, 則矩陣Mt的元素Mtij(1≤i,j ≤n) 是關(guān)于X1,X2,··· ,Xk+n的多項(xiàng)式. 判斷M迭代t次后的矩陣是否為一個(gè)MDS 矩陣, 我們需要判斷矩陣Mt所有的子方陣是否可逆, 即判斷所有子方陣的行列式是否為零. 下面給出檢查矩陣是否為MDS 矩陣的一種算法[13].

MDS 條件[13]設(shè)A為Mn(F2m) 中的非零矩陣,A中所有非零元分別用F2上未定元表示. 則A的子方陣的行列式是一系列F2上關(guān)于這些未定元的多項(xiàng)式. 將這些多項(xiàng)式分解為若干個(gè)不可約多項(xiàng)式, 則A的每個(gè)子方陣都唯一對(duì)應(yīng)一個(gè)不可約多項(xiàng)式的集合(若這些多項(xiàng)式中包含零多項(xiàng)式, 則將零多項(xiàng)式加入到此不可約多項(xiàng)式的集合中). 將A的所有子方陣對(duì)應(yīng)的不可約多項(xiàng)式集合并起來得到的集合記為T, 稱T為矩陣A的MDS 條件.A是MDS 矩陣當(dāng)且僅當(dāng)A中非零元在F2m中的取值, 使得集合T中任意不可約多項(xiàng)式不等于零.

注意到,T中可能會(huì)包含零多項(xiàng)式, 這樣的矩陣一定不是MDS 矩陣. 為了方便判斷, 我們引入MDS條件多項(xiàng)式的概念.

定義4 記集合T中所有元素相乘得到的多項(xiàng)式為fA, 稱fA為矩陣A的MDS 條件多項(xiàng)式.

顯然, 矩陣A是MDS 矩陣,A的MDS 條件多項(xiàng)式fA必為非零多項(xiàng)式. 即只有當(dāng)A的MDS 條件多項(xiàng)式不為零多項(xiàng)式時(shí), 它才有可能構(gòu)成MDS 矩陣.

引理1A為MDS 矩陣當(dāng)且僅當(dāng)A中非零元的取值使得MDS 條件多項(xiàng)式fA不等于零.

注3 設(shè)M ∈Mn(F2m) 是k-XOR 矩陣. 則M是(k,t) 迭代MDS 矩陣, 當(dāng)且僅當(dāng)Mt的MDS 條件多項(xiàng)式fMt在M的非零元取值下的值fMt(m1,m2,··· ,mk+n)/=0, 其中m1,m2,··· ,mk+n分別表示M的非零元.

例2 設(shè)M ∈M3(F2m) 是3-XOR 矩陣,X1,X2,··· ,X6分別表示M的非零元,

從而

矩陣M2的MDS 條件為

為(3,2) 迭代MDS 矩陣.

2.2 矩陣及元素的異或數(shù)

定義5[8]設(shè)M ∈Mm(F2) 是非奇異矩陣. 矩陣M的異或數(shù)定義為M非零元的個(gè)數(shù)減去矩陣維數(shù)m, 記為XOR(M), 即XOR(M)=θ(M)-m.

設(shè)p(X) 為F2上次數(shù)為m的不可約多項(xiàng)式, 則F2m～= F2[X]/(p(X)). 有限域F2m上的任意元素α都可以表示為F2上次數(shù)小于m的多項(xiàng)式, 記為fα(X). 令p(X) 的友矩陣為A, 則有限域F2m上的任意元素α都對(duì)應(yīng)F2上一個(gè)m階矩陣fα(A), 這建立了F2m到Mm(F2) 上的一一對(duì)應(yīng).

定義6[15]設(shè)α為有限域F2[X]/(p(X))上的元素.α的異或數(shù)定義為實(shí)現(xiàn)α與域上任意元素β相乘所需的異或操作數(shù), 記為XOR(α).

有限域上元素的異或數(shù)可以通過其對(duì)應(yīng)的矩陣來度量, 即XOR(α)=XOR(Mα).

例3 令α=X+1∈F2[X]/(X4+X+1),β=b3X3+b2X2+b1X+b0是F2[x]/(X4+X+1)上任意元,bi ∈F2. 則

其中符號(hào)“⊕” 表示比特異或, 觀察可知XOR(α)=5.α·β表示為矩陣乘法也可以寫為:

注意到p(X)=X4+X+1 的友矩陣A為

從而α=X+1 對(duì)應(yīng)的矩陣為A+I=Mα. 顯然XOR(Mα)=θ(Mα)-4=9-4=5=XOR(α).

對(duì)于有限域F2m上n階非奇異矩陣M的異或數(shù), 則是通過將有限域F2m上的每個(gè)元素用其對(duì)應(yīng)的F2上的矩陣替換, 從而得到一個(gè)F2上的mn階矩陣, 設(shè)為Mmn.M ∈Mn(F2m) 的異或數(shù)即定義為Mmn ∈Mmn(F2) 的異或數(shù). 因此有

其中αi(1≤i ≤k) 表示矩陣M的非零元.

2.3 置換矩陣及置換相似

本文還需用到置換矩陣的相關(guān)性質(zhì)和置換相似的概念及其性質(zhì). 置換矩陣即每行和每列有且僅有一個(gè)元素為1 而其余元素都為0 的矩陣. 顯然, 置換矩陣與矩陣相乘, 僅改變矩陣元素的行列位置, 不改變矩陣元素的數(shù)值. 因此, 置換矩陣的乘積也為置換矩陣.

引理2 令矩陣P, D ∈Mn(F2m) 且P是置換矩陣,D是非奇異對(duì)角矩陣. 則對(duì)任意矩陣A, 有θ(A)=θ(AP)=θ(PA)=θ(AD)=θ(DA).

證明:P為置換矩陣, 顯然有θ(A) =θ(AP) =θ(PA). 又D是非奇異對(duì)角矩陣, 令M=AD,有Mij=AijDjj(1≤i,j ≤n), 則Mij/= 0 當(dāng)且僅當(dāng)Aij/= 0, 從而θ(A) =θ(AD). 同理可證,θ(A)=θ(DA).

定義7 設(shè)矩陣A, B ∈Mn(F2m). 如果存在置換矩陣P, 使得B=P-1AP, 則稱矩陣A和B是置換相似的.

顯然, 置換相似是矩陣上的一種等價(jià)關(guān)系.

引理4 設(shè)A, B ∈Mn(F2m) 是置換相似的. 則

(1)A是迭代MDS 矩陣當(dāng)且僅當(dāng)B是迭代MDS 矩陣, 且迭代次數(shù)相同;

(2)A是對(duì)角矩陣當(dāng)且僅當(dāng)B是對(duì)角矩陣;

(3) XOR(A)=XOR(B).

證明: (1) 置換矩陣P與矩陣相乘, 僅改變矩陣元素的行列位置, 不改變矩陣元素的數(shù)值, 從而置換相似顯然保持矩陣的MDS 性質(zhì). 設(shè)A=P-1BP, 其中P是置換矩陣.A是迭代MDS 矩陣當(dāng)且僅當(dāng)存在正整數(shù)t, 使得At是MDS 矩陣. 而At=(P-1BP)t=P-1BtP是MDS 矩陣當(dāng)且僅當(dāng)Bt是MDS矩陣.

為一個(gè)對(duì)角矩陣. 反之亦然.

(3)A, B置換相似, 則它們有著相同的非零元. 令非零元分別為X1,X2,··· ,Xk+n, 則

3 4 階(3, 3) 迭代MDS 矩陣的構(gòu)造

本節(jié)將使用無特殊結(jié)構(gòu)的矩陣構(gòu)造迭代MDS 矩陣, 并且使得矩陣迭代次數(shù)小于矩陣階時(shí)就能滿足MDS 性質(zhì). 在矩陣構(gòu)造過程中, 為了獲得更加輕量級(jí)的結(jié)果, 我們令矩陣由大量的零元和少數(shù)異或數(shù)小的元素組成. 本節(jié)給出了迭代次數(shù)為3 的4 階迭代MDS 矩陣所含非零元個(gè)數(shù)的下界. 進(jìn)一步地, 由于單位元是有限域非零元中異或數(shù)最低的元素, 在非零元個(gè)數(shù)達(dá)到下界時(shí), 通過實(shí)驗(yàn)計(jì)算找到了迭代MDS 矩陣非零元中所含單位元個(gè)數(shù)的上界. 本節(jié)給出的搜索策略, 實(shí)現(xiàn)了對(duì)迭代次數(shù)為3, 非零元個(gè)數(shù)達(dá)到下界的4階迭代MDS 矩陣的窮搜.

3.1 4 階(k, 3) 迭代MDS 矩陣

本文主要研究4 階迭代MDS 矩陣的構(gòu)造. 在過去的構(gòu)造方法中, 利用多項(xiàng)式的友矩陣構(gòu)造MDS 矩陣, 至少需要迭代4 次才能得到一個(gè)MDS 矩陣. 因此, 我們先考慮迭代次數(shù)為3 的情況.

在構(gòu)造之前, 首先要確定有限域F2m上4×4 矩陣M能夠構(gòu)造(k,3) 迭代MDS 矩陣時(shí), 矩陣非零元θ(M)=k+4 的最小值. 在此之前, 先來看一個(gè)引理.

引理5 設(shè)A ∈Mn(F2m) 且θ(A)≤2, 則有θ(A2)≤2, 且θ(A2)=2 當(dāng)且僅當(dāng)A為如下三種情形:

(1)A中的兩個(gè)非零元都在對(duì)角線上;

(2)A中的兩個(gè)非零元關(guān)于對(duì)角線對(duì)稱;

(3)A中的兩個(gè)非零元在同一行或同一列且一個(gè)在對(duì)角線上.

證明: 當(dāng)θ(A)≤2 時(shí), 矩陣A可表示為A=a1E(i1j1)+a2E(i2j2), 其中a1,a2∈F2m且(i1,j1)/=(i2,j2). 因此有

從而

當(dāng)θ(A)＜2,a1,a2至少有一個(gè)等于0, 則θ(A2)≤1.

當(dāng)θ(A)=2,a1,a2/=0, 則有

定理1 設(shè)A ∈M4(F2m) 是(k,3) 迭代MDS 矩陣, 則k ≥3.

證明: 反證法. 假設(shè)A=PD+B是M4(F2m) 中2-XOR 矩陣, 其中P是置換矩陣,D是非奇異對(duì)角矩陣,θ(B)=2. 令P′=PD, 我們有

由引理5 可知θ(B2)≤2. 根據(jù)引理2, 對(duì)于任意矩陣M, 有θ(P′M) =θ(PDM) =θ(M). 因此,θ(P′3) =θ(P′) = 4 且θ(P′k1BP′k2) =θ(B) = 2(k1,k2是整數(shù)). 下面分四種情形證明θ(A3)＜16, 即A3不可能是MDS 矩陣.

情形1.θ(B2)≤1. 當(dāng)θ(B2)≤1 時(shí),θ(P′B2), θ(B2P′)≤1. 又θ(BP′B) =θ(BP′BP′) =θ((BP′)2)且θ(BP′) =θ(B) = 2, 因此θ(BP′B)≤2. 當(dāng)θ(B2) = 0 時(shí),θ(B3) = 0; 當(dāng)θ(B2) = 1時(shí),θ(B3) =θ(B2·B)≤2, 且θ(B3) = 2 時(shí)一定有B的非零元在同一行且都不在對(duì)角線上, 但此時(shí)θ(B2)=0, 矛盾. 從而θ(B3)≤1. 所以有

情形2.θ(B2) = 2 且B中的兩個(gè)非零元都在對(duì)角線上. 此時(shí),B為含兩個(gè)非零元素的對(duì)角矩陣. 我們有

根據(jù)引理5 可知θ((BP′)2)≤2.

即矩陣P′-1BP′的非零元在第3 行第4 列和第4 行第3 列. 相同的方法計(jì)算可得矩陣P′-2BP′2的非零元在第1 行第2 列和第2 行第1 列, 與B的非零元位置相同. 因此θ(B+P′-2BP′2+P′-1BP′)≤4,θ(A3)≤6+4+4+0=14＜16.

情形4.θ(B2) = 2 且B中的兩個(gè)非零元在同一行或同一列且一個(gè)在對(duì)角線上. 不妨設(shè)B中的兩個(gè)非零元在同一行. 則對(duì)?M ∈M4(F2m), θ(BM)≤4, 且BM的非零元都在同一行. 此時(shí),

同理可證B中的兩個(gè)非零元在同一列的情形.

綜上所述, 對(duì)任意2-XOR 矩陣A, 都有θ(A3)＜16.

注4 在不考慮迭代次數(shù)的情況下,M4(F2m) 中迭代MDS 矩陣非零元個(gè)數(shù)至少為5, 且取到下界時(shí),矩陣迭代次數(shù)至少為14[1].

定理1 給出的下界是建立在矩陣元素在有限域的基礎(chǔ)之上, 實(shí)際上可以推廣到有限域上的矩陣環(huán)中,得到一樣的下界. 考慮矩陣環(huán)上的迭代次數(shù)為3 次的4 階k-異或矩陣M=PD+B, 其中D為矩陣環(huán)上的對(duì)角矩陣(即有限域上的分塊對(duì)角矩陣, 此時(shí)D有可能為奇異矩陣),P為矩陣環(huán)上的置換矩陣(即每行每列中只有一個(gè)位置是單位矩陣, 其余位置都為零矩陣). 當(dāng)D為非奇異矩陣時(shí), 即分塊對(duì)角矩陣的每一個(gè)分塊都是一個(gè)非奇異矩陣, 此時(shí)M中的非零元為矩陣環(huán)中的非奇異矩陣, 該類型矩陣M的非零元下界推導(dǎo)方法與定理1 證明方法類似(矩陣環(huán)中元素的非交換性使得個(gè)別細(xì)節(jié)地方證明略有不同); 當(dāng)D為奇異矩陣時(shí),M中的非零元可為矩陣環(huán)中任意的非零矩陣, 總可以找到矩陣M′=PD′+B′, 它和M具有相同的非零位置, 且每個(gè)非零位置上為非奇異矩陣, 并滿足M迭代3 次后所含非零元的個(gè)數(shù)要小于等于M′迭代3 次后所含非零元的個(gè)數(shù). 從而此種類型的M迭代3 次后能為MDS 矩陣(所含非零元個(gè)數(shù)必為16), 所含非零元的個(gè)數(shù)必大于等于M=PD+B,D為非奇異矩陣的情形.

根據(jù)定理1, 構(gòu)造4×4 的(k,3) 迭代MDS 矩陣,k必須滿足k ≥3. 而矩陣的非零元個(gè)數(shù)越少, 越有可能構(gòu)造出實(shí)現(xiàn)代價(jià)更低的迭代MDS 矩陣. 本節(jié)接下來主要討論k=3 時(shí)迭代MDS 矩陣的構(gòu)造.

3.2 4 階(3, 3) 迭代MDS 矩陣搜索

第一步, 非零元位置的選擇. 確定7 個(gè)非零元的位置, 初步排除部分不滿足迭代MDS 性質(zhì)的3-XOR矩陣.

設(shè)M ∈M4(F2m) 為3-XOR 矩陣,M的非零元按其在矩陣中的行列位置, 從左到右從上到下分別設(shè)為X1,X2,··· ,X7, 則矩陣M3的元素是關(guān)于X1,X2,··· ,X7的多項(xiàng)式. 計(jì)算M3, 若M3的某個(gè)元素為零多項(xiàng)式, 則篩掉對(duì)應(yīng)的M. 通過實(shí)驗(yàn)可以發(fā)現(xiàn), 迭代3 次后矩陣元素都是關(guān)于X1,X2,··· ,X7的非零多項(xiàng)式的3-XOR 矩陣有120 個(gè).

第二步, 矩陣的分類. 將120 個(gè)矩陣按置換相似進(jìn)行分類, 并過濾掉部分迭代后MDS 條件多項(xiàng)式為零多項(xiàng)式的矩陣.

由引理4, 置換相似保持矩陣的迭代MDS 性質(zhì). 將矩陣按置換相似進(jìn)行分類, 矩陣搜索空間減小為不同置換相似類的集合. 注意到, 置換相似變換僅改變矩陣非零元的位置不改變非零元數(shù)值. 在進(jìn)行矩陣置換相似分類時(shí), 可令X1,X2,··· ,X7= 1. 此時(shí)搜索空間變?yōu)?20 個(gè)0, 1 矩陣的集合U, 對(duì)集合U做置換相似分類, 從而得到120 個(gè)矩陣的置換相似分類Ui={PMiP-1,P置換矩陣}, 1≤i ≤5, 見表2.

表2 矩陣置換相似分類Table 2 Permutation similarity classification

Ui中矩陣彼此間都是置換相似的, 它們有著相同的迭代MDS 性質(zhì)和相等的異或數(shù). 因此, 只用檢查矩陣M1,M2,··· ,M5的迭代MDS 性質(zhì). 若M4(F2m) 中矩陣M是(3,3) 迭代MDS 矩陣, 則MDS條件多項(xiàng)式fM3必為非零多項(xiàng)式. 計(jì)算矩陣M1,M2,··· ,M5迭代3 次后對(duì)應(yīng)矩陣的MDS 條件多項(xiàng)式fM3i(1≤i ≤5), 排除MDS 條件多項(xiàng)式fM3i為零多項(xiàng)式對(duì)應(yīng)的矩陣Mi. 例如:

3.3 主要結(jié)果

盡可能多的取值為1. 令X1,X2,··· ,X7取值都為1 或任意6 個(gè)取值為1, 另1 個(gè)仍為未定元, 都使得fM31=fM32=0. 令X1,X2,··· ,X7中任意5 個(gè)取值為1, 另外2 個(gè)未定元分別設(shè)為X,Y(共有21 種取值可能), 此時(shí)存在部分取值使得fM31或fM32為關(guān)于X,Y的非零多項(xiàng)式. 從而(3,3) 迭代MDS 矩陣非零元取值1 的個(gè)數(shù)不大于5, 且非零元對(duì)1 的取值不是任意的, 結(jié)果見表3.

表3 含5 個(gè)1 的(3, 3) 迭代MDS 矩陣類型Table 3 Types of (3, 3) iterative MDS matrix containing five 1’s

我們重點(diǎn)關(guān)注M4(F24) 和M4(F28) 中的(3,3) 迭代MDS 矩陣, 分別找到了M4(F24) 和M4(F28)中異或數(shù)最小的(3,3) 迭代MDS 矩陣, 異或數(shù)分別為15 和30, 如矩陣

其中α和β分別為F24上生成多項(xiàng)式X4+X+1 和F28上生成多項(xiàng)式X8+X4+X3+X2+1 的根.則A3是MDS 矩陣且XOR(A)=XOR(α2)+XOR(α-1)+3×4=2+1+12=15;B3是MDS 矩陣且XOR(B)=XOR(β)+XOR(β-1)+3×8=3+3+24=30.

注意到, 當(dāng)k ≥4 時(shí),M4(F24) 中矩陣含有固定的異或數(shù)km ≥16, 不可能構(gòu)造異或數(shù)比15 更小的(k,3) 迭代MDS 矩陣. 而對(duì)于(3,3) 迭代MDS 矩陣, 至少存在2 個(gè)非零元取值不為1, 因此矩陣異或數(shù)≥3×4+2×1 = 14, 且當(dāng)且僅當(dāng)矩陣5 個(gè)非零元取值為1 且另外兩個(gè)非零元異或數(shù)均為1 時(shí), 等號(hào)有可能成立. 我們對(duì)該類型矩陣實(shí)現(xiàn)了窮搜, 這類矩陣是不存在的, 即等號(hào)不能成立. 因此有命題1.

命題1M4(F24) 中(k,3) 迭代MDS 矩陣的異或數(shù)最小值為15, 且當(dāng)且僅當(dāng)k=3 時(shí)能取到最小值.

注5 在文獻(xiàn)[5,8] 中, 作者利用4 階友矩陣構(gòu)造(3,t) 迭代MDS 矩陣, 在F24和F28上得到矩陣異或數(shù)最低分別為15 和33 的(3,4) 迭代MDS 矩陣. 在F24上, 我們構(gòu)造的迭代MDS 矩陣, 在保證了矩陣非零元個(gè)數(shù)相同且矩陣異或數(shù)相等的情況下, 實(shí)現(xiàn)了迭代次數(shù)的降低. 而在F28上, 我們構(gòu)造的迭代MDS 矩陣, 不僅迭代次數(shù)降低為3 次, 同時(shí)有著更低的異或數(shù)30.

此外, 我們也在有限域F25,F26,F27上對(duì)表3 中矩陣進(jìn)行了搜索, 找到了異或數(shù)最低分別為18, 21,25 的(3,3) 迭代MDS 矩陣. 我們將本文得到的4 階(3,3) 迭代MDS 矩陣結(jié)果與已知結(jié)果進(jìn)行了比較,見表4.

表4 4 階(3, 3) 迭代MDS 矩陣結(jié)果的比較Table 4 Comparison of known results on (3, 3) iterative MDS matrices of order 4

4 其他類型迭代MDS 矩陣

4.1 4 階(5, 2) 迭代MDS 矩陣

進(jìn)一步減小4 階迭代MDS 矩陣的迭代次數(shù), 考慮M4(F2m) 中(k,2) 迭代MDS 矩陣的構(gòu)造. 關(guān)于k的取值范圍, 我們有以下定理.

定理2 設(shè)A ∈M4(F2m) 是(k,2) 迭代MDS 矩陣, 則k ≥5.

證明: 假設(shè)A=PD+B是M4(F2m) 中4-XOR 矩陣, 則

下面通過對(duì)矩陣B的秩Rank(B) 進(jìn)行討論, 分情況證明A2不可能是MDS 矩陣.

當(dāng)Rank(B)＜4 時(shí). 因?yàn)棣?B) = 4, 矩陣B至少存在某一行或某一列全是零元, 從而矩陣A存在某一行或某一列只含一個(gè)非零元. 不妨設(shè)A的第一行只有一個(gè)非零元且A1i/=0. 則要使得A2第i行不含零元, 必有Ai1,Ai2,Ai3,Ai4/= 0. 又因?yàn)棣?A) = 8, 則另外兩行有三個(gè)非零元, 從而矩陣A必還存在另一行也只含一個(gè)非零元, 設(shè)該非零元是Ai′j, 則i′/=1, j/=i(否則A不是k-XOR 矩陣). 同樣地, 要使得A2第j行不含零元, 則必有Aj1,Aj2,Aj3,Aj4/= 0, 這與θ(A) = 8 矛盾. 即Aj1,Aj2,Aj3,Aj4中至少有一個(gè)為0, 因此一定有θ(A2)＜16. 當(dāng)矩陣A的某一列只有一個(gè)非零元, 類似可證.

當(dāng)Rank(B) = 4 時(shí). 因?yàn)棣?B) = 4, 矩陣B每行每列只含一個(gè)非零元, 即矩陣A每行每列含有兩個(gè)非零元. 要使得A2是MDS 矩陣, 則θ(A2) =θ(P′2+P′B+BP′+B2) = 16, 其中P′=PD.又因?yàn)棣?P′2) =θ(P′B) =θ(BP′) =θ(B2) = 4, 所以矩陣P′2, P′B, BP′, B2的非零元所在位置互不相同, 每個(gè)非零元?jiǎng)偤檬蔷仃嘇2對(duì)應(yīng)位置的元素. 且由于矩陣P, B每行每列均只含一個(gè)非零元, 所以P′2, P′B, BP′, B2的非零項(xiàng)都只是A中某兩個(gè)元素的乘積, 此時(shí)A2的每一個(gè)元素都僅是A中某兩個(gè)元素的乘積, 即(A2)ij=AikAkj,1≤i,j,k ≤4.

假設(shè)矩陣A第i行的兩個(gè)非零元分別為Aij1,Aij2, 第i列的兩個(gè)非零元分別為Ak1i,Ak2i. 則矩陣A2存在二階子方陣

因此A2不可能是MDS 矩陣.

采用第3 節(jié)同樣的搜索策略, 在F24和F28上, 我們找到了異或數(shù)最小的(5,2) 迭代MDS 矩陣, 異或數(shù)分別為23 和49, 如矩陣

其中α和β分別為F24上生成多項(xiàng)式X4+X+1 和F28上生成多項(xiàng)式X8+X4+X3+X2+1 的根.則A2是MDS 矩陣且XOR(A)=XOR(α)+2XOR(α-1)+5×4=1+2+20=23;B2是MDS 矩陣且XOR(B)=3XOR(β)+5×8=3×3+40=49.

命題2M4(F24) 中(k,2) 迭代MDS 矩陣的異或數(shù)最小值等于23, 此時(shí)矩陣非零元素個(gè)數(shù)為9, 迭代次數(shù)等于2.

在有限域F25,F26,F27上的搜索結(jié)果, 見表5.

表5 4 階(5, 2) 迭代MDS 矩陣結(jié)果Table 5 Results of (5, 2) iterative MDS matrices of order 4

4.2 4 階(2, 4) 迭代MDS 矩陣

基于迭代MDS 矩陣通過循環(huán)矩陣來實(shí)現(xiàn)最優(yōu)擴(kuò)散的特性, 使得優(yōu)化迭代MDS 矩陣存在兩個(gè)方向:

(1) 減小矩陣的迭代次數(shù), 從而縮短實(shí)現(xiàn)過程中的時(shí)間延遲; (2) 減少矩陣的非零元個(gè)數(shù), 從而降低矩陣的異或數(shù). 第3 節(jié)及4.1 節(jié)正是通過減小矩陣的迭代次數(shù)獲得更優(yōu)的迭代MDS 矩陣. 本節(jié)主要是通過減小矩陣的非零元個(gè)數(shù), 來構(gòu)造M4(F2m) 中迭代次數(shù)等于矩陣階數(shù)但非零元個(gè)數(shù)小于7 的迭代MDS 矩陣.

定理3 設(shè)A ∈M4(F2m) 是(k,4) 迭代MDS 矩陣, 則k ≥2.

證明: 假設(shè)A=PD+B是M4(F2m) 中1-XOR 矩陣, 即矩陣B只含一個(gè)非零元. 令P′=PD,則

根據(jù)定理2 可知,若A2∈M4(F2m)是迭代次數(shù)等于2 的迭代MDS 矩陣,則θ(A2)≥9. 因此,A4=(A2)2不可能是MDS 矩陣, 即A不可能是(k,4) 迭代MDS 矩陣.

因此, 矩陣迭代次數(shù)與階數(shù)相同都等于4 時(shí), 矩陣非零元個(gè)數(shù)的最小值為6. 根據(jù)定理1 和2 可知, 要使得4 階2-XOR 矩陣是迭代MDS 矩陣, 則其迭代次數(shù)必≥4. 接下來考慮(2,4) 迭代MDS 矩陣的構(gòu)造. 根據(jù)第3 節(jié)的搜索策略, 通過對(duì)2-XOR 矩陣的篩選, 滿足迭代4 次后的矩陣不含零元, 且MDS 條件多項(xiàng)式不等于零的矩陣僅有兩類不同的置換相似類. 用未知元X1,X2,··· ,X6分別表示非零元, 篩選和分類結(jié)果見表6.

表6 (2, 4) 迭代MDS 矩陣類型Table 6 Permutation similarity classes of (2, 4) iterative MDS matrices

顯然, 矩陣M1即為文獻(xiàn)[2] 中所提出的稀疏型DSI 矩陣. 進(jìn)一步搜索, 在F24上可得異或數(shù)最小為10 的(2,4) 迭代MDS 矩陣

其中α是生成多項(xiàng)式X4+X+1 的根. 這正是文獻(xiàn)[2] 中所構(gòu)造的最優(yōu)稀疏DSI 矩陣. 除此之外, 置換相似類W2也可以構(gòu)造同樣優(yōu)異的迭代MDS 矩陣. 取

當(dāng)A ∈M4(F24),α是生成多項(xiàng)式X4+X+1 的根時(shí),A4是MDS 矩陣且XOR(A) = 2XOR(α)+2×4 = 10; 當(dāng)A ∈M4(F28),α是生成多項(xiàng)式X8+X4+X3+X2+1 的根時(shí),A4也是MDS 矩陣且XOR(A)=2XOR(α)+2×8=22.

注6 異或數(shù)為10, 是M4(F24) 中非零元個(gè)數(shù)為6, 迭代次數(shù)為4 的迭代MDS 矩陣的異或數(shù)所能達(dá)到的最小值(文獻(xiàn)[1], 引理18). 異或數(shù)為22 也是M4(F28) 中非零元個(gè)數(shù)為6, 迭代次數(shù)為4 的迭代MDS 矩陣的異或數(shù)所能達(dá)到的最小值. 這是由于k ≥3 時(shí),M4(F28) 中矩陣含有固定的異或數(shù)km ≥24,不可能構(gòu)造異或數(shù)比22 更小的(k,4) 迭代MDS 矩陣. 而對(duì)于(2,4) 迭代MDS 矩陣, 至少存在2 個(gè)非零元取值不為1, 且在生成多項(xiàng)式為X8+X4+X3+X2+1 的域F28中, 非0, 1 的元素的異或數(shù)最小等于3.

我們將得到的4 階(2,4) 迭代MDS 矩陣結(jié)果與已知結(jié)果進(jìn)行了比較, 見表7.

表7 4 階(2, 4) 迭代MDS 矩陣結(jié)果的比較Table 7 Comparison of known results on (2, 4) iterative MDS matrices of order 4

4.3 5 階(4, 4) 迭代MDS 矩陣

對(duì)于5 階矩陣, 經(jīng)過實(shí)驗(yàn)計(jì)算我們發(fā)現(xiàn), 要使得矩陣迭代次數(shù)小于矩陣階數(shù), 如取迭代次數(shù)為4 時(shí), 必有矩陣非零元個(gè)數(shù)≥9. 考慮構(gòu)造(4,4) 迭代MDS 矩陣. 我們找到了域F28上最小異或數(shù)為38 的(4,4)迭代MDS 矩陣. 如矩陣

其中α是F28上生成多項(xiàng)式X8+X4+X3+X2+1 的根.A4是MDS 矩陣且XOR(A)=XOR(α)+XOR(α-1)+4×8=3+3+32=38.

類似的, 文獻(xiàn)[5,6,8] 利用友矩陣構(gòu)造5 階迭代MDS 矩陣時(shí), 矩陣非零元個(gè)數(shù)等于9, 即構(gòu)造的是(4,5) 迭代MDS 矩陣. 根據(jù)迭代矩陣的第二個(gè)優(yōu)化方向, 本文對(duì)迭代次數(shù)等于5 的5 階矩陣, 將其非零元個(gè)數(shù)減小為8 個(gè), 對(duì)(3,5) 迭代MDS 矩陣進(jìn)行了搜索. 在F28上, 我們找到了異或數(shù)最小等于35 的(3,5) 迭代MDS 矩陣. 如矩陣

其中α是生成多項(xiàng)式X8+X7+X6+X+1 的根.A5和B5都是MDS 矩陣且XOR(A)=XOR(B)=2XOR(α)+XOR(α2)+3×8=2×3+5+24=35. 這個(gè)結(jié)果也是該域上異或數(shù)最低的迭代MDS 矩陣,通過本文的搜索策略可以找到所有異或數(shù)最低的(3,5) 迭代MDS 矩陣, 包括稀疏DSI(3,5) 迭代MDS矩陣[2], 另外還找到了迭代次數(shù)等于5, 異或數(shù)為35 的一般類型(3,5) 迭代MDS 矩陣, 結(jié)果比較見表8.

表8 5 階迭代MDS 矩陣結(jié)果的比較Table 8 Comparison of known results on iterative MDS matrices of order 5

注7 矩陣A即為文獻(xiàn)[2] 中構(gòu)造的5 階稀疏DSI 迭代MDS 矩陣, 此處計(jì)算該DSI 矩陣的異或數(shù)使用的是本文統(tǒng)一的度量方式, 在文獻(xiàn)[2] 中通過優(yōu)化矩陣實(shí)現(xiàn)過程, 使實(shí)現(xiàn)該矩陣只需31 個(gè)異或數(shù).

5 總結(jié)

本文首先研究了迭代次數(shù)為3 的4 階迭代MDS 矩陣所含非零元個(gè)數(shù)的下界, 證明了其下界為7.通過非零元位置的選擇、矩陣的置換相似分類和非零位置元素的確定, 實(shí)現(xiàn)了非零元個(gè)數(shù)達(dá)到下界7 的4 階迭代MDS 矩陣的窮搜. 進(jìn)一步為了得到更加輕量的結(jié)果, 考慮7 個(gè)非零元中可以取值為1 的個(gè)數(shù).實(shí)驗(yàn)結(jié)果表明, 7 個(gè)非零元中最多5 個(gè)可以取值為1. 在此情形下, 我們?cè)贔24上找到了非零元個(gè)數(shù)達(dá)到最小值7, 異或數(shù)也達(dá)到最小值為15 的4 階迭代MDS 矩陣, 在保證矩陣非零元個(gè)數(shù)相同且異或數(shù)相等的情況下, 實(shí)現(xiàn)了迭代次數(shù)的降低; 在F28上找到了非零元個(gè)數(shù)達(dá)到最小值7, 異或數(shù)為30 的4 階迭代MDS 矩陣, 實(shí)現(xiàn)了迭代次數(shù)的降低同時(shí)也有著更低的異或數(shù). 隨后, 我們也證明得到了迭代次數(shù)分別為2、4 的4 階迭代MDS 矩陣, 以及通過實(shí)驗(yàn)得到迭代次數(shù)為4 的5 階迭代MDS 矩陣所含非零元個(gè)數(shù)的下界. 利用同樣的搜索策略, 我們也找到了非零元個(gè)數(shù)達(dá)到下界, 矩陣異或數(shù)也達(dá)到最小值的一般型輕量迭代MDS 矩陣.