蘇 俊, 王 鑫, 王 濤, 楊 波

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

1 引言

擴(kuò)散層作為分組密碼和哈希函數(shù)的核心組件, 其目的是提高擴(kuò)散和混淆程度來實(shí)現(xiàn)雪崩效應(yīng)[1], 這有助于抵抗差分分析、線性分析以及一些未知分析方法的攻擊. 通常使用分支數(shù)這一概念作為評價(jià)擴(kuò)散層安全性能的指標(biāo)[2]. 具體體現(xiàn)為分支數(shù)較大, 則該密碼系統(tǒng)的擴(kuò)散性能較優(yōu), 抵抗差分攻擊與線性攻擊的能力更強(qiáng). 隨著輕量級密碼學(xué)的快速發(fā)展, 利用軟硬件設(shè)備設(shè)計(jì)高效的擴(kuò)散層逐漸成為研究熱點(diǎn)[3,4].

從編碼理論的角度看, 采用最大距離可分(Maximum Distance Separable, MDS) 碼構(gòu)造擴(kuò)散層可使分支數(shù)達(dá)到最大[5], 然而由于有限域中乘法的存在, 導(dǎo)致傳統(tǒng)MDS 不適用于RFID 系統(tǒng)和傳感器網(wǎng)絡(luò)等資源受限的環(huán)境. 為了解決這一問題, PHOTON 輕量級Hash 函數(shù)族的設(shè)計(jì)者們[6]采用流密碼算法中的LFSR 設(shè)計(jì)思想通過遞歸構(gòu)建擴(kuò)散層置換[7], 其首先實(shí)現(xiàn)一個(gè)線性反饋寄存器的循環(huán)函數(shù), 然后運(yùn)行幾輪函數(shù)之后得到一個(gè)MDS 矩陣, 此方法能較好的節(jié)省硬件空間, 但該方法需要迭代多次, 導(dǎo)致方法效率低,不適用于低時(shí)延的環(huán)境[8]; 采用直接方法構(gòu)造輕量級MDS 矩陣可以提高算法效率, 但其只關(guān)注硬件實(shí)現(xiàn),而未考慮到軟件性能[9]; Philip 等人提出采用循環(huán)結(jié)構(gòu)來構(gòu)建輕量級MDS 矩陣[10], 其所得的循環(huán)矩陣中所有矩陣塊結(jié)構(gòu)相同, 因此可以通過重復(fù)使用乘法電路來節(jié)省硬件面積. 因此, 在擴(kuò)散層中使用循環(huán)矩陣可以在硬件面積和時(shí)鐘周期之間進(jìn)行權(quán)衡[11,12].

循環(huán)移位和異或運(yùn)算的線性變換與循環(huán)矩陣一一對應(yīng)[13], 所以利用循環(huán)移位和異或運(yùn)算來構(gòu)建擴(kuò)散層的方法具有循環(huán)矩陣同樣的優(yōu)勢, 且其確定線性變換相對應(yīng)矩陣的第一行后, 經(jīng)過循環(huán)就能確定整個(gè)循環(huán)矩陣, 因此也稱此結(jié)構(gòu)為逐位循環(huán)[14]. 采用循環(huán)移位和異或運(yùn)算構(gòu)造最優(yōu)線性變換[15], 不僅運(yùn)算效率高、軟硬件實(shí)現(xiàn)簡單, 同時(shí)還避免了條件分支語句和查表運(yùn)算導(dǎo)致算法容易被攻擊的缺點(diǎn)[16]. 文獻(xiàn)[14]中對擴(kuò)散層的最優(yōu)線性變換轉(zhuǎn)換成循環(huán)矩陣, 再判斷其子矩陣全部是非奇異矩陣來證明該擴(kuò)散層具有最大分支數(shù)[17]. 但是上述方法僅能夠證明最優(yōu)擴(kuò)散層中的分支數(shù)大小, 無法判斷非最優(yōu)擴(kuò)散層中分支數(shù)的大小.

為了解決上述問題,在本文中,我們提出了一種反證的方法,利用擴(kuò)散層中輸入與輸出的關(guān)系證明分支數(shù)的大小. 這種方法不僅在證明方式上更直接, 而且不再局限于最優(yōu)線性變換. 我們對輸入形式為(Fn2)m的最優(yōu)線性變換利用上述方法進(jìn)行了詳細(xì)證明, 最后, 給出了擴(kuò)散層中線性變換的一種篩選算法和(Fn2)m上最優(yōu)與次優(yōu)線性變換組合, 以及分析篩選結(jié)果后得到兩個(gè)結(jié)論.

2 基本概念

2.1 分支數(shù)

W(P(X)) 表示擴(kuò)散層中輸出數(shù)據(jù)的漢明重量, 當(dāng)B(P)=m+1 時(shí), 擴(kuò)散層的分支數(shù)達(dá)到最大, 被稱為最優(yōu)線性變換[12]; 當(dāng)B(P)=m時(shí), 稱為次優(yōu)線性變換, 它能夠用更少的移位和異或運(yùn)算來實(shí)現(xiàn), 所以更具有輕量化, 并且在多輪迭代后能夠有最好擴(kuò)散效果, 因此研究次優(yōu)線性變換也有一定的現(xiàn)實(shí)意義[20].

2.2 一般形式與必要條件

3 一類最優(yōu)線性變換的證明

下面分別討論x1,x2,x3,x4中任意不為0 情況下X和Y的漢明重量之和, 也就是X的漢明重量為分別為1, 2, 3 和4 時(shí)上述線性變換的分支數(shù). 從等式中可以看到y(tǒng)1,y2,y3,y4的形式相似, 所以分類討論時(shí), 從x1,x2,x3,x4中任意選取xi不為0 后會得到相似形式的y1,y2,y3,y4, 所以不同xi的選取對證明過程不會產(chǎn)生影響.

3.1 X 中漢明重量為1

當(dāng)X中漢明重量為1 時(shí), 也就是x1,x2,x3,x4中僅存在一個(gè)不為0 的情況, 不失一般性, 設(shè)x1?=0,x2,x3,x4=0, 此時(shí)有

假設(shè)y1,y2,y3,y4中至少存在一個(gè)為0, 那么分別討論y1,y2,y3,y4等于0 的情況:

(1) 當(dāng)y1= 0 時(shí), 按塊展開得等式x11⊕x12= 0,x12⊕x13= 0,x13⊕x14= 0, 那么x14= 0, 則有x1=0, 這與條件相矛盾, 所以y1?=0.

(2) 當(dāng)y2= 0 時(shí), 按塊展開得等式x11= 0,x12= 0,x13= 0,x14⊕x11= 0 則有x1= 0, 這與條件相矛盾, 所以y2?=0.

(3) 當(dāng)y3=y4=0 時(shí), 按塊展開得等式x11=0,x12=0,x13=0,x14=0 則有x1=0, 這與條件相矛盾, 所以y3=y4=0.

綜上所述, 當(dāng)x1?=0 時(shí),y1,y2,y3,y4均不為0, 所以X和Y的漢明重量之和為5.

3.2 X 中漢明重量為2

當(dāng)X中漢明重量為2 時(shí), 討論x1,x2,x3,x4中存在兩個(gè)不為0 的情況, 不失一般性, 設(shè)x1,x2?=0, x3,x4=0, 此時(shí)有

此種情況可以分為兩類x1=x2和x1?=x2討論:

(1) 當(dāng)x1=x2時(shí), 會有

由上推理可得x2= 0, 這與條件x2?= 0 相矛盾, 所以當(dāng)y2= 0 時(shí),y1=y2?= 0; 綜上所述當(dāng)x1,x2?=0 時(shí),y1,y2,y3,y4至少存在三個(gè)不為0, 所以在該種情況下X和Y的漢明重量之和至少為5.

3.3 X 中漢明重量為3

當(dāng)X中漢明重量為3 時(shí), 討論x1,x2,x3,x4存在三個(gè)不為0 的情況, 設(shè)x1,x2,x3?=0,x4=0, 此時(shí)有

僅需要證明y1,y2,y3,y4中至少存在兩個(gè)不為0, 就可以判斷X和Y的漢明重量之和不小于5; 利用反證法, 假設(shè)y1,y2,y3,y4至少存在三個(gè)為0, 由于

可以將這種情況分為兩類: (1)y1=y4=0 的情況下, 判斷y2和y3是否等于0; (2)y2=y3=0 的情況下, 判斷y1和y4是否等于0. 下面進(jìn)行討論:

3.4 X 中漢明重量為4

當(dāng)X中漢明重量為4 時(shí), 討論x1,x2,x3,x4全部不為0 的情況, 設(shè)x1,x2,x3,x4?= 0, 此時(shí)僅需要證明y1,y2,y3,y4中至少存在一個(gè)不為0, 可證得X和Y的漢明重量之和不小于5. 利用反證法, 設(shè)y1,y2,y3,y4=0, 則有

4 循環(huán)移位與異或擴(kuò)散層的篩選

一般篩選特定分支數(shù)的線性變換總是依賴于程序的遍歷, 因此確定一個(gè)較小的空間可極大地節(jié)約遍歷時(shí)間并提高搜索特定線性變換的概率. 本節(jié)根據(jù)定理1 和定理2 給出一個(gè)篩選特定分支的線性變換算法,即直接對輸入數(shù)據(jù)進(jìn)行運(yùn)算后進(jìn)行分支數(shù)大小的篩選. 算法的輸入為循環(huán)移位項(xiàng)數(shù)和指定分支數(shù), 輸出為線性變換組合. 算法對移位項(xiàng)數(shù)為n的線性變換組合進(jìn)行篩選, 首先遍歷該移位項(xiàng)數(shù)下的所有線性變換組合, 其中, 在每種線性組合中遍歷混淆層輸出數(shù)據(jù), 然后計(jì)算輸入與輸出的漢明重量, 如果漢明重量小于分支數(shù)Branch 則中斷X遍歷, 開始進(jìn)行下一種線性組合篩選. 本節(jié)以篩選X ∈(F82)4上最簡形式的最優(yōu)線性變換為例, 其核心算法如下:

算法1 篩選特定分支數(shù)的線性變換組合Input: 移位項(xiàng)數(shù)r = 5; 分支數(shù)Branch = 5 Output: 移位數(shù)l1,l2,l3,l4,l5 1 for l1 from 0 to 6 do 4 for l5 from l1 +1 to 7 do 2 ···;3 for l4 from 24 to 31 do 5 for X from 1 to 232 ?1 do 6//擴(kuò)散層中輸入數(shù)據(jù)進(jìn)行線性變化7 Y = [X ?l1|X ?(32?l1)]∧[X ?l2|X ?(32?l2)]∧···∧[X ?l5|X ?(32?l5)]8//計(jì)算輸入與輸出的漢明重量之和Weight = [(X & 0xf0000000)]+···+[[(X & 0x0000000f)]]+[[(Y &0xf0000000)]]+···+[[(Y & 0x0000000f)]]10 if Weight ＜Branch then then 9 11 go to Step4;12 else 13 save l1,l2,l3,l4,l5 to text;//篩選成功, 結(jié)果存入文件14 end 15 end 16 end 17 end 18 end

4.1 ()4 上最優(yōu)線性變換

表1 ()4 上的分支數(shù)為5 的擴(kuò)散層Table 1 Diffusion layer with 5 branches on ( )4

表1 ()4 上的分支數(shù)為5 的擴(kuò)散層Table 1 Diffusion layer with 5 branches on ( )4

n r (Fn2 )4 中的l1,l2,···,lr 4 5 {0, 1, 5, 9, 12}{0, 3, 7, 11, 12}{0, 4, 5, 9, 13}{0, 4, 7, 11, 13}{1, 4, 8, 9, 13}{1, 5, 8, 12, 13}{3, 4, 8,11, 15}{3, 7, 8, 12, 15}4 7 {0, 1, 4, 6, 8, 11, 12}{0, 2, 4, 7, 8, 12, 13}{0, 3, 4, 8, 9, 12, 14}{0, 4, 5, 8, 10, 12, 15}8 5 {0, 2, 10, 18, 24}{0, 6, 14, 22, 24}{0, 8, 10, 18, 26}{0, 8, 14, 22, 26}{2, 8, 16.18, 26}{2, 10, 16, 24,26}{6, 8, 16, 22, 20}{6, 14, 16, 24, 30}8 7 {0, 2, 8, 12, 16, 22, 24}{0, 4, 5, 13, 17, 22}{0, 4, 8, 14, 16, 24, 26}{0, 4, 9, 11, 19, 24, 29}{0, 6, 8, 16,18, 24, 28}{0, 6, 10, 15, 19, 27, 28}{0, 8, 10, 16, 20, 24, 30}{1, 3, 11, 16, 21, 24, 28}{1, 5, 9, 12, 17, 19,27}{1, 6, 10, 16, 20, 21, 29}{2, 6, 12, 13, 20, 27, 28}{2, 7, 11, 19, 20, 24, 30}{2, 8, 12, 13, 21, 25,30}{3, 4, 8, 14, 18, 23, 27}{3, 4, 10, 14, 20, 21, 28}{3, 7, 13, 21, 23, 28, 31}{3, 9, 13, 16, 20, 25, 27}{3,11, 12, 16, 22, 26, 31}{4, 5, 12, 19, 20, 26, 30}{4, 7, 11, 15, 21, 29, 31}{4, 11, 12, 18, 22, 28, 29}{5, 7,12, 15, 19, 23, 29}{5, 9, 14, 18, 24, 28, 29}{5, 13, 25, 20, 23, 27, 31}

分析表1 的線性組合不難看出, 在循環(huán)移位與異或運(yùn)算最優(yōu)擴(kuò)散層中, 當(dāng)X ∈(Fin2)m時(shí), 分支數(shù)不會發(fā)生改變, 因此有如下推論:

表2 ()4 中最優(yōu)擴(kuò)散層的最簡形式Table 2 Simplest form of optimal diffusion layer on ()4

表2 ()4 中最優(yōu)擴(kuò)散層的最簡形式Table 2 Simplest form of optimal diffusion layer on ()4

最優(yōu)線性變換 (Fn2 )4 中的l1,l2,l3,l4,l5 (Fn 2 )4 中的l1,l2,l3,l4,l5第一組 0,1,5,9,12 0, 1 4 n,n+ 1 4 n,2n+ 1 4 n,3n第二組[14] 0,3,7,11,12 0, 3 4 n,n+ 3 4 n,3n第三組 0,4,5,9,13 0,n,n+ 1 4 n,2n+ 3 4 n第四組[21] 0,4,7,11,15 0,n,n+ 3 4 n,2n+ 1 4 n,3n+ 1 4 n第五組 1,4,8,9,13 1 4 n,2n+ 3 4 n,3n+ 3 4 n,n,2n,2n+ 1 4 n第六組 1,5,8,12,13 1 4 n,3n+ 1 4 n,n+ 1 4 n第七組 3,4,8,11,15 3 4 n,2n,3n,3n+ 1 4 n,n,2n,2n+ 3 4 n第八組 3,7,8,12,15 3 4 n,3n+ 3 4 n,n+ 3 4 n,2n,3n,3n+ 3 4 n

4.2 ()4 上次優(yōu)線性變換

表3 ()4 上分支數(shù)為4 的次優(yōu)擴(kuò)散層Table 3 Suboptimal diffusion layer with branch number of 4 on ()4

表3 ()4 上分支數(shù)為4 的次優(yōu)擴(kuò)散層Table 3 Suboptimal diffusion layer with branch number of 4 on ()4

n r (Fn 2 )4 中的l1,l2,···,lr 4 3 {0, 4, 8}{0, 4, 12}{0, 8, 12}{4, 8, 12}4 5 {0, 1, 4, 8, 9}{0, 1, 4, 9, 12}{0, 1, 8, 9, 12}{0, 1, 5, 9, 13}{0, 2, 4, 8, 10}{0, 2, 4, 10, 12}{0, 2, 6, 10,14}{0, 2, 8, 10, 12}{0, 3, 4, 8, 11}{0, 3, 4, 11, 12}{0, 3, 5, 11, 13}{0, 3, 7, 11, 15}{0, 3, 8, 11, 12}{0, 4,5, 8, 12}{0, 4, 5, 12, 13}{0, 4, 6, 8, 14}{0, 4, 6, 12, 14}{0, 4, 7, 8, 15}{0, 4, 7, 12, 15}{0, 5, 8, 12,13}{0, 6, 8, 12, 14}{0, 7, 8, 12, 15}{1, 4, 5, 9, 13}{1, 4, 7, 9, 15}{1, 4, 8, 9, 12}{1, 5, 8, 9, 13}{1, 5, 9,12, 13}{1, 7, 9, 12, 15}{2, 4, 6, 10, 14}{2, 4, 8, 10, 12}{2, 6, 8, 10, 14}{2, 6, 10, 12, 14}{3, 4, 8, 11,12}{3, 5, 8, 11, 13}{3, 7, 8, 11, 15}{3, 7, 11, 12, 15}{4, 5, 8, 12, 13}{4, 6, 8, 12, 14}{4, 7, 8, 12, 15}8 3 {0, 8, 16}{0, 8, 24}{0, 16, 24}{8, 16, 24}8 5 {0, 1, 8, 16, 17}{0, 1, 8, 17, 24}{0, 1, 9, 17, 25}{0, 1, 16, 17, 24}{0, 2, 8, 16, 18}{0, 2, 8, 18, 24}{0, 2,10, 18, 26}{0, 2, 16, 18, 24}{0, 3, 8, 16, 19}{0, 3, 8, 19, 24}{0, 3, 11, 19, 27}{0, 3, 16, 19, 24}{0, 4, 8,16, 20}{0, 4, 8, 20, 24}{0, 4, 12, 20, 28}{0, 4, 16, 20, 24}{0, 5, 8, 16, 21}{0, 5, 8, 21, 24}{0, 5, 9, 21,25}{0, 5, 13, 21, 29}{0, 5, 16, 21, 24}{0, 6, 8, 22, 24}{0, 6, 10, 22, 26}{0, 6, 14, 22, 30}{0, 6, 15, 22,24}{0, 7, 8, 16, 23}{0, 7, 8, 23, 24}{0, 7, 9, 23, 25}{0, 7, 11, 23, 27}{0, 7, 15, 23, 31}{0, 7, 16, 23,24}{0, 8, 9, 16, 25}{0, 8, 9, 24, 25}{0, 8, 9, 24, 26}{0, 8, 10, 16, 26}{0, 8, 11, 16, 27}{0, 8, 11, 24,27}{0, 8, 12, 16, 28}{0, 8, 12, 24, 28}{0, 8, 13, 16, 29}{0, 8, 13, 24, 29}{0, 8, 14, 16, 30}{0, 8, 14, 23,30}{0, 8, 15, 16, 31}{0, 8, 15, 24, 31}{0, 9, 16, 24, 25}{0, 10, 16, 24, 26}{0, 11, 16, 24, 25}{0, 12, 16,24, 28}{0, 13, 16, 24, 29}{0, 14, 16, 24, 30}{0, 15, 16, 24, 31}{1, 8, 9, 17, 25}{1, 8, 13, 17, 29}{1, 8,15, 17, 31}{1, 8, 16, 17, 24}{1, 9, 16, 17, 25}{1, 9, 17, 24, 25}{1, 13, 17, 24, 29}{1, 15, 17, 24, 31}{2,8, 10, 18, 26}{2, 8, 14, 18, 30}{2, 8, 16, 19, 18, 24}{2, 10, 16, 18, 26}{2, 10, 18, 24, 26}{2, 14, 18, 24,30}{3, 8, 11, 19, 27}{3, 8, 15, 19, 31}{3, 8, 16, 17, 24}{3, 11, 16, 19, 27}{3, 11, 19, 24, 27}{3, 15, 19,24, 31}{4, 8, 12, 20, 28}{4, 8, 16, 20, 24}{4, 12, 16, 20, 28}{4, 12, 20, 24, 28}{5, 8, 13, 21, 29}{5, 8,16, 21, 24}{5, 9, 16, 21, 25}{5, 13, 16, 21, 29}{5, 13, 21, 24, 29}{6, 8, 14, 22, 30}{6, 8, 16, 22, 24}{6,10, 16, 22, 26}{6, 14, 16, 22, 30}{6, 14, 22, 24, 30}{6, 8, 16, 22, 31}{7, 8, 15, 23, 31}{7, 8, 16, 23,24}{7, 9, 16, 23, 25}{7, 11, 16, 23, 27}{7, 14, 16, 24, 30}{7, 15, 16, 23, 31}{7, 15, 23, 24, 31}{8, 9, 16,24, 25}{8, 10, 16, 24, 26}{8, 11, 16, 24, 27}{8, 12, 16, 24, 28}{8, 13, 16, 24, 29}{8, 15, 16, 24, 31}

通過分析表3 中次優(yōu)線性組合, 我們發(fā)現(xiàn)在循環(huán)移位與異或運(yùn)算構(gòu)造的非最優(yōu)線性變換有如下結(jié)論:

推論2 如果線性變換L(X,m,n) 是分支數(shù)為B的非最優(yōu)線性變換, 那么該線性變換滿足下列條件:移位項(xiàng)數(shù)r為奇數(shù)且r+1≥B,移位數(shù)l至少從B?1 個(gè)不同區(qū)間[ni,n(i+1)]內(nèi)取值,i=0,1,··· ,m?1.

假設(shè)在分支數(shù)為B的線性變換L(X,m,n) 中,r+1＜B, 經(jīng)線性變換后知Y中最多r項(xiàng)包含x1的最低位信息, 換句話說x1的最低位參與生成Y中最多r項(xiàng)yi的異或運(yùn)算, 在該情形下, 若X中僅有x1的最低位為1, 也就是X=1 時(shí), 輸出Y中最多r項(xiàng)yi非零, 那么其漢明重量最大為r, 所以線性變換的分支數(shù)為r+1, 此時(shí)r+1＜B與分支數(shù)為B條件矛盾, 所以在分支數(shù)為B的線性變換L(X,m,n) 中,r+1≥B, 并且由定理2 中公式(4) 得知, 要想x1的最低位參與Y中r項(xiàng)y的生成, 移位數(shù)l至少從B ?1 個(gè)[ni,n(i+1)] 區(qū)間取值, 其中i=0,1,··· ,m ?1.

5 結(jié)論