一類新的基于元胞自動機的S 盒的線性性質研究*

關 杰, 盧健偉, 劉 帥

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

1 引言

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

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

2 基本概念

3 的線性性質分析

那么ρf(0)=0.

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

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

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

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

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

3.1 關于Fnnew 譜值取值范圍的猜想證明

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

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

當n為偶數(shù)時:

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

3.2 Fnnew 的掩碼結構和計數(shù)

下面考慮掩碼對計數(shù)問題, 由上述證明過程可知, 一個輸出掩碼μ對應四個輸入掩碼η, 故當n ≥5且w(μ)=1 時掩碼對數(shù)為4n,而當n=6 時還存在w(μ)=6 的情況,對應的掩碼對數(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ù);

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

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

4 結束語

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

附錄

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