循環移位與異或構造擴散層的新證明方法*

蘇 俊, 王 鑫, 王 濤, 楊 波

陜西師范大學 計算機科學學院, 西安710119

1 引言

擴散層作為分組密碼和哈希函數的核心組件, 其目的是提高擴散和混淆程度來實現雪崩效應[1], 這有助于抵抗差分分析、線性分析以及一些未知分析方法的攻擊. 通常使用分支數這一概念作為評價擴散層安全性能的指標[2]. 具體體現為分支數較大, 則該密碼系統的擴散性能較優, 抵抗差分攻擊與線性攻擊的能力更強. 隨著輕量級密碼學的快速發展, 利用軟硬件設備設計高效的擴散層逐漸成為研究熱點[3,4].

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

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

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

2 基本概念

2.1 分支數

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

2.2 一般形式與必要條件

3 一類最優線性變換的證明

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

3.1 X 中漢明重量為1

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

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

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

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

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

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

3.2 X 中漢明重量為2

當X中漢明重量為2 時, 討論x1,x2,x3,x4中存在兩個不為0 的情況, 不失一般性, 設x1,x2?=0, x3,x4=0, 此時有

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

(1) 當x1=x2時, 會有

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

3.3 X 中漢明重量為3

當X中漢明重量為3 時, 討論x1,x2,x3,x4存在三個不為0 的情況, 設x1,x2,x3?=0,x4=0, 此時有

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

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

3.4 X 中漢明重量為4

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

4 循環移位與異或擴散層的篩選

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

算法1 篩選特定分支數的線性變換組合Input: 移位項數r = 5; 分支數Branch = 5 Output: 移位數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//擴散層中輸入數據進行線性變化7 Y = [X ?l1|X ?(32?l1)]∧[X ?l2|X ?(32?l2)]∧···∧[X ?l5|X ?(32?l5)]8//計算輸入與輸出的漢明重量之和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;//篩選成功, 結果存入文件14 end 15 end 16 end 17 end 18 end

4.1 ()4 上最優線性變換

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

表1 ()4 上的分支數為5 的擴散層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 的線性組合不難看出, 在循環移位與異或運算最優擴散層中, 當X ∈(Fin2)m時, 分支數不會發生改變, 因此有如下推論:

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

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

最優線性變換 (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 上次優線性變換

表3 ()4 上分支數為4 的次優擴散層Table 3 Suboptimal diffusion layer with branch number of 4 on ()4

表3 ()4 上分支數為4 的次優擴散層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 中次優線性組合, 我們發現在循環移位與異或運算構造的非最優線性變換有如下結論:

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

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

5 結論