【文章內(nèi)容簡介】 然，布爾函數(shù)也不例外。從代數(shù)的角度，分析布爾函數(shù)主要采用多項(xiàng)式表示和小項(xiàng)表示。 頻譜方法頻譜分析作為研究布爾函數(shù)的一個(gè)重要工具，通過其可以分析布爾函數(shù)的譜特性。天津科技大學(xué) 2022 屆本科生畢業(yè)論文8 矩陣方法布爾函數(shù)最直觀的表示方法就是矩陣表示，在定序意義下，重量為 的w元布爾函數(shù)之集和 上 矩陣之間是一一對(duì)應(yīng)的。n2Fnw?)21(n? 重量分析方法對(duì)任意兩個(gè)布爾函數(shù) 和 ，定義 和),.()1nxfx?),.(1nxg?)(xf的距離為)(xg f?記為 ，即,fd),(gfd?)(fw對(duì)和函數(shù)的重量有如下關(guān)系式： （231 ）f?f)(2fg?重量分析方法是通過分析布爾函數(shù)的重量特征來研究布爾函數(shù)的方法，這種方法簡單易懂，很適合工程應(yīng)用。以上研究方法因?yàn)槠涮攸c(diǎn)不同，適用于不同的研究場(chǎng)景和領(lǐng)域。天津科技大學(xué) 2022 屆本科生畢業(yè)論文93 布爾函數(shù)的密碼學(xué)性質(zhì)布爾函數(shù)在不同領(lǐng)域有著不同的應(yīng)用，因而衍生出了不同的函數(shù)類。人們對(duì)不同種類的布爾函數(shù)的研究歸結(jié)為對(duì)布爾函數(shù)某種性質(zhì)的研究。本章著重介紹布爾函數(shù)的一些重要性質(zhì)。 布爾函數(shù)的 Walsh 變換及其性質(zhì) 兩種 Walsh 變換在 節(jié)中已經(jīng)介紹過布爾函數(shù)的 Walsh 譜表示和 Walsh 變換對(duì)研究布爾函數(shù)的重要性。本節(jié)首先討論 Walsh 變換及其性質(zhì)。如無特別聲明， 均)(xf指 元布爾函數(shù)。n已知 210()()nwxfxfS???A若記 （311 ）()1wxwQA則當(dāng) 取遍 （或 ）時(shí)，就得到一個(gè)函數(shù)系 [11]：wnF2120??n， （312 ）)(xw?nF2此函數(shù)系是一個(gè)正交函數(shù)系，即滿足 )(Quv?????vun,0該函數(shù)系（311 ）稱為 Walsh 函數(shù)系。顯然，對(duì)給定的 ， ，有xw)(xQ?。)(wQx可以看作 在 Walsh 函數(shù)系下的展開式。 是展210()nwxfxfS???A)(xf )(Sf開式的系數(shù)，即 Walsh 譜。還有另外一種展開式：)(f （313 ）)(xf?)(210)(xQwSfn???其中 （314 ）)()1()(20xSwwfnf??天津科技大學(xué) 2022 屆本科生畢業(yè)論文10為了區(qū)別，將 稱為 的第一種 Walsh 譜或線性譜，而將 稱為)(wSf )(xf )(wSf的第二種 Walsh 譜或循環(huán)譜。)(xf定理 與 的關(guān)系如下：)(f )(f （315 ）)(wSf???????0),(21xSf Walsh 變換的性質(zhì)Walsh 變換有如下性質(zhì)：性質(zhì) 1（平穩(wěn)性） 若 在 的譜值為 ，則 在 的譜值為)(xf )(Sf )(axf?w （316 ）,(waQf性質(zhì) 2（線性姓） 若 在 的譜值為 ， 若 在 的譜值為 ，)(xf )(f )(xg)(Sg則 在 的譜值為)(xbgaf?w （317 ）)()(wbSagf?性質(zhì) 3（Plancheral 公式） （318 ）)(2)0(120 fxnfwfn ?????此性質(zhì)又稱為初值定理。性質(zhì) 4（Parseval 公式） （319 ）1)(120???xSnwf此即能量守恒定理。 布爾函數(shù)的線性性定義 如果 ),.(1nxf?),.(,.(11nbnxlxg??則稱 元布爾函數(shù)是部分線性的，其中n； 。??????nbiibncl11),.( ,2??Fni定義 設(shè) 是 元布爾函數(shù)， ，稱 為 的一個(gè)線性結(jié)構(gòu)，)xf a)(xf則對(duì)任意 ， 為常數(shù)。若 ，稱 為 的nFx2?)((fa 0)(??xf a()fx不變線性結(jié)構(gòu)。若 ，稱 為 的恒變線性結(jié)構(gòu)。記 {全f ?E天津科技大學(xué) 2022 屆本科生畢業(yè)論文11體線性結(jié)構(gòu)}，則 是 的一個(gè)線性子空間，若該子空間的維數(shù)為正，即EnF2，則稱 是一個(gè)線性結(jié)構(gòu)函數(shù) [10]。0?Dim)(xf記 }0)((|{0 ????xfafE11則有如下性質(zhì)：① , ；??10E?0?② 是 的子空間；?③ 若 ，則 ；11,Ea?④ 設(shè) ，若 ，則 ， 。r20?r2?1?r若 ，則稱 為 的線性結(jié)構(gòu)維數(shù)，此時(shí)有如下兩種情況：??q)(xf① ；1||?E② ，即 為空集。,01設(shè) 是線性結(jié)構(gòu)函數(shù)，若 ，則稱 為 I 型線性結(jié)構(gòu)函數(shù)；若)(xf }0{?E)(xf，這時(shí)必有 ，則稱 是一個(gè) II 型線性結(jié)構(gòu)函數(shù)。}{0?1)(xf定義 設(shè) ，若 的取值不影響 的取值，則稱?)(f,.1ni )(xf與 無關(guān)。該性質(zhì)稱為與變?cè)獰o關(guān)性，最初稱與變?cè)獰o關(guān)性為退化，定義)(fi如下：定義 設(shè) ，若存在 上的 矩陣 ,使得)(xf),.1nxf nF2k?)(n?D),.((1ygD?則稱 是退化的。)(xf容易看出，若 與變?cè)獰o關(guān)，則必然退化，退化性是與變?cè)獰o關(guān)性的推)(f廣 [12]。由此可以得出如下定理：定理 是退化的 。f }0{??E推論：II 型線性結(jié)構(gòu)函數(shù)是不可退化的。定理 是部分線性的，則 是退化的。)(xf )(xf 布爾函數(shù)的非線性性顧名思義，非線性性和線性性是相對(duì)的。代數(shù)次數(shù)大于一的函數(shù)是非線性函數(shù)，雖同為非線性函數(shù)，差異卻很大 [12]。例如 和4321)(xxf??都是 2 次非線性函數(shù)，但 是部分線性的，而 是非退43212)(xxf??1 )(2f化的， 比 更接近線性函數(shù)，或者說 更容易用線性函數(shù)來逼近，f)(f f于是人們便引入了“非線性度”這一概念來描述一個(gè)函數(shù)非線性的程度 [10]。定義 設(shè) 是 元一個(gè)布爾函數(shù)，記 為所有 元線性函數(shù)之集。xfn][xLn則稱 （331 ）][mixLln?),(lfd][ixLln??)(lfw?為 的非線性度，記為 ，即 的非線性度為其與所有線性函數(shù)的最短)(xf fN天津科技大學(xué) 2022 屆本科生畢業(yè)論文12距離，很明顯線性函數(shù)非線性度為 [10]。同理稱0 （332 ）][maxLln?),(lfd為 的線性度，記為 。 ，即 的線性度為其與所有線性函數(shù)的最長距離。)(xf fC)(f由定義 可知，對(duì)任意 元布爾函數(shù) 有n)(xf （333 ）fN?fCn2?定義 設(shè) 是 元一個(gè)布爾函數(shù)，若比值函數(shù) 滿足)(xf 12/)(??nfNq，則稱布爾函數(shù) 具有高非線性度。lim(x)1q???()f對(duì)任意 元布爾函數(shù) ，當(dāng)其非線性度 時(shí)，n 1/2nf?， ，顯然布爾函數(shù)滿足高非線性度，此時(shí)，我們稱/2?li(x)1q???為 Bent 函數(shù)。()fxBent 函數(shù)乃非線性度最高的函數(shù)，對(duì)布爾函數(shù)的研究有著極其重要的作用。定義 對(duì)任意元布爾函數(shù) ，若 的取值不影響的),.()1nxfx?i取值，則稱 與 無關(guān)。()fx()fxi定義 設(shè)布爾函數(shù) ： ，對(duì)于任意給定的 ，()f2nF2,naF?且 0?對(duì)任意的 ，如果 恒為常數(shù)，那么稱 為 的一個(gè)線性結(jié)2nF?a?()f構(gòu)。記其中的常數(shù)為 ，則線性結(jié)構(gòu)表示為b, 。2{|())}nExfxb???2 相關(guān)免疫性相關(guān)免疫性作為布爾函數(shù)的一種統(tǒng)計(jì)性質(zhì)，在布爾函數(shù)的研究中有著重要意義。定義 設(shè) 是 個(gè)彼此獨(dú)立且對(duì)稱的 元隨機(jī)變量的布),.()1nxfx?2爾函數(shù)，當(dāng)且僅當(dāng) 與 中的 個(gè)隨機(jī)變量統(tǒng)計(jì)獨(dú)立，即當(dāng)且僅當(dāng)互信f息 [13] （341 ）1()。,.)0miiIf?時(shí)，稱 為 階相關(guān)免疫函數(shù)。其中對(duì)任意一組 ，有()fxm1,.miix成立。?當(dāng) 時(shí)，稱 為 階相關(guān)免疫函數(shù) [10]，亦叫相關(guān)免疫函數(shù)；當(dāng) ，?()fx1 2?稱 為高階相關(guān)免疫函數(shù)。顯然，如果 是 階相關(guān)免疫的，則對(duì)任意()f ()f， 是 階相關(guān)免疫的，相關(guān)免疫記為 ， 階相關(guān)免疫記為r()fr CICI，相應(yīng)的函數(shù)稱為 函數(shù)和 函數(shù)。CIIm 布爾函數(shù)的平衡性我們?cè)? 節(jié)定義了平衡布爾函數(shù)： = ，即 的真值表中 0()wf12?n()fx和 1 的個(gè)數(shù)相等。布爾函數(shù)的很多性質(zhì)，例如擴(kuò)散準(zhǔn)則、雪崩準(zhǔn)則和相關(guān)免疫天津科技大學(xué) 2022 屆本科生畢業(yè)論文13準(zhǔn)則等都可以用平衡性來定義，平衡性也是密碼函數(shù)的設(shè)計(jì)準(zhǔn)則之一。定義 對(duì)任意布爾函數(shù) ，如果),.()1nxfx? （351 ）(,.iif???則稱對(duì)變量 是線性的，其中 是與 無關(guān)的 元函數(shù)。ix1定理 布爾函數(shù) 對(duì)自變量 是線性的，當(dāng)且僅當(dāng)對(duì)任),.)nf i意 有1,.n （352 ）1(,..,ifx?1(,..,)infx其中 的取值為 0 或 1， ， ， 。ix?i?fA 布爾函數(shù)的對(duì)稱性定義 設(shè) 是 元布爾函數(shù)，如果對(duì)任意 階置換矩陣 有()fxn P （361 ）()fxP?則稱 是對(duì)稱函數(shù)。()fx顯然，如果 是對(duì)稱函數(shù)，那么任意交換其分量的位置， 不變，也()f ()fx就是 ，不妨設(shè) ， 。所以，ij??ij?1(,..,)ijnfx1(,..,jinf對(duì)任意 ，只要 ，則 ，也就是說當(dāng)布爾函數(shù)輸出2,nyF?y)wx?(yf?向量的漢明重量相同時(shí)，產(chǎn)生的輸出值也不變，這就是布爾函數(shù)的線性不變性，亦稱仿射不變性。 嚴(yán)格雪崩準(zhǔn)則嚴(yán)格雪崩準(zhǔn)則由 Webster 和 Tavares 在 1986 年首次提出，它對(duì)研究 S 盒有重要意義。定義 若對(duì)任意 ， ，總有 是平衡函數(shù)，2naF?()1w?())fxa?則稱 滿足嚴(yán)格雪崩準(zhǔn)則。如果固定任意 個(gè)變?cè)蟮玫降娜?元函數(shù)()fx knk?都滿足嚴(yán)格雪崩準(zhǔn)則，則稱 滿足 階嚴(yán)格雪崩準(zhǔn)則 [12]。()fx定義 若對(duì)任意 ， ，總有 是平衡函數(shù)，則稱2n0?())f為差分均勻函數(shù)。()fx差分均勻函數(shù)有 個(gè)輸入 個(gè)輸出，任意若干個(gè)輸入位發(fā)生改變，導(dǎo)致輸出1發(fā)生變化的概率為 ，滿足這種差分均勻性的函數(shù)為 Bent 函數(shù)。函數(shù)滿足最/大非線性性等價(jià)于函數(shù)滿足差分分布均勻 [12]。 擴(kuò)散準(zhǔn)則定義 若對(duì)任意 且 ，總有 是平衡函數(shù)，即2naF?0?())fxa?，則稱 關(guān)于 滿足擴(kuò)散準(zhǔn)則。若對(duì)任意滿足n1()()2wfxa???()fxa的 ， 關(guān)于 滿足擴(kuò)散準(zhǔn)則，則稱 滿足 次擴(kuò)散準(zhǔn)則。如1k?(fxfk果固定 的任意 個(gè)分量后得到的全部 元函數(shù)都滿足 次擴(kuò)散準(zhǔn)則，則fmm?稱 滿足 階 次擴(kuò)散準(zhǔn)則 [12]。 階 次擴(kuò)散準(zhǔn)則就是 次擴(kuò)散準(zhǔn)則。擴(kuò)散() 0k準(zhǔn)則記為 ， 次擴(kuò)散準(zhǔn)則記為 ,滿足相應(yīng)準(zhǔn)則的函數(shù)稱為 函數(shù)和PC()PCPC函數(shù) [12]。k在本章中，我們簡要介紹了布爾函數(shù)的一些密碼學(xué)特性及一些簡單結(jié)論。天津科技大學(xué) 2022 屆本科生畢業(yè)論文14布爾函數(shù)的密碼學(xué)性質(zhì)除了以上討論的非線性、平衡性、相關(guān)免疫性、嚴(yán)格雪崩和擴(kuò)散準(zhǔn)則等外，還有退化性、線性結(jié)構(gòu)等 [12]。天津科技大學(xué) 2022 屆本科生畢業(yè)論文154 序列密碼與布爾函數(shù)在第 2 章我們已經(jīng)簡單提到過序列密碼。序列密碼體制的安全性取決于密鑰流，而密鑰流序列由密鑰流生成器產(chǎn)生，常見的密鑰流生成器有前饋序列生成器、非線性反饋位移寄存器、非線性組合序列生成器和鐘控序列生成器等 [1]。在密鑰流生成器中，布爾函數(shù)起著極其關(guān)鍵的作用，所以本章著重討論布爾函數(shù)在流密碼中的應(yīng)用，對(duì)這些生成器我們并不一一介紹。 序列密碼概述 序列密碼原理現(xiàn)實(shí)中的各種信息或信源一般是圖像、報(bào)文、語言和數(shù)據(jù)等，一般都是經(jīng)編碼器轉(zhuǎn)化為 0,1 序列，即二進(jìn)制序列，加密是針對(duì) 0,1 序列進(jìn)行的。所以我們假設(shè)序列密碼中的密文空間，密鑰空間和明文空間均為二進(jìn)制序列組成的集合[14]。通信系統(tǒng)的模型如圖 41 所示。 明文 0,1 序列 恢復(fù)的明文 0,1 序列 信源 加密器 解密器 信宿圖 41 保密通信模型在序列密碼中，序列密碼將明文消息序列 用密鑰流序列12,.m?逐位加密，通過加密變換 （通常采用二元加法運(yùn)算）得到密文序12,.k?kE列 ，因此密碼系統(tǒng)的安全性主要取決于密鑰流序列的性能。c在序列密碼系統(tǒng)中，因?yàn)槊魑男蛄信c密鑰流逐位加密，所以密鑰流的長度必須與明文序列的長度相等，但這樣的序列卻難于管理和分配，所以實(shí)際中的密鑰序列均由密鑰空間中較短的密鑰經(jīng)過某些算法生成的 [1]。當(dāng)密鑰流序列是完全隨機(jī)序列時(shí)（一次一密鑰） ，該系統(tǒng)是不可破的，稱之為完全保密系統(tǒng)。稱但通常通過確定的算法產(chǎn)生的密鑰流序列是偽隨機(jī)序列，并非完全隨機(jī)，此時(shí)的密碼系統(tǒng)就不再完全保密了，因此為了保證密碼系統(tǒng)的安全性，密鑰流序列必須滿足一定的要求 [12]。 序列密碼對(duì)密鑰流的要求設(shè)計(jì)序列密碼的目的是為了設(shè)計(jì)一個(gè)能產(chǎn)生具有完全隨機(jī)性的密鑰流序列