一類新的基于元胞自動(dòng)機(jī)的S 盒的線性性質(zhì)研究*

關(guān) 杰, 盧健偉, 劉 帥

戰(zhàn)略支援部隊(duì)信息工程大學(xué), 鄭州450001

1 引言

元胞自動(dòng)機(jī)[1]是一種用來(lái)模擬和分析復(fù)雜離散問(wèn)題的并行計(jì)算模型, 能夠由一些簡(jiǎn)單的局部規(guī)則產(chǎn)生較為復(fù)雜的變換, 組合后可以實(shí)現(xiàn)混淆和擴(kuò)散[2], 也可以用于偽隨機(jī)數(shù)生成器的構(gòu)造[3], 因此在密碼學(xué)中有許多的應(yīng)用. 我們可以將元胞自動(dòng)機(jī)的變換過(guò)程定義為S 盒變換, 稱其為基于元胞自動(dòng)機(jī)的S 盒[4].這類S 盒一般實(shí)現(xiàn)代價(jià)較低, 并且有良好的安全性能, 最經(jīng)典的是作為SHA-3[5]標(biāo)準(zhǔn)之一的Keccak 雜湊函數(shù)[6]的S 盒. 另外, Panama[7]、RadioGatún[8]、Subterranean[9]和3Way[10]所使用的S 盒也與Keccak 的S 盒有相同的局部規(guī)則.

文獻(xiàn)[11] 中提出了一類新的基于元胞自動(dòng)機(jī)的S 盒Fnnew, 它的局部規(guī)則的作用域范圍為5 個(gè)元胞,具有較小的軟件與硬件成本. 該類S 盒的具體描述如下:

2 基本概念

3 的線性性質(zhì)分析

那么ρf(0)=0.

引理2[14]若布爾函數(shù)f(x) 和g(x) 是互為仿射等價(jià)的, 則ρf(0)=ρg(0).

該引理揭示了對(duì)于一個(gè)布爾函數(shù)的輸入變量進(jìn)行可逆線性變換后, 在0 點(diǎn)的Walsh 譜不變. 史丹萍等人給出了一個(gè)不相交化算法(算法1[14], 具體見(jiàn)附錄), 可以有效地將任意給定的二次布爾函數(shù)轉(zhuǎn)換為不相交二次型.

引理3[14]對(duì)于不相交二次型f=xi1xi2+···+xi2k?1xi2k+xj1+···+xjs,f在0 點(diǎn)的Walsh譜值計(jì)算方法如下:

這里coef(xu) 表示xu在f中的系數(shù).

引理3 提供了計(jì)算不相交二次型在0 點(diǎn)的Walsh 譜值的一種方法, 其中k表示f中不同二次項(xiàng)的個(gè)數(shù), 根據(jù)算法1 和引理3 我們可以有效地計(jì)算出任意二次布爾函數(shù)在0 點(diǎn)的Walsh 譜值.

3.1 關(guān)于Fnnew 譜值取值范圍的猜想證明

文獻(xiàn)[12] 給出了針對(duì)Keccak 算法S 盒的相關(guān)結(jié)論的證明, 然而Keccak 算法S 盒的局部規(guī)則只有一個(gè)二次項(xiàng), 因此從Walsh 譜的定義入手, 分析η·X ⊕μ·Y的結(jié)構(gòu)即可證明. 然而Fnnew的局部規(guī)則中有兩個(gè)二次項(xiàng), 且二次項(xiàng)之間有一個(gè)公共變量, 所以從Walsh 譜的定義入手直接證明猜想1 是十分困難的.

本文從f?η,μ的結(jié)構(gòu)入手, 首先將f?η,μ經(jīng)過(guò)算法1 后化成的不相交二次型記為?f, 由于f?η,μ與?f是互為仿射等價(jià)的, 由引理2 可知兩者在0 點(diǎn)的Walsh 譜值相等, 再由引理3, 分析猜想1 中k的取值等價(jià)于分析?f中不相交二次項(xiàng)的個(gè)數(shù). 下面給出定理1 及其具體證明.

當(dāng)n為偶數(shù)時(shí):

(2) 假設(shè)n=t ≥6 且t為偶數(shù)時(shí), 結(jié)論成立, 下證n=t+2 時(shí), 結(jié)論也成立.

3.2 Fnnew 的掩碼結(jié)構(gòu)和計(jì)數(shù)

下面考慮掩碼對(duì)計(jì)數(shù)問(wèn)題, 由上述證明過(guò)程可知, 一個(gè)輸出掩碼μ對(duì)應(yīng)四個(gè)輸入掩碼η, 故當(dāng)n ≥5且w(μ)=1 時(shí)掩碼對(duì)數(shù)為4n,而當(dāng)n=6 時(shí)還存在w(μ)=6 的情況,對(duì)應(yīng)的掩碼對(duì)數(shù)再加4,得證.

(1)w(μ)=2,μi0=μi0+1=1,ηi0+4=1;

(2)w(μ)=2,μi0=μi0+2=1,ηi0+3⊕ηi0+4=1;

(3)w(μ)=3,μi0=μi0+1=μi0+2=1,ηi0⊕ηi0+3=1;

(4)w(μ)=3,μi0=μi0+1=μi0+3=1,ηi0⊕ηi0+1⊕ηi0+2=1;

(5)w(μ)=4,μi0=μi0+1=μi0+2=μi0+3=1,ηi0+2⊕ηi0+3⊕ηi0+4=1;

(6)w(μ)=5,w(η) 為奇數(shù);

且此時(shí)滿足|ρFn(η →μ)|=1/4 的掩碼對(duì)數(shù)為416.

證明: 由引理2 和引理3 可知, 非平凡相關(guān)優(yōu)勢(shì)取到最小值1/4 當(dāng)且僅當(dāng)f?η,μ經(jīng)過(guò)算法1 后得到的式子?f中有兩個(gè)不相交的二次項(xiàng), 即不存在獨(dú)立的單次項(xiàng), 由算法1 可知當(dāng)w(μ)=1 時(shí)顯然?f中只有一個(gè)二次項(xiàng), 此時(shí)相關(guān)優(yōu)勢(shì)不可能取到1/4. 下面討論w(μ)?=1:

4 結(jié)束語(yǔ)

基于元胞自動(dòng)機(jī)的S 盒已經(jīng)被應(yīng)用于許多密碼算法中, 但結(jié)構(gòu)上都與Keccak 類S 盒類似. 文獻(xiàn)[11]中提出了一類新的基于元胞自動(dòng)機(jī)的S 盒, 并分析了其置換與差分性質(zhì), 指出該類S 盒有著比Keccak 類S 盒更好的差分性質(zhì). 本文進(jìn)一步研究了其線性性質(zhì), 將相關(guān)優(yōu)勢(shì)取值問(wèn)題轉(zhuǎn)化為不相交二次型中二次項(xiàng)的個(gè)數(shù)問(wèn)題, 有效地解決了這類S 盒的Walsh 譜分布規(guī)律問(wèn)題. 研究表明, 這類S 盒的線性性質(zhì)也優(yōu)于Keccak 類S 盒. 接下來(lái)的工作是分析這類S 盒的其它密碼學(xué)性質(zhì), 為評(píng)估其替代Keccak 類S 盒后算法的安全性提供技術(shù)支持.

附錄

表1 相關(guān)優(yōu)勢(shì)計(jì)數(shù)表[11]Table 1 Count of related advantages table [11]