王念平，洪禮榮

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

1 引言

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

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

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

圖1 MARS 密碼結(jié)構(gòu)

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

圖2 類MARS 密碼結(jié)構(gòu)

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

2 預(yù)備知識

3 類MARS 密碼結(jié)構(gòu)的線性特性分析

首先，給出3 個引理。

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

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

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

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

4 線性變換的一種優(yōu)化設(shè)計

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

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

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

圖3 一類特殊的類MARS 密碼結(jié)構(gòu)

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

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

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

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

表1 2 種密碼結(jié)構(gòu)的活動輪函數(shù)個數(shù)的下界與L(t)的比較

5 結(jié)束語

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