基于Rotation-XOR 的MDS 線性變換的研究*

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

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

1 引言

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

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

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

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

2 預(yù)備知識

2.1 基本符號

2.2 分支數(shù)

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

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

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

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

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

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

定理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 個元素的整數(shù)集合.

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

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

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

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

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

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

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

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

其中0 ≤di＜m,0 ≤i ＜n+1, d1為自由項.

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

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

線性變換L(X) 對應(yīng)的矩陣L 就是一個循環(huán)矩陣, 可表示為L = 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 個同階對角矩陣之和的形式, 可定義為:

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

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

圖2 A 的對角矩陣表示形式: 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中元素個數(shù)小于m,即Li+1是奇異矩陣,因此di≥di+1(i=2,3,···,n-1);

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

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

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

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

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

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

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

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

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

圖3 I =9 時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, “?” 表示這兩個對角矩陣之和滿秩.

表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 時集合{4} 所有可能的MDS 線性變換Table 2 All possible MDS linear transformation in {4} when I = 9

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

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

(1) 集合中只有一個元素. 此時共有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) 集合中有兩個元素. 此時共有4 種集合可選, 分別是: {1,0}, {2,0},{3,0},{4,0}. 不失一般性地假設(shè)di取自集合{4,0}, 根據(jù)引理1 可知d0≤d8, 因此有d0= 0. 由表3 可知此時至少有4 個di取值相同, 與之對應(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必須按照集合中元素的順序依次選取. 下面對不同類型的集合分別證明.

(1) 集合中只有一個元素. 此時共有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) 集合中有兩個元素. 此時共有9 種集合可選, 分別是: {5,1},{5,0},{1,0},{6,2},{6,0},{2,0},{7,1},{7,3},{7,0}. 不失一般性地假設(shè)di取自集合{5,1},此時至少有4 個di取值相同,與之對應(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) 集合中有三個元素. 此時共有4 種集合可選, 分別是: {5,1,0},{6,2,0},{7,1,0},{7,3,0}. 不失一般性地假設(shè)di取自集合{5,1,0}, 由表4 可知此時至少有3 個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 時集合{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)

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

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

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

(1) 集合中只有一個元素. 此時共有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) 集合中有兩個元素. 此時共有4 種集合可選, 分別是: {5,1},{6,2},{7,1},{7,3}. 不失一般性地假設(shè)di取自集合{5,1}, 此時至少有4 個di取值相同, 與之對應(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)

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

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

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

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

圖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) 將計數(shù)器S 的初值設(shè)置為0, S 表示I =9 時可能的MDS 線性變換個數(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 線性變換個數(shù)S.

算法1 搜索I =9 時有限域(F82)8 上可能的MDS 線性變換Input: I = 9 時有限域(F82)8 上的所有線性變換Output: MDS 線性變換的可能個數(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 實驗環(huán)境的主要參數(shù)如表5 所示, 利用Magma 軟件調(diào)用算法1, S 的返回結(jié)果為0, 進而驗證了引理5 至引理7.

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

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

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

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

5.1 I =11 時線性變換的等價劃分

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

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

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

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

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

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

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

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

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

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

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

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

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

表8 3 個自由項恰好落在同一個矩陣的所有情況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,因此上述等價劃分方法將有限域()8上基于Rotational-XOR 的全體11 項線性變換劃分為15 種不同的形式.

5.2 算法實現(xiàn)

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

(1) 將計數(shù)器S 的初值設(shè)置為0, S 表示I =11 時MDS 線性變換的個數(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] 上對L(X) 進行窮搜, 令count 表示某個線性變換的分支數(shù)(每次窮搜一個線性變換前置零)、x0至x7表示X 的8 個分量、y0至y7表示L(X) 的8 個分量, 若a／=0(其中a ∈[x0,··· ,x7]∪[y0,··· ,y7]), count 加1;

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

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

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

算法2 搜索I =11 時有限域(F82)8 上的MDS 線性變換Input: I = 11 時有限域(F82)8 上的所有線性變換Output: I = 11 時MDS 線性變換的個數(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線性變換. 通過分析首行矩陣的性質(zhì), 證明此規(guī)模下異或項數(shù)取最小值9 項時不存在MDS 線性變換, 并利用Magma 軟件驗證該結(jié)論. 進而研究異或項數(shù)為11 項時的MDS 線性變換, 得出此規(guī)模下異或項數(shù)取11 項時也不存在MDS 線性變換. 這兩個結(jié)論為之后設(shè)計有限域()8上基于Rotational-XOR 的MDS 擴散層提供了理論參考.

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