基于SAT的線性擴散層分支數的快速計算方法

苗旭東，張 晶，胡建勇，董新鋒，張文政

（中國電子科技集團公司第三十研究所，四川 成都 610041）

0 引言

分組密碼算法通常有混淆層和擴散層，例如，高級加密碼標準AES[1]算法的混淆層由一排并置的8比特S盒組成，擴散層由基于域上構造的最大距離可分碼（Maximum Distance Separable codes，MDS）矩陣組成；商用密碼無線加密標準算法SMS4[2]的混淆層也是由一排并置的8比特S盒組成，而擴散層由基于循環異或（Rotation-XOR，RX）構造的線性擴散層組成。差分分析[3]和線性分析[4]作為分組密碼算法安全性分析的基本方法，在分析過程中會利用線性擴散層的分支數大小來衡量密碼算法的擴散效果。因此，算法設計人員在設計線性擴散層時往往期望差分和線性分支數盡可能大，差分分支數和線性分支數達到最大值的稱為最優擴散變換，分支數越大通常密碼算法的擴散速度越快。

為了保障線性擴散層分支數的大小，算法設計人員通常采用構造的方法，常用的方法有，通過線性編碼理論構造MDS[1]、特殊小矩陣構造大的擴散層[5-10]、線性反饋移位寄存器構造擴散層[11-15]、RX結構構造擴散層[16-20]等。一般構造出的線性擴散層分組較小（不超過32比特），通過定義也可以直接計算其分支數的大小，而對于分組較大（大于32比特）的線性擴散層的分支數很難通過定義去驗證，例如，將SMS4的RX結構的線性擴散層分組擴寬成64比特，隨機選擇移位項數達到9項時，即成為的線性變換，利用定義直接計算其分支數的計算復雜度達到O(264)，計算復雜度過高，利用目前的資源很難計算出來。而公開文獻中并沒有有效的快速計算方法。基于此，本文提出一種通用的快速計算線性擴散層分支數的方法，能夠在較短的時間內計算出分組大于32比特的線性擴散層的分支數，使算法設計人員對線性擴散層的選擇范圍更廣，更能準確把控算法的安全性。

本文第1節介紹了線性擴散層及分支數的定義；第2節將線性擴散層分支數的計算問題轉換為布爾可滿足性問題（Boolean Satisfiability Problem，SAT），結合SAT求解器，給出了差分和線性分支數的建模方法和搜索方法；第3節隨機構造了一批RX結構的線性擴散層，并利用本文提出的方法搜索了該類擴散層的分支數，首次得到循環異或項數為9、分支數達到8的RX結構的線性擴散層；最后部分對本文進行了總結和展望。

1 基本概念

1.1 線性擴散層

線性擴散層θ如圖1所示，x→θ(x)=y為有限域上的變換。

圖1 線性擴散層

線性擴散層內部通常由移位、異或等線性操作組成，外部輸入輸出為：

本文將xi,yi稱作字塊，xij,yij稱作比特，每個輸入輸出比特xij,yij(1≤i≤n,1≤j≤m)均為二元域上的變量，取值為0或1，為GF(2m)的域。

1.2 分支數

定義1 擴散層θ的分支數B(θ)定義為：

式中：ωb(x)為非零xi(1≤i≤n)的個數，被稱為x的包重量，通常分塊大小為8比特時，xi為一個字節；分塊大小為4比特時，xi為一個半字節（nibble）。本文將xi統稱為一個字塊。

對任何線性變換θ，因為θ(x)⊕θ(x*)=θ(x⊕x*)，所以差分分支數和分支數是一致的，計算方法相同。

即線性變換θ(x)=x×M的線性分支數等于λ(x)=x×Mt，因此當線性變換矩陣M是對稱矩陣時，即M=Mt時，線性分支數和差分分支數相等。

2 分支數計算轉換為SAT

本節將線性擴散層分支數的計算問題轉換為SAT問題，借助SAT求解器強大的計算能力，可以快速計算出線性擴散層的分支數。

2.1 SAT

SAT是第一個被證明的非確定性多項式（Nondeterministic Polynominal，NP）完全問題，屬于命題邏輯的范疇，它的輸入一般采用合取范式（Conjunctive Normal Form，CNF）。SAT問題就是判斷是否存在一個或多個變量賦值，使得該CNF公式滿足，即使得CNF公式中所有子句為真。

合取范式是一些子句（clause）的合取（“與”構成的邏輯公式），每個子句都是一些字的析取（“或”構成的邏輯公式），而每個字是一個布爾變量或者該布爾變量的非。舉例來說：

以上公式中x1,x2,x3,x3,x4,x5為字，x1,(x2∨?x3),(x3∨x4),?x5為子句，子句之間用“與”操作連接，字之間用“或”操作連接。

2.2 分支數計算轉換為SAT

將線性擴散層分支數的計算問題轉換為SAT問題，本質上是將線性擴散的差分和線性傳播行為用合取范式表示。由于線性擴散層中使用的操作有分支、異或、移位以及字塊和比特之間的關系，本節介紹基本操作的合取范式刻畫方法。

線性擴散層中使用的賦值、拉線、移位操作，實質均是賦值表達，假設x為賦值操作的輸入，y為賦值操作的輸出，即表示x=y表達式，用合取范式表示為：

式中：和為和的取反操作。

線性擴散層中任意兩比特之間的異或操作x⊕y=z，如圖2所示。

圖2 異或操作

異或的差分傳播關系用合取范式表示為[21]：

異或的線性傳播關系用合取范式表示為：

線性擴散層內部任意比特的分支操作x→(y,z)，如圖3所示。

圖3 分支操作

分支的差分傳播關系合取范式表示為[21]：

分支的線性傳播關系合取范式表示為：

字塊xi,yi(1≤i≤n)是否為零也可以用值0和1來表示，當每個字節塊中的任意比特非零時，相應的字塊值為1，表示相應字塊的輸入輸出差分或線性掩碼非零；當每個字節塊中的所有比特為零時，相應的字節塊值為0，表示相應字塊的輸入輸出差分或線性掩碼為0；合取范式表示該約束關系為：

本節將線性擴散層內部常見的操作用合取范式表示完畢，對任意一個待分析的線性擴散層，可按照上述基本操作的合取范式刻畫方法，將差分或線性在線性擴散層中的傳播行為用SAT分析模型表示。

2.3 搜索算法

計算線性擴散層的分支數時，首先要確保線性擴散層的輸入比特非零，即至少引入1比特差分或線性掩碼，用合取范式表示為：

計算分支數大小，即統計線性擴散層的輸入輸出非零字塊xi的最小個數，本質是判定以下不等式是否成立。

式中：k為指定分支數的大小。由于合取范式不支持以上線性不等式表達，需要將該線性不等式轉換為合取范式，本文采用序列編碼方法[22]，將該問題轉化為合取范式，如圖4所示。

圖4 序列編碼電路

將以上電路轉換為合取范式表示為[21,22]：

將該約束條件寫入SAT模型即可判斷指定活躍S盒個數k是否有滿足解。可用算法1進行搜索求解。

算法的求解思路：首先將分支數的大小設定為一個最小的初始值k=2（線性置換的分支數不小于2）；其次當SAT模型沒有滿足解，逐漸增大分支數的值，直到SAT模型有滿足解時，就可以確定此滿足解k即為分支數的大小。

3 實用效果

為了檢驗基于SAT分支數計算方法的實用效果，本文隨機構造了一批分組為64比特、分塊為8的RX結構的線性擴散層，為有限域上的變換，分別測試了循環移位項數為7、9時的分支線。

當循環移位項數為7時，RX結構擴散層表示形式為：

式中：x為64比特；a，b，c，d，e，f，g為循環移位常數。7項循環移位常數需要滿足以下性質：

使用基于SAT的分支數計算方法測試其分支數，由于RX結構的線性擴散矩陣是對合的，因此差分分支數和線性分支數的大小相等，因此統一用分支數來表示，表1為循環移位常數(a,b,c,d,e,f,g)取不同值時的部分測試結果。

表1 異或項數為7時分支數測試數據

從表1中可以看出，異或項數為7時，測試分支數的速度很快，通常在1分鐘內就可以測試出分支數的大小。

當循環移位項數為9，RX結構擴散層表示形式為：

式中：x為64比特，循環移位項數為9，分別為(a,b,c,d,e,f,g,h,i)。循環移位項數需要滿足以下性質：

式中：i和其他移位項目彼此不相等。表2為循環移位常數(a,b,c,d,e,f,g,h,i)取不同值時的部分測試結果。

表2 異或項數為9時分支數測試數據

共測試了4 000組不同移位項數的RX結構的分支數，本文方法均能在較短的時間內計算出分支數大小，平均用時僅為560s。同時，首次通過隨機構造再測試的方法得到異或項數為9時，分支數達到8的3個RX結構的擴散層。分別為：

由于本文借助的是SAT求解器，SAT求解器采用的是啟發式算法，不能精確估計需要的時間。因此，僅能通過大量的實驗得出：對一般的線性擴散層，利用SAT求解器均能在較短的時間測試出分 支數。

4 結語

本文提出了一種基于SAT的快速計算線性擴散層分支數的通用方法，將線性擴散層差分和線性分支數的計算問題轉換為SAT問題，并給出了詳細的建模方法和搜索過程。利用本文提出的方法計算了一批隨機構造的RX結構線性擴散層的分支數，首次得到分組為64、分塊為8、異或項數為9時，分支數達到8的線性擴散層。本方法對密碼算法的設計和分析都具有一定的實用價值。由于借助的是SAT求解器，無法精確估計測試分支數的時間，后續會繼續通過大量的實驗來進一步驗證本方法的有 效性。