淺析Xiao-Massey定理的意義和作用

馮登國(guó)

(中國(guó)科學(xué)院 軟件研究所，北京 100190)

相關(guān)攻擊從對(duì)基于線性反饋移位寄存器(Linear Feedback Shift Register，LFSR)的序列密碼的分析起步，最早是由BLASER等人[1]提出的。真正有價(jià)值的工作是由SIEGENTHALER[2]提出的非線性組合生成器的分別征服相關(guān)攻擊，其基本思想是利用組合函數(shù)的輸出與輸入分量或者某些輸入分量子集之和的相關(guān)性，窮搜索某個(gè)特定LFSR的初始狀態(tài)或者某幾個(gè)LFSR 的初始狀態(tài)，而各個(gè)LFSR 的初始狀態(tài)就是非線性組合生成器的子密鑰，這就是最早的相關(guān)攻擊?！胺謩e征服(divide-and-conquer)”起名于一種圖論算法，體現(xiàn)了“分而治之”的思想，意為將一個(gè)待求解的問題分成許多子問題，然后對(duì)每個(gè)子問題求解，最后再綜合求解。為了對(duì)抗這種相關(guān)攻擊方法，SIEGENTHALER提出了布爾函數(shù)的相關(guān)免疫的概念[3]，用于度量和刻畫非線性組合序列密碼抵抗分別征服相關(guān)攻擊的能力。相關(guān)免疫布爾函數(shù)是一類重要的密碼函數(shù)，其頻譜特征刻畫是構(gòu)造和分析這類函數(shù)的理論基礎(chǔ)。肖國(guó)鎮(zhèn)(G.Z.Xiao)教授和梅西(J.L.Massey)教授于1988年給出了相關(guān)免疫布爾函數(shù)的沃爾什(Walsh)頻譜特征刻畫[4]，這一工作被國(guó)內(nèi)外學(xué)者稱之為Xiao-Massey定理。關(guān)于相關(guān)免疫函數(shù)更多的進(jìn)展可參閱文獻(xiàn)[5-6]及其參考文獻(xiàn)。

首先回顧了Xiao-Massey定理，其次簡(jiǎn)述了Xiao-Massey定理的意義，然后闡釋了Xiao-Massey定理的作用，最后總結(jié)了全文。

1 Xiao-Massey定理

(1)

式(1)的逆變換(又稱反演公式)為

(2)

上面各式中的求和是指實(shí)數(shù)求和，式(2)可由式(1)推導(dǎo)出。

計(jì)算沃爾什變換有快速算法[5]，稱之為快速沃爾什變換，其時(shí)間和存儲(chǔ)復(fù)雜度分別為O(n2n)和O(2n)。

(3)

則稱f與變?cè)獂i1，xi2，…，xim統(tǒng)計(jì)無關(guān)(也稱統(tǒng)計(jì)獨(dú)立)。如果f與x1，x2，…，xn中的任意m個(gè)變?cè)冀y(tǒng)計(jì)無關(guān)，則稱f是m階相關(guān)免疫的。特別地，如果f既是平衡的，又是m階相關(guān)免疫的，則也稱f是m階彈性的。

Xiao和Massey[4]用沃爾什譜刻畫了相關(guān)免疫函數(shù)的特征，并給出了一個(gè)非常重要的引理，國(guó)際上稱之為Xiao-Massey引理。

由Xiao-Massey引理可推出以下結(jié)論。

下面的引理2給出了f與變?cè)獂i1，xi2，…，xim統(tǒng)計(jì)無關(guān)的重量特征。

引理2設(shè)f(x)如定義2中所述，f(x)與變?cè)獂i1，xi2，…，xim統(tǒng)計(jì)無關(guān)，則WH(f)=2mk0，k0為非負(fù)整數(shù)。

證明：因?yàn)閒(x)與變?cè)獂i1，xi2，…，xim統(tǒng)計(jì)無關(guān)，因此，

P(f=1|xi1，xi2，…，xim)=P(f=1) 。

由

且

得

即

WH(f)=2mWH(f′) 。

其中，f′表示給定xi1=ci1，xi2=ci2，…，xim=cim的條件下，f關(guān)于n-m個(gè)變?cè)獅x1，x2，…，xn}{xi1，xi2，…，xim}的函數(shù)。

下面給出Xiao-Massey定理。

可由定理2直接推出f(x)與變?cè)獂i1，xi2，…，xim統(tǒng)計(jì)無關(guān)的譜特征。

2 Xiao-Massey定理的意義

Xiao-Massey定理具有以下重要意義：

(1) 該定理為頻譜技術(shù)在密碼學(xué)中的應(yīng)用開辟了一條廣闊的道路。自從Xiao-Massey定理提出以來，人們高度重視頻譜技術(shù)在密碼設(shè)計(jì)和分析中的應(yīng)用。一方面積極發(fā)展和完善頻譜理論與方法；另一方面深度挖掘頻譜技術(shù)在密碼學(xué)中的應(yīng)用與作用。主要包括以下研究?jī)?nèi)容：

① 適用于研究高階逼近的頻譜理論與方法，如二階沃爾什譜、m階沃爾什譜等；

② 適用于研究域、環(huán)等代數(shù)結(jié)構(gòu)上的密碼函數(shù)的頻譜理論與方法；

③ 適用于研究多輸出函數(shù)的頻譜理論與方法；

④ 密碼函數(shù)的各種性質(zhì)的頻譜特征刻畫；

⑤ 頻譜技術(shù)在密碼分析中的應(yīng)用，如最佳仿射逼近分析[7]、最大相關(guān)攻擊[5]等；

⑥ 探索其他頻譜技術(shù)在密碼學(xué)中的應(yīng)用。

(2) 該定理為研究相關(guān)免疫函數(shù)找到了一個(gè)新的研究工具，創(chuàng)新性地刻畫了相關(guān)免疫布爾函數(shù)的頻譜特征。起初人們對(duì)相關(guān)免疫函數(shù)的認(rèn)識(shí)非常有限，Xiao-Massey定理的提出，打開了人們認(rèn)識(shí)相關(guān)免疫函數(shù)的視野，給出了若干刻畫相關(guān)免疫函數(shù)特征的方法，并進(jìn)一步刻畫了相關(guān)免疫階與其他非線性準(zhǔn)則之間的關(guān)系。主要包括以下研究?jī)?nèi)容：

① 相關(guān)免疫函數(shù)的特征刻畫，如特征矩陣的各種刻畫以及與組合設(shè)計(jì)和糾錯(cuò)編碼中對(duì)偶距離之間的關(guān)系等；

② 相關(guān)免疫階與其他非線性準(zhǔn)則之間的關(guān)系，如非線性次數(shù)、非線性度、線性結(jié)構(gòu)、擴(kuò)散準(zhǔn)則等；

③ 高度非線性相關(guān)免疫函數(shù)的構(gòu)造與計(jì)數(shù)；

④ 滿足各種密碼學(xué)性質(zhì)的密碼函數(shù)的構(gòu)造與計(jì)數(shù)；

⑤ 探索新的非線性度量準(zhǔn)則。

(3) 該定理將概率統(tǒng)計(jì)問題轉(zhuǎn)化為代數(shù)問題。相關(guān)免疫函數(shù)的判定本是一個(gè)計(jì)算概率統(tǒng)計(jì)的問題，但通過Xiao-Massey定理將其轉(zhuǎn)化為計(jì)算某些特定點(diǎn)的譜值是否為零的代數(shù)問題。由于計(jì)算沃爾什譜有快速算法，因此，這樣做不僅可行，而且具有重要的實(shí)際意義。這就迫使人們不得不重視以下研究問題：

① 各種頻譜技術(shù)的快速計(jì)算方法；

② 概率統(tǒng)計(jì)問題與代數(shù)問題的相互轉(zhuǎn)化方法。

(4) 該定理將時(shí)域處理問題轉(zhuǎn)化為頻域處理問題。直接處理相關(guān)免疫布爾函數(shù)涉及的運(yùn)算是邏輯運(yùn)算，需要在時(shí)域上處理問題，有時(shí)不是很方便，但通過Xiao-Massey定理將其轉(zhuǎn)換為頻域上的運(yùn)算，也就是實(shí)數(shù)域上的算術(shù)運(yùn)算，這樣處理起來更加方便和簡(jiǎn)單。這種思想在科學(xué)研究中非常重要，它將A中的問題Q通過變換T轉(zhuǎn)化為B中的問題T(Q)，而在B中T(Q)的研究比較簡(jiǎn)單并可通過T(Q)的研究獲得Q的特征，即使不能求出T-1，這也是十分有價(jià)值的。

3 Xiao-Massey定理的作用

Xiao-Massey定理本質(zhì)上給出了相關(guān)免疫函數(shù)的另一個(gè)等價(jià)定義，在一些場(chǎng)景中使用起來十分方便。Xiao-Massey定理在相關(guān)免疫函數(shù)的判定、相關(guān)免疫函數(shù)的構(gòu)造與計(jì)數(shù)、相關(guān)免疫階與其他非線性準(zhǔn)則(如非線性次數(shù)、非線性度等)之間的關(guān)系刻畫、序列密碼分析等方面具有重要的作用和價(jià)值。本節(jié)僅給出Xiao-Massey定理在3個(gè)方面的作用。

3.1 相關(guān)免疫函數(shù)的判定

由Xiao-Massey定理可推出以下結(jié)論。

注意到

(-1)f(x)=1-2f(x) ，

且

因此，Sf(w)=0，當(dāng)且僅當(dāng)f(x)+w·x是平衡的。從而，推論3得證。

由推論3易推出以下結(jié)論。

下面的算法1給出了構(gòu)造相關(guān)免疫函數(shù)的一個(gè)遞歸方法[3]。

算法1設(shè)f1和f2分別是n個(gè)變?cè)膍階相關(guān)免疫函數(shù)，令

則f是n+1個(gè)變?cè)膍階相關(guān)免疫函數(shù)。次數(shù)?0f=max{?0f1，?0f2}+1。

可直接利用Xiao-Massey定理判定算法1構(gòu)造出的f是n+1個(gè)變?cè)膍階相關(guān)免疫函數(shù)。

3.2 相關(guān)免疫階與非線性次數(shù)之間的關(guān)系

(4)

其中，a0，ai1，i2，…，ir∈F2，求和符號(hào)“∑”是指在F2上的求和。式(4)稱為f(x)的多項(xiàng)式表示。常將式(4)按變?cè)齼缂跋聵?biāo)的字典序?qū)懗?/p>

f(x)=a0+a1x1+a2x2+…+anxn+a1，2x1x2+…+an-1，nxn-1xn+…+a1，2，…，nx1x2…xn。

(5)

式(5)稱為f(x)的代數(shù)正規(guī)型。任一確定的n個(gè)變?cè)牟紶柡瘮?shù)f(x)的代數(shù)正規(guī)型是惟一的。一個(gè)乘積項(xiàng)(也稱單項(xiàng)式)xi1xi2…xir的次數(shù)定義為r，非零常數(shù)項(xiàng)的次數(shù)定義為0，0的次數(shù)定義為-。布爾函數(shù)f的次數(shù)定義為f的代數(shù)正規(guī)型中具有非零系數(shù)的乘積項(xiàng)中的最大次數(shù)，記為?0f。當(dāng)?0f=1時(shí)，稱f(x)為線性布爾函數(shù)；當(dāng)?0f≥2時(shí)，稱f(x)為非線性布爾函數(shù)。

現(xiàn)在觀察f(x)的最高次項(xiàng)x1x2…xn出現(xiàn)的充要條件。易知

這里“∑”是實(shí)數(shù)求和，即a1，2，…，n=WH(f) mod 2?？傻胊1，2，…，n=1，當(dāng)且僅當(dāng)WH(f)為奇數(shù)。由此可見，當(dāng)WH(f)為偶數(shù)時(shí)，a1，2，…，n=0，即最高次項(xiàng)不出現(xiàn)。特別地，平衡布爾函數(shù)無最高次項(xiàng)x1x2…xn。

下面說明相關(guān)免疫階和非線性次數(shù)之間的關(guān)系[3-4，8]。

注意到式(4)中除系數(shù)為ai1，i2，…，ir的項(xiàng)之外，其余各項(xiàng)在Si1，i2，…，ir上模2求和結(jié)果均為0，因此，有

(6)

ai1，i2，…，ir=2r×2-nWH(f)(mod 2)=2r-n+mk0(mod 2) ，

這里WH(f)=2mk0(由引理2可知)。所以，當(dāng)r>n-m時(shí)，ai1，i2，…，ir=0。當(dāng)r=n-m時(shí)，若k0為奇數(shù)，則所有的n-m次項(xiàng)都出現(xiàn)；若k0為偶數(shù)，則所有的n-m次項(xiàng)都不出現(xiàn)。

當(dāng)WH(f)=2n-1，m≤n-2時(shí)，可知k0為偶數(shù)。于是對(duì)于r≥n-m，都有ai1，i2，…，ir=0。

3.3 相關(guān)免疫階與非線性度之間的關(guān)系

非線性度是衡量布爾函數(shù)的非線性程度的一個(gè)重要指標(biāo)，它刻畫了一個(gè)布爾函數(shù)和線性布爾函數(shù)類之間的符合程度，其精確定義如下。

為布爾函數(shù)f的非線性度。其中，dH(f(x)，l(x))表示f(x)與l(x)之間的漢明距離，即

對(duì)于二元域，有dH(f(x)，l(x))=WH(f+l)。

下面的定理給出了布爾函數(shù)的非線性度的沃爾什譜表示。

(7)

式(7)表明，布爾函數(shù)f的非線性度與f的最大絕對(duì)譜值有關(guān)。同時(shí)，也說明了f的譜值實(shí)質(zhì)上反映了該函數(shù)與線性函數(shù)之間的符合程度，亦即非線性程度。

定理1中的式(3)可改寫為

(8)

則

(9)

式(9)可由式(7)和式(8)直接推出。式(9)表明，Nf越大，NSf就越??；反之亦然。說明Nf和NSf之間存在著一種制約關(guān)系。從這里也不難看出，一個(gè)布爾函數(shù)的譜值中零值過多，必將導(dǎo)致其非線性度下降，故而從密碼學(xué)角度來看，不是理想的函數(shù)。因此，在設(shè)計(jì)密碼函數(shù)時(shí)要注意到這一點(diǎn)。

下面說明布爾函數(shù)的相關(guān)免疫階和非線性度之間的關(guān)系[5]。

由定理2和式(9)易知，f(x)的相關(guān)免疫階m和其非線性度Nf之間有如下關(guān)系：

(10)

式(10)可改寫為

(11)

式(11)表明，m與Nf之間存在某種制約關(guān)系，相關(guān)免疫階m對(duì)非線性度Nf的影響較大。在具體應(yīng)用時(shí)，應(yīng)適當(dāng)折中。還可以給出一個(gè)更精細(xì)的關(guān)系[5]。

4 總 結(jié)

文中主要淺析了Xiao-Massey定理的意義和作用。這一定理為頻譜技術(shù)在密碼學(xué)中的應(yīng)用開辟了一條廣闊的道路，充分證明頻譜技術(shù)是研究相關(guān)免疫函數(shù)的強(qiáng)有力工具。文中僅僅列舉了3個(gè)方面的作用，關(guān)于Xiao-Massey定理的作用遠(yuǎn)不止這些。

5 跋

為了真誠(chéng)地紀(jì)念我的導(dǎo)師肖國(guó)鎮(zhèn)先生，我重溫了Xiao-Massey定理。通過回憶肖老師當(dāng)時(shí)對(duì)我的教誨和指導(dǎo)，梳理出此文。我認(rèn)為這是對(duì)肖老師最好的紀(jì)念和思念。

曾有人講過，一個(gè)人的生命主要由三部分組成：一是自然生命，這一點(diǎn)大家比較容易理解；二是親戚朋友的生命，也就是說，只要他的親戚朋友還在世，有人就會(huì)不時(shí)地提起他，惦記他；三是比較親近的晚輩的生命，比如弟子、徒弟等也會(huì)不時(shí)地想起他，思念他。當(dāng)這些人都已不在世時(shí)，這個(gè)人的生命也就真正結(jié)束了。我想肖老師不止這些，至少還有Xiao-Massey定理，他會(huì)永遠(yuǎn)活在密碼人的心中。