張 晶, 王 鑫, 張麗娜, 楊 波, 胡冰潔

陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院, 西安710119

1 引言

Shannon[1]提出密碼系統(tǒng)設(shè)計(jì)的兩個(gè)基本原則: 混淆和擴(kuò)散, 分別在迭代型分組密碼的混淆層和擴(kuò)散層具有廣泛應(yīng)用. 混淆層采用非線性的并置S 盒構(gòu)造. 擴(kuò)散層采用有限域(Fm2)n上的線性變換構(gòu)造, 其中m 表示一個(gè)S 盒的比特長(zhǎng)度, n 表示S 盒的個(gè)數(shù). 性能良好的擴(kuò)散層可抵抗差分密碼分析[2]和線性密碼分析[3], 其性能通過(guò)分支數(shù)的大小來(lái)衡量, 其中分支數(shù)指任意連續(xù)兩輪運(yùn)算間最小的活躍S 盒數(shù)目.分支數(shù)達(dá)到最大的擴(kuò)散層為最優(yōu)擴(kuò)散層, 即MDS (Maximum Distance Separable) 擴(kuò)散層, 其本質(zhì)是一個(gè)MDS 線性變換, 它對(duì)應(yīng)的矩陣為MDS 矩陣, 其中最大分支數(shù)為S 盒的數(shù)目加1.

MDS 矩陣被廣泛應(yīng)用于各種分組密碼算法的設(shè)計(jì)中, 例如AES[4]、SMS4[5]、Twofish[6]、FOX[7]、流密碼算法MUGI[8]、散列函數(shù)Maelstrom[9]以及PHOTON 輕量級(jí)散列函數(shù)族[10]等. 目前構(gòu)造MDS矩陣主要方法有[11]: 線性碼[4]、特殊矩陣[12-19]、線性反饋移位寄存器[9,10,20-22](Linear Feedback Shift Register, LFSR)、循環(huán)移位和異或運(yùn)算[23-27](Rotational-XOR) 等. 其中, 利用線性碼、特殊矩陣構(gòu)造的MDS 矩陣硬件實(shí)現(xiàn)效率較低, 因此不適用于資源受限的環(huán)境; 基于LFSR 構(gòu)造MDS 矩陣可節(jié)省內(nèi)存空間, 但需要大量時(shí)鐘周期, 因此不適用于低時(shí)延環(huán)境. 基于Rotational-XOR 構(gòu)造的MDS 線性變換同時(shí)具備利用線性碼、特殊矩陣和LFSR 構(gòu)造的優(yōu)勢(shì), 并能增強(qiáng)密碼算法抵抗各種密碼分析的能力, 故已被很多對(duì)稱密碼算法采用, 例如SMS4 算法、3GPP LTE 國(guó)際加密標(biāo)準(zhǔn)ZUC 算法、MD6、SHA-256 等.

2007 年, Wang[23]提出一個(gè)基于Rotational-XOR 構(gòu)造MDS 線性變換的必要條件: 異或項(xiàng)數(shù)大于等于n+1, 線性變換中有n 項(xiàng)移位的區(qū)間固定; 給出一個(gè)構(gòu)造分塊規(guī)模為4 的MDS 線性變換的通式.2012 年, 李瑞林、熊海等人[24]研究了基于Rotational-XOR 的對(duì)合線性變換, 給出這類線性變換的計(jì)數(shù)公式, 指出它們的分支數(shù)上界為4. 同年, 曹云飛和劉瑤[25]提出一類基于Rotational-XOR、分組規(guī)模為32 的MDS 線性變換的構(gòu)造方法. 2017 年, 郭等人[26]首次在沒(méi)有輔助搜索的前提下構(gòu)造出分塊規(guī)模為4 的MDS 線性變換, 并指出其對(duì)應(yīng)的MDS 矩陣需滿足的必要條件, 利用該條件篩選出此規(guī)模下MDS線性變換的可能形式. 2018 年, 董新峰等人[27]提出一類基于Rotational-XOR 的輕量化MDS 線性變換的最簡(jiǎn)形式和構(gòu)造方法, 并給出分組規(guī)模為16 時(shí)該類MDS 線性變換的計(jì)數(shù)結(jié)果和相應(yīng)實(shí)例. 然而, 以上文獻(xiàn)的研究主要集中在分組規(guī)模為16 和32、分塊規(guī)模為4 的情況, 所得通式也不適用于更大規(guī)模. 基于Rotational-XOR 且具有時(shí)延低、運(yùn)算快、計(jì)算資源小等特性, 研究更大規(guī)模下的MDS 線性變換將縮短數(shù)據(jù)加解密所用的時(shí)間, 使信息傳輸更加高效.

本文在文獻(xiàn)[23,26] 的基礎(chǔ)上研究分組規(guī)模為64、分塊規(guī)模為8 的MDS 線性變換的必要條件, 探尋該規(guī)模下的MDS 線性變換. 首先通過(guò)分析首行矩陣的性質(zhì), 給出MDS 矩陣的一個(gè)必要條件為矩陣中不可能有連續(xù)三個(gè)矩陣塊相同, 根據(jù)該條件證明此規(guī)模下異或項(xiàng)數(shù)取最小值9 項(xiàng)時(shí)不存在MDS 線性變換,并利用Magma 軟件驗(yàn)證該結(jié)論. 進(jìn)而研究異或項(xiàng)數(shù)為11 項(xiàng)時(shí)的MDS 線性變換, 將此情況下的所有線性變換分為三種情況, 分別是一個(gè)矩陣中至多有一個(gè)自由項(xiàng)、存在兩個(gè)自由項(xiàng)落在同一矩陣中和三個(gè)自由項(xiàng)恰好落在同一矩陣中. 這三種情況將該規(guī)模下的88×56×55×54 個(gè)線性變換等價(jià)劃分為15 種形式,設(shè)計(jì)15 個(gè)算法分別搜索后得到此規(guī)模下異或項(xiàng)數(shù)取11 項(xiàng)時(shí)也不存在MDS 線性變換.

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

2.1 基本符號(hào)

2.2 分支數(shù)

定義1 L 的差分分支數(shù)定義為:

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

其中LT是L 的轉(zhuǎn)置.

當(dāng)Bd(L) = Bl(L) = n+1 時(shí), 稱分支數(shù)達(dá)到最大. 此時(shí)L 為MDS 矩陣, 其對(duì)應(yīng)的線性變換L(X)稱為最優(yōu)線性變換或MDS 線性變換.

定義3 定義分塊矩陣L=(Li,j),1 ≤i,j ≤n, 其中(Li,j) 是F2上的m 階方陣, 則有如下形式:

其中, m ＞1 時(shí)稱(L1,1,L1,2,··· ,L1,n) 為L(zhǎng) 的首行矩陣.

定理1[11](MDS 矩陣判定定理) 假設(shè)分塊矩陣L = (Li,j),1 ≤i,j ≤n, 將Li,j看作L 的1 階子矩陣. L 為MDS 矩陣的充要條件是L 的任意t 階子矩陣均滿秩(1 ≤t ≤n).

3 基于Rotational-XOR 的線性變換

其中0 ≤li＜mn, S 是包含I 個(gè)元素的整數(shù)集合.

通過(guò)限制li的區(qū)間, 能夠篩選出可能的MDS 線性變換, 因此給出依據(jù)li判斷MDS 線性變換的必要條件.

引理1[23]L(X) 為MDS 線性變換的必要條件:

(1) 異或項(xiàng)數(shù)I 為奇數(shù), 且I ≥n+1;

(2) 存在n 項(xiàng)li, 滿足mi ≤li＜m(i+1).

根據(jù)引理1 可知MDS 線性變換異或項(xiàng)數(shù)的最小值為n+1, 因此本節(jié)研究I =n+1 時(shí)的線性變換.

其中0 ≤li＜mn, li兩兩互不相等.

由引理1 可知, 此時(shí)L(X) 中僅第n+1 項(xiàng)ln的區(qū)間不受限制, 因此約定ln為自由項(xiàng). 為表述方便,將公式(5)中的li按照從小到大的順序排列, 即令li＜li+1恒成立.

假設(shè)自由項(xiàng)位于區(qū)間[0,m) 內(nèi), 線性變換L(X) 可表示為:

其中0 ≤di＜m,0 ≤i ＜n+1, d1為自由項(xiàng).

定義4 若矩陣的每行元素均由前一行各元素依次循環(huán)右移一個(gè)位置得到, 則稱這個(gè)矩陣為循環(huán)矩陣,形式為:

其中A,B,C,D 既可以是單個(gè)元素, 也可以是t 階方陣(t ＞1).

線性變換L(X) 對(duì)應(yīng)的矩陣L 就是一個(gè)循環(huán)矩陣, 可表示為L(zhǎng) = Circ(L1,L2,··· ,Ln), 其中Li表示m 階方陣(i=1,2,··· ,n). L 首行矩陣的一般形式為圖1 所示.

圖1 L 首行矩陣的一般形式Figure 1 General type of first row’s matrix of L

定義5 若m 階方陣A 表示為t 個(gè)同階對(duì)角矩陣之和的形式, 可定義為:

其中ai,j是F2中的一個(gè)元素, diag(σk) 表示m 階對(duì)角矩陣. diag(σk) 在所有j-i = σk的位置上都滿足ai,j=1, 其余位置上滿足ai,j=0.

滿足定義5 的方陣均可表示為多個(gè)同階對(duì)角矩陣之和的形式. 例如圖2 中的矩陣可表示為A=diag(5)+diag(0)+diag(-3).

圖2 A 的對(duì)角矩陣表示形式: A=diag(5)+diag(0)+diag(-3)Figure 2 Representation of diagonal matrix of A: A=diag(5)+diag(0)+diag(-3)

引理2 L(X) 是MDS 線性變換的必要條件是:

(1) d0／=d1;

(2) di≥di+1, 其中i=2,3,··· ,n-1;

(3) max{d0,d1}≥d2;

(4) min{d0,d1}≤dn.

證明: 假設(shè)L 是MDS 矩陣, 根據(jù)定理1, L 的所有1 階子矩陣均滿秩.

(1) 若d0=d1, 則L1定為奇異矩陣, 因此d0／=d1;

(2) 若di＜di+1,則Li+1中元素個(gè)數(shù)小于m,即Li+1是奇異矩陣,因此di≥di+1(i=2,3,···,n-1);

(3) 假設(shè)d0＜d1, 若此時(shí)d1＜d2, 則L2中元素個(gè)數(shù)小于m, 即L2是奇異矩陣, d1＜d0時(shí)同理,因此需滿足max{d0,d1}≥d2;

(4) 假設(shè)d0＜d1, 若此時(shí)d0＞dn, 則L1中元素個(gè)數(shù)小于m, 即L1是奇異矩陣, d1＜d0時(shí)同理,因此需滿足min{d0,d1}≤dn;綜上所述, 引理2 得證.

引理3[26]若L = Circ(L1,L2,··· ,Ln) 是MDS 矩陣, 當(dāng)L 首行有兩個(gè)連續(xù)相同的矩陣塊時(shí), 其它任意兩個(gè)連續(xù)矩陣塊之和都應(yīng)是非奇異的.

推論1 若L=Circ(L1,L2,··· ,Ln) 是MDS 矩陣, 則L 中不可能有連續(xù)三個(gè)矩陣塊相同.

證明: 假設(shè)L1= L2= L3, 顯然L2+L3是奇異矩陣, 不滿足引理3, 因此MDS 矩陣L 中不存在連續(xù)三個(gè)矩陣塊相同的情況.

4 I = 9 時(shí)有限域(F82)8 上基于Rotational-XOR 的MDS 線性變換的存在性證明

基于Rotational-XOR 的線性變換可用一個(gè)循環(huán)矩陣乘以一個(gè)向量來(lái)表示, 所以通過(guò)研究循環(huán)矩陣L的性質(zhì)可確定()8上MDS 線性變換的存在性. 根據(jù)引理1, 有限域()8上基于Rotational-XOR 的MDS 線性變換最小異或項(xiàng)數(shù)為9 項(xiàng). 令I(lǐng) = 9 且自由項(xiàng)d1位于區(qū)間[0,m), L 首行矩陣的一般形式為圖3 所示(假設(shè)d0＜d1).

為了簡(jiǎn)化, 可用(d0,d1,d2,d3,d4,d5,d6,d7,d8) 唯一地表示一個(gè)線性變換(例如圖4 表示線性變換(0,1,1,1,1,1,1,1,1)). 顯然,圖3 中矩陣C 至矩陣H 均由兩個(gè)對(duì)角矩陣構(gòu)成,可表示為diag(α)+diag(-β).

引理4[26]m 階方陣A=diag(α)+diag(-β)(其中α,β ＞0) 是非奇異的當(dāng)且僅當(dāng)(α+β)|m.

圖3 I =9 時(shí)L 首行矩陣的一般形式Figure 3 Representation of diagonal matrix of L when I =9

圖4 (0,4,4,4,4,4,4,4,4) 的首行矩陣Figure 4 First row’s matrix of (0,4,4,4,4,4,4,4,4)

在表1 中, 行表示diag(α), 列表示diag(-β). 令-β = di-8, α = di+1, “?” 表示這兩個(gè)對(duì)角矩陣之和滿秩.

表1 ()8 上的所有滿秩矩陣A, 其中A = diag(α)+diag(－β),α,β ＞0Table 1 All non-singular matrix A on ()8, where A = diag(α)+diag(－β),α,β ＞0

表1 ()8 上的所有滿秩矩陣A, 其中A = diag(α)+diag(－β),α,β ＞0Table 1 All non-singular matrix A on ()8, where A = diag(α)+diag(－β),α,β ＞0

-β α 1 2 3 4 5 6 7-1? ? ?-2 ? ?-3 ? ?-4 ?-5 ?-6 ?-7 ?

表2 I = 9 時(shí)集合{4} 所有可能的MDS 線性變換Table 2 All possible MDS linear transformation in {4} when I = 9

由表3 可知, 確定集合后di必須按照集合中元素的順序依次選取. 下面對(duì)不同類型的集合分別證明.

表3 I = 9 時(shí)集合{4} 所有可能的MDS 線性變換Table 3 All possible MDS linear transformation in {4} when I = 9

(1) 集合中只有一個(gè)元素. 此時(shí)共有5 種集合可選, 分別是: {1},{2},{3},{4},{0}. 不失一般性地假設(shè)di取自集合{4}. 如圖4 所示, 線性變換(0,4,4,4,4,4,4,4,4) 的首行矩陣中B =C =D =E =F =G=H, 與推論1 矛盾, 所以(0,4,4,4,4,4,4,4,4) 不是MDS 線性變換;

(2) 集合中有兩個(gè)元素. 此時(shí)共有4 種集合可選, 分別是: {1,0}, {2,0},{3,0},{4,0}. 不失一般性地假設(shè)di取自集合{4,0}, 根據(jù)引理1 可知d0≤d8, 因此有d0= 0. 由表3 可知此時(shí)至少有4 個(gè)di取值相同, 與之對(duì)應(yīng), 一定有某三塊連續(xù)的矩陣塊相同. 如圖5 所示, 線性變換(0,4,4,4,4,0,0,0,0)的首行矩陣中B = C = D 且F = G = H, 與推論推論1 矛盾, 所以(0,4,4,4,4,0,0,0,0) 不是MDS 線性變換.

圖5 (0,4,4,4,4,0,0,0,0) 的首行矩陣Figure 5 First row’s matrix of (0,4,4,4,4,0,0,0,0)

由表4 可知, 確定集合后, di必須按照集合中元素的順序依次選取. 下面對(duì)不同類型的集合分別證明.

(1) 集合中只有一個(gè)元素. 此時(shí)共有4 種集合可選, 分別是: {5},{6},{7},{0}. 不失一般性地假設(shè)di取自集合{5}. 如圖6 所示, 線性變換(0,5,5,5,5,5,5,5,5) 的首行矩陣中B = C = D = E = F =G=H, 與推論推論1 矛盾, 所以(0,5,5,5,5,5,5,5,5) 不是MDS 線性變換;

(2) 集合中有兩個(gè)元素. 此時(shí)共有9 種集合可選, 分別是: {5,1},{5,0},{1,0},{6,2},{6,0},{2,0},{7,1},{7,3},{7,0}. 不失一般性地假設(shè)di取自集合{5,1},此時(shí)至少有4 個(gè)di取值相同,與之對(duì)應(yīng),一定有某三塊連續(xù)的矩陣塊相同. 如圖7 所示,線性變換(0,5,5,5,5,1,1,1,1)的首行矩陣中B =C =D且F =G=H, 與推論推論1 矛盾, 所以(0,5,5,5,5,1,1,1,1) 不是MDS 線性變換;

(3) 集合中有三個(gè)元素. 此時(shí)共有4 種集合可選, 分別是: {5,1,0},{6,2,0},{7,1,0},{7,3,0}. 不失一般性地假設(shè)di取自集合{5,1,0}, 由表4 可知此時(shí)至少有3 個(gè)di的取值相同. 如圖8 所示, 線性變換(0,5,5,5,1,1,1,0,0) 的首行矩陣中B = C, 并且G 與H 之和為奇異矩陣, 與引理3 矛盾, 所以(0,5,5,5,1,1,1,0,0) 不是MDS 線性變換.

表4 d0 = 0 及I = 9 時(shí)集合{5,1,0} 所有可能的MDS 線性變換Table 4 All possible MDS linear transformation in {5,1,0} when d0 = 0 and I = 9

圖6 (0,5,5,5,5,5,5,5,5) 的首行矩陣Figure 6 First row’s matrix of (0,5,5,5,5,5,5,5,5)

圖7 (0,5,5,5,5,1,1,1,1) 的首行矩陣Figure 7 First row’s matrix of (0,5,5,5,5,1,1,1,1)

圖8 (0,5,5,5,1,1,1,0,0) 的首行矩陣Figure 8 First row’s matrix of (0,5,5,5,1,1,1,0,0)

其余線性變換的證明過(guò)程類似于這三種形式, 且結(jié)果均與推論1 或引理3 矛盾, 此處不再贅述. 因此當(dāng)d0=0 且I =9 時(shí), 有限域()8上不存在MDS 線性變換.

引理7 當(dāng)d0／=0 且I =9 時(shí), 有限域()8上不存在MDS 線性變換.

證明: 根據(jù)引理2 可知d0≤d8, 所以當(dāng)d0／= 0 時(shí), 有d8／= 0. 已知d1＞4, 為使所有一階子矩陣滿秩, di(i=2,··· ,8) 的取值集合共有8 種, 分別是: {5,1},{6,2},{7,1},{7,3},{5},{6},{7},{0}. 確定集合后, di必須按照集合中元素的順序依次選取. 下面對(duì)不同類型的集合分別證明.

(1) 集合中只有一個(gè)元素. 此時(shí)共有4 種集合可選, 分別是: {5},{6},{7},{0}. 不失一般性地假設(shè)di取自集合{5}. 如圖9 所示, 線性變換(3,5,5,5,5,5,5,5,5) 的首行矩陣中C = D = E = F = G = H, 與推論1 矛盾, 所以(3,5,5,5,5,5,5,5,5) 不是MDS 線性變換;

圖9 (3,5,5,5,5,5,5,5,5) 的首行矩陣Figure 9 First row’s matrix of (3,5,5,5,5,5,5,5,5)

(2) 集合中有兩個(gè)元素. 此時(shí)共有4 種集合可選, 分別是: {5,1},{6,2},{7,1},{7,3}. 不失一般性地假設(shè)di取自集合{5,1}, 此時(shí)至少有4 個(gè)di取值相同, 與之對(duì)應(yīng), 一定有某三塊連續(xù)的矩陣塊相同. 如圖10 所示, 線性變換(1,5,5,5,5,1,1,1,1) 的首行矩陣中C = D 且F = G = H, 與推論1 矛盾, 所以(1,5,5,5,5,1,1,1,1) 不是MDS 線性變換.

圖10 (1,5,5,5,5,1,1,1,1) 的首行矩陣Figure 10 First row’s matrix of (1,5,5,5,5,1,1,1,1)

其余線性變換下的證明過(guò)程類似于這兩種形式, 且結(jié)果均與推論1 矛盾, 此處不再贅述. 因此d0／= 0且I =9 時(shí), 有限域()8上不存在MDS 線性變換.

上述證明過(guò)程中, 限定自由項(xiàng)d1位于區(qū)間[0,m) 內(nèi)且d0＜d1. 事實(shí)上這兩個(gè)限制條件對(duì)有限域()8上滿足引理1 的所有9 項(xiàng)線性變換進(jìn)行了等價(jià)劃分:

(1) 根據(jù)L(X) 循環(huán)移位m 的倍數(shù)時(shí)分支數(shù)保持不變可知, 自由項(xiàng)d1位于區(qū)間[mt,m(t+1)),t =1,2,··· ,7, 等價(jià)于對(duì)自由項(xiàng)d1位于區(qū)間[0,m) 時(shí)的線性變換L(X) 循環(huán)右移mt 位, 例如線性變換(1,5,5,5,1,1,0,0,0) 和線性變換(0,1,5,5,5,1,1,0,0) 的分支數(shù)相同, 但前者的自由項(xiàng)位于區(qū)間[0,8), 后者的自由項(xiàng)位于區(qū)間[8,16), 如圖11 所示線性變換(0,1,5,5,5,1,1,0,0) 等價(jià)于對(duì)線性變換(1,5,5,5,1,1,0,0,0) 循環(huán)右移8 位, 因此MDS 線性變換不存在的結(jié)論在d1位于其它區(qū)間時(shí)仍然成立;

(2) d0和d1均位于矩陣A 中, 在其余項(xiàng)數(shù)均不變時(shí)交換d0和d1的順序, 線性變換不變. 例如:(1,5,5,5,5,1,1,1,1) 和(5,1,5,5,5,1,1,1,1) 是同一個(gè)線性變換. 因此令d0＜d1時(shí)證明的MDS 線性變換不存在的結(jié)論在d0＞d1時(shí)仍然成立.

圖11 (1,5,5,5,1,1,0,0,0) 和(0,1,5,5,5,1,1,0,0) 的首行矩陣Figure 11 First row’s matrix of (1,5,5,5,1,1,0,0,0) and (0,1,5,5,5,1,1,0,0)

(1) 將計(jì)數(shù)器S 的初值設(shè)置為0, S 表示I =9 時(shí)可能的MDS 線性變換個(gè)數(shù);

(2) 共嵌套9 層循環(huán)限定di(i=0,1,··· ,8) 的范圍, 其中di∈[0,8);

(3) 判斷線性變換L(X) 是否滿足引理2 至引理4, 若不滿足任意一條引理, 將其丟棄; 否則L(X) 可能是MDS 線性變換, 令S 加1;

(4) 循環(huán)結(jié)束后返回可能的MDS 線性變換個(gè)數(shù)S.

算法1 搜索I =9 時(shí)有限域(F82)8 上可能的MDS 線性變換Input: I = 9 時(shí)有限域(F82)8 上的所有線性變換Output: MDS 線性變換的可能個(gè)數(shù)S 1 S ←0;2 for d0 ∈[0,8) do 5 if 不滿足引理2 ‖ 不滿足引理3 ‖ 不滿足引理4 then 3 ··· //嵌套7 層循環(huán), 限定d1 至d7 的取值區(qū)間;4 for d8 ∈[0,8) do 6 continue;7 end S++;9 end 10 ···;11 end 12 return S;8

算法1 實(shí)驗(yàn)環(huán)境的主要參數(shù)如表5 所示, 利用Magma 軟件調(diào)用算法1, S 的返回結(jié)果為0, 進(jìn)而驗(yàn)證了引理5 至引理7.

表5 實(shí)驗(yàn)環(huán)境的主要參數(shù)Table 5 Main parameters of experimental environment

綜上所述, 可得到定理2.

5 I = 11 時(shí)有限域()8 上基于Rotational-XOR 的MDS 線性變換的研究

第4 節(jié)證明了異或項(xiàng)數(shù)取最小值9 時(shí), 不存在基于Rotational-XOR 的MDS 線性變換. 根據(jù)引理1,有限域()8上的MDS 線性變換L(X) 異或項(xiàng)數(shù)至少為11 項(xiàng), 因此研究I = 11 時(shí)MDS 線性變換的存在性問(wèn)題. 首先將I = 11 時(shí)滿足引理1 的88×56×55×54 個(gè)線性變換等價(jià)劃分為15 種形式, 然后分別研究各種形式下的線性變換.

5.1 I =11 時(shí)線性變換的等價(jià)劃分

根據(jù)引理1, I =11 時(shí)L(X) 中有3 個(gè)自由項(xiàng), 而L(X) 對(duì)應(yīng)的循環(huán)矩陣L 首行共有8 個(gè)矩陣, 因此可分為三種情況: 一個(gè)矩陣中至多有一個(gè)自由項(xiàng); 存在兩個(gè)自由項(xiàng)落在同一矩陣中; 三個(gè)自由項(xiàng)恰好落在同一矩陣中. 下面依次進(jìn)行分析.

此處引入一種表述方法: 用三個(gè)數(shù)字表示自由項(xiàng)依次在L 首行矩陣塊中的位置. 例如: “124” 表示自由項(xiàng)分別位于第一塊、第二塊、第四塊矩陣中; “113” 表示有兩個(gè)自由項(xiàng)位于第一塊矩陣中, 第三個(gè)自由項(xiàng)位于第四塊矩陣中; “111” 表示三個(gè)自由項(xiàng)均位于第一塊矩陣中.

(1) 一個(gè)矩陣中至多有一個(gè)自由項(xiàng)第(1) 種情況共需搜索(88×7×7×7)×7×8×6 個(gè)線性變換, 如表6 所示, 共有56 種分配方式滿足一個(gè)矩陣中至多有一個(gè)自由項(xiàng).

表6 一個(gè)矩陣中至多有1 個(gè)自由項(xiàng)的所有情況Table 6 All cases where there is at most one free term in one matrix

(a) 由于L(X) 循環(huán)移位m 的倍數(shù)時(shí)分支數(shù)保持不變, 因此表6 同列的任一行中3 個(gè)自由項(xiàng)位置均可由前一行循環(huán)右移一個(gè)矩陣得到, 所以同列的8 種形式等價(jià), 首行的7 種形式涵蓋了這56 種分配方式.

(b) 假設(shè)3 個(gè)自由項(xiàng)分別位于“123” 中, 此時(shí)自由項(xiàng)的全排列共有6 種方式, 它們是相等的. 例如: 3 個(gè)自由項(xiàng)d1,d2,d3位于“123” 中和d2,d1,d3位于“123” 中是同一個(gè)線性變換.

通過(guò)上述等價(jià)劃分,同一矩陣中至多有一個(gè)自由項(xiàng)時(shí)共有7 種形式,分別為: “123”,“124”,“125”,“126”, “127”, “135”, “136”, 判斷該情況下是否存在MDS 線性變換僅需搜索(88×7×7×7)×7個(gè)線性變換即可.

(2) 存在兩個(gè)自由項(xiàng)落在同一個(gè)矩陣中第(2) 種情況共需搜索(88×7×6×7)×7×8×3 個(gè)線性變換, 如表7 所示, 共有56 種分配方式存在兩個(gè)自由項(xiàng)落在同一個(gè)矩陣中.

(a) 由于L(X) 循環(huán)移位m 的倍數(shù)時(shí)分支數(shù)保持不變, 表7 同列的任一行中3 個(gè)自由項(xiàng)位置均可由前一行循環(huán)右移一個(gè)矩陣得到, 所以同列的8 種形式等價(jià), 首行的7 種形式涵蓋了這56種分配方式.

(b) 假設(shè)3 個(gè)自由項(xiàng)分別位于“113” 中, 此時(shí)自由項(xiàng)的全排列共有3 種方式, 它們是相等的. 例如: 3 個(gè)自由項(xiàng)d1,d2,d3位于“113” 中和d2,d1,d3位于“113” 中是同一個(gè)線性變換.

表7 存在2 個(gè)自由項(xiàng)落在同一個(gè)矩陣的所有情況Table 7 All cases where there are 2 free terms in same matrix

通過(guò)上述等價(jià)劃分,存在兩個(gè)自由項(xiàng)落在同一矩陣時(shí)共有7 種形式,分別為: “112”,“113”,“114”,“115”, “116”, “117”, “118”, 判斷該情況下是否存在MDS 線性變換僅需搜索(88×7×6×7)×7個(gè)線性變換即可.

(3) 三個(gè)自由項(xiàng)恰好落在同一個(gè)矩陣中第(3) 種情況共需搜索(88×7×6×5)×8 個(gè)線性變換, 如表8 所示, 共有8 種分配方式三個(gè)自由項(xiàng)恰好落在同一個(gè)矩陣中. 由于L(X) 循環(huán)移位m 的倍數(shù)時(shí)分支數(shù)保持不變, 所以表8 中的3 個(gè)自由項(xiàng)位置均可由前一列循環(huán)右移一個(gè)矩陣得到, 因此這8 種形式等價(jià). 通過(guò)上述等價(jià)劃分, 三個(gè)自由項(xiàng)恰好落在同一矩陣塊時(shí)僅有一種形式, 即“111”, 判斷該情況下是否存在MDS 線性變換僅需搜索88×7×6×5 個(gè)線性變換即可.

表8 3 個(gè)自由項(xiàng)恰好落在同一個(gè)矩陣的所有情況Table 8 All cases where there are exactly 3 free terms in same matrix

由于(88×7×7×7)×7×8×6+(88×7×6×7)×7×8×3+(88×7×6×5)×8=88×56×55×54,因此上述等價(jià)劃分方法將有限域()8上基于Rotational-XOR 的全體11 項(xiàng)線性變換劃分為15 種不同的形式.

5.2 算法實(shí)現(xiàn)

對(duì)滿足引理1 的線性變換進(jìn)行等價(jià)劃分后, 應(yīng)分別搜索每種形式下MDS 線性變換的數(shù)目, 5.2 節(jié)給出通用搜索算法2. 算法步驟如下:

(1) 將計(jì)數(shù)器S 的初值設(shè)置為0, S 表示I =11 時(shí)MDS 線性變換的個(gè)數(shù);

(2) 共嵌套11 層循環(huán)限定di(i=0,1,··· ,10) 的范圍, 其中di∈[0,8);

(3) 判斷線性變換L(X) 是否滿足引理2 至引理4, 若不滿足任意一條引理, 將其丟棄; 否則L(X) 可能是MDS 線性變換, 令S 加1;

(4) 在X ∈[0x1,0xFFFFFFFFFFFFFFFF] 上對(duì)L(X) 進(jìn)行窮搜, 令count 表示某個(gè)線性變換的分支數(shù)(每次窮搜一個(gè)線性變換前置零)、x0至x7表示X 的8 個(gè)分量、y0至y7表示L(X) 的8 個(gè)分量, 若a／=0(其中a ∈[x0,··· ,x7]∪[y0,··· ,y7]), count 加1;

(5) 若X 和Y 的16 個(gè)分量中非零個(gè)數(shù)小于9, 說(shuō)明L(X) 不是MDS 線性變換, 令S 減1 并退出本層循環(huán);

(6) 循環(huán)結(jié)束后返回MDS 線性變換的個(gè)數(shù)S.

算法2 實(shí)驗(yàn)環(huán)境的主要參數(shù)如表5 所示. 使用Magma 軟件調(diào)用算法2 對(duì)表6-表8 中15 種形式的線性變換進(jìn)行等價(jià)意義下的窮搜, S 的返回值均為0. 由此給出定理3.

算法2 搜索I =11 時(shí)有限域(F82)8 上的MDS 線性變換Input: I = 11 時(shí)有限域(F82)8 上的所有線性變換Output: I = 11 時(shí)MDS 線性變換的個(gè)數(shù)S 1 S ←0;2 for d0 ∈[0,8) do 3 ··· //嵌套9 層循環(huán), 限定d1 至d9 的取值區(qū)間;4 for d10 ∈[0,8) do 5 if 不滿足引理2 ‖ 不滿足引理3 ‖ 不滿足引理4 then 6 continue;7 end 8 S++;9 for X ∈[0x1,0xFFFFFFFFFFFFFFFF] do 10 Y = L(X),count ←0;11 x0 = X&0x00000000000000FF;12 x1 = X&0x000000000000FF00;13 ···;14 x7 = X&0xFF00000000000000;15 y0 = Y&0x00000000000000FF;16 y1 = Y&0x000000000000FF00;17 ···;18 y7 = Y&0xFF00000000000000;19 for a ∈[x0,··· ,x7]∪[y0,··· ,y7] do 20 if a /= 0 then 21 count++;22 end 23 end 24 if count ＜9 then 25 S--;26 break;27 end 28 end 29 end 30 ···;31 end 32 return S

6 結(jié)論

本文研究并給出分組規(guī)模為64、分塊規(guī)模為8 的MDS 線性變換的必要條件, 探尋該規(guī)模下的MDS線性變換. 通過(guò)分析首行矩陣的性質(zhì), 證明此規(guī)模下異或項(xiàng)數(shù)取最小值9 項(xiàng)時(shí)不存在MDS 線性變換, 并利用Magma 軟件驗(yàn)證該結(jié)論. 進(jìn)而研究異或項(xiàng)數(shù)為11 項(xiàng)時(shí)的MDS 線性變換, 得出此規(guī)模下異或項(xiàng)數(shù)取11 項(xiàng)時(shí)也不存在MDS 線性變換. 這兩個(gè)結(jié)論為之后設(shè)計(jì)有限域()8上基于Rotational-XOR 的MDS 擴(kuò)散層提供了理論參考.

在未來(lái)工作中, 一方面, 我們會(huì)繼續(xù)研究異或項(xiàng)數(shù)為13 項(xiàng)時(shí)有限域(F82)8上的MDS 線性變換的存在性問(wèn)題; 另一方面, 若降低一部分對(duì)安全性的需求, 也可研究有限域()8上的類MDS 線性變換.