動態(tài)策略在S盒設(shè)計中的最新應(yīng)用
相關(guān)鏈接： 中國安全網(wǎng) 中國質(zhì)量網(wǎng) 中國論文網(wǎng) 中國資訊網(wǎng)
作者：鄭曉敏
1 引言
作為分組密碼算法中唯一的非線性部件，S盒的構(gòu)造隨DES算法的流行而引起人們的關(guān)注。S盒的密碼強(qiáng)度對整個分組密碼算法的安全有重要的影響，在抗差分密碼分析和線性密碼分析方面尤為突出。S盒的密碼學(xué)性能主要有下面幾個度量指標(biāo)：差分均勻度、非線性度、正交性、項數(shù)分布、代數(shù)次數(shù)和雪崩效應(yīng)等。隨著傳感器網(wǎng)絡(luò)技術(shù)的發(fā)展，人們對安全的要求也越來越高，密碼算法要想得到廣泛使用，則需要保證使用的S盒有較高的安全強(qiáng)度，且不存在陷門問題。為了避免存在陷門的嫌疑，目前主流的S盒構(gòu)造仍傾向于選取公開的數(shù)學(xué)計算方法。如何在數(shù)學(xué)計算方法構(gòu)造S盒的基礎(chǔ)上提高算法的安全強(qiáng)度，對算法進(jìn)行優(yōu)化改進(jìn)，仍是當(dāng)前研究的重點(diǎn)。近年來，對于動態(tài)S盒的研究已然拉開了序幕。2007年，殷新春等在Rijndael算法的基礎(chǔ)上提出了一種基于密鑰控制的多S盒的Rijndael算法。2012年，Szaban等提出了一種基于CA (cellular automata)的S盒構(gòu)造方法。人們還提出了一些不同的動態(tài)S盒構(gòu)造方法。本文在此基礎(chǔ)上，結(jié)合Fesitel構(gòu)架和S盒重構(gòu)思想，提出了一種與密鑰
和輸入明文相關(guān)的動態(tài)S盒構(gòu)造方法，并對其進(jìn)行了性能分析。
2 S盒的相關(guān)知識
2.1 S盒的基礎(chǔ)
S盒是目前諸多分組密碼算法的核心模塊，因此人們對S盒的構(gòu)造方法以及性能進(jìn)行了大量的研究。在分組密碼算法中，通常使用表格來表示S盒，而與之對應(yīng)的密碼算法中的調(diào)用也大多是通過查表的方式完成。例如，在DES密碼算法中，采用的是6x4的S盒，則使用4行16列的表格來表示：在AES密碼算法中，采用的是8x8的S盒，表示為16行16列的表格。在很多密碼算法設(shè)計中簡化了S盒的模型和計算方法，但其本質(zhì)仍是從域GF(2)n到域GF(2)m的多輸出布爾函數(shù)。
2.2構(gòu)造S盒的數(shù)學(xué)模型
S盒的構(gòu)造主要分為數(shù)學(xué)方法構(gòu)造和智能算法隨機(jī)生成。數(shù)學(xué)方法構(gòu)造相對比較穩(wěn)定，可以有效地保證較好的密碼安全性。在參考文獻(xiàn)中介紹了常用的幾種方法。
(1)對數(shù)函數(shù)和指數(shù)函數(shù)
SAFER系列密碼采用的均是這一組函數(shù)，因為它們擁有良好的密碼學(xué)性能。在8x8的S盒置換中，代數(shù)次數(shù)和項數(shù)與隨機(jī)置換的相應(yīng)值接近，非線性度和差分均勻度也都相對較好。
(2)有限域上的逆映射
有限域上的逆映射是當(dāng)前構(gòu)造S盒的主要方法，許多著名的密碼算法均采用逆映射來完成S盒的構(gòu)造，如Shark、Square等。但由于在有限域GF（2n)中的表達(dá)式太過簡單，導(dǎo)致Shark密碼算法不能有效抵抗插值攻擊。因此常將逆映射與仿射函數(shù)相結(jié)合來彌補(bǔ)這個缺點(diǎn)。
(3)有限域上的冪函數(shù)
冪函數(shù)是人們在尋求構(gòu)造S盒方法的過程中發(fā)現(xiàn)的一種有限域的特殊結(jié)構(gòu)，因其具有一定的研究價值而受到研究人員的關(guān)注，由此誕生了名為冪函數(shù)的一種代數(shù)結(jié)構(gòu)。冪函數(shù)被運(yùn)用到了密碼算法的設(shè)計中。但是，冪函數(shù)的代數(shù)結(jié)構(gòu)相對簡單，難以抵御插值攻擊和高階差分密碼分析攻擊，通常只將冪函數(shù)運(yùn)算作為構(gòu)造S盒的基礎(chǔ)部分。
(4)混沌映射
確定性混沌系統(tǒng)具有很好的不可預(yù)知性和隨機(jī)性，在密碼算法中也占有一席之地�；煦鐚W(xué)中的“初始敏感性”與密碼學(xué)中要求輸入的微小改變能夠引起輸出的較大變化的特性契合，也采用混沌映射構(gòu)造S盒。
3動態(tài)S盒的設(shè)計
3.1 S盒的構(gòu)造
AES優(yōu)質(zhì)密碼S盒的構(gòu)造主要分3步：第一步，求出伽羅瓦域CF(2n)上的既約多項式對應(yīng)狀態(tài)字的逆元；第二步，利用仿射變換公式對得到的逆元結(jié)果做仿射變換；第三步，利用密碼學(xué)性能分析方法從得到的大量S盒中選取性能優(yōu)異的S盒。
3.1.1 求乘法逆元
求某個有限域GF(2n)上的乘法逆元，首先需要知道該域的一個既約多項式。在確定有限域后，通過相關(guān)計算可以求得域GF(2n)上存在的所有n次既約多項式。例如，域GF(2#)上存在3個4次既約多項式，域GF(26)上存在9個6次既約多項式，域GF(28)上存在30個8次既約多項式。在同一個有限域GF（2n)上選取不同的既約多項式，可以計算得到不同的逆元集，同時改變仿射變換公式的輸入變量，進(jìn)而得到更多性能相似而輸出不同的S盒。
3.1.2仿射變換求S盒
在求得選定的既約多項式的乘法逆元之后，便可以將求得的結(jié)果輸入仿射變換公式進(jìn)行S盒的構(gòu)造。目前構(gòu)造S盒的主流仿射變換公式如下：
在域GF(2n)上選取A(x)時，只需要滿足最高次數(shù)是n且較為簡單的多項式，比如選擇多項式A(x）=xn+1。接著選取B(x)，對多項式B(x)的選取則需要保證與A(x)互素。如果選取的A(X)是不可約多項式，由于在有限域內(nèi)不可約多項式與任意多項式互素，B(x)則可以任意選取。然后選取C(x)，C(x)的選取是為了保證得到的S盒不包含反不動點(diǎn)和不動點(diǎn)，因此即使在確定了多項式A(x)和B(x)后，C(x)往往還是存在多種不同選擇，這也可以得到更多的S盒。
例如，在有限域CF(26)中若選取A(x)=x6+1，那么在選取B(x)時，需要與A(x)互素，而X6+1=(X+1）2(X2+X+1）2，所以在選擇B(x)時可以將要求簡化為：保證不含x+l和X2+X+1這兩個因子的多項式，當(dāng)然也可以直接選擇不可約多項式作為B(x)。通過相關(guān)計算可以得出以下滿足條件的部分取值，其中B(x)不是不可約多項式：
從式(2)中，任選其一作為仿射參數(shù)進(jìn)行S盒的構(gòu)造，首先選定既約多項式為X6+X5+1，求得其對應(yīng)的乘法逆元見表1。
根據(jù)表1中的乘法逆元，選取B(x)=x5+x4+x2，C(X）=X4+X2+X+1；結(jié)合仿射公式可以求得6x6的S盒，見表2。
由于在動態(tài)S盒設(shè)計時需要使用4x4的S盒，因此重點(diǎn)對4x4的S盒進(jìn)行了構(gòu)造，并按照S盒的設(shè)計準(zhǔn)則進(jìn)行了性能分析篩選，最終得到了一批符合要求的S盒。例如：選擇既約多項式為X4+X3+X2+X +1，仿射參數(shù)為：A(X)=X4+1，B(x)=x3+x2+x，C(x)=x2+x+1，通過計算可以得到4x4的S盒，見表3。
若選擇既約多項式X4+X 3+1，仿射參數(shù)為：A(X)=4+1，B(X)=X3+X+1，C(X)=X，則經(jīng)計算可以得到4x4的S盒，見表4。
上述計算方法可以完成不同的S盒構(gòu)造，并通過S盒的性能分析進(jìn)行篩選，最終將性能優(yōu)異的S盒運(yùn)用到密碼算法的設(shè)計中。
為了滿足實(shí)際應(yīng)用需要，還可以考慮輸入與輸出位數(shù)不同的S盒。在一些密碼算法的實(shí)際設(shè)計中一般要求S盒的輸入位數(shù)不小于輸出位數(shù)，即n≥m。比如，LOKI算法中使用規(guī)模為12x8的S盒，DES算法中使用的是6x4的S盒，而Rijndael算法和Towfish算法使用了8x8的S盒，Serpent算法中使用了4x4的S盒。在NESSIE標(biāo)準(zhǔn)中，MISYTI算法使用規(guī)模為7x7和9x9的S盒，Camellia算法使用規(guī)模為8x8的S盒。S盒的規(guī)模較大時，非線性特征一般較好，可以有效地抵抗線性分析攻擊。因此一般認(rèn)為m和n的值越大．S盒的密碼強(qiáng)度越高，且當(dāng)m與n的差值很小時，可以有效抵抗差分密碼分析和線性密碼分析等利用統(tǒng)計特征的攻擊。然而m和n值的不斷增大，也會增加算法的設(shè)計難度以及存儲空間和硬件成本。因此，在選擇構(gòu)造S盒的規(guī)模時，往往需要考慮更多的因素。
3.2動態(tài)S盒的設(shè)計
3.2.1 Feistel結(jié)構(gòu)模型和S盒重構(gòu)
Feistel密碼結(jié)構(gòu)作為密碼算法設(shè)計的主流結(jié)構(gòu)之一，首先是在DES的設(shè)計中發(fā)明并應(yīng)用。繼而在GOST、RC5等分組密碼算法中得以推廣使用，F(xiàn)eistel將輸入的明文切分為Lx和Rx兩部分，如圖1所示。
輸入明文首先拆分為兩個等長的部分：Lx和R2，Kx+l是經(jīng)過密鑰擴(kuò)展算法求得的第x+l輪子密鑰，從圖1的運(yùn)算過程可以看出，新的左半部分和右半部分生成方式為：Lx+1=Rx;Rx+l=Lx+F(Rx，Kx+1)，迭代n輪后最終的密文輸出結(jié)果是：C=（Ln，Rn)。對Feistel結(jié)構(gòu)來說，任何函數(shù)F在算法中均可正常工作，并輕松完成解密過程。
在第3.1節(jié)提到，S盒的構(gòu)造規(guī)模越大，密碼強(qiáng)度越高，抵抗差分攻擊和線性攻擊的能力就越好。而m和n值過大會增加算法的設(shè)計難度、存儲空間和硬件消耗，不利于硬件實(shí)現(xiàn)和實(shí)際應(yīng)用。因此，在分組密碼中往往采用小S盒組合拼湊的方法，提出了S盒重構(gòu)的思想，如DES中使用8個6x4的S盒，GOST中使用8個4x4的S盒。通過對S盒進(jìn)行重構(gòu)，用小規(guī)模S盒實(shí)現(xiàn)了大規(guī)模S盒的性能，增加了密碼強(qiáng)度，降低了資源消耗。對分組密碼算法的重構(gòu)模型和重構(gòu)設(shè)計結(jié)構(gòu)做出了一定的分析研究。
3.2.2動態(tài)S盒的概念
從密碼算法研究可知，當(dāng)n值增大到一定程度時，域GFf21上的置換幾乎都是非退化的，如果此時S盒的選取與輸入明文和密鑰相關(guān)，能極大提高其密碼學(xué)特性。有關(guān)研究人員已經(jīng)構(gòu)造了置換和密鑰相關(guān)的動態(tài)S盒。在參考文獻(xiàn)中也引入了利用密鑰進(jìn)行選擇的動態(tài)S盒構(gòu)
造。置換過程中的可選擇機(jī)會越多，動態(tài)S盒的密碼學(xué)性能也就越好。在參考文獻(xiàn)中，對提出的一類動態(tài)S盒構(gòu)造方法進(jìn)行了差分性質(zhì)研究，其分析結(jié)果表示該類動態(tài)S盒變換具有良好的差分特性，動態(tài)S盒的研究改進(jìn)切實(shí)可行。
考慮到Feistel結(jié)構(gòu)的特點(diǎn)，結(jié)合S盒的重構(gòu)思想，提出了動態(tài)S盒的設(shè)計原理：將n位輸入進(jìn)行拆分，一部分作為選取S的依據(jù)，另一部分則作為選定的S盒的輸入，中間還可以進(jìn)行一些簡單的運(yùn)算，兩部分各自輸出的組合作為設(shè)計方案的輸出結(jié)果。
3.2.3動態(tài)S盒的設(shè)計流程
動態(tài)S盒的設(shè)計思想主要來源于S盒的拆分與組合思想和Feistel結(jié)構(gòu)原理，主要步驟如下。
第一步：利用現(xiàn)有的S盒計算方法得到大量S盒，挑選性能優(yōu)異的構(gòu)建S盒容量集。
第二步：從集合中選取參與運(yùn)算的m個S盒，并進(jìn)行編號。
第三步：利用動態(tài)S盒原理，調(diào)用選定的S盒，進(jìn)行后續(xù)運(yùn)算。
在動態(tài)S盒設(shè)計中，首先對S盒的性能嚴(yán)格把關(guān)，選取性能優(yōu)異的S盒作為候選集。保證每個候選S盒的選取概率相等，相互之間獨(dú)立不相關(guān)，每個候選S盒的密碼學(xué)安全強(qiáng)度保持一致或相近。此外，S盒選取的決定因子同時與輸入的明文和密鑰相關(guān)，通過明文密鑰的不可預(yù)知和可隨機(jī)變換的特點(diǎn)，使S盒的隱蔽性更強(qiáng)，增加了S盒的安全，提高了密碼算法的安全強(qiáng)度。
動態(tài)S盒的設(shè)計流程如圖2所示。
從實(shí)現(xiàn)8位主流S盒的設(shè)計角度出發(fā)，參考動態(tài)S盒的設(shè)計原理和拆分組合的設(shè)計思想，以Feistel結(jié)構(gòu)為基礎(chǔ)，考慮將8位的輸入拆分為L4和R4兩部分。如圖2所示，選取4x4 S盒為原型，構(gòu)建動態(tài)S盒。首先將8位輸入明文與密鑰進(jìn)行運(yùn)算，然后將8位的運(yùn)算結(jié)果拆分為左4位和右4位，右4位用于進(jìn)行S盒的選擇，同時與某個變量經(jīng)過異或運(yùn)算后作為一部分的輸出，剩下的左4位輸入4x4 S盒進(jìn)行置換運(yùn)算，這樣實(shí)際上使用一次4x4 S盒完成了8x8規(guī)模的運(yùn)算。具體結(jié)構(gòu)流程如圖3所示。
由Fesitel結(jié)構(gòu)特點(diǎn)可知，有一半的輸入并未進(jìn)行置換運(yùn)算，但通過實(shí)際算法中的多輪迭代可以很好地彌補(bǔ)這一不足，做到全覆蓋置換混淆。
在Feistel結(jié)構(gòu)基礎(chǔ)上進(jìn)行拓展，還可以將8位的輸入拆分為左右位數(shù)不相等的兩部分。比如拆分為2位和6位，2位用來選擇S盒，剩下6位也是輸入6x6的S盒進(jìn)行置換運(yùn)算，得到2+6 S盒。以此類推，還可以構(gòu)建1+7 S盒和3+5 S盒。參照8x8 S盒設(shè)計得到的動態(tài)S盒可以實(shí)現(xiàn)不同的8位輸入使用不同的S盒進(jìn)行置換的目標(biāo)，同時具體使用哪個S盒由輸入明文和密鑰共同決定。
當(dāng)然，動態(tài)S盒的思想也可以運(yùn)用到輸入為16位甚至更大的結(jié)構(gòu)設(shè)計中，那么將會得到更多的組合。這在一定程度上完成了對S盒的隱藏保護(hù)，增加了S層置換的安全強(qiáng)度，提高了加密算法遭到破解的難度。
4性能分析
根據(jù)動態(tài)S盒設(shè)計方案，在性能分析時采用4x4的S盒完成了具體設(shè)計，并做一些仿真分析。首先，通過前面提到的S盒的構(gòu)造方法，構(gòu)造了一批性能優(yōu)異的4x4 S盒，并從中隨機(jī)選取了16個作為候選集。然后對選中的S盒進(jìn)行了隨機(jī)編號0~15，得到參與運(yùn)算的4x4 S盒集：SO，Sl，…，S14，S15。
具體流程如圖4所示，當(dāng)輸入為01100101時，拆分后，右邊4位選擇編號為S5的S盒，并與K進(jìn)行異或運(yùn)算后作為輸出的左4位。然后將剩余4位輸入S盒進(jìn)行置換，最后得到輸出為11010010。
此外，在對選擇位進(jìn)行異或變換時，引入了變量K，而K的取值是可以自行設(shè)定的，這就等于在引入輸入明文和密鑰對S盒選取的控制之外，還引入了一個影響因子，K值的變化也會導(dǎo)致后續(xù)運(yùn)算的差異。受動態(tài)S盒設(shè)計思路的指導(dǎo)，此處的K值也可以作為一個動態(tài)變化的因子，進(jìn)而增加S層的靈活多變性。
(1)非線性度分析
由S盒的構(gòu)造準(zhǔn)則可知，如果S(x)：GF(2n)→GF（2n)，則它的非線性度可以表示為：
度較好。而對動態(tài)S盒而言，由于引入了輸入明文和密鑰控制，使得在S盒的選取上更加隨機(jī)靈活多變，非線性特性更好。
(2)代數(shù)次數(shù)和項數(shù)分布
該4x4 S盒可表示為4個只含“與”和“異或”邏輯符號的布爾方程：該方案具體實(shí)現(xiàn)如圖4所示，代人圖4中選擇的S盒的相關(guān)參數(shù)，可以通過布爾函數(shù)的小項表示法求得4個布爾方程，由4個布爾方程可知：代數(shù)次數(shù)為：D(fi)=3，項數(shù)分別為：12、10、12、10。代數(shù)次數(shù)達(dá)到了最佳(n,-l)，而方程項數(shù)越多，復(fù)雜度就越高。因此該S盒的安全性能得到提高，可以較好地抵抗線性攻擊等。
(3)雪崩效應(yīng)分析
如果改變輸入的1 bit，輸出比特中約有一半發(fā)生改變，則稱S(x)滿足雪崩效應(yīng)。如果改變輸入的1 bit．每個輸出發(fā)生改變的概率均為1/2，則稱S(x)滿足嚴(yán)格雪崩準(zhǔn)則(SAC)。通過對上述S盒進(jìn)行計算得到數(shù)據(jù)見表5，從表5中數(shù)據(jù)來看，選取的4x4 S盒滿足SAC，雪崩效應(yīng)理想，與已有算法相比，性能更好。
(4)差分均勻度分析
差分攻擊是針對分組密碼的有效攻擊手段之一，δ的值越小，抵抗差分攻擊的能力就越強(qiáng)。該S盒的差分分布見表6，其中，X表示輸入的差分值，Y，表示輸出的差分值。當(dāng)X=l，y=E時，8=4，意味著輸入差分為1，輸出差分為E的情況出現(xiàn)了4次。
從表6中數(shù)據(jù)可知，該S盒的差分統(tǒng)計最多次數(shù)為4，符合4差分一致性。此外，表6中每行只有一個差分輸出統(tǒng)計值為4，且數(shù)據(jù)分布相對均勻，可以很好地抗擊差分密碼分析。
5結(jié)束語
在某些加密模式下，加密的過程是高度確定的，這就意味著在密鑰保持不變的情況下，輸入相同的明文分組可以得到相同的密文輸出。這種高度的確定性給數(shù)據(jù)帶來了安全隱患，攻擊者可以通過對輸出數(shù)據(jù)進(jìn)行流量分析，得到某些消息是否多次進(jìn)行傳輸，進(jìn)而可以對某些重復(fù)出現(xiàn)的明文進(jìn)行重新排序，達(dá)到攻擊的目的。
動態(tài)S盒設(shè)計提出的目的就是要打破這種加密過程高度確定的格局，增加明文輸入和密鑰對S盒的影響，改變以往使用固定不變S盒的模式，以S盒動態(tài)可變的特點(diǎn)來增加S層置換的復(fù)雜度，為密碼算法的S層注入隨機(jī)的特性，利用明文輸入和密鑰兩者共同決定S層中對S盒的調(diào)用，并引入控制變量K，充分利用現(xiàn)有資源，完成了對S層的優(yōu)化改進(jìn)目標(biāo)，更好地實(shí)現(xiàn)了S層的非線性混淆的任務(wù)。
通過對其性能進(jìn)行分析對比，該設(shè)計能更好地保護(hù)S盒，提高密碼算法的安全強(qiáng)度，增加算法的靈活性，進(jìn)而對密碼算法的差分分布和線性分布產(chǎn)生影響，從而顯著提高整個算法的安全強(qiáng)度，更好地抵御更多的攻擊。
6摘 要：
分組密碼作為信息安全應(yīng)用的主流加密方法，在無線傳感器網(wǎng)絡(luò)中也得到了廣泛應(yīng)用。而S盒作為分組密碼算法的核心模塊之一，其設(shè)計好壞直接影響著整個密碼算法。為了在有限的資源下，提高分組密碼算法的安全強(qiáng)度，對分組密碼算法以及S盒構(gòu)造設(shè)計進(jìn)行了深入的分析研究，結(jié)合Feistel架構(gòu)和S盒重構(gòu)的思想，提出了動態(tài)S盒的設(shè)計方案，并對其進(jìn)行了相關(guān)分析驗證。結(jié)果表明，經(jīng)過該設(shè)計，安全性能確實(shí)有所提高。
