一種新的面向硬件輕量級(jí)near-MDS矩陣的構(gòu)造算法*

張怡帆,任炯炯,陳少真

1.解放軍信息工程大學(xué),鄭州450001

2.數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室,鄭州450001

1 引言

線性擴(kuò)散層是對(duì)稱密碼的一個(gè)重要組件,它為對(duì)稱密碼算法提供了內(nèi)部獨(dú)立性.對(duì)于對(duì)稱密碼算法來(lái)說(shuō),其線性擴(kuò)散層是設(shè)計(jì)時(shí)需要重點(diǎn)考慮的關(guān)鍵部件.我們用分支數(shù)來(lái)衡量一個(gè)擴(kuò)散層的安全性,分支數(shù)較大的擴(kuò)散層能更好地抵抗差分和線性攻擊.在資源受限的環(huán)境下,不僅需要考慮安全性,而且要關(guān)注輕量級(jí)密碼算法擴(kuò)散層的硬件效率.隨著輕量級(jí)密碼的快速發(fā)展[1–4],如何構(gòu)造分支數(shù)較大,硬件效率高的輕量級(jí)擴(kuò)散層引起人們的重視.

分支數(shù)達(dá)到最大的矩陣稱作MDS矩陣,能實(shí)現(xiàn)最好的擴(kuò)散效果,因此許多MDS矩陣如遞歸MDS矩陣和對(duì)合MDS矩陣的構(gòu)造方法被提出[5–16].許多算法諸如AES 等的線性擴(kuò)散層采用MDS矩陣以期達(dá)到最好的擴(kuò)散性,但MDS矩陣中的每一個(gè)元素均為非零,因此在硬件應(yīng)用時(shí)耗能較大,效率較低.在資源受限的今天,算法實(shí)現(xiàn)起來(lái)較為困難.隨著物聯(lián)網(wǎng)技術(shù)等普適計(jì)算的發(fā)展,對(duì)硬件提出了新的安全需求,輕量級(jí)密碼的研究領(lǐng)域越來(lái)越受重視.輕量級(jí)密碼算法對(duì)安全性的要求相較來(lái)說(shuō)有所降低,而如何在保證安全性的前提下提高效率受到了廣泛關(guān)注.

2008年,Choy[17]和Khoo[9]將差分分支數(shù)達(dá)到次優(yōu)的矩陣定義為almost-MDS矩陣,由于兩篇文章中的almost-MDS矩陣對(duì)應(yīng)不同文獻(xiàn)給出的線性碼定義,因此將差分與線性分支數(shù)均達(dá)到次優(yōu)的矩陣稱為near-MDS矩陣.與MDS矩陣相比,near-MDS矩陣的分支數(shù)僅次于MDS矩陣,安全性也僅次于MDS矩陣,但其具有實(shí)現(xiàn)代價(jià)小的優(yōu)勢(shì).在對(duì)安全性的要求降低,實(shí)現(xiàn)代價(jià)要求提高的資源受限環(huán)境下,用near-MDS矩陣作為擴(kuò)散層是一個(gè)很好的選擇.實(shí)際上,一些用near-MDS矩陣構(gòu)造的擴(kuò)散層在硬件應(yīng)用上的表現(xiàn)優(yōu)于MDS矩陣或者迭代MDS矩陣.近來(lái),near-MDS矩陣已經(jīng)被許多輕量級(jí)分組密碼采用,包括PRINCE[18]、FIDES[19]、PRIDE[20]、Midori[21]和MANTIS[22]等.Near-MDS矩陣被廣泛應(yīng)用在低消耗低延遲的輕量級(jí)分組密碼的設(shè)計(jì)中,因此研究此類(lèi)矩陣具有一定的密碼學(xué)價(jià)值和現(xiàn)實(shí)意義.

有限域F2m中的每個(gè)元素都可以表示成F2上的m×m矩陣,所以F2m上的MDS矩陣實(shí)際上對(duì)應(yīng)著F2上的一個(gè)分塊矩陣,每一塊都是m×m大小,需要注意的是,并不是F2上的每一個(gè)矩陣都可以代表有限域F2m內(nèi)的一個(gè)元素,這取決于它的最小多項(xiàng)式是否為不可約的.Li[23]利用有限域F2m內(nèi)的元素作為擴(kuò)散矩陣的元素,在F24上構(gòu)造出10 個(gè)XORs 最少的4×4 near-MDS矩陣.但是有限域F2m內(nèi)的元素乘法問(wèn)題[5]只是上線性變換的一種特殊形式,在上還存在著許多不能用有限域F2m中的元素乘法表示的線性變換[10],上的線性變換空間可以表示為F2上的m×m矩陣.因此,若只考慮在有限域F2m中構(gòu)造MDS矩陣有可能會(huì)導(dǎo)致丟失一些較好的構(gòu)造結(jié)果,在上的線性變換空間中,有可能構(gòu)造出新的符合要求的輕量級(jí)near-MDS矩陣.在之前的構(gòu)造方法中,用來(lái)構(gòu)造矩陣的元素滿足成對(duì)交換,或者假定滿足成對(duì)交換[24,25],但該假定條件也可能會(huì)導(dǎo)致丟失較好的構(gòu)造結(jié)果,所以本文中,沒(méi)有假定用來(lái)構(gòu)造near-MDS矩陣的上的線性變換是成對(duì)交換的.

在對(duì)稱密碼算法中,最常用的是4 比特S盒和8 比特S盒,最常用擴(kuò)散矩陣的維度是4.當(dāng)矩陣維度較大時(shí),計(jì)算復(fù)雜度會(huì)變得非常復(fù)雜,因此將重點(diǎn)放在利用和上的線性變換來(lái)構(gòu)造4×4 near-MDS矩陣上.本文利用直接將F2上的m×m矩陣作為擴(kuò)散矩陣元素的方法,利用循環(huán)矩陣、對(duì)合矩陣的性質(zhì)給出了循環(huán)對(duì)合矩陣元素間滿足的性質(zhì)引理,利用引理給出算法搜索的約束條件,并借助Matlab 構(gòu)造出4×4 循環(huán)對(duì)合near-MDS矩陣,在m=4時(shí)可以找到48 個(gè)滿足條件XORs 最少的4×4 循環(huán)對(duì)合near-MDS矩陣,m=8時(shí),依據(jù)文獻(xiàn)[9,14,26]中提到的子域構(gòu)造方法,可直接得到異或操作數(shù)最少的8×8 循環(huán)對(duì)合near-MDS矩陣,較之前結(jié)果找到了更多的XORs 最少的循環(huán)對(duì)合near-MDS矩陣,且計(jì)算復(fù)雜度較小,在Windows 10 系統(tǒng)、i5-6200U CPU 處理器、4 G 內(nèi)存的機(jī)器條件下僅需要大概6 分鐘.

本文結(jié)構(gòu)安排如下:第2 節(jié)給出了本文所涉及的符號(hào)表示及相關(guān)基礎(chǔ)知識(shí); 第3 節(jié)給出對(duì)near-MDS矩陣內(nèi)元素的一個(gè)基本限制條件以及對(duì)合循環(huán)near-MDS矩陣的構(gòu)造方法,并給出了自動(dòng)搜索算法以及結(jié)果; 第4 節(jié)給出了一個(gè)簡(jiǎn)短的總結(jié).附錄中記錄了本文所有的搜索結(jié)果.

2 基礎(chǔ)知識(shí)

2.1 符號(hào)表示

XORs:異或操作次數(shù);

Bd(L):矩陣L的差分分支數(shù);

Bl(L):矩陣L的線性分支數(shù);

#A:A·x所需的異或操作次數(shù);

ω(A[i]):矩陣A中第i行非零元素的個(gè)數(shù).

2.2 相關(guān)基礎(chǔ)知識(shí)

本節(jié)介紹一些相關(guān)的基礎(chǔ)概念和定義.

2.2.1 分支數(shù)

對(duì)x,y∈,若映射A:→滿足A(x+y)=A(x)+A(y),則稱為線性映射.在F2上固定的一組基,則上的一個(gè)線性映射可以表示為F2上的一個(gè)m×m矩陣,我們用A來(lái)表示,滿足A(x)=A·x,其中x=(x1,··· ,xm)∈,在本文中代表一個(gè)列向量.一個(gè)線性映射是上的一個(gè)置換當(dāng)且僅當(dāng)它的矩陣表示是非奇異的.GL(m,S)代表所有m×m的非奇異矩陣,矩陣中元素屬于S,S是一個(gè)元素集.

每個(gè)線性擴(kuò)散層都是一個(gè)線性映射,可以用如下矩陣表示:

其中Li,j是F2上的m×m矩陣,對(duì)X=(x1,··· ,xn)∈L(X)=其中對(duì)于X=(x1,···,xn)∈中非零元素的個(gè)數(shù)定義為重量,用

定義1矩陣L是上的n×n矩陣,L的差分分支數(shù)定義為

L的線性分支數(shù)定義為

分支數(shù)可以用線性碼的最小距離來(lái)表示.

定理1[27]假設(shè)矩陣L是上的n×n矩陣,C是上的一個(gè)[2n,n]線性碼,它的生成矩陣是(In|LT),其中In是一個(gè)n維單位矩陣.則矩陣L的差分分支數(shù)等價(jià)于線性碼C的最小距離,即Bd(L)=d(C).此外,Bl(L)=d(C⊥),其中C⊥是C的共軛碼.

令C是一個(gè)[N,k]線性碼,當(dāng)C的最小距離達(dá)到上界d(C)=N?k+1[28]時(shí),我們稱其為一個(gè)MDS 線性碼.若生成矩陣是(Ik|LT)的線性碼CL是一個(gè)MDS 線性碼,則稱矩陣L是MDS矩陣.MDS矩陣的差分分支數(shù)和線性分支數(shù)同時(shí)達(dá)到上界[29],即Bl(L)=d(CL)=N?k+1.

MDS矩陣分支數(shù)達(dá)到最大,能實(shí)現(xiàn)最好的擴(kuò)散效果,但是由于MDS矩陣的每一個(gè)元素均為非零,在硬件應(yīng)用時(shí)耗能較大,效率較低.為折衷考慮安全性與效率的問(wèn)題,本文主要研究非MDS矩陣中分支數(shù)達(dá)到最大的矩陣,下面我們給出near-MDS矩陣的定義.

定義2當(dāng)Bd(L)=Bl(L)=d(CL)=n時(shí),上的n×n矩陣L是near-MDS矩陣.

在文獻(xiàn)[29]中,一個(gè)[n,k]線性碼C滿足條件d(C)=n?k,d(C⊥)=k.那么根據(jù)定理1,若一個(gè)n×n矩陣L滿足Bd(L)=Bl(L)=n,那么矩陣(In|LT)是一個(gè)[2n,n,n]near-MDS 線性碼的生成矩陣.由此我們給出定理2.

定理2[30]L是一個(gè)n維的非MDS矩陣,n是一個(gè)正整數(shù)且n≥2.則L是一個(gè)near-MDS矩陣的充要條件是:對(duì)任意的1≤g≤n?1,矩陣L的每一個(gè)g×(g+1)子矩陣和(g+1)×g子矩陣都至少有一個(gè)非奇異的g×g子矩陣.

由定理2 可知,當(dāng)n較大時(shí),為驗(yàn)證near-MDS矩陣的性質(zhì),計(jì)算量會(huì)相當(dāng)復(fù)雜.因此本文重點(diǎn)研究4×4 矩陣,這是在密碼算法中被廣泛使用的矩陣大小.本文利用循環(huán)矩陣來(lái)構(gòu)造輕量級(jí)near-MDS矩陣,循環(huán)矩陣可以用第一行的元素來(lái)定義,因此可以重復(fù)利用元件,提高硬件應(yīng)用效率.

定理3[11]對(duì)任意置換矩陣P1和P2,矩陣L和P1LP2有相同的差分和線性分支數(shù).

由定理3 可得,當(dāng)循環(huán)矩陣Circ(A,B,C,D)的第一行元素發(fā)生位置改變時(shí),矩陣的分支數(shù)保持不變.

2.2.2 XOR 數(shù)

a,b∈F2,a+b被稱為比特XOR 運(yùn)算.對(duì)于A∈GF(m,F2),#A表示A·x所需的XOR 操作次數(shù),其中表示矩陣A中第i行非零元素的個(gè)數(shù).例如為方便描述,本文用矩陣每一行非零元素的位置給出一個(gè)矩陣的簡(jiǎn)單表達(dá)式,例如[2,3,4,[1,4]]是矩陣A的簡(jiǎn)單表達(dá)式.

對(duì)之前給出的矩陣L=令X=(x1,··· ,xn)∈我們給出所需要的異或操作數(shù),其中Li,j(xj)=以矩陣L的第一行為例,所需的異或操作數(shù)為#L1,1+#L1,2+···+#L1,n+(l?1)·m,l為第一行中非零Li,j的個(gè)數(shù).

2.2.3 循環(huán)矩陣

特殊矩陣具有特殊的結(jié)構(gòu)特點(diǎn),其特點(diǎn)在應(yīng)用過(guò)程中可能有利于降低硬件耗能,因此考慮借助特殊矩陣形式來(lái)構(gòu)造擴(kuò)散矩陣.本小節(jié)給出本文所用特殊矩陣的定義.

定義3一個(gè)矩陣被稱為循環(huán)矩陣當(dāng)且僅當(dāng)它的每一行都是前一行向右(向左)循環(huán)一個(gè)元素的位置.

例如對(duì)一個(gè)4×4 的循環(huán)矩陣我們表示為:Circ(A,B,C,D)=循環(huán)矩陣每一行的元素均與第一行相同,在硬件應(yīng)用時(shí)可以重復(fù)利用乘法元件,進(jìn)而大大提高硬件應(yīng)用效率,因此被很多輕量級(jí)密碼算法所采用.

3 輕量級(jí)循環(huán)near-MDS矩陣

本節(jié)研究輕量級(jí)循環(huán)對(duì)合near-MDS矩陣的構(gòu)造方法,證明矩陣元素滿足循環(huán)對(duì)合性質(zhì)所必須遵循的性質(zhì)引理,根據(jù)引理,給出了搜索算法的約束條件條件,借助Matlab 尋找滿足條件的異或數(shù)最少的矩陣.本文搜索到了48 個(gè)滿足條件的循環(huán)對(duì)合near-MDS矩陣,較之前搜索結(jié)果更多,并且減少了搜索的時(shí)間復(fù)雜度,在Windows 10 系統(tǒng)、i5-6200U CPU 處理器、4 G 內(nèi)存的機(jī)器條件下需要大概6 分鐘.

3.1 Near-MDS矩陣的元素限制條件

near-MDS矩陣的分支數(shù)達(dá)到次優(yōu),其矩陣元素有如下特點(diǎn):

引理1假設(shè)循環(huán)矩陣Circ(A,B,C,D)是一個(gè)near-MDS矩陣,則矩陣元素A,B,C,D中至多有一個(gè)為零矩陣O.

證明:若A,B,C,D中有兩個(gè)元素為O,假設(shè)為A,B.根據(jù)定理2,當(dāng)g=1時(shí)矩陣Circ(A,B,C,D)有一個(gè)1×2 的子矩陣不滿足至少有一個(gè)1×1 的子矩陣是非奇異的,與定理2 給出的near-MDS 性質(zhì)矛盾.所以矩陣元素A,B,C,D中至多有一個(gè)為零矩陣O.

本文的主要目標(biāo)是減少搜索范圍,尋找 XORs 最少的 near-MDS矩陣.根據(jù)引理1,假設(shè)Circ(A,B,C,D)中一直存在一個(gè)零矩陣O,根據(jù)定理3,循環(huán)矩陣第一行元素位置發(fā)生變化時(shí),矩陣的分支數(shù)保持不變,因此本文重點(diǎn)研究Circ(O,A,B,C)這種形式的矩陣.

3.2 構(gòu)造循環(huán)對(duì)合矩陣

循環(huán)矩陣元素排列有很明顯的特點(diǎn),若要一個(gè)循環(huán)矩陣Circ(O,A,B,C)同時(shí)滿足對(duì)合性,其元素相互之間也存在一定的約束條件,對(duì)此本文有如下結(jié)果:

引理2L=Circ(O,A,B,C)是一個(gè)循環(huán)矩陣,其中A,B,C∈GL(m,F2).矩陣L滿足對(duì)合性當(dāng)且僅當(dāng)下列等式同時(shí)滿足:AB=BA,BC=CB,A2=C2,AC+CA+B2=I.

證明:通過(guò)矩陣乘法,可以得到

若矩陣L具有對(duì)合性,則滿足條件L2=Circ(I,0,0,0),因此L是一個(gè)對(duì)合矩陣當(dāng)且僅當(dāng)下列條件同時(shí)滿足:AB=BA,BC=CB,A2=C2,AC+CA+B2=I.

由引理2 給出的矩陣Circ(O,A,B,C)滿足對(duì)合性其元素之間具有的約束條件,下面給出循環(huán)對(duì)合矩陣的一般構(gòu)造方法.首先我們給出乘法階的定義:對(duì)于矩陣A∈GL(m,F2),滿足等式Ad=I的最小正整數(shù)d稱為A的乘法階.

引理3假設(shè)A,C∈GL(m,F2)且滿足條件A2=C2=I,I+A+C的乘法階為4k?2,其中k≥1.令B=(I+A+C)2k,則矩陣Circ(O,A,B,C)是一個(gè)對(duì)合矩陣.

證明:令B=(I+A+C)2k,因?yàn)锳和C滿足條件A2=C2=I,根據(jù)引理2,我們只需證明下面等式即可:

首先容易證明

然后可得B=(I+A+C)2k=(I+AC+CA)k.因此

同理我們可以證得BC=CB.因?yàn)?I+A+C)4k?2=I,因此我們可以得到

根據(jù)引理3,我們得到了矩陣Circ(O,A,(I+A+C)2k,C)是對(duì)合矩陣.

注意:當(dāng)A=C時(shí),(I+A+C)的乘法階為1,不滿足4k?2 的條件.這種情況下L=Circ(O,A,B,C)=Circ(O,A,B,A)仍為一個(gè)循環(huán)矩陣,若要滿足對(duì)合性應(yīng)同時(shí)滿足條件B2=I,AB=BA,根據(jù)條件仍可尋找循環(huán)對(duì)合矩陣.

由引理2、引理3,我們給出要使矩陣滿足循環(huán)對(duì)合性,矩陣元素所需滿足的條件,利用引理給出自動(dòng)搜索算法的約束條件,進(jìn)而可以很大程度減小搜索范圍.再利用定理2 給出的near-MDS矩陣的特性,借助Matlab,進(jìn)一步搜索循環(huán)對(duì)合near-MDS矩陣.下面給出算法介紹以及搜索結(jié)果.

3.3 自動(dòng)化搜索算法及結(jié)果

在上一節(jié)中我們推導(dǎo)出滿足循環(huán)對(duì)合條件的矩陣元素之間所需滿足的條件

(1)A=C時(shí),A2=C2=I,(I+A+C)4k?2=I,k≥1,B=(I+A+C)2k.

(2)A=C時(shí),B2=I,AB=BA.

將矩陣元素所滿足的式子轉(zhuǎn)化為算法中的約束條件,縮小搜索范圍,在得到循環(huán)對(duì)合矩陣之后進(jìn)一步檢驗(yàn)其是否具有near-MDS矩陣的性質(zhì),最終獲得循環(huán)對(duì)合near-MDS矩陣.構(gòu)造算法步驟如下:

首先獲得一個(gè)集合S,其中包含所有滿足對(duì)合性的矩陣.然后分以下兩種情況討論:

(1)A=C時(shí),我們選取矩陣對(duì)(A,C)∈S×S,計(jì)算I+A+C的乘法階d,若dmod 4=2,則是循環(huán)對(duì)合矩陣.

(2)A=C時(shí),選取B∈S,若滿足AB=BA,則Circ(O,A,B,A)是循環(huán)對(duì)合矩陣.

本文借助Matlab 計(jì)算機(jī)程序,通過(guò)添加對(duì)矩陣元素的限制條件縮小搜索范圍,對(duì)滿足條件的循環(huán)對(duì)合near-MDS矩陣進(jìn)行算法搜索.為尋找異或數(shù)最少的矩陣,矩陣元素集S的選擇在搜索算法中起到了關(guān)鍵的作用,一般來(lái)說(shuō),元素的XORs 越少,矩陣的XORs 也會(huì)相應(yīng)較少,因此在選擇矩陣元素集時(shí),首先從XORs 最少的矩陣集S開(kāi)始搜索.因?yàn)閄ORs 最少為0,所以本文首先尋找滿足對(duì)合性且XORs 為0即非零元素個(gè)數(shù)為4 的矩陣,將其作為矩陣集S,在S中搜索是否存在滿足上述兩種情況之一(A,B,C).若不存在,則擴(kuò)大矩陣集S的范圍,尋找滿足對(duì)合性且XORs 為0 或者XORs 為1 的矩陣,將其作為矩陣集S進(jìn)行搜索.以此類(lèi)推,直到找到滿足條件的(A,B,C).

其次,在得到循環(huán)對(duì)合矩陣后我們要驗(yàn)證其是否為near-MDS矩陣,根據(jù)定理2 給出的near-MDS 性質(zhì),對(duì)任意的1≤g≤n?1,矩陣L的每一個(gè)g×(g+1)子矩陣和(g+1)×g子矩陣都至少有一個(gè)非奇異的g×g子矩陣.若一個(gè)矩陣為非奇異矩陣,則其行列式一定不為0.為驗(yàn)證near-MDS 性質(zhì),對(duì)于一個(gè)g×(g+1)子矩陣或者(g+1)×g子矩陣,我們需要計(jì)算其所有的g×g子矩陣行列式的絕對(duì)值,為保證至少有一個(gè)非奇異的g×g子矩陣,應(yīng)滿足所有的g×g子矩陣的行列式絕對(duì)值之和大于0.由此,為驗(yàn)證所構(gòu)造循環(huán)對(duì)合矩陣是否為near-MDS矩陣,本節(jié)給出如下引理及證明.

引理4令d1,d2,··· ,dk≥0 代表k個(gè)正數(shù)值,其中k是一個(gè)正整數(shù),若d1,d2,··· ,dk中至少有一個(gè)非零值當(dāng)且僅當(dāng)d1+d2+···+dk>0.

證明:因?yàn)閐1,d2,··· ,dk≥0,要滿足d1+d2 +···+dk=0,當(dāng)且僅當(dāng)d1=d2=···=dk=0,與所給條件矛盾.因此應(yīng)滿足d1+d2+···+dk>0.

綜合考慮之前給出的元素約束條件以及near-MDS矩陣性質(zhì)驗(yàn)證方法,利用Matlab 計(jì)算機(jī)程序,給出的具體搜索算法.見(jiàn)算法1.

算法1 構(gòu)造循環(huán)對(duì)合矩陣并檢驗(yàn)near-MDS矩陣的性質(zhì)Input:矩陣元素限制條件; 4×4 循環(huán)矩陣Circ(O,A,B,C);Output:循環(huán)對(duì)合near-MDS矩陣Circ(O,A,B,C)1 S ←?;2 if N2=I & & #N=4 then 24 for g ∈[1,n?1]do 25 for 矩陣T 所有g(shù)×(g+1)和(g+1)×g 子矩陣M do 3 N ∈S;4 end 5 for A=C do 26 p ←0;27 for 矩陣M 的所有g(shù)×g 子矩陣N do 6(A,C)∈S×S;7 計(jì)算I +A+C 的乘法階d ;8 if d mod 4=2 then 28 計(jì)算行列式det(N)的絕對(duì)值q;29 p ←p+q;30 if p=0 then 9 B=(I +A+C)d2+1;10 end 11 end 12 for A=C do 31 return false;32 end 33 else 13 B ∈S;14 if AB=BA then 15 T=Circ(O,A,B,C);16 end 17 end 18 if 不存在(A,B,C)滿足條件then 34 T=Circ(O,A,B,C)是一個(gè)循環(huán)對(duì)合35 near-MDS矩陣36 end 37 end 38 end 39 end 40 return T 19 重新選擇矩陣集S;20 if N2=I & & #N=4+1=5 then 21 N ∈S;22 end 23 end

搜索結(jié)果如下:

m=4時(shí),本文選取S∈GL(4,F2).首先搜索XORs 為0 的矩陣集S,在S中搜索到了滿足Circ(O,A,B,C)是near-MDS矩陣的(A,B,C),并且#A+#B+#C=0,達(dá)到了矩陣第一行元素異或操作數(shù)之和的最小值.利用上述算法我們找到了48 組滿足條件的(A,B,C),其中有36 組滿足A=C,12 組滿足A=C.

實(shí)例:

(1)m=4 且A=C時(shí),A=[4,2,3,1],C=[4,2,3,1],B=[1,3,2,4].

(2)m=4 且A=C時(shí),A=[3,4,1,2],C=[4,3,2,1],B=[1,2,3,4].

m=8時(shí),因?yàn)橐呀?jīng)構(gòu)造出m=4時(shí)滿足#A+#B+#C=0 的循環(huán)對(duì)合near-MDS矩陣,根據(jù)文獻(xiàn)[9,14,26]中提到的子域構(gòu)造方法,我們很容易在GL(8,F2)中構(gòu)造出滿足#A+#B+#C=0 的循環(huán)對(duì)合near-MDS矩陣.舉例介紹子域構(gòu)造方法,令X,Y,Z∈GL(4,F2),#X=#Y=#Z=0 并且Circ(O,X,Y,Z)是一個(gè)循環(huán)對(duì)合near-MDS矩陣,則對(duì)A,B,C∈GL(8,F2),Circ(O,A,B,C)也是一個(gè)循環(huán)對(duì)合near-MDS矩陣,其中

實(shí)例:

(1)m=8 且A=C時(shí),A=[4,2,3,1,8,6,7,5],C=[4,2,3,1,8,6,7,5],B=[1,3,2,4,5,7,6,8].

(2)m=8 且A=C時(shí),A=[3,4,1,2,7,8,5,6],C=[4,3,2,1,8,7,6,5],B=[1,2,3,4,5,6,7,8].

表1 給出了用本文方法構(gòu)造的滿足條件的矩陣數(shù)與已知的用有限域內(nèi)元素乘法問(wèn)題構(gòu)造的矩陣數(shù)的比較,可以看出本文構(gòu)造出了較之前結(jié)果更多的滿足條件的矩陣,這對(duì)算法的設(shè)計(jì)具有一定的借鑒意義.所有的構(gòu)造算法結(jié)果見(jiàn)附錄.

表1 本文結(jié)果與文獻(xiàn)[22]結(jié)果對(duì)比Table 1 Compare results of proposed method and Ref.[22]

4 總結(jié)

在資源受限的環(huán)境下,輕量級(jí)密碼算法擴(kuò)散層的設(shè)計(jì)更加注重硬件效率.隨著輕量級(jí)密碼的快速發(fā)展,構(gòu)造分支數(shù)較大,硬件效率高的輕量級(jí)擴(kuò)散層是一個(gè)亟需解決的問(wèn)題.

本文主要探索了用F2上的m×m矩陣來(lái)構(gòu)造4×4 輕量級(jí)near-MDS矩陣的方法,理論上證明了如何判斷循環(huán)對(duì)合的性質(zhì)引理,在此基礎(chǔ)上,將引理?xiàng)l件轉(zhuǎn)化為自動(dòng)搜索算法的約束條件,給出了Matlab程序編譯算法,實(shí)現(xiàn)了對(duì)滿足條件矩陣的算法搜索.利用循環(huán)矩陣和對(duì)合矩陣的特性推導(dǎo)出矩陣元素之間的關(guān)系,在Matlab 算法搜索過(guò)程中添加矩陣元素的約束條件,縮小搜索范圍,降低復(fù)雜度.同時(shí)選擇XORs 較少的矩陣元素,以獲得硬件效率高的擴(kuò)散矩陣.本文對(duì)F2上的4×4 循環(huán)對(duì)合near-MDS矩陣進(jìn)行了搜索,找到了48 個(gè)XORs 最少的矩陣,較之前利用有限域內(nèi)元素乘法構(gòu)造的滿足條件的10 個(gè)矩陣,不僅給出滿足條件的矩陣數(shù)量更多,而且降低了搜索的時(shí)間復(fù)雜度.如何利用其它類(lèi)型特殊矩陣的性質(zhì)獲得矩陣元素約束條件以及構(gòu)造更大維度的輕量級(jí)near-MDS矩陣還需要進(jìn)一步的研究與實(shí)驗(yàn).

附錄

(1)A=C,m=4時(shí),滿足B2=I、AB=BA,Circ(O,A,B,C)是上的循環(huán)對(duì)合near-MDS矩陣.我們找到了36 組滿足條件的[A,B].

1.A=[4,3,2,1]B=[4,3,2,1]

2.A=[4,3,2,1]B=[3,4,1,2]

3.A=[4,3,2,1]B=[2,1,4,3]

4.A=[4,3,2,1]B=[1,2,3,4]

5.A=[4,2,3,1]B=[4,2,3,1]

6.A=[4,2,3,1]B=[1,3,2,4]

7.A=[3,2,4,1]B=[1,2,3,4]

8.A=[2,4,3,1]B=[1,2,3,4]

9.A=[3,4,1,2]B=[4,3,2,1]

10.A=[3,4,1,2]B=[3,4,1,2]

11.A=[3,4,1,2]B=[2,1,4,3]

12.A=[3,4,1,2]B=[1,2,3,4]

13.A=[4,2,1,3]B=[1,2,3,4]

14.A=[3,2,1,4]B=[3,2,1,4]

15.A=[3,2,1,4]B=[1,4,3,2]

16.A=[2,3,1,4]B=[1,2,3,4]

17.A=[4,1,3,2]B=[1,2,3,4]

18.A=[3,1,2,4]B=[1,2,3,4]

19.A=[2,1,4,3]B=[4,3,2,1]

20.A=[2,1,4,3]B=[3,4,1,2]

21.A=[2,1,4,3]B=[2,1,4,3]

22.A=[2,1,4,3]B=[1,2,3,4]

23.A=[2,1,3,4]B=[2,1,3,4]

24.A=[2,1,3,4]B=[1,2,4,3]

25.A=[1,4,3,2]B=[3,2,1,4]

26.A=[1,4,3,2]B=[1,4,3,2]

27.A=[1,3,4,2]B=[1,2,3,4]

28.A=[1,4,2,3]B=[1,2,3,4]

29.A=[1,3,2,4]B=[4,2,3,1]

30.A=[1,3,2,4]B=[1,3,2,4]

31.A=[1,2,4,3]B=[2,1,3,4]

32.A=[1,2,4,3]B=[1,2,4,3]

33.A=[1,2,3,4]B=[4,3,2,1]

34.A=[1,2,3,4]B=[3,4,1,2]

35.A=[1,2,3,4]B=[2,1,4,3]

36.A=[1,2,3,4]B=[1,2,3,4]

(2)A=C,m=4時(shí),(I+A+C)2=I,此時(shí)B=(I+A+C)2=I,Circ(O,A,B,C)是上的循環(huán)對(duì)合near-MDS矩陣.我們找到了12 組滿足條件的[A,C].

1.A=[4,3,2,1]C=[3,4,1,2]

2.A=[4,3,2,1]C=[2,1,4,3]

3.A=[4,3,2,1]C=[1,2,3,4]

4.A=[3,4,1,2]C=[4,3,2,1]

5.A=[3,4,1,2]C=[2,1,4,3]

6.A=[3,4,1,2]C=[1,2,3,4]

7.A=[2,1,4,3]C=[4,3,2,1]

8.A=[2,1,4,3]C=[3,4,1,2]

9.A=[2,1,4,3]C=[1,2,3,4]

10.A=[1,2,3,4]C=[4,3,2,1]

11.A=[1,2,3,4]C=[3,4,1,2]

12.A=[1,2,3,4]C=[2,1,4,3]