動態密碼結構抵抗差分密碼分析能力評估

王念平，郭祉成

（信息工程大學，河南 鄭州 450001）

1 引言

隨著分組密碼研究的不斷深入，一些學者為了提高分組密碼算法的安全性，提出了動態分組密碼算法[1-10]，這就為分組密碼算法的設計提供了一條新的思路。“動態”是指分組密碼算法的某些組件（例如S 盒、擴散層或輪函數等）有多種選擇，或者說這些密碼組件是動態可變的。但必須指出，這些動態分組密碼算法的抗攻擊能力很大程度上取決于所采用的分組密碼結構的抗攻擊能力，因此，對動態分組密碼結構（即某些密碼組件動態可變的分組密碼結構）的研究具有重要的意義。

另一方面，差分密碼分析[11]是攻擊分組密碼最有效的方法之一，對分組密碼抵抗差分密碼分析的能力進行評估一直都是密碼學研究的熱點。如果分組密碼的最大差分特征概率足夠小，就可以認為該分組密碼能夠抵抗差分密碼分析。在評估分組密碼抵抗差分密碼分析的能力時，研究方法通常是給出多輪差分特征中活動輪函數或活動S 盒個數的下界，進而給出最大差分特征概率的上界。

一般來說，將分組密碼結構的某些組件（例如S 盒、擴散層或輪函數等）動態化，就可以構成動態分組密碼結構，但如果這些組件設計不當，就有可能導致動態分組密碼結構中的某些密碼結構抗攻擊能力較弱。這樣，密碼分析者就有可能針對這一較弱的結構進行攻擊，從而帶來意想不到的后果。因此，在設計動態分組密碼結構時，一定要盡量保證動態密碼結構中的任一結構具有相同或相近的抗攻擊能力，避免出現某一結構抗攻擊能力較弱的情況。

基于上述的想法，本文根據差分傳遞規律，提出一種動態密碼結構，并對其抵抗差分密碼分析的能力進行了詳細的評估，給出了多輪差分特征中活動輪函數個數的下界。該動態密碼結構的特點是第6t(?t≥ 1)輪中的擴散層可以從{0,1}4上的多個線性雙射（對應于4 階0-1 可逆矩陣）中任意選取，即6t(?t≥ 1)輪中的擴散層是動態可變的。這里所說的“擴散層”是指整體結構中的擴散層，而不是輪函數中的擴散層。需要強調的是，本文提出的動態密碼結構中的擴散層并不是隨意選取的，也并非涵蓋所有的4 階0-1 可逆矩陣，而是根據差分傳遞規律設計的。擴散層的設計是本文的創新之處，給出多輪差分特征中活動輪函數個數的下界是本文首要解決的問題。

目前，與動態分組密碼結構有關的研究主要有以下2 個方面。1) 對動態分組密碼的設計思想和設計方法進行研究和探討[1-3,12-19]。文獻[1]設計了一種嵌套復用S 盒的動態密碼算法，為不同用戶提供不同的分組密碼算法。文獻[2]通過變換對稱密碼算法中的編制要素，實現動態對稱密碼算法。文獻[3]提出“對稱密碼算法簇模型”，從混亂層和擴散層2 個方面研究分組密碼的動態組件設計問題，并基于AES、Camellia、SMS4 算法給出了具體的密碼算法簇，進而討論了相應的硬件實現性能。文獻[12-16]對幾類動態分組密碼結構的設計方法以及抵抗差分或線性密碼分析的能力進行了分析。文獻[17-19]通過選取不同的擴散矩陣，提升了密碼算法中活動輪函數個數的下界，提高了密碼算法抵抗差分或者線性密碼分析能力。2) 針對具體的分組密碼算法，將某些密碼組件動態化，形成動態分組密碼算法[4-10]。文獻[4-6]基于SMS4 算法，利用時間戳動態改變算法中的固定參數，從而實現密碼算法的動態化。文獻[7,9-10]利用密鑰控制動態可變的S 盒，能夠使密碼算法動態可變。文獻[8]基于Feistel 結構，設計了結合密鑰相關的動態S 盒和P 盒，提出了一種動態分組密碼算法。除了文獻[12-16]中的相應結果外，大多工作都是針對具體的密碼算法中的組件（如S 盒、P 盒、某個參數等）進行研究的，針對動態分組密碼結構本身的研究并不多。本文提出的動態密碼結構與以上所述的這些研究都有所不同，因此本文的研究具有重要的意義。此外，動態分組密碼結構的安全性研究對動態分組密碼設計與分析具有重要的指導意義，可以根據本文提出的動態密碼結構設計出相應的動態分組密碼算法。本文對該動態密碼結構進行抵抗差分密碼分析，其分析結果可以保證基于該結構設計的動態分組密碼算法抵抗差分密碼分析的安全性，并為動態分組密碼算法設計提供了一定的依據。

2 預備知識

CLEFIA 密碼結構如圖1 所示，它有4 個輸入分支(x0,x1,x2,x3)和4 個輸出分支(y0,y1,y2,y3)，每一輪中有2 個輪函數f0和f1，線性變換采用循環左移變換，其中k=(k0,k1)表示輪密鑰，⊕表示異或運算。

圖1 CLEFIA 密碼結構

CLEFIA 變形密碼結構如圖2 所示，其主要特點是線性變換P（即擴散層）可以從形如的4階0,1 可逆矩陣中任意選取，其中λi,μi∈{0,1}，0≤i≤ 4。顯然，對任意給定的i,0≤i≤ 4，λi和μi都有2 種選取方法（即0 或1），故線性變換P共有 25×2=26種選取方法。

由圖2 可知，CLEFIA 變形密碼結構的輸入與輸出的關系式為

圖2 CLEFIA 變形密碼結構

6t+m(t≥0,0≤m≤ 5)輪基于CLEFIA 變形密碼結構的動態密碼結構（以下簡稱動態密碼結構）如圖3 所示，它由t個“單元”Gi（1 ≤i≤t）和m輪CLEFIA 密碼結構組成。其中任一“單元”Gi（即第6i-5 輪～第6i輪，1≤i≤t，如圖4 所示）由6 輪密碼結構構成：前5 輪是如圖1 所示的CLEFIA 密碼結構，第6 輪是如圖2 所示的CLEFIA變形密碼結構。也就是說，6t+m輪動態密碼結構中，第6 輪、第12 輪、…、第6t輪是如圖2 所示的CLEFIA 變形密碼結構，其他輪都是如圖1 所示的CLEFIA 密碼結構。需要強調的是，第6 輪、第12輪、…、第6t輪中的線性變換可以相同，也可以不同，換句話說，第6 輪、第12 輪、…、第6t輪中的線性變換是獨立選取的，故6t+m（t0,0≤m≤5）輪動態密碼結構共包含(25×2)t=26t種密碼結構。

圖3 基于CLEFIA 變形密碼結構的動態密碼結構

圖4 “單元”Gi

定義1[20]設(X,+)和(Y,+)都是有限交換群，f:X→Y，α∈X，β∈Y，令

則稱pf(α→β)為f在輸入差為α條件下，輸出差為β的差分概率。此外，也稱α→β為f的一個差分對應，并稱pf(α→β)為該差分對應的概率。其中“+”表示群(X,+)中的運算，和#{·} 都表示集合的元素個數。

定義2[20]設 (X,+)是有限交換群，，則 稱的一個起點為α1，終點為αn1+的差分傳遞鏈。

定義3[21]設α→β是輪函數（包括f0和f1）的一個差分對應，若α≠0，則稱該輪函數是活動的，或稱該輪函數是活動輪函數。

引理1[16]對于圖1 所示的CLEFIA 密碼結構，設輪函數都是雙射，則r（r≥ 0）輪差分特征至少有個活動輪函數。其中，rmod6表示r除以6 的最小非負余數，表示不小于x的最小整數。

3 CLEFIA 動態密碼結構抵抗差分密碼分析

首先，給出所有非0 輸入差分經一輪CLEFIA密碼結構（如圖1 所示）迭代后的差分對應。

以輸入差分為(0,0,1,1)=3 時的情形為例。此時，第3 分支與第4 分支輸入差分不為0，CLEFIA密碼結構的一輪差分對應為

其中，箭頭上方括號中的1 表示輪函數f1的輸入差分塊為非0 差分塊，即活動輪函數的個數為1。以下都用表示輸入差分α經過u(u≥1) 輪迭代后輸出差分為β，且活動輪函數的個數為v。

上述差分對應的計算過程如下：在輪函數f0和f1都為雙射的條件下，當輸入差分為3=(0,0,1,1)時，輪函數f0的輸出差分塊為0 差分塊，輪函數f1的輸出差分塊為非0 差分塊，故由“0⊕0=0”和“1⊕1=0或1”知，經過輪函數f0和f1以及異或運算作用后，其輸出結果為(0,0,1,0)或(0,0,1,1)，再經過循環左移變換，其輸出結果為(0,1,0,0) 或(0,1,1,0)，即4 或6。

類似地，所有非0 輸入差分經一輪CLEFIA 密碼結構迭代后的差分對應為

其次，給出所有非0 輸入差分經一輪CLEFIA變形密碼結構（如圖2 所示）迭代后的差分對應。

當線性變換P∈P1時，以輸入差分為(0,0,1,1)=3時的情形為例。此時，第3 分支與第4分支輸入差分不為0，CLEFIA 變形密碼結構的一輪差分對應為

其中，λi∈{0,1},2≤i≤ 4，且運算⊕滿足規則“0⊕0=0”“0⊕1=1”“1⊕0=1”“1⊕1=0或1”。當λi遍歷 0,1 時，(1,λ2,λ3,1⊕λ4)的取值為(1,0,0,1⊕0)=(1,0,0,1)，(1,0,0,1⊕1)=(1,0,0,0)或(1,0,0,1)，(1,0,1,1⊕0)=(1,0,1,1)，(1,0,1,1⊕1)=(1,0,1,0) 或 (1,0,1,1)，(1,1,0,1⊕0)=(1,1,0,1)，(1,1,0,1⊕1)=(1,1,0,0)或(1,1,0,1)，(1,1,1,1⊕0)=(1,1,1,1)，(1,1,1,1⊕1)=(1,1,1,0)或 (1,1,1,1)，即(1,λ2,λ3,1⊕λ4)的取值∈{8,9,10,11,12,13,14,15}，故上述的一輪差分對應可簡記為

其中，箭頭上方括號中的1 表示輪函數f1的輸入差分塊為非0 差分塊，即活動輪函數的個數為1。

當線性變換P∈P2時，仍以輸入差分為(0,0,1,1)=3 時的情形為例。同樣可以給出輸入差分3 經一輪CLEFIA 變形密碼結構迭代后的差分對應為

利用上述的P∈P1和P∈P2時的差分對應，進一步可以給出當線性變換P∈P1∪P2時，輸入差分3 經一輪CLEFIA 變形密碼結構迭代后的差分對應為

類似地，所有非0 輸入差分經一輪CLEFIA 變形密碼結構迭代后的差分對應為

利用上述的一輪CLEFIA 密碼結構的差分對應和一輪CLEFIA 變形密碼結構的差分對應，可以進一步給出所有非0 輸入差分經6 輪動態密碼結構（如圖3 和圖4 所示）迭代后的差分對應為

由上面的討論，可得以下引理。

引理2對于圖3 所示的動態密碼結構，若輪函數都是雙射，則有以下結論成立。

1) 6 輪差分特征中活動輪函數的個數 ≥6。

2) 活動輪函數為6 的6 輪差分特征只可能為

引理3對于圖3 所示的動態密碼結構，在輪函數都是雙射的條件下，19 輪差分特征中活動輪函數的個數 ≥19，即對于

證明由引理2 的1)可知，6 輪差分特征中活動輪函數的個數 ≥ 6，故vi≥6（1≤i≤3）。

最后，將本文結果與文獻[14]中的動態密碼結構的相應結果進行比較，如表1 所示。

表1 本文結果與文獻[14]中相應結果的比較

由表1 可知，對于本文提出的動態密碼結構，當迭代輪數l=6t(t≥ 1)或l=6t+1(t≥ 3)時，l(l≥ 1)輪差分特征至少有l個活動輪函數，當迭代輪數l取其他值時，l(l≥ 1)輪差分特征至少有l-1個活動輪函數。與文獻[14]中的I 型類CLEFIA 動態密碼結構相比，6t+1(t≥ 3)輪差分特征的活動輪函數個數的下界增加了1。與文獻[14]中的Ⅱ型類CLEFIA 動態密碼結構相比，本文提出的動態密碼結構在迭代輪數相同的情況下具有相同的活動輪函數個數的下界。另外還可以看出，在迭代輪數相同的情況下，本文提出的動態密碼結構所包含的密碼結構個數比I 型類CLEFIA 動態密碼結構的相應結果略少（即，顯然l=6t(t≥ 1)時二者相等），比Ⅱ型類CLEFIA 動態密碼結構的相應結果要多（即）。這里，表示不大于x的最大整數，表示不小于x的最小整數。

本文的研究結果對分組密碼算法的設計與分析具有重要的指導意義。根據定理2 可知，如果知道輪函數的最大差分概率Pmax，就能估計出任意輪最大差分特征概率的上界。當采用本文提出的動態密碼結構設計分組密碼算法時，其抵抗差分密碼分析的能力就有了依據。例如，一個輸入規模為128 bit的分組密碼算法采用圖3 所示的動態密碼結構，且輪函數f0和f1（如圖1 和圖2 所示）都采用SDS結構（代替-擴散-代替結構）[22]。其中，SDS 結構中的S 變換是4 個AES[23]S 盒的并置，D 變換是4階MDS 矩陣（顯然其差分分支數[23]為5）。因S 盒的最大差分概率為2-6[23]，故輪函數的差分概率≤(2-6)4=2-24[22]，從而l(?l≥ 1)輪最大差分特征概率≤2-24×N(l)。例如，l=6時，6 輪最大差分特征概率≤2-24×6=2-144。

4 實驗分析

本文通過Python 編程對CLEFIA動態密碼結構差分特征活動輪函數個數的下界進行驗證（實驗環境為Windows 10，I7-5500U 2.4 GHz，8 GB RAM），并將結果與I 型類CLEFIA 動態密碼結構和Ⅱ型類CLEFIA 動態密碼結構差分特征活動輪函數個數的下界進行比較。表2 給出了不同迭代輪數3 種密碼結構差分特征活動輪函數個數下界的對比。

表2 3 種密碼結構差分特征活動輪函數個數下界的對比

在實驗分析中，將活動輪函數個數的下界的求解問題轉換為混合整數線性規劃（MILP,mixed integer linear programming）[24]問題，利用Gurobi軟件求解MILP 問題得到活動輪函數個數的下界。但是在實際差分密碼分析中，真實差分特征的活動輪函數個數往往大于MILP 方法得到的理論估計，所以實際的下界大于或等于估計的下界。

對l(l≥1) 輪CLEFIA 動態密碼結構差分特征活動輪函數個數的下界進行求解，基本過程概括如下。

步驟1對于l輪CLEFIA 動態密碼結構，其線性變換P的選擇有種，并存儲P的所有可能的組合。

步驟 2任意選擇一種P的組合，當輪數imod6 ≠0(1≤i≤l)，對于CLEFIA 密碼結構進行建模；當輪數imod6=0(1≤i≤l)，對于選定P的CLEFIA 變形密碼結構進行建模，利用MILP 求解活動輪函數的個數并記錄。

步驟3重復步驟2，直至遍歷所有P的組合。

步驟4輸出CLEFIA 動態密碼結構差分特征活動輪函數個數的下界。

具體建模過程如下。對于密碼結構中的異或操作，設其輸入差分為(xin0,xin1)，輸出差分為xout，引入輔助變量d，則上述變量的取值范圍均為{0,1}，可以得到

以第i(1≤i≤l,imod6 ≠0)輪CLEFIA 密碼結構的建模為例，設輸入差分為(x4i-4,x4i-3,x4i-2,x4i-1)，輸出差分為(x4i,x4i+1,x4i+2,x4i+3)，dj,dj+1為引入的輔助變量，可以構建

以第i(i=6t,t≥ 1)輪CLEFIA 動態密碼結構的建模為例，當線性變換時，設輸入差分為(x4i-4,x4i-3,x4i-2,x4i-1)，輸出差分為(x4i,x4i+1,x4i+2,x4i+3)，dj,dj+1,dj+2為引入的輔助變量，可以構建

對于每一輪的輸入差分(x4i,x4i+1,x4i+2,x4i+3)，活動輪函數的個數取決于輸入差分的第一分支和第三分支，即f0和f1的輸入差分，因此活動輪函數個數下界的求解可表示為。利用Gurobi 軟件對該MILP 問題進行求解即可得到CLEFIA 動態密碼結構差分特征活動輪函數個數的下界。

通過實驗分析可得1～20 輪CLEFIA 動態密碼結構差分特征活動輪函數個數的下界，并且實驗結果與推導結果相同。

5 結束語

本文提出了一種動態密碼結構，該動態密碼結構的特點是第6t(?t≥ 1)輪中的擴散層可以從{0,1}4上的多個線性雙射（對應于4 階0-1 可逆矩陣）中任意選取，即6t(?t≥ 1)輪中的擴散層是動態可變的，因此該動態密碼結構包含多個分組密碼結構。本文通過對6 輪差分特征的傳遞規律的分析，在輪函數都是雙射的條件下，證明了l(l≥ 1)輪差分特征中活動輪函數個數的下界為N(l)，從而若設輪函數的最大差分概率為Pmax，則l輪動態密碼結構的最大差分特征概率≤[pmax]N(l)。對于本文提出的動態密碼結構，還有一些問題需要進一步研究，例如，該動態密碼結構抵抗不可能差分分析、零相關線性分析以及積分分析等分析方法的能力如何？同時，能否找到更合適的線性變換，使相同輪數的差分特征具有更多的活動輪函數，也值得進一步研究。