類MARS 密碼結構的線性特性及其優化設計

王念平，洪禮榮

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

1 引言

線性密碼分析是Matsui[1]在1993 年歐洲密碼年會上提出的一種針對迭代型分組密碼的已知明文攻擊方法，其基本思想是利用分組密碼算法中明文、密文和密鑰之間的不平衡線性逼近來恢復某些密鑰比特。對分組密碼而言，線性密碼分析經過不斷的豐富與發展，已成為最有效的密碼分析方法之一。因此，評估分組密碼抵抗這一攻擊的能力是分組密碼設計中必須考慮的問題。

在對分組密碼抵抗線性密碼分析的能力進行評估時，通常的做法是估計多輪線性逼近中活動輪函數（即輸出線性逼近非零的輪函數）或活動S 盒（即輸出線性逼近非零的S 盒）個數的下界，進而給出最大線性逼近概率的上界。如果該上界足夠小，就可以認為分組密碼具有較強的抵抗線性密碼分析的能力。因此，活動輪函數或活動S 盒的個數是評估分組密碼抵抗線性密碼分析能力的重要指標。

MARS 密碼結構[2-4（]如圖1 所示）是一種典型的密碼結構，例如 AES（advanced encryption standard）競賽的5 個最終候選算法之一的MARS[2]就采用了這樣的結構。針對MARS 密碼結構，人們進行了深入的研究。文獻[3]研究了MARS 密碼結構的隨機性。文獻[5-7]對MARS 密碼結構或嵌套代替?置換網絡（SPN,substitution-permutation network）的MARS 密碼結構抵抗線性密碼分析的能力進行了詳細的分析。文獻[8]利用不可能差分歸一化（UID,unified impossible differential）方法找到了廣義MARS 密碼結構的11 輪不可能差分。文獻[9]研究了類MARS 密碼結構的不可能差分，證明了n分支類MARS 密碼結構存在3n? 1輪不可能差分，且當n是奇數時，任意輪結構均存在不可能差分。文獻[10]進一步研究嵌套SPN 結構的類MARS 密碼結構，將不可能差分的長度擴展至12 輪，且這個結果與輪函數和擴散層的結構無關。文獻[11]針對嵌套SPN 結構的MARS 密碼結構，利用計算機搜索算法找到了1～21 輪差分特征中活動S 盒個數的下界，并指出該算法可直接用于線性密碼分析，即通過考慮對偶結構來計算線性逼近中活動S 盒個數的下界。文獻[12]證明了MARS 密碼結構和SMS4 密碼結構[4]之間存在差分?線性對偶性，再結合文獻[13]對SMS4 密碼結構的評估結果，給出目前針對MARS 密碼結構的多輪線性逼近中活動輪函數個數下界的最新理論成果。具體地，對于 MARS 密碼結構，當輪函數是雙射時，5i+j(i≥0,0≤j≤4)輪線性逼近至少有個活動輪函數，其中表示不大于x的最大整數（下同）。

圖1 MARS 密碼結構

現在的問題是對于如圖1 所示的MARS密碼結構，如果將其中的線性變換（即循環左移變換）用{0,1}4上的某個線性雙射（對應于某個4 階0,1 可逆矩陣）代替，那么活動輪函數個數的下界可能達到的最大值是多少？另外，能否找到一種線性雙射，使活動輪函數個數的下界達到或接近可能的最大值？基于這種想法，本文提出了類MARS 密碼結構，如圖2 所示，研究了該密碼結構的線性特性，并給出了線性變換的一種優化設計方法。這里所說的類MARS 密碼結構是指每一輪中的線性變換從{0,1}4上的線性雙射（對應于4 階0,1 可逆矩陣）中選取。在此特別指出，每一輪中的線性變換從{0,1}4上的線性雙射中選取并不是說{0,1}4上的每一個線性雙射都是合適的。例如，恒等映射作為每一輪中的線性變換顯然就不合適。事實上，在實際的密碼設計中，每一輪中的線性變換一般從那些性能較好的、合適的線性雙射中選取。

圖2 類MARS 密碼結構

本文的研究結果表明，對于類MARS 密碼結構，每一輪中的線性變換只要從{0,1}4上的線性雙射中選取，無論怎樣設計線性變換，t(1≤t≤ 3)輪線性逼近中都至少有一條線性逼近，其活動輪函數的個數為0；4 輪線性逼近中至少有一條線性逼近，其活動輪函數的個數 ≤ 1；t(t>4)輪線性逼近中至少有一條線性逼近，其活動輪函數的個數≤8t/15。這些線性逼近是由類MARS 密碼結構本身決定的，或者說是固有的線性特性。在此基礎上，本文給出了線性變換的一種優化設計方法，該優化設計使活動輪函數個數的下界與MARS 密碼結構相比更加接近可能的最大值。

2 預備知識

3 類MARS 密碼結構的線性特性分析

首先，給出3 個引理。

定理2 實際上是說，無論每一輪中的線性變換怎樣設計，t(t>4)輪線性逼近的活動輪函數個數的下界≤。

為方便起見，將定理1 和定理2 合寫成定理3。

定理3對于圖2 所示的類MARS 密碼結構，t(t≥ 1)輪線性逼近中至少有一條線性逼近，其活動輪函數的個數≤L(t)。其中

由定理3 知，無論每一輪中的線性變換怎樣設計，t(t>4)輪線性逼近的活動輪函數個數的下界都小于或等于L(t)。

4 線性變換的一種優化設計

本節給出類MARS密碼結構中線性變換的一種優化設計方法，該優化設計使活動輪函數個數的下界與MARS 密碼結構相比更加接近可能的最大值L(t)。

圖3 是一類特殊的類MARS 密碼結構，其中虛線方框部分表示線性變換。由圖3 可知，其1 輪輸入與輸出的關系式可以表示為

其中，k表示輪密鑰，⊕表示異或運算，fk表示輪函數，N表示線性變換（即圖3 中虛線方框部分）所對應的4 階0,1 可逆矩陣，N。

圖3 一類特殊的類MARS 密碼結構

為了直觀起見，針對1～32 輪的情形，將MARS密碼結構（如圖1 所示）、一類特殊的類MARS 密碼結構（如圖3 所示）的活動輪函數個數的下界與定理3 中L(t)的值進行比較。其中，MARS 密碼結構的下界是指圖1 所示的MARS密碼結構的活動輪函數個數的下界，該結果由文獻[12-13]可得。特殊的類MARS密碼結構的下界是指圖3 的一類特殊的類MARS 密碼結構的活動輪函數個數的下界，該結果可利用與文獻[13]類似的推導方法得出，在此不再贅述。

2 種密碼結構的活動輪函數個數的下界與L(t)的比較如表1 所示。由表1 可以看出，當線性逼近的輪數較大時，MARS 密碼結構的活動輪函數個數的下界與L(t)相比有較大的差距。例如，當線性逼近的輪數 ≥ 21時，二者的差值 ≥ 3；當線性逼近的輪數≥ 27時，二者的差值 ≥ 4；當線性逼近的輪數為32時，二者的差值為5。但這類特殊的類MARS 密碼結構的活動輪函數個數的下界與L(t)更加接近。當線性逼近的輪數為6、17、19、20、21、23、25、30、31 和32 時，二者的差值為2；當線性逼近的輪數為5、7、8、9、10、11、12、15、16、18、22、24、26、27 和29時，二者的差值為1；其他情形下二者的差值為0。

以上分析結果表明，從抵抗線性密碼分析的角度來講，這類特殊的類MARS 密碼結構中的線性變換設計得較好。從應用層面來講，當輪數 ≥ 12時，這類特殊的類MARS 密碼結構的活動輪函數個數的下界比MARS 密碼結構的活動輪函數個數的下界要大，這意味著與MARS 密碼結構相比，采用這類特殊的類MARS 密碼結構的密碼算法可以在更少輪數內達到足夠的安全強度。從實現效率來講，這類特殊的類MARS 密碼結構僅增加了少許異或運算，對于算法的實現效率影響不大。

實際上，圖3 中的線性變換（即虛線方框部分）僅僅是一種優化設計方法。除此之外，還有其他的優化設計方法，使在相同的輪數下，活動輪函數個數的下界與MARS 密碼結構相比更接近于L(t)（L(t)的含義見定理3）。例如，將圖3 中的線性變換用它的逆變換代替，也可以得到相同的活動輪函數個數的下界。從道理上講，通過分析全部可能的線性變換，就可以找到類MARS 密碼結構中線性變換的最優化設計，但由于異或運算“⊕”的影響，使搜索到的活動輪函數個數的下界比實際的下界可能要小，因此不能確定圖3 中的線性變換是否最優。如何尋找類MARS 密碼結構中線性變換的最優化設計，還需要進一步的探討。另外，本文的研究結果表明，無論類MARS 密碼結構中的線性變換怎樣設計，多輪線性逼近中活動輪函數個數的下界都不可能超過某個值，這些特性是由類MARS 密碼結構本身決定的，它揭示了類MARS 密碼結構固有的線性特性，這種研究方法對其他分組密碼結構的研究也具有一定的借鑒意義。例如，用本文的研究方法可以證明，對類SMS4 密碼結構（即將SMS4 密碼結構中的線性變換用{0,1}4上的線性雙射代替），也有與定理1～定理3 類似的結論成立。

表1 2 種密碼結構的活動輪函數個數的下界與L(t)的比較

5 結束語

本文提出了類MARS 密碼結構，通過分析一類具有特殊結構的線性逼近的傳遞規律，給出了該密碼結構的若干線性特性。具體地，不論每一輪的線性變換怎樣從{0,1}4上的線性雙射中選取，t(1≤t≤ 3)輪線性逼近中至少有一條線性逼近，其活動輪函數的個數為0；4 輪線性逼近中至少有一條線性逼近，其活動輪函數的個數不超過1；t(t>4)輪線性逼近中至少有一條線性逼近，其活動輪函數的個數不超過。在此基礎上，給出了類MARS 密碼結構中線性變換的一種優化設計方法，該優化設計使活動輪函數個數的下界與MARS 密碼結構相比更加接近可能的最大值L(t)（L(t)的含義見定理3），從抵抗線性密碼分析的角度來講，該線性變換設計得較好。