【導(dǎo)讀】本文對中國分組密碼新標(biāo)準(zhǔn)SMS4算法、美國高級(jí)加密標(biāo)準(zhǔn)AES、示各個(gè)算法S盒的優(yōu)缺點(diǎn)。

　　

【正文】 計(jì)中，為了防止插入攻擊， 通常要求 變換的代數(shù)式具有足夠高的次數(shù)和復(fù)雜度。 S盒的代數(shù)表達(dá)式可以 用如下 拉格郎日 插 值多項(xiàng)式求出， 2552550 ,0()jii j i j ijxxf x y xx? ???? ?? ? )255,...,1,0( ?i )255,...,1,0( ?j 其中的運(yùn)算 是 在 有 限 域 )2( 8GF 上 實(shí)施 的 ， 有 限 域 以 不 可 約多項(xiàng)式8 4 3 1( ) 1m x x x x x? ? ? ? ?為生成多項(xiàng)式， 以 元素 1??x? 為 生成元 。 差分特性 差分密碼分析 是以色列密碼學(xué)家 EliB iham 和 AdiS hamir 于 1990 年提出的一種選擇明文攻擊方法，是迄今為止攻擊迭代密碼 (所謂迭代密碼就是以迭代一個(gè)簡單的輪函數(shù)為基礎(chǔ)的密碼，在密鑰控制下以迭代方式多次利用它進(jìn)行加密變換 )最有效的方法之一，其基本思想是通過分析特定明文差對相應(yīng)密文差的影響來獲得可能性最大的密鑰，它 是目前對分組密碼最為有效的攻擊方法之一 ， 雖然差分攻擊方法未 能破譯 16 一輪的 DES，但是用它破譯輪數(shù)低的 DES 是很成功的。 差分密碼分析主要利用了 S 盒差分分布矩陣中的特殊元素，如果某些元素值明顯大于 其它 元素值，則這些位置 將 有助于差分攻擊。 因此 ， S盒抗差分密碼分析能力 的研究主要 從其差分分布矩陣 著手。 采用類似文獻(xiàn)的思想，我們對 S 盒的差分均勻度和 差分分布矩陣 進(jìn)行如下定義： 定義 1 mn? S盒 )2()2(: mn GFGFf ? 的 差分均勻度 定義 為 }12, .. .,1,0。12, .. .,1,0|m a x { ????? mnijf ji?? ， 其中， |})()(|)2({| jinij xfxfGFx ??? ????? ， ji ??, 分別為 ji, 的二進(jìn)制表示 ， 21 12, .. .,1,0。12, .. .,1,0 ???? mn ji 。 S盒差分分布矩陣 定義為 ?????????????????????)12)(12(1)12(0)12()12(11110)12(00100)(mnnnmmf????????????????? 線性特性 線性密碼分析是一種已知明文攻擊，最早由 Matsui 在 1993 年的歐密會(huì)上提出。 其基本思想是通過尋找一個(gè)給定密碼算法的有效的線性近似表達(dá)式來破譯密碼系統(tǒng)。線性密碼分析可用 247 個(gè)己知明文破譯 16 輪 DES，并且在某些情況下能夠唯密文攻擊。現(xiàn)行線性攻擊的推廣也很多，如多重線性密碼分析、非線性密碼分析、劃分密碼分析等。 該攻擊方法的目標(biāo)是尋找到并利用明文 P ，密文 C 和密鑰 K 的若干位之間的一個(gè)線性表達(dá)式 )()()( ??? ????? KCP 。該表達(dá)式成立的概率與 21 的偏差大小是線性密碼分析成功的一個(gè)重要的衡量指標(biāo)。線性密碼分析思想歸結(jié)到核 心部件 S 盒就是要考察其輸入輸出比特之間的相關(guān)關(guān)系，用以下的線性分布矩陣來刻劃。 定義 2 mn? S盒 )2()2(: mn GFGFf ? 的 線性分布矩陣 定義 為 ?????????????????????)12)(12(1)12(0)12()12(11110)12(00100)(mnnnmmf?????????????????， 其中，對 mn GFGF )2(,)2( ?? ?? ， 1][10 ][][10 ][ 2|})2(|{| ????? ??????? ?? ntmt tsns sn xxGFxx ??? ?? ， 這里 ][10 ][ sns sx ??? ??和 ][10 ][ tmt tx ??? ??為二進(jìn)制向量的內(nèi)積運(yùn)算。 S 盒布爾函 數(shù)的性質(zhì) 布爾函數(shù)在當(dāng)今密碼設(shè)計(jì)與分析中具有非常重要的地位，在最近 20年關(guān)于布爾函數(shù)的性質(zhì)以及具有特殊性質(zhì)的布爾函數(shù)構(gòu)造一直是密碼學(xué)中最活躍的研究領(lǐng)域之一。布爾 22 函數(shù) (單輸出和多輸出 )在密碼算法的設(shè)計(jì)與分析中，不僅具有重要理論意義，也有著一定的應(yīng)用價(jià)值。例如在流密碼中最常用的密鑰流生成器是非線性濾波生成器和非線性組合生成器，對它們的研究可歸結(jié)為對布爾函數(shù)的研究。而現(xiàn)代分組密碼體制中普遍使用的核心模塊 s一盒的研究亦可歸結(jié)為多輸出布爾函數(shù)的研究。人們對布爾函數(shù)的各種性質(zhì)進(jìn)行了大量研究，對布爾函數(shù)的非線性次數(shù)、非線 性度及相關(guān)度、線性結(jié)構(gòu)與退化性、穩(wěn)定性與相關(guān)免疫性、嚴(yán)格雪崩準(zhǔn)則 (SAC)和擴(kuò)散準(zhǔn)則等進(jìn)行了深入研究，特別是對抵抗相關(guān)攻擊的相關(guān)免疫函數(shù)類、抗線性分析的 Bent函數(shù)類進(jìn)行了系統(tǒng)的研究，取得了豐碩的成果。 在研究序列密碼中多個(gè) LFSR 的非線性組合序列器的破譯問題時(shí)，針對驅(qū)動(dòng)序列的信息在輸出序列中的一種熵漏實(shí)施的攻擊稱為相關(guān)攻擊。為此，日本學(xué)者 Siegenthalar 于1984 年率先提出組合函數(shù)相關(guān)免疫的概念。值得肯定的是，具有相關(guān)免疫性的布爾函數(shù)能抵抗分別征服攻擊 (DC)和一定階的仿射攻擊。為了研究密鑰流序列 的線性復(fù)雜度的穩(wěn)定性和使一些流密碼能抗 BAA攻擊， Rothans于 1976年提出一種穩(wěn)定的布爾函數(shù) —— Bent函數(shù)。 Bent 函數(shù)具有穩(wěn)定性、能抵抗最優(yōu)仿射逼近攻擊 (BAA)、抵抗差分攻擊和具有最高的非線性度等良好的密碼學(xué)性質(zhì)，但也存在無相關(guān)免疫性、不平衡等缺點(diǎn)。后來， C． Carlet和 Partially對 Bent的概念進(jìn)行了推廣，提出了部分 Bent函數(shù)、半 Bent函數(shù)和廣義 Bent函數(shù)等概念。對于多輸出布爾函數(shù)，有類函數(shù)既具有相關(guān)免疫又具有平衡性，這就是有Chor 和 Bent 等人分別提出的彈性函數(shù)。該函 數(shù)的應(yīng)用領(lǐng)域包括容錯(cuò)分布計(jì)算、量子密碼密鑰分配和序列密碼的隨機(jī)序列生成。 定義 3 將 GF(2)上的函數(shù)稱為布爾函數(shù)，即定義 n 元布爾函數(shù) )(xf 為如下映射： f : (2) (2)nGF GF? ， 其中， (2)nx GF? , ( ) (2)f x GF? 。 定義 4 n 元布爾函數(shù) ()fx的次數(shù) 定義為其多項(xiàng)式表達(dá)式 ???? ?110)( xaaxf nnnnnnnn xxxaxxaxxaxa ??? ? 2112112112 ????? ??中最高次項(xiàng)的次數(shù) 1...max{ | 0}j jkka ?， 記為 degf 。 若 degf =1，則稱 ()fx為仿射函數(shù)。當(dāng) 0 0a? 時(shí) ， 仿射函數(shù)被稱為線性函數(shù)。當(dāng) degf 2? 時(shí)，稱為 ()fx非線性函數(shù)。 定義 5 對 n 元 布爾 函數(shù) )2()2(: GFGFf n ? ，若其 真值表中 “1” 的個(gè)數(shù)等于 “0”的個(gè)數(shù) ，即均為 12?n ，則稱 f 滿足平 衡性 (Balanceness)。 各種分組密碼 算法的 S盒是一個(gè) 8)2(GF 到 )2(GF 的一一映射 ， 當(dāng)輸入遍歷 0～ 255時(shí) ， 23 輸出也遍歷 0～ 255， 所以每一個(gè)輸出 比特位置上 都含有 128 個(gè) “1” ， 128 個(gè) “0” ， 從而 它們 S盒的每一輸出比特均是平衡的 。 定義 6 設(shè) ()fx是一個(gè) n 元布爾函數(shù) ，記 ??xLn 為所有 n 元 線性函數(shù) (包括仿射函數(shù) )之集。 ()fx的非線性度 定義為 )(min),(min][][ lfwlfd xLlxLl nn ?? ??，記為 fN ，即 ()fx的非線性度 為 其與所有線性函數(shù)之最短距離 。稱 ),(m ax][ lfdxLl n?為 ()fx的線性度，即 ()fx的線性度 是 ()fx與所有線性函數(shù)的最大距離。若 ()fx的非線性度 滿足 fN = 1211 22 ?? ? nn ，則稱 ()fx為 Bent 函數(shù)，也稱完全非線性函數(shù)。 布爾函數(shù) ()fx的非線性度 fN 是用來衡量抵抗 “ 線性攻擊 ” 能力的一個(gè)非線性準(zhǔn)則，fN 越大，則在某種意義上布爾函數(shù) ()fx抵抗 “ 線性攻擊 ” 的能力越強(qiáng) ； 反之， fN 越小，則布爾函數(shù) ()fx抵抗 “ 線性攻擊 ” 的能力越弱。 ()fx的非線性度 也可 利用循環(huán)譜的最大值 得 ： 12 ( )2nf aN ?? ， 其中 )(m a x)(120 wSa fw n ????。 定義 7 n 元布爾函數(shù)的循環(huán) Walsh 譜變換定義為 255 ()() 0( ) 2 ( 1 )n f x x wf xSw ? ? ?????， 其中 nGFw )2(? ， nGFx )2(? ， 1100 ... ?????? nn xwxwxw 。 循環(huán)譜 衡量 的是 ()fx與線性函數(shù) wx? 的相符合程度， 也就是 ()fx與線性函數(shù) wx? 相符的 x 的 個(gè)數(shù) 減去 ()fx與線性函數(shù) wx? 不 相 符的 x 的 個(gè)數(shù) 之差。 所以布爾函數(shù)的 Walsh循環(huán)譜的數(shù)值越大，說明布爾函數(shù)的 Walsh 環(huán)譜與線性函數(shù)越接近 ，對應(yīng)的 S 盒就越容易被攻擊，性能越 壞 。 布爾函數(shù)的 另外一種譜值為 線性 Walsh 譜 ，定義如下： 定義 8 n 元布爾函數(shù) 的線性 Walsh 譜變換定義為 2550( ) 2 ( 1 ) ( )n x wfxS w f x???? ? ??， 其中 nGFw )2(? ， nGFx )2(? ， 1100 ... ?????? nn xwxwxw 。 24 兩種譜值是等價(jià)的，它們 之間存在轉(zhuǎn)換關(guān)系()2 ( ) , 0()1 2 ( ) , 0ff fS w wSwS w w????? ?????， 并且 循環(huán)譜的零譜值個(gè)數(shù))(fSN線性譜 的零譜值個(gè)數(shù)fSN+1， 這里不再展開討論線性譜的性質(zhì)。但需要注意的是，由 12/12/)(1 ????fSnnf NN 可知零譜值個(gè)數(shù)和非線性度之間存在著制約關(guān)系：零譜值個(gè)數(shù)過大將導(dǎo)致非線性度的下降，反之非線性度上升。 嚴(yán)格雪崩 準(zhǔn)則用于考察 ()fx輸入變化對輸出變化的影響：即 當(dāng) 任 一輸入比特改變 (從 x 變?yōu)?cx? )時(shí) ， 使輸出發(fā)生 變化 ( )()( cxfxf ?? )的 x 的 個(gè)數(shù)與不 發(fā)生 變化( )()( cxfxf ?? )的 x 的 個(gè)數(shù)是否相等 的問題 ，如果 都 相等， 則 ()fx滿足嚴(yán)格雪崩準(zhǔn)則 ；否則不滿足 嚴(yán)格雪崩準(zhǔn)則。滿足嚴(yán)格雪崩準(zhǔn)則 的函數(shù) ， 其輕微的 輸入變化 將導(dǎo)致 輸出的巨大改變 。 定義 9 設(shè) (2) , 0,nGF????若 1( ( ) ( ) ) 2 nw f x f x ? ?? ? ?，即 ( ) ( )f x f x ???是平衡函數(shù) ， 則稱 ()fx 關(guān)于 ? 滿足擴(kuò)散準(zhǔn)則 PC(Propagation Criterion)。若對任意滿足1 ( )wk???的 ? ， ()fx關(guān) 于 ? 滿足擴(kuò)散準(zhǔn)則 ， 則稱 ()fx滿足 k次擴(kuò)散準(zhǔn)則 ，記為 )(kPC 。若任意固定 ()fx的 m 個(gè)分量的值所得到的 mn? 元函數(shù)均滿足 k 次擴(kuò)散準(zhǔn)則，則稱 ()fx滿足 m 階 k 次擴(kuò)散準(zhǔn)則。 k 次擴(kuò)散準(zhǔn)則 用于進(jìn)一步考察 ()fx輸入變化對輸出變化的影響： 當(dāng) 任何幾個(gè) 輸入比特改變 (從 x 變?yōu)???x )時(shí) ， 輸出發(fā)生 變化 ( )()( ??? xfxf )的 x 的 個(gè)數(shù)與不 發(fā)生 變化( )()( ??? xfxf )的個(gè)數(shù)是否相等 的問題 ，如果 都 相等， 則 ()fx滿足 k 次擴(kuò)散準(zhǔn)則 ；否則不滿足 k次擴(kuò)散準(zhǔn)則。 定義 10 對 n 元布爾函數(shù) ()fx 和 nGF )2(?? ，如果 對于任意 (2)nx GF? 都 有( ) ( )f x f x c?? ? ? (常數(shù) )，則稱 ? 為 ()fx的一個(gè)線性結(jié)構(gòu) 。若 0c? ，則 稱 ? 為 ()fx的一個(gè) 不變線性結(jié)構(gòu) ； 若 1c? ，則 稱 ? 為 ()fx的一個(gè) 恒變線性結(jié)構(gòu) 。 25 4 3 種分組算法代數(shù)性質(zhì)的分析和比較 AES算法 S盒 代數(shù)性質(zhì)分 析 AES算法的 S盒 S盒作為 AES算法的唯一的非線性運(yùn)算直接決定了算法的好壞，它的代數(shù)結(jié)構(gòu)也成為分析的焦點(diǎn)。 S盒運(yùn)算是一個(gè)獨(dú)立作用于狀態(tài)字節(jié)的非線性變換，包括在有限域 GF(2)中的乘法逆的運(yùn)算， GF(2)域下的仿射矩陣變換與常量 ‘ 63’ 的加法運(yùn)算 3個(gè)步驟。 (1)在)1( )()2( 348 28 ????? xxxx xZGF域中求乘法逆的運(yùn)算，即輸入 )2( 8GF?? ，求)2( 8GF?? 滿足： )1m o d (1 348 ?????? xxxx?? 則有： ??? ???? ? 00 02541 ????? (1) (2)令 x=v在 GF(2)8中的元素分量為 ),,( 01234567 xxxxxxxx ，仿射變換如下： ????????????????