【導(dǎo)讀】設(shè)計(jì)優(yōu)良的S盒保證密碼算法能夠較好地抵抗差分密碼分析和線性密碼分析等攻。擊，而S盒任何不好的性質(zhì)都可能會影響到整個密碼算法的安全性。本文對中國分組密。代數(shù)次數(shù)等性質(zhì)，理論上證明了SMS4算法S盒所擁有的一些較好的安全特性。一些較好的安全特性。

　　

【正文】 關(guān)免疫的。 定理 f(x)是正交的，則 f(x)是 J階相關(guān)免疫的充要條件是對于任意的jvWGFu Hn ??? )(1:)2( 及 mii ??1: ，有 S(f)(ei,v)=0 定理 (X)是 J階彈性函數(shù)，當(dāng)且僅當(dāng)對于任意的 mGFu )2(? 是 J階平衡相關(guān)免疫函數(shù)，當(dāng)且僅當(dāng)對于任意的， jvWGFu Hn ??? )(1:)2( 及 0:)2( ?? uGFu m ,有S(f)(u,v)=0. 定義 (x):GF(2)n一 GF(2)m,nm,X1,x2,...,xn是 n個獨(dú)立的，均勻分布的二元隨機(jī)變量，隨機(jī)向量 Z=f(x)=(f1(x),...,fm(x))。如果對于任意的 jiii , 21 ? ， nii j ???? ?11 及 kuWGFu Hm ??? )(1:)2( ,U*Z與 ? ?ixii xxx , 21 ? 統(tǒng)計(jì)獨(dú)立，? ? ??? ikiiixii xxxaaxf ?21...210 17 則稱 f(x)是 k級 J階相關(guān)免疫的。 定理 (x) 是 k 級 i 階 相 關(guān) 免 疫 的 充 分 必 要 條 件 是 對 于 任 意 的jvWGFu Hn ??? )(1:)2( 及 kuWGFu Hm ??? )(1:)2( ，有 S(f)(u,v)=0。 第四章 S盒的設(shè)計(jì)準(zhǔn)則與設(shè)計(jì)方法 S盒首次出現(xiàn)在 lucifer算法中，隨后因 DES的使用而廣為流行。 S盒是許多密碼算法中唯一的非線性部件，因此，它的密碼強(qiáng)度決定了整個密碼的安全強(qiáng)度。自從 1977年美國數(shù)據(jù)加密標(biāo) 準(zhǔn) DES公布后，最近幾年隨著高級數(shù)據(jù)加密標(biāo)準(zhǔn) (AES)和 NESSIE計(jì)劃的推出了許多數(shù)據(jù)加密算法的基本模型，例如 Rijndael,MARS,Camellia和 MISTY1等。這些加密算法的安全性均基于 S盒的密碼強(qiáng)度，而這些 S盒本質(zhì)上均可看作是一組非線性布爾函數(shù)的有機(jī)組合。 S盒主要提供了分組密碼算法所必須的混淆作用，但如何全面準(zhǔn)確地度量 S盒的密碼強(qiáng)度，如何設(shè)計(jì)安全有效的 S盒是分組密碼設(shè)計(jì)和研究中的難題。目前， S盒主要用以下指標(biāo)來度量 :非線性度、差分均勻度、代數(shù)次數(shù)和項(xiàng)數(shù)分布、正交性、雪崩效應(yīng)和擴(kuò)散特性。 SP網(wǎng)絡(luò)結(jié)構(gòu)的密碼還要求 S盒具有可逆性。另外，一個密碼要讓別人放心使用，還要求 S盒沒有陷門。目前比較流行的是 8X8的 S盒。 S盒的數(shù)學(xué)描述 定義 S:GF(2)nGF(2)m為 nxm的 S盒 (也稱為多輸出函數(shù)或向量函數(shù) )，記做 Y=S(x)其中 ? ? ? ?nn GFxxx 2,1 ?? ? , ? ? ? ?mm GFyyy 2,1 ?? ? . 在實(shí)際中一般要求 mn? .DES有 6x4的 S盒， LDKI有 12x8的 S盒，在 AES中， Rijndael有 8x8的 S盒 ,Towfish有 8x8的 S盒， Serpent有 4x4的 S盒 。NESSIE中， MISTYI有 7x7和 9x9的 S盒， Camellia有 8x8的 S盒。關(guān)于參數(shù) m,n的選擇目前普遍認(rèn)為是越大越 好，而且 m,n值應(yīng)當(dāng)接近，這樣難以發(fā)現(xiàn)某些攻擊 (如差分密碼分析和線性密碼分析 )所用的統(tǒng)計(jì)特征，而且 m,n很大時，幾乎所有的 S盒均是非線性的，有較好的抗線性分析能力。但反過來， m和n過大將給 S盒的設(shè)計(jì)帶來困難，而且增加算法的存儲量。 顯然，一個 nXm的 S盒可以表示為 GF(2)n上 m個布爾函數(shù) Yi=fi(x1,...， xn)的 組合S(x)=(f1(x),...,fn(x))，因此 S盒的許多密碼學(xué)性質(zhì)都可以用多輸出布爾 函 數(shù)來描述。 S盒的設(shè)計(jì)準(zhǔn)則 S盒主要提供了分組密碼算法所必須的混淆作用，但如何全面準(zhǔn)確地度量強(qiáng)度，如何設(shè)計(jì)安全有效的 S盒是分組密碼設(shè)計(jì)和分析中的研究難題。目前， S盒主要用 以下指標(biāo)來 18 度量 :非線性度、正交性、差分均勻度、雪崩效應(yīng)和擴(kuò)散特性、 代數(shù)次數(shù)和項(xiàng) 數(shù)分布。 SP網(wǎng)絡(luò)結(jié)構(gòu)的密碼還要求 S盒具有可逆性。縱觀近幾年的研究結(jié)果 ，給出 S盒如下設(shè)計(jì)準(zhǔn)則。 S盒的非線性度 非線性度的概念最初由 Pieprz業(yè)等人在 1988年引入，它是 S盒的主要設(shè)計(jì)準(zhǔn)則之一，它決定了基于 S盒的密碼算法抗擊線性密碼分析的能力。 定義 f(x):GF(2)nGF(2)是一個 n元布爾函數(shù)，稱 ? ?lfdNHLlf ,m in??為 f(x)的非線性度。其中 Ln表示全體。元線性和仿射函數(shù)之集， d,(f,l)為 f和 l之間的 漢明 距離。 n元布爾函數(shù) f的非線性度的上界為 ]27[121 22 ?? ? nn ，當(dāng)且僅當(dāng) f為 bent函數(shù)時達(dá)到該上界 121 22 ?? ? nn 。 n元 bent布爾函數(shù)是指和每個 線 性布爾函數(shù)的距離都是 121 22 ?? ? nn 的 n元布 爾函數(shù)。因?yàn)?Nf為正整數(shù)，所以 2n 必為正整數(shù)， 這說明 n為偶數(shù)。故 bent函數(shù)存在的必要條件是 n為偶數(shù)。雖然 bent函數(shù)的非線性度最佳，但它存在一些缺陷，例如，它不是平衡的，它的代數(shù)次數(shù)不超過 ]27[2n 。 定義 S(x)=(f1(x)， ? ,fm(x)):GF(2)n– GF(2)m是一個多輸出函數(shù)，則 ? ? ? ?? ?xlxSudN Hs ,m in ?? 為 S(x)的非線性度。 在線性密碼分析中，關(guān)鍵的一步是構(gòu)造單輪的有效線性逼近，而單輪的線性逼近總是離不開 S盒的線性逼近。令 S(x):GF(2)nGF(2)m,xy=S(x)是一個 nXm的 S盒，它的任意線性逼近都可以表示為 : a*x=b*y 其中 nGFa )2(? mGFb )2(? 。而且上式成立的概率 P滿足nsNP 22121 ???、 ,且稱21?P為線性逼近優(yōu)勢。 由此可見，針對線性密碼分析 ， S盒的非線性度越大越好。利用布爾函數(shù)非線性度的有關(guān)結(jié)果可得 :4Xm的 S盒和 8Xm的 S盒的最佳優(yōu)勢為 22和 24。 引理 令 S(x):GF(2)nGF(2)m,A 是 GF(2) 上的一個 nXn 的可逆矩陣 , nGFb )2(? , mGFc )2(? ，令 G(x)=S(xA+b)+c，則 S和 G有相同的非線性度。 S盒的正交性 從本質(zhì)上說，我們希望 S盒的作用類似于只讀存儲器 址，輸 19 出為存儲器內(nèi)容， 這種性質(zhì)稱為正交性， 同時也稱為等概性或平衡性。 定義 (x)=(f1(x),? ,fm(x)):GF(2)nGF(2)m,若對任意的。 m)(GFa 2? 恰有 2nm個 n)(GFx 2? 使得 f(x)=a，則稱 f(x)是正交的。 強(qiáng)的 S盒必須具備正交性，否則在隨機(jī)均勻輸入下， S盒的某些輸出向量將頻繁出現(xiàn) 密碼分析者可以利用這種不平衡性攻擊基于此 S盒的密碼體制。 引理 S(x):GF(2)nGF(2)m,A是 GF(2)上的一個 nXn的可逆矩陣， n)(GFb 2? ， m)(GFc 2? ，令 G(x)=S(xA+b)+c，則 S和 G有相同的正交性。 證明 :類似于定理 ，由一階廣義 Walsh譜的定義有 : ? ?? ? ? ? ? ?? ? ? ? ? ?? ?39。,1,1, 1 vuSvAuSvuS SSG ???? ? 其中 v’ =vA1，顯然當(dāng) v遍歷 GF(2)n時 v39。也遍歷 GF(2)n. 由定理 S(x)是正交的，當(dāng)且僅當(dāng) m)(GFu 2? , ? ?? ? 00,0 ?? uSu S . 顯然當(dāng) S正交時，對于任意的 02 ?? u,)(GFu m ，有 S(s)(u,0)=0，則對于任意的02 ?? u,)(GFu m ，有 S(G)(u,0)= S和 G有相同的正交性。 引理 令 S(x):GF(2)nGF(2)m,A 是 GF(2) 上 的 一 個 mxm 的 可 逆 矩 陣 ，n)(GFb 2? m)(GFc 2? ，令 G(x)=(S(x+b)+c)A，則 S和 G有相同的正交性。 證明 : 類 似 于 定 理 的 證 明 過 程 ， 由 一 階 廣 義 Walsh 譜 的 定 義有 : ? ? ? ? ? ?? ? ? ? ? ?? ?vuSvuASvuS suc Avbsuc AvbG ,39。1,1,)( ?? ???? 其中 u39。=uA，顯然當(dāng) u遍歷 GF(2)m時 u’也遍歷 GF(2)m，且 0?u 時 039。?u . 由定理 S(x)是正交的，當(dāng)且僅當(dāng) mGFu )2(? ， ? ?? ? 00,0 ?? uSu s 。 顯然當(dāng) S正交時，對于任意的 039。,)2(, ?? uGFu m ,有 S（ G） (u,0)=0,則對于任意的 039。,)2(, ?? uGFu m ，有 S(G)(u,0)=0，其中 u39。= S和 G有相同的正交性。 S盒的強(qiáng)嚴(yán)格雪崩特性與強(qiáng)擴(kuò)散特性 嚴(yán)格雪崩特性和擴(kuò)散特性用于衡量 S盒的輸入改變對輸出改變的隨機(jī)性，它也是 S盒設(shè)計(jì)的重要指標(biāo)之一，因?yàn)椴罘置艽a分析的本質(zhì)取決于輸入輸出改變量的不均勻分布。 20 定義 (x):GF(2)nGF(2)m ， 如 果 對 于 任 意 的 niGFe ni ??? 1,)2( , 都有S(x)+S(x+ei)的每個分量函數(shù)的任意線性組合都是一個平衡函數(shù)，則稱 S滿足強(qiáng)嚴(yán)格雪崩準(zhǔn)則。其中 i個分量為 1，其余分量為 0。 定義 (x):GF(2)nGF(2)m，如果 aEGF(x)，使得 S(x)+S(x+a)的每個分量函數(shù)的任意線性組合都為平衡函數(shù)，則稱 S關(guān)于。滿足強(qiáng)擴(kuò)散準(zhǔn)則。如果對所有的向量? ? kaWxGFa Hn ??? 1,)( ， S關(guān)于 a滿足強(qiáng)擴(kuò)散準(zhǔn)則，則稱 S滿足強(qiáng) k次擴(kuò)散準(zhǔn)則。 擴(kuò)散準(zhǔn)則從本質(zhì)上講就是輸入改變對于輸出的影響，滿足擴(kuò)散準(zhǔn)則就是說對于輸入改變 a, nxGFu )(? ，導(dǎo)致輸出的改變概率為 。對于 S盒的擴(kuò)散準(zhǔn)則，從理論上來說，過分強(qiáng)調(diào) S盒的擴(kuò) 散準(zhǔn)則將限制其他準(zhǔn)則的滿足，從而給構(gòu)造高強(qiáng)度的 S盒帶來困難。例如，nXm的 S盒滿足 n次擴(kuò)散準(zhǔn)則時，必須要求 n為偶數(shù)， mn 2? ，則 S盒的正交性不能得到滿足，從而要使 S盒滿足擴(kuò)散準(zhǔn)則，同時要保證其他密碼學(xué)性質(zhì)是非常困難的。為了在保證其他密碼學(xué)性質(zhì)的基礎(chǔ)上，同時也能夠衡量 S盒的擴(kuò)散特性，我們引入擴(kuò)散效應(yīng)的逼近優(yōu)勢。定義 (x):GF(2)nGF(2) 關(guān)于。 ? ? kaWxGFa Hn ??? 1,)( 的不變集 ????aUkf 為? ?? ? ? ? ? ? ? ? ? ? ? ? }1,2,:2{ kaWGFaxfaxfGFxaU Hnnkf ??????? 引理 ? ?? ?aUx kf? 則對于任意的 ? ? 1,2 ??? awGFw n ,有 S(f)(w)=0. 證明 :設(shè) ? ?? ?aUx kf? ,有布爾函數(shù)的 Walsh譜定義有 ? ?? ?? ? ? ?? ?? ? ? ?? ?? ? ? ?? ?? ? ? ?? ?? ? ? ?? ?wswSfawGFxxwxfawnGFxawxwxfnGFxawxwaxfnGFxxwxfnfnnnn??????????????????????????????????????11)1(21212122222 若 w*a=1,顯然有 S(f)(w)=0. 定義 (x)=(S1(x),? ,Sm(x)):GF(2)nGF(2)m關(guān)于 a的 k階擴(kuò)散效應(yīng)的逼近 優(yōu)勢為 ? ?? ? ? ??? ?????? ?? mikSnkS UmaP1221211 1 21 定義 (x)=(S1(x),?,S m(x)):GF(2)nGF(2)m的 k階擴(kuò)散效應(yīng)的逼近優(yōu)勢為? ?? ? ? ?????? aPGFaP SkinkS121 引理 令 S(x)GF(2)nGF(2)m ， A 是 GF(2) 上 的 一 個 nXn 的 可 逆 矩 陣 ，nGFb )2(? , mGFc )2(? ， 令 G(x)=S(xA+b)+c，則 S和 G有相同的強(qiáng)擴(kuò)散特性。 證明 :類似于定理 ，由一階廣義 Walsh譜的定義有 : ? ?? ? ? ? ? ?? ? ? ? ? ?? ?39。,1,1, 11 1* vuSvAuSvuS Scuv bAScuv bAG ???? ?? ???? 其中， 139。 ??vAv ，顯然當(dāng)，遍歷 GF(2)n時， V’也遍歷 GF(2)n。 顯然有 S2G)(u,v)=S2(S)(u39。,v) 由定理 :若 S滿足強(qiáng) k階擴(kuò)散準(zhǔn)則，則 ? ?? ?? ? ? ?? ?? ?? ?? ?? ?? ? ?????? ????m mGFu GFu avuSavuG vuSvuS2 2 39。22 1139。,1, ?? 則 G滿足強(qiáng) k階擴(kuò)散準(zhǔn)則。 所以， S和 G有相同的強(qiáng)擴(kuò)散特性。 引理 令 S(x):GF(2)nGF(2)m,A 是 GF(2)上的一個。 Xm 的可逆矩陣，nGFb )2(? mGFc )2(? 令 G(x)=(S(x+b)+c)A，則 s 和 G 有相同的強(qiáng)擴(kuò)散特性。 證明 : 類 似 于 定 理 的