內(nèi)容分析案例

抵抗代數(shù)，系統(tǒng)中使用的布爾函數(shù)必須具有盡可能高的代數(shù)免疫度，甚給定一個n，可構(gòu)造多個代數(shù)免疫度最優(yōu)的函數(shù)。...........................................................................................................................1第一章緒 研究的背景及意 國內(nèi)外研究現(xiàn) 本文主要工 第二章背景知 序列簡 序列的代數(shù)低次多變元非線性方程組的建 求解多變元非線性方程組的方 布爾函數(shù)基礎(chǔ)知 布爾函數(shù)的基本概 布爾函數(shù)的基本性 旋轉(zhuǎn)對稱布爾函 第三章代數(shù)免疫度最優(yōu)的偶數(shù)元旋轉(zhuǎn)對稱布爾函數(shù)的構(gòu) 充分條件及預(yù)備知 構(gòu)造方 代數(shù)免疫 非線性 本章小 第四章代數(shù)免疫度最優(yōu)的奇數(shù)元旋轉(zhuǎn)對稱布爾函數(shù)的研 預(yù)備知 構(gòu)造方 代數(shù)免疫 非線性 代數(shù)次 本章小 第五章結(jié)論與展 本文工作總 有待進一步研究的問題及展 第一章研究的背景及意國內(nèi)外研究現(xiàn)狀本文主要工第二章景序列簡序列（又稱流）是學(xué)中一個重要的體制。它的可以追溯到20世紀(jì)20年代的古典學(xué)中的Vernam體制。它將明文流和密鑰流都隨機的產(chǎn)生，則Vernam被稱為一次一密。1949年，Shannon（香農(nóng)）證明序列就是模仿“一次一密”設(shè)計的。定設(shè)k是系統(tǒng)的密鑰源，也稱為初始密鑰，它通過安全信道傳輸，通信雙方在擁有相同的密鑰源k的前提下，能夠通過密鑰序列產(chǎn)生器生成相同的密鑰序列： kikn1。令 mimn1是待加密的消息序列。則密文序列為cE為加密變換。若 Ek(mi ki，則稱這類為加法序列i序列可以劃分為同步序列和自同步序列其中，0是初始狀態(tài)，可由密鑰kfg是產(chǎn)生密鑰序列zi的函數(shù)，h是將密鑰序列zi和明文mi組合產(chǎn)生密文ci的輸出函數(shù)。加過程如圖圖00同步序列加流iii

h mi（a）加 同步序列中，發(fā)送方和接收方必須同步。正因為此特性，主動的插入、刪除和密文位的重放都會造成失步，并能夠被檢查放發(fā)現(xiàn)。同步序列還有無錯誤的特點，即傳輸過程的一個密文位被修改（不是被刪除）不影響其他密文位的，但如果主動者有選擇的篡改密文位，那么我們就判斷明文碼被稱為自同步序列或非同步序列。加密過程為：ii 其中 (ct,ct ,c1)稱為初始狀態(tài)，k是密鑰，g是產(chǎn)生密鑰序列zi的函數(shù)h是將密鑰序列zi和明文mi組合產(chǎn)生密文ci的輸出函數(shù)。加過程如圖01：圖01自同步序列加流程

h1 mi（a）加 同步序列更好的抵抗基于明文冗余的。序列的主要特點有加運算只是簡單的模二加運算；安全強度主要依KG生成的密鑰序列{ki{ki具有均勻的n利用統(tǒng)計方法由{ki}提取關(guān)于KG結(jié)構(gòu)或者Ｋ的信息在計算上是不可性，即{ki}的每一比特均與Ｋ的大多數(shù)比特有關(guān)。擴散性，即Ｋ的任一比特將引起{ki}序列的代數(shù)布爾函數(shù)基礎(chǔ)知識布爾函數(shù)的基本概設(shè)n為整數(shù)， {0,1}為二元域2.1nf2記為f(x)，其中 n，f 22記B為所有n元布爾函數(shù)組成的集合。則顯然|B|22n 設(shè)f f(x1,x2,...,xn {a1,a2...,an} n，如果對所有的2

n有 則稱被覆蓋，記為 2在““序下，n上所有向量從小到大可排列成如下（字典順序2 f

2，于是任一n元布爾函數(shù)與一段長度為2n01如表2-1給出了一個2元函數(shù)f f(x1,x2)的例子。其對應(yīng)的真值表向量 2-1xf000011101100定義00任一nf(x1,x2,...,xn都可以唯一表示成2過n

a12...nx1x2...xnf(xa12...nx1x2...xn其中a0,ai,aij,...,a12...n 2，這種表示方式稱為f(x1,x2,...,xn)的代數(shù)正規(guī)型（ANF。式中系數(shù)不為零的項的最大次數(shù)稱為f的代數(shù)次數(shù)，記為deg(f)。代數(shù)次數(shù)不超BM，一般要求布爾函數(shù)具有較高的代數(shù)次數(shù)[39][112]2為(vi,1,vi,2,...,vi,n)i1,2,...,k，那么有2if(x1,xiv1,1v2,1vv1,1v2,1vk,1V布爾函數(shù)的基本性質(zhì)對nf(xsupp(f和offset(f分別成f(x的支撐集和零wt(f)|supp(f|f的漢明重量。若|supp(f)||offset(f|f(x)是平衡的，此時wt(f)2向量 (x1,x2,...,xn n的支撐集定義為 {i|2

n}。向量的漢明重量定義為 |supp(x)|任意兩個布爾函數(shù)f和g的漢明距離為d(f,g) Walsh定義2對任意的 Bn，其Walsh變換定義Wf2其中 n，xw是向量x和w的內(nèi)積2對于向量 n，稱Wf(w)是f在w點的Walsh系數(shù)。f在空間n所有向量上的 3一個n元布爾函數(shù)的非線性度NL(f

NL(f mind(f,gNL(f 2n 1max|W(w)22w 2性質(zhì)1[39]nf的非線性度NL(fn2nn2n 。n2n n2n NL(f很好的學(xué)性質(zhì)，比如擴散性穩(wěn)定性等。相關(guān)免疫性的概率最早是由Siegenthaler[149]在研究序列系統(tǒng)的安全性時列在序中使用的布爾函數(shù)需要滿足相關(guān)免疫條件:即固列x中的某些坐標(biāo)分量xi，f(x)1的概率不變。關(guān)于這個定義,有很多等價的表達形式,Xiao-Massey定理[167]刻畫了相關(guān)免疫函數(shù)的頻譜特征，這里我們把它作為相關(guān)免2.8[167]f(x)Bnf(x是m(1mn0平衡的m階相關(guān)免疫函數(shù)稱為mf(x是彈性函數(shù),定義00對于n元布爾函數(shù)f，滿足f 0的n元布爾函數(shù)g稱為f的零化子。的零化集定義為4nf的代數(shù)免疫度(AlgebraicImmunityAI)AI(f1[36]對任意nf，其代數(shù)免疫度AI(f滿足：n33如果nf的代數(shù)免疫度AI(fn代數(shù)免疫度衡量了布爾函數(shù)抵抗標(biāo)準(zhǔn)代數(shù)的能力。布爾函數(shù)代數(shù)免疫度越高，則抵抗標(biāo)準(zhǔn)代數(shù)的能力越強。所以，一般要求系統(tǒng)使用的布爾函數(shù)應(yīng)5當(dāng)n1,wt(x)n/Fn

0,

當(dāng)nFn

0,1設(shè)n為偶數(shù)，則式（00）Walsh WF當(dāng)

WF1設(shè)n2k1，則式（01）Walsh 當(dāng) nWF 2 當(dāng) n2( 當(dāng) 1， 7時，有2kkWF2kk旋轉(zhuǎn)對稱布爾函數(shù)在1998年的歐密會上,首次出現(xiàn)了旋轉(zhuǎn)對稱布爾函數(shù)的概念,這類函數(shù)在密非常重要。通過實驗驗證人們發(fā)現(xiàn)，旋轉(zhuǎn)對稱布爾函數(shù)還具有很好的學(xué)性

2n個相比相同變量的全體布爾函數(shù)(共定義6設(shè) (x1,x2,...,xn Fn，則對于x n)以及 nk的定義可以推廣到向量x上n設(shè){i1,i2,...,im supp(x)，則對任意的ij m)，定k的定義可以推廣到集合{i,i,...,i上 1 從k和k

supp(k k(supp(x)) n定義7布爾函數(shù) B，如果對任意的 (k f n)成立，nn, (x1,x2,...,xn) n產(chǎn)生的軌道定義為2Gn第三章數(shù)免疫度最優(yōu)的偶數(shù)元旋轉(zhuǎn)對稱布爾函數(shù)足該充分條件，從而表明該類函數(shù)代數(shù)免疫度最優(yōu)，能夠有效抵抗代數(shù)。同充分條件及預(yù)備知識223.1[18設(shè)n為偶數(shù)，向量a1,a2,...,a

是Fn上所有漢明重量為n/2對任意的 n)，集合A和A0定義n A0Ai令集合I,J, n/2)，且兩兩互不相交。若對任意的 I，存在一個向 ai使得 Ai[i*iA*]，類似地，對任意的 J，存在一個向量 aj使 A0

iA0j*jj設(shè)n為偶數(shù) 包含的元素個數(shù)M n/ 。定義(h)和v(h使得 kk2h 22h 22 kk、現(xiàn)在我們證明(h)和v(h 證明由h和k的范圍得 2n/ 2

1 ，于是 h1。 由

2及k的范圍可得

ttk

2。因此t(h)k n n |kkkk所以向量(h)和v(h 引理3.1對任意的 H和 Kh，有1.|Gn 2

supp(q(( supp(q(v(hnnn證明由(h)和v(h2 n引理3.2任給一個 H，則對任意的 Kh和 n假設(shè)存在一個

使得qsupp(( supp(v(h))。由 n 'nknkk又因為連續(xù)子集q' qsupp(( supp(v('nknkkq'1,...,t(h)}（3-nkk'nnkk對另外續(xù)子集q' qsupp(( supp(v(h))，'nnkknq'nq' 1,...,t(h)}（3- nnkk而由 2可得，|q'{1,2,...,h} |q'{k, 1}||{k, 1,...,t(h)}|。因此式nnkk和式(3-3)不能同時滿足，這和qsupp(( supp(v(h) 。因而n'n 引理3.3任給一個 H，則對任意的k Kh， k和 q 1 1假設(shè)存在一個

1)使得qsupp(( supp(v(h))nnnn (1)當(dāng)''q'{k1,...,t(h)}（3-n1' 2n對連續(xù)子集q'{k qsupp((' 2n222 41q'{k{k 1,...,t(h)}（3- 21 ) 和supp(v(h))同時也滿足) 111故式（3-4）和式(3-5)不能同時滿足。這和qsupp(( 。因而n'n n-1)（3-0當(dāng)q022由 h， 1和 k1，0n supp(v(h))（3-0n 構(gòu)造方下面對每一個偶數(shù) 16)構(gòu)造出了一類具有 4

定理3.2：選取偶數(shù)n， 164令 1，構(gòu)造 N)使得4 p

2 21}{ p},2{n2{n22 構(gòu)造 Kh)滿足 kk) nn 2p

N滿足1supp(lp構(gòu)否f否代數(shù)免疫度 1引理3.4任給一個 H，則對任意的 Kh， N， 1假設(shè)存在r 1)滿)11而2222 )，因定理3.3對于任意的h H定理3.2構(gòu)造的函數(shù)f(x)是代數(shù)免疫度最優(yōu)的偶數(shù)元對任意的 H，令 I2，且1對任意的 有 12 q1 q1 )，A表示線性子空間 n 2 i Ai。由文獻[16]中的定理1知 i*iA*i對任意的 I2，有 N1n ( n/2)n1q hK, 1 n，令q1((hA如上所述，則有

A 假設(shè)存在 I)滿足 A*,令 * 1)。由Ai由引理3.2和3.3可知 k，這與 i，因此2對于 I,根據(jù)引理3.4，可知 A I)。故對任意的 I，都2

i 1令 N2) N2) N2)n}，對任意的 J滿1 有 )用A0表示線性子空間 nsupp(a N 。由文獻[16]中的定理1可知，有 。令 N2) N2) N2)n}，對于任意的 N) q q1(l)。對任意的 I， J K， n然滿足 定理3.4任給一個 H，則定理3.2構(gòu)造的旋轉(zhuǎn)對稱布爾函數(shù)f(x)的非線性NL(f滿足

n n 2n1n NL(f) 2 n1n 2n1n 22222Wf2222下面討論對不同漢明重量的u計算Wf(u)

n，于222nn22nn N2 2

n，于22222Wf2222n11p1p21pWfn11p Wf由于N

N，因此對任意的偶數(shù) 16)，有1Wf n1.1有

n (1)2n，于2n2nWf 2nn2N22n2nWf 2nn2N22因此對任意的偶數(shù) 16)，有nnN2nnN2 nn2

21nn1n 121nn1n 2 ，比較這四種情況可知當(dāng) 1時Wf(u)最大，注意，2w2NL(f 2n 1max|W(w|，于是NL(2w2f 2n NL(f

2n

n為偶數(shù) 2 4性度最高，尤其是隨著n增大這種優(yōu)勢越明顯。3.1n文獻文獻本章小17中構(gòu)造的代數(shù)免疫度最優(yōu)的偶數(shù)元旋轉(zhuǎn)對稱布爾函數(shù)的方法的基礎(chǔ)上進行改進。其非線性度有了較明顯的提高。并且給定一個偶數(shù) 16)，通過我們的 第四章數(shù)免疫度最優(yōu)的奇數(shù)元旋轉(zhuǎn)對稱布爾函數(shù)了此類布爾函數(shù)代數(shù)免疫度最優(yōu)，并計算了這類函數(shù)的非線性度，分析了這類函預(yù)備知首先，我們回顧一下一個整數(shù)k—個正整數(shù)k的構(gòu)成可以看成一個序列(k1,k2,...,ki)， ki滿足 k，并且k1,k2, ki有序。這樣，不同順序的兩個序列是k的兩個不(2,1,1,1)，(1,4)，(13,1)，(1,2,2，(1,2,1,1)，(1,13)，(1,1,2,1，(1,1,1,2)，(1,1,1,1,1。的所有構(gòu)成計數(shù)記為(k)。規(guī)定(0) 引理4.1[20]正整數(shù)k的所有構(gòu)成計數(shù)為： 2k1（4- { Wk {u,...,u Wk1， n。F(x)是擇 函數(shù)。如果集合T，U

證明：對k當(dāng) 7時，容易驗證該不等式成立00假設(shè) k時 2k0 2k0 3)2k0成立，即0

k0 0下面證明當(dāng) 02(k02(k0 2(k01) 2(k01)(k0 (k0 (k01)1) 0 0003)00000構(gòu)造方記W

)=i},{n|{n|wt( i} n|

n設(shè)

i i{h| 6)，集合H滿足 {h| 二元域上的集合Th H)如下{(1,...,1,0,1,...,1,{(1,...,1,0,1,...,1,0,...,1,...,1,0,0,...,0)Wk|k1 k2 ki 由 Wh可得

{, h。由引理4.1可得|Th 2h 1按字典順序給集合Th {h,h,..., (2h2

}（4-Wk我們定義另外一個集合Wk任給一個向量 (x,x,...,x n，定義 (x,...,x)1 u3s定義集合Tu3sTUF(x)5中的nU代數(shù)免疫度引理4.3對任意的 H， Th以及uh Uh 2h 1,以下結(jié)論

對任意的0ln，l

n

l

，l(u u恒成立lhslhsnl

n，

n l對任意的l

n時

對任意的h1,h2H并且滿足h1時，(h) l(u(h))成立。hsnlhsnll當(dāng) t，l

n時

由式（4-2）知hn( h)2k(。當(dāng)且僅 或者 2（2，k2 ki1）時，h2(k1h)，而由Th的定以及k5huhs并且k1k2 kih，h2(k1h)0于是由Th和Uh的定義以及h2(k1h01，2由hhlhif知對任意的

n，ll l

)hh

0和 2 (l(u hl (u hl if nhs h hs h (l(u (u if (uh (1,1)(l(u if s nhs知對任意的 n，ln

43l(uu的證明方法（僅需將u替換成n保持ln

）滿足k'k'k'k'滿足k'k' k' h h同樣可以通過l(u u的證明方（將u替換 ，l(uh)h n 換成l )）得n(h2h當(dāng)h當(dāng)

lh11hlh11h1h1。當(dāng)h2(k1h21ln2(k1h22(當(dāng)n2(k1h21ln1(h設(shè) (1,...,1,0,...,1,...,1,0,0,...,0,1,0,1,0,...,1,0)。h k' k' '2(k1 2(k1

' t得結(jié)h165的證明方法（將(h)1l )替換成l(u)，h替換 ,h替換成'）得到 h2 n

hs n，其中 h.根據(jù)引理4.2，考慮到T'和U中向量的順序，要證式（4-5）中的函數(shù)f(x2h數(shù)免疫度最優(yōu)，即證T和2h

ln

)，nmnm)nl2hnm)nm)nl2hmn )lmn )ln(h22h.12.設(shè)

) 2k xUk2h2 k2h2h3i h3i（8Wf下面我們對不同漢明重量的向量u計算Wf(u) 0，即 (0,0,...,0)，由于F(x)是平衡的，集合T'和U'中的元素 n1 2 n1 2k2h2k2h2k2h2h