一類新的基于元胞自動(dòng)機(jī)的S盒的密碼學(xué)性質(zhì)研究

關(guān)杰，黃俊君

（解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué)密碼工程學(xué)院，河南 鄭州 450001）

1 引言

基于元胞自動(dòng)機(jī)（CA, cellular automaton）的S盒[1]因其良好的密碼學(xué)性質(zhì)及較低的實(shí)現(xiàn)成本被廣泛應(yīng)用到許多密碼算法中，其中最典型的是已經(jīng)作為SHA-3標(biāo)準(zhǔn)[2]之一的Keccak雜湊函數(shù)[3]。本文選用了一個(gè)作用域范圍僅為3個(gè)元胞的局部規(guī)則，從而使該算法的S盒有著極小的軟件實(shí)現(xiàn)成本及硬件實(shí)現(xiàn)消耗。目前，接觸到的其他利用元胞自動(dòng)機(jī)的局部規(guī)則定義S盒的密碼都使用了與Keccak雜湊函數(shù)的 S盒相同的局部規(guī)則，如 Panama[4]、Subterranean[5]和 3Way[6]。除了這些 S盒外，還有一些密碼算法使用的S盒是Keccak雜湊算法的S盒的仿射變換，如Ascon[7]。

本文通過實(shí)驗(yàn)找到了一類新的基于元胞自動(dòng)機(jī)的S盒，并對(duì)這一類S盒的密碼學(xué)性質(zhì)進(jìn)行研究，該類S盒相比Keccak雜湊函數(shù)的S盒差分性質(zhì)更好，并且在輸入輸出規(guī)模為5時(shí)也是一個(gè)置換，因此這一類新的S盒有潛力代替Keccak雜湊函數(shù)的S盒，為密碼設(shè)計(jì)者提供設(shè)計(jì)參考。

2 基本概念

2.1 S盒的密碼學(xué)性質(zhì)

在分組密碼的設(shè)計(jì)中，最通用的設(shè)計(jì)準(zhǔn)則就是香農(nóng)提出的混亂和擴(kuò)散原則[8]。在實(shí)際的設(shè)計(jì)過程中通常使用S盒來提供混亂效果，在很多密碼中S盒都是唯一的非線性環(huán)節(jié)。一個(gè)m進(jìn)n出的S盒可以用映射表示，其中，m、n都是正整數(shù)。

置換性質(zhì)[9]和差分性質(zhì)是S盒重要的密碼學(xué)性質(zhì)，具有良好差分性質(zhì)及滿足置換條件的S盒將有更廣泛的應(yīng)用場(chǎng)景。下面給出置換和差分的定義。

定義1[10]設(shè)，若對(duì)任意且，有，稱F是一個(gè)置換。

定義2[11]設(shè)，那么稱為F在輸入差分為α，輸出差分為β下的差分轉(zhuǎn)移概率，其中，#{?}代表集合中元素的個(gè)數(shù)。

2.2 元胞自動(dòng)機(jī)

元胞自動(dòng)機(jī)是一種廣泛應(yīng)用在不同領(lǐng)域，用來模擬和分析復(fù)雜離散問題的并行運(yùn)算模型。一個(gè)CA可以表示為一個(gè)由元胞（cell）組成的元胞空間（lattice）。在每一步狀態(tài)更新中，元胞空間中的每一個(gè)元胞根據(jù)局部規(guī)則（local rule）同步更新狀態(tài)。CA中所有元胞的狀態(tài)從原有狀態(tài)到一步更新后的狀態(tài)之間的映射可以用全局規(guī)則（global rule）來表示。事實(shí)上，如果經(jīng)過合理的設(shè)計(jì)及選取，全局規(guī)則可以是一個(gè)具有良好密碼學(xué)性質(zhì)的非線性映射，即本文要研究的基于CA的S盒。根據(jù)劃分的不同，CA有很多分類，本文僅考慮一種可以用作S盒的一維布爾型循環(huán)邊界CA，這種CA的定義如下。

可以把元胞空間看作是等間隔排列在直線上的一系列完全相同的元胞，且每個(gè)元胞的狀態(tài)均取自集合Z2={0,1}。

設(shè)Z*為整數(shù)集合，假設(shè)元胞空間的規(guī)模為n且n∈Z*，即該CA由n個(gè)元胞組成，那么所有元胞的狀態(tài)可以用一行有限的符號(hào)序列來表示，當(dāng)其中每一個(gè)符號(hào)取特定狀態(tài)就可以構(gòu)成一個(gè)狀態(tài)序列，稱每個(gè)這樣的狀態(tài)序列為CA的一個(gè)構(gòu)型。構(gòu)型中的每一個(gè)元胞是用取自Z2的狀態(tài)來表示的，例如構(gòu)型X可以表示為，其中，

在一次狀態(tài)更新中，設(shè)更新前的構(gòu)型為X，那么更新后的構(gòu)型完全由X決定，記為X′。其中，X′中第i個(gè)元胞x′i的狀態(tài)由X的xi及其右邊不超過r(r≤n-1)個(gè)元胞的狀態(tài)決定，即

下面，給出一維布爾型循環(huán)邊界CA的定義，如定義3所示。

定義 3[12]映射為一維布爾型循環(huán)邊界 CA，其中，*n∈Z為元胞空間的規(guī)模，存在r＞0及，對(duì) CA的任意構(gòu)型，有

其中，r為CA的鄰域半徑，f為CA的局部規(guī)則，F(xiàn)n為CA的全局規(guī)則。

圖1是一維布爾型循環(huán)邊界CA的示例，其元胞空間的規(guī)模n=5，局部規(guī)則可表示為，且其鄰域半徑r=2?？梢钥吹剑谶@種循環(huán)邊界的CA中，其元胞空間可以看作一個(gè)首尾相接的環(huán)，最開始的元胞接在最后一個(gè)元胞后，因此在更新最后r個(gè)元胞的狀態(tài)時(shí)，會(huì)從最開始的r個(gè)元胞中選取部分作為其右鄰域的一部分。在圖1中，CA向量的最右側(cè)用最開始的r=2個(gè)元胞接上，在最后2個(gè)元胞更新時(shí)可以作為其右鄰域。

圖1 一維布爾型循環(huán)邊界CA示例

圖1中的CA的局部規(guī)則就是用于Keccak的非線性變換χ，本文將該CA的局部規(guī)則記為fK，全局規(guī)則記為。

接下來，本文將給出CA的一個(gè)重要性質(zhì)。本文所有運(yùn)算都是在模n上進(jìn)行的。

定理1CA的平移不變性。設(shè)為一個(gè) CA，其局部規(guī)則為，其中n∈Z*,r＞0且n＞r，設(shè)為該CA的構(gòu)型，令σk(X)為對(duì)X循環(huán)左移k位，那么?X、?k∈Zn均有

證明令，那么，所以有

故結(jié)論成立，證畢。

在一般的CA中，局部規(guī)則對(duì)第i個(gè)元胞xi的作用域?yàn)?，不僅跟右鄰域相關(guān)，還與左鄰域相關(guān)。但是根據(jù)定理1可知，把CA的構(gòu)型經(jīng)過平移后可以與上文介紹的CA的局部規(guī)則一樣，僅與右鄰域相關(guān)而不改變其置換性質(zhì)和差分性質(zhì)。

2.3 一類新的基于CA的S盒

由于用全局規(guī)則就可以唯一地表示一個(gè) CA，而一個(gè)CA經(jīng)過合理地設(shè)計(jì)后，可以使全局規(guī)則成為一個(gè)密碼學(xué)性質(zhì)良好的非線性變換，從而可以用作密碼環(huán)節(jié)中的S盒。為了找到密碼學(xué)性質(zhì)良好的基于CA的S盒，本文通過實(shí)驗(yàn)窮舉了規(guī)模為5的所有CA并從中篩選出一個(gè)CA。該CA具有良好的差分性質(zhì)且滿足置換條件，然后本文將其在不同的規(guī)模下的情況抽象成一類CA。

下面，給出本文要研究的這一類新的基于 CA的S盒的定義。

定義 4設(shè)n≥5，映射為一類CA，其局部規(guī)則為且滿足

3 的置換性質(zhì)分析

置換性質(zhì)是S盒一個(gè)重要的密碼學(xué)性質(zhì)，滿足置換性質(zhì)的S盒在很多密碼體制中實(shí)現(xiàn)數(shù)據(jù)變換，具有廣泛的應(yīng)用場(chǎng)景。

引理1對(duì)于元胞空間規(guī)模n為偶數(shù)的CA，設(shè)局部規(guī)則為f(x0,x1,…,xr)且r＜n，若r為奇數(shù)，有若r為偶數(shù)，有那么該 CA的全局規(guī)則n

F必然不是一個(gè)置換。

證明設(shè)X、X*∈Z2n，如果能夠找到X≠X*，使得F(X)=F(X*)，那么F不是一個(gè)置換。由于n為偶數(shù)，本文令令X*=若r為奇數(shù)，有

若r為偶數(shù)，有

顯然，此處X≠X*，但有所以此時(shí)全局規(guī)則nF不是一個(gè)置換，證畢。事實(shí)上，Keccak中的非線性映射的全局規(guī)則在n為偶數(shù)時(shí)不是一個(gè)置換，因?yàn)閷?duì)應(yīng)的局部規(guī)則fK有，根據(jù)引理1即得。

引理 2設(shè)n≥6且n為奇數(shù)，對(duì)于，有對(duì)于

證明首先，令，令X′=那么有

當(dāng)n=7時(shí)，令X=(1,1,1,1,0,0,1)，容易驗(yàn)證成立；當(dāng)n=9時(shí)，令X=(1,1,1,1,0,0,1,0,0)，同樣有0,1,1,1,1)成立；當(dāng)n≥11時(shí)，令X=(1,1,1,1,0,0,1,，驗(yàn)證有。又因?yàn)?/p>

綜上所述，結(jié)論成立，證畢。

定理2 設(shè)，當(dāng)n=5時(shí)，是置換；當(dāng)n≥6時(shí)，不是置換。

證明對(duì)于，容易驗(yàn)證遍歷 32個(gè)輸入X會(huì)有對(duì)應(yīng) 32個(gè)不同的輸出Y，即對(duì)于任意的，必然有Y≠Y*，所以是置換。

下面，分2種情況討論n≥6時(shí)不是一個(gè)置換。

情況1n≥6且n為偶數(shù)，此時(shí)由得

所以根據(jù)引理1可知，當(dāng)n為偶數(shù)時(shí)不是一個(gè)置換。

情況2n≥6且n為奇數(shù)，由引理2可以構(gòu)造同時(shí)可以構(gòu)造，也有但是，所以此時(shí)也不是一個(gè)置換。

綜上所述可知，當(dāng)n≥6時(shí)，均不是一個(gè)置換，證畢。

4 的差分性質(zhì)分析

令n∈Z*，設(shè)，記的輸入差分為，輸出差分為，由于，那么輸入差分和輸出差分之間滿足如式(1)所示的等式。

本文把n位輸入差分和輸出差分的關(guān)系用n個(gè)式子組成的方程組來表示，如式(2)所示。

該差分方程組對(duì)應(yīng)的n維系數(shù)矩陣就是的差分矩陣，記為A，如式(3)所示。

其中，Ai(i∈{0,1,2,…,n-1})表示A的第i行。另外，A僅與的輸入差分相關(guān)。

定理 3設(shè)n≥5，對(duì)于，任意輸入差分及輸出差分β，若差分轉(zhuǎn)移概率，那么一定有其中表示A的秩。

證明設(shè)的輸入，輸入差分及輸出差分分別為和。其中，。由式(1)可得

對(duì)于確定的iα及iβ，本文可以得到方程組系數(shù)的值及yi的值，所以該方程組就是Z2上的非齊次線性方程組，并且其系數(shù)矩陣即為的差分轉(zhuǎn)移矩陣A。將該非齊次線性方程組用矩陣形式表示，如式(4)所示。

其中，ki∈{0,1}，ηi是方程組線性無關(guān)的基礎(chǔ)解系，。遍歷所有的ki可以得到所有方程組的解，所以解的個(gè)數(shù)為2n-r個(gè)，也就是說所以有

證畢。

定理4設(shè)n≥5，對(duì)于，任意輸入差分α及輸出差分β，若差分轉(zhuǎn)移概率不為0和1，那么

證明設(shè)的輸入輸入 差分，輸出差分β=

首先，對(duì)任意選定的α≠0及輸出差分β，若存在X滿足，則顯然X⊕α滿足此式，所以非零時(shí)必為偶數(shù)。故當(dāng)差分轉(zhuǎn)移概率非零時(shí)，其最小值為，所以顯然成立。

由k2αi=0可知k2=0。下面分別討論αi-1取值為0和1這2種情況。

情形 1若αi-1=0，由得k0=0。因?yàn)閗0、k1、k2不全為0，所以必有k1=1。那么由得αi+1=αi= 1，最后根據(jù)有αi-1=0?？紤]，經(jīng)初等變換后有

情形2若αi-1=1，由知。因?yàn)椴蝗珵?，所以必有k0=1。

經(jīng)過上面討論可知，對(duì)任意輸入差分α≠0，A的秩r≥3。根據(jù)定理3，任取輸出差分β，若β)≠0，則必有證畢。

5 的差分分布

定理 5設(shè)n≥5，對(duì)于，任意輸入差分及輸出差分，設(shè)σk(α)為對(duì)α循環(huán)左移k位，那么令若且，則

證明不妨先設(shè)k=1，對(duì)有。記在輸入差分為α與α′時(shí)的差分轉(zhuǎn)移矩陣分別為和那么有

在Z2上對(duì)其進(jìn)行初等變換可以轉(zhuǎn)化為

另外只需將上面的α替換成σ1(α)，α′替換成σ2(α)，就有k=2時(shí)成立。同樣地，k為其他值時(shí)定理均成立，證畢。

定理 6設(shè)n≥5，對(duì)于，給定輸入差分設(shè)α的漢明重量為w(α)，對(duì)于任意輸出差分β，若，那么當(dāng)或

證明當(dāng)w(α)=1時(shí)，考慮α′=(0,0,…,0,1)時(shí)的情況，即而其余位置均為 0。此時(shí)將在Z2上進(jìn)行初等變換，可以得到有3行非零的階梯型矩陣所以此時(shí)A的秩r=3，由定理3可知，對(duì)于任意輸出差分β，若。又由定理5，若w(α)=1，必然存在使得，所以時(shí)就有

當(dāng)w(α)=n-1時(shí)，同樣地，考慮時(shí)的情況，即α0′=0而其余位置均為1。此時(shí)，在2

Z上進(jìn)行初等變換，可以得到有n-1行非零的階梯型矩陣所以A的秩r=n-1。由定理3可知，存在2n-1個(gè)不同的β使。又由定理5，若必然存在使所以時(shí)就有

根據(jù)定理5可知，循環(huán)移位等價(jià)的2個(gè)輸入差分對(duì)應(yīng)的非平凡差分轉(zhuǎn)移概率是相等的。從而本文可以根據(jù)循環(huán)移位等價(jià)將w(α)=2和w(α)=3時(shí)的α進(jìn)行分類。

的輸入差分α在w(α)=2時(shí)根據(jù)循環(huán)移位等價(jià)可以分為{σk(5)|k∈Z}={5,9,10,18,20}和2類。在w(α)=3時(shí)也可以分為和兩類。由定理5可知，同一類中的輸入差分對(duì)應(yīng)相同的非平凡差分轉(zhuǎn)移概率。經(jīng)驗(yàn)證可知，{σk(5)|k∈Z}和{σk(11)|k∈Z}對(duì)應(yīng)的非平凡差分轉(zhuǎn)移概率記這2個(gè)集合的并集為；而{σk(3)|k∈Z}和{σk(7)|k∈Z}對(duì)應(yīng)的非平凡差分轉(zhuǎn)移概率，記這2個(gè)集合的并集為至此本文已經(jīng)得到的輸入差分α在w(α)=2和w(α)=3時(shí)對(duì)應(yīng)的非平凡差分轉(zhuǎn)移概率情況。

定理 7設(shè)的輸入差分為α，其漢明重量為w(α)，對(duì)任意β∈Z5，如果當(dāng)且僅當(dāng)時(shí)，；當(dāng)且僅當(dāng)時(shí)

證明由于w(α)∈{0,1,2,3,4,5}。當(dāng)w(α)=0時(shí)，或1；由定理6，當(dāng)w(α)=4或w(α)=5時(shí)，若，則有，則有又根據(jù)上面的討論，當(dāng)w(α)=2或w(α)=3時(shí)，若α∈Ω1，，而當(dāng)w(α)=1時(shí)，若則其對(duì)應(yīng)的非平凡差分轉(zhuǎn)移概率，而若α∈Ω，則其對(duì)應(yīng)的非平2凡差分轉(zhuǎn)移概率

表1 和的差分轉(zhuǎn)移概率計(jì)數(shù)

表1 和的差分轉(zhuǎn)移概率計(jì)數(shù)

差分轉(zhuǎn)移概率 5 F 5 n e w F K 1 1 1 1 4 0 2 0 1 8 1 2 0 1 2 0 1 6 2 5 6 1 7 6 0 6 4 7 7 0 7 1

6 結(jié)束語

雖然目前有許多密碼已經(jīng)使用了基于元胞自動(dòng)機(jī)的S盒，但都使用了Keccak的局部規(guī)則或者仿射變換。本文通過實(shí)驗(yàn)找到了一類新的基于元胞自動(dòng)機(jī)的S盒并研究了其置換性質(zhì)和差分性質(zhì)，證明了該類S盒在規(guī)模為5時(shí)是一個(gè)置換，并且其非平凡差分轉(zhuǎn)移概率的取值范圍為而Keccack的S盒的非平凡差分轉(zhuǎn)移概率的取值范圍則為另外，本文進(jìn)一步研究了該類S盒在規(guī)模為5時(shí)的差分分布情況，給出了該類S盒在取到最大和最小非平凡差分轉(zhuǎn)移概率時(shí)的充要條件。最后通過比較和的差分轉(zhuǎn)移概率的計(jì)數(shù)情況可以發(fā)現(xiàn)，相比差分分布更加均勻。所以該類S盒有著比Keccak類S盒更好的差分性質(zhì)。接下來的工作重點(diǎn)是從理論上研究這類 S盒抵抗線性分析以及立方攻擊[14]等各類攻擊方法的效果。