類MARS 密碼結(jié)構(gòu)的線性特性及其優(yōu)化設(shè)計(jì)

王念平，洪禮榮

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

1 引言

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

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

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

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

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

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

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

2 預(yù)備知識(shí)

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

首先，給出3 個(gè)引理。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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