基于SAT的線性擴(kuò)散層分支數(shù)的快速計(jì)算方法

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

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

0 引言

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

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

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

1 基本概念

1.1 線性擴(kuò)散層

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

圖1 線性擴(kuò)散層

線性擴(kuò)散層內(nèi)部通常由移位、異或等線性操作組成，外部輸入輸出為：

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

1.2 分支數(shù)

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

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

對任何線性變換θ，因?yàn)棣?x)⊕θ(x*)=θ(x⊕x*)，所以差分分支數(shù)和分支數(shù)是一致的，計(jì)算方法相同。

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

2 分支數(shù)計(jì)算轉(zhuǎn)換為SAT

本節(jié)將線性擴(kuò)散層分支數(shù)的計(jì)算問題轉(zhuǎn)換為SAT問題，借助SAT求解器強(qiáng)大的計(jì)算能力，可以快速計(jì)算出線性擴(kuò)散層的分支數(shù)。

2.1 SAT

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

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

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

2.2 分支數(shù)計(jì)算轉(zhuǎn)換為SAT

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

線性擴(kuò)散層中使用的賦值、拉線、移位操作，實(shí)質(zhì)均是賦值表達(dá)，假設(shè)x為賦值操作的輸入，y為賦值操作的輸出，即表示x=y表達(dá)式，用合取范式表示為：

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

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

圖2 異或操作

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

異或的線性傳播關(guān)系用合取范式表示為：

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

圖3 分支操作

分支的差分傳播關(guān)系合取范式表示為[21]：

分支的線性傳播關(guān)系合取范式表示為：

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

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

2.3 搜索算法

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

計(jì)算分支數(shù)大小，即統(tǒng)計(jì)線性擴(kuò)散層的輸入輸出非零字塊xi的最小個數(shù)，本質(zhì)是判定以下不等式是否成立。

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

圖4 序列編碼電路

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

將該約束條件寫入SAT模型即可判斷指定活躍S盒個數(shù)k是否有滿足解?？捎盟惴?進(jìn)行搜索求解。

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

3 實(shí)用效果

為了檢驗(yàn)基于SAT分支數(shù)計(jì)算方法的實(shí)用效果，本文隨機(jī)構(gòu)造了一批分組為64比特、分塊為8的RX結(jié)構(gòu)的線性擴(kuò)散層，為有限域上的變換，分別測試了循環(huán)移位項(xiàng)數(shù)為7、9時(shí)的分支線。

當(dāng)循環(huán)移位項(xiàng)數(shù)為7時(shí)，RX結(jié)構(gòu)擴(kuò)散層表示形式為：

式中：x為64比特；a，b，c，d，e，f，g為循環(huán)移位常數(shù)。7項(xiàng)循環(huán)移位常數(shù)需要滿足以下性質(zhì)：

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

表1 異或項(xiàng)數(shù)為7時(shí)分支數(shù)測試數(shù)據(jù)

從表1中可以看出，異或項(xiàng)數(shù)為7時(shí)，測試分支數(shù)的速度很快，通常在1分鐘內(nèi)就可以測試出分支數(shù)的大小。

當(dāng)循環(huán)移位項(xiàng)數(shù)為9，RX結(jié)構(gòu)擴(kuò)散層表示形式為：

式中：x為64比特，循環(huán)移位項(xiàng)數(shù)為9，分別為(a,b,c,d,e,f,g,h,i)。循環(huán)移位項(xiàng)數(shù)需要滿足以下性質(zhì)：

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

表2 異或項(xiàng)數(shù)為9時(shí)分支數(shù)測試數(shù)據(jù)

共測試了4 000組不同移位項(xiàng)數(shù)的RX結(jié)構(gòu)的分支數(shù)，本文方法均能在較短的時(shí)間內(nèi)計(jì)算出分支數(shù)大小，平均用時(shí)僅為560s。同時(shí)，首次通過隨機(jī)構(gòu)造再測試的方法得到異或項(xiàng)數(shù)為9時(shí)，分支數(shù)達(dá)到8的3個RX結(jié)構(gòu)的擴(kuò)散層。分別為：

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

4 結(jié)語

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