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

馮登國

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

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

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

1 Xiao-Massey定理

(1)

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

(2)

上面各式中的求和是指實數求和，式(2)可由式(1)推導出。

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

(3)

則稱f與變元xi1，xi2，…，xim統計無關(也稱統計獨立)。如果f與x1，x2，…，xn中的任意m個變元都統計無關，則稱f是m階相關免疫的。特別地，如果f既是平衡的，又是m階相關免疫的，則也稱f是m階彈性的。

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

由Xiao-Massey引理可推出以下結論。

下面的引理2給出了f與變元xi1，xi2，…，xim統計無關的重量特征。

引理2設f(x)如定義2中所述，f(x)與變元xi1，xi2，…，xim統計無關，則WH(f)=2mk0，k0為非負整數。

證明：因為f(x)與變元xi1，xi2，…，xim統計無關，因此，

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

由

且

得

即

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

其中，f′表示給定xi1=ci1，xi2=ci2，…，xim=cim的條件下，f關于n-m個變元{x1，x2，…，xn}{xi1，xi2，…，xim}的函數。

下面給出Xiao-Massey定理。

可由定理2直接推出f(x)與變元xi1，xi2，…，xim統計無關的譜特征。

2 Xiao-Massey定理的意義

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

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

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

② 適用于研究域、環等代數結構上的密碼函數的頻譜理論與方法；

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

④ 密碼函數的各種性質的頻譜特征刻畫；

⑤ 頻譜技術在密碼分析中的應用，如最佳仿射逼近分析[7]、最大相關攻擊[5]等；

⑥ 探索其他頻譜技術在密碼學中的應用。

(2) 該定理為研究相關免疫函數找到了一個新的研究工具，創新性地刻畫了相關免疫布爾函數的頻譜特征。起初人們對相關免疫函數的認識非常有限，Xiao-Massey定理的提出，打開了人們認識相關免疫函數的視野，給出了若干刻畫相關免疫函數特征的方法，并進一步刻畫了相關免疫階與其他非線性準則之間的關系。主要包括以下研究內容：

① 相關免疫函數的特征刻畫，如特征矩陣的各種刻畫以及與組合設計和糾錯編碼中對偶距離之間的關系等；

② 相關免疫階與其他非線性準則之間的關系，如非線性次數、非線性度、線性結構、擴散準則等；

③ 高度非線性相關免疫函數的構造與計數；

④ 滿足各種密碼學性質的密碼函數的構造與計數；

⑤ 探索新的非線性度量準則。

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

① 各種頻譜技術的快速計算方法；

② 概率統計問題與代數問題的相互轉化方法。

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

3 Xiao-Massey定理的作用

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

3.1 相關免疫函數的判定

由Xiao-Massey定理可推出以下結論。

注意到

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

且

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

由推論3易推出以下結論。

下面的算法1給出了構造相關免疫函數的一個遞歸方法[3]。

算法1設f1和f2分別是n個變元的m階相關免疫函數，令

則f是n+1個變元的m階相關免疫函數。次數?0f=max{?0f1，?0f2}+1。

可直接利用Xiao-Massey定理判定算法1構造出的f是n+1個變元的m階相關免疫函數。

3.2 相關免疫階與非線性次數之間的關系

(4)

其中，a0，ai1，i2，…，ir∈F2，求和符號“∑”是指在F2上的求和。式(4)稱為f(x)的多項式表示。常將式(4)按變元升冪及下標的字典序寫成

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

(5)

式(5)稱為f(x)的代數正規型。任一確定的n個變元的布爾函數f(x)的代數正規型是惟一的。一個乘積項(也稱單項式)xi1xi2…xir的次數定義為r，非零常數項的次數定義為0，0的次數定義為-。布爾函數f的次數定義為f的代數正規型中具有非零系數的乘積項中的最大次數，記為?0f。當?0f=1時，稱f(x)為線性布爾函數；當?0f≥2時，稱f(x)為非線性布爾函數。

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

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

下面說明相關免疫階和非線性次數之間的關系[3-4，8]。

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

(6)

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

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

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

3.3 相關免疫階與非線性度之間的關系

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

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

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

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

(7)

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

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

(8)

則

(9)

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

下面說明布爾函數的相關免疫階和非線性度之間的關系[5]。

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

(10)

式(10)可改寫為

(11)

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

4 總 結

文中主要淺析了Xiao-Massey定理的意義和作用。這一定理為頻譜技術在密碼學中的應用開辟了一條廣闊的道路，充分證明頻譜技術是研究相關免疫函數的強有力工具。文中僅僅列舉了3個方面的作用，關于Xiao-Massey定理的作用遠不止這些。

5 跋

為了真誠地紀念我的導師肖國鎮先生，我重溫了Xiao-Massey定理。通過回憶肖老師當時對我的教誨和指導，梳理出此文。我認為這是對肖老師最好的紀念和思念。

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