【正文】 大 的 密 鑰 量③ 。人們通常用“復(fù)雜度”來描述這種“困難性” 。 ①，即攻擊者獲得當(dāng)前密鑰下的某些明文和密文對。研究分組密碼就是研究這種置換，()kEX2nmF到而布爾置換由一組具有一定關(guān)系的布爾函數(shù)構(gòu)成，所以對布爾置換的研究同樣可以歸結(jié)為對布爾函數(shù)的研究 [12]。所以要求同時滿足多個準(zhǔn)則，同時也出現(xiàn)這樣的問題，當(dāng)幾個準(zhǔn)則相互抵觸制約的時候如何尋求平衡來保證各個指標(biāo)的折中。12/)(??nfNqlim1xq???(x)f對任意 元布爾函數(shù) ，當(dāng)其非線性度 時，f 1/2nfN??， ，顯然布爾函數(shù)滿足高非線性度，此時，我們稱/li()x為 Bent 函數(shù)。布爾函數(shù)只有滿足一定的設(shè)計準(zhǔn)則，才能保證系統(tǒng)符合安全性的基本要求并可以抵抗現(xiàn)有的攻擊 從而保證系統(tǒng)的安全，為，此對流密碼中的布爾函數(shù)提出如下準(zhǔn)則，概括起來如下 [12]：① 平衡性平衡性即是為保證輸出的密鑰流序列具有良好統(tǒng)計特性而對布爾函數(shù)提出的準(zhǔn)則。()Nfx?定義 上的序列 ， 的線性復(fù)雜度 定義為產(chǎn)生該qF1,. ()Ca序列的 上級數(shù)最少的 LFSR 的級數(shù)。{}ia??對獨(dú)立均勻分布的二進(jìn)隨機(jī)變量序列 ，它的自相關(guān)函數(shù) 的期望值為{}iX()xR? （439 ）[()]xER??01=?????， 當(dāng) 時， 當(dāng) 時定理 上的 級 序列 具有如下性質(zhì) [15]：2Fnm{}ia① 在一個周期內(nèi)，0,1 出現(xiàn)之次數(shù)分別為 ， 。2 12n定理 設(shè)序列 的極小多項式為 ， ，則序列 的周期{}ia()Qx?{}ia是 整除 的最小正整數(shù) ，即 的階。定理 上的一個 級位移寄存器是非奇異的，當(dāng)且僅當(dāng)反饋函數(shù)2Fn可表示為01(,.)nfx? （433 ）01(,.)nfx?0x??1(,.)ngx?其中 是與 無關(guān)的 元布爾函數(shù)。因?yàn)轵?qū)動部分的設(shè)計相對更容易，因此非線性組合部分的設(shè)計便成為研究密鑰流生成器的重點(diǎn)和難點(diǎn)。上述要求的前兩條是為了擾亂或有效的掩蓋明文序列的統(tǒng)計隨機(jī)性，第三條是序列密碼理論的核心，決定密碼的強(qiáng)度。 明文 0,1 序列 恢復(fù)的明文 0,1 序列 信源 加密器 解密器 信宿圖 41 保密通信模型在序列密碼中，序列密碼將明文消息序列 用密鑰流序列12,.m?逐位加密，通過加密變換 （通常采用二元加法運(yùn)算）得到密文序12,.k?kE列 ，因此密碼系統(tǒng)的安全性主要取決于密鑰流序列的性能。k在本章中，我們簡要介紹了布爾函數(shù)的一些密碼學(xué)特性及一些簡單結(jié)論。()fx定義 若對任意 ， ，總有 是平衡函數(shù)，則稱2n0?())f為差分均勻函數(shù)。定義 對任意布爾函數(shù) ，如果),.()1nxfx? （351 ）(,.iif???則稱對變量 是線性的，其中 是與 無關(guān)的 元函數(shù)。2{|())}nExfxb???2 相關(guān)免疫性相關(guān)免疫性作為布爾函數(shù)的一種統(tǒng)計性質(zhì)，在布爾函數(shù)的研究中有著重要意義。同理稱0 （332 ）][maxLln?),(lfd為 的線性度，記為 。由此可以得出如下定理：定理 是退化的 。若 ，稱 為 的恒變線性結(jié)構(gòu)。)(wQx可以看作 在 Walsh 函數(shù)系下的展開式。天津科技大學(xué) 2022 屆本科生畢業(yè)論文93 布爾函數(shù)的密碼學(xué)性質(zhì)布爾函數(shù)在不同領(lǐng)域有著不同的應(yīng)用，因而衍生出了不同的函數(shù)類。布爾函數(shù)也可以通過投影空間的特征函數(shù)和狀態(tài)圖等表示。若 ，則定義 ；若0)(?0?，則稱 為仿射函數(shù)；當(dāng) 時，仿射函數(shù)被稱為線性函數(shù)；若)(?fde)(xf，則稱 為非線性函數(shù) [11]。本節(jié)將簡要介紹幾種布爾函數(shù)的表示方法。2在本文中，我們用 表示在有限域 = 上的所有 元組中的集合的元nF2F}1,0{n素。加密后輸出的等長密文組kE1(,.),.,.myy 序列密碼序列密碼也稱為流密碼（Stream Cipher ） [9]，具有實(shí)現(xiàn)簡單、加解密速度快、幾乎沒用錯誤傳播的特點(diǎn)，所以其在專用或機(jī)密機(jī)構(gòu)中有很大的優(yōu)勢，其應(yīng)用領(lǐng)域主要包括無線通信、外交通信。涉及設(shè)備濫用的攻擊必須通過良好的管理或使用適當(dāng)?shù)姆来鄹脑O(shè)備進(jìn)行防御。因?yàn)殡p鑰密碼體制的特點(diǎn)是將加解密的密鑰分開，同時也就將加解密能力分開了，因此它既可用于在公共網(wǎng)絡(luò)中實(shí)現(xiàn)保密通信，也可以用于認(rèn)證系統(tǒng)中進(jìn)行發(fā)送者的身份確認(rèn)。 密碼體制的分類根據(jù)不同的標(biāo)準(zhǔn)，密碼體制有不同的分類。經(jīng)過加密的消息稱為密文，加密該消息的編碼工具被稱為編碼器，而他們發(fā)送密碼電文的對象被稱為接收器。 本文研究的主要內(nèi)容本文著重討論布爾函數(shù)的密碼學(xué)性質(zhì)及其在密碼學(xué)中應(yīng)用，主要內(nèi)容安排如下：① 主要介紹布爾函數(shù)的研究背景和意義，以及國內(nèi)外的研究現(xiàn)狀。相關(guān)免疫性作為布爾函數(shù)的一種統(tǒng)計性質(zhì)，在布爾函數(shù)的研究中有著重要意義，它首先由 Tsiegenthaler 于 1984 年在研究流密碼系統(tǒng)安全性時提出。所以，為保障信息來源的完整性可靠性，必須有效地構(gòu)造具有良好的加密特性的布爾函數(shù)。從第二次世界大戰(zhàn)以來，密碼學(xué)理論和技術(shù)的應(yīng)用已經(jīng)不在局限于某個領(lǐng)域，不僅涵蓋了軍事、國防和金融，而且包含了政府、文教和商業(yè)的各個領(lǐng)域 [1]。文中首先介紹了布爾函數(shù)的研究背景、重要性及國內(nèi)外研究現(xiàn)狀，并概述了密碼學(xué)相關(guān)的基礎(chǔ)知識，給出了布爾函數(shù)的定義，對其各種表示方法和研究方法進(jìn)行介紹，主要介紹了真值表，小項表示等。其次討論了布爾函數(shù)的幾個密碼學(xué)性質(zhì)和定理，重點(diǎn)介紹了作為布爾函數(shù)研究的一個重要工具——Walsh 譜，并介紹了布爾函數(shù)的密碼學(xué)性質(zhì)，主要包括非線性、平衡性、相關(guān)免疫和嚴(yán)格雪崩等。而現(xiàn)在，現(xiàn)代密碼理論及其技術(shù)已與個人信息保密與否密切相關(guān)，這也就為密碼學(xué)理論及其技術(shù)的應(yīng)用和研究提供了極為廣闊的前景。人們已經(jīng)對布爾函數(shù)的研究比較多的有高非線性，平衡性，對稱性，擴(kuò)散性，相關(guān)免疫性和嚴(yán)格雪崩等特性，并且碩果累累，但要達(dá)到人們對信息保密程度的要求仍還有很多工作要做。我國密碼學(xué)研究的代表人物肖教授發(fā)現(xiàn)了 bent 函數(shù)具有一個非常重要的性質(zhì)：函數(shù)的相關(guān)免疫階與非線性次數(shù)之間此消彼長，相互矛盾。② 主要介紹與密碼學(xué)相關(guān)的概念以及密碼體制和布爾函數(shù)的表示方法和研究方法。使用該編碼器來加密明文的一組規(guī)則稱為加密算法。 私鑰密碼體制和公鑰密碼體制 [1]根據(jù)密碼系統(tǒng)密鑰的特點(diǎn)，密碼體制可以分為私鑰密碼體制和公鑰密碼體制，而私鑰密碼體制又稱對稱密碼體制或單鑰密碼體制，公鑰密碼體制則又稱為非對稱密碼體制或雙鑰密碼體制。公鑰密碼體制相對于私鑰體制對通訊環(huán)境的安全性要求較弱，因而其應(yīng)用領(lǐng)域較廣，但是其運(yùn)行速度較慢 [8]。 ） 。只有一次一密的密碼體制是不可能被破譯的，這一結(jié)論于 1949 年已被香農(nóng)（Shannon）證明，這極大的支持了流密碼的研究，序列密碼方案的研究過程便是對一次一密系統(tǒng)的嘗試，或者說“一次一密”的密碼只是序列密碼的入門。然后，一個 元布爾函數(shù)被定義為一個從 到 的映射。 真值表 任何 元布爾函數(shù)可以被表示為一個 長度的二進(jìn)制向量，這就nn2是所謂的真值表：, （221 ）)1,()0,1(),0( ， ?????fff也稱為 的函數(shù)值向量，記為 [4]。2? Walsh 譜表示設(shè) ， ， 與 的點(diǎn)積定義為1(,.)nx1(,.)nw?2F??2則 元布爾函數(shù) 的 Walsh 變換定義為nf （225 ）20()()nwxfxSf???A其逆變換為 （226 ） 210()()nwxfxf??A（ ）稱為 的 Walsh 譜。 布爾函數(shù)的研究方法布爾函數(shù)有不同的表示方法 [10]，而不同的表示方法在不同的研究中有其各自的優(yōu)勢，所以我們要根據(jù)不同的表示方法采用不同的研究方法，以便更好地展開研究，目前主流的研究方法有以下幾種。人們對不同種類的布爾函數(shù)的研究歸結(jié)為對布爾函數(shù)某種性質(zhì)的研究。 是展210()nwxfxfS???A)(xf )(Sf開式的系數(shù)，即 Walsh 譜。記 {全f ?E天津科技大學(xué) 2022 屆本科生畢業(yè)論文11體線性結(jié)構(gòu)}，則 是 的一個線性子空間，若該子空間的維數(shù)為正，即EnF2，則稱 是一個線性結(jié)構(gòu)函數(shù) [10]。f }0{??E推論：II 型線性結(jié)構(gòu)函數(shù)是不可退化的。 ，即 的線性度為其與所有線性函數(shù)的最長距離。定義 設(shè) 是 個彼此獨(dú)立且對稱的 元隨機(jī)變量的布),.()1nxfx?2爾函數(shù)，當(dāng)且僅當(dāng) 與 中的 個隨機(jī)變量統(tǒng)計獨(dú)立，即當(dāng)且僅當(dāng)互信f息 [13] （341 ）1()。ix1定理 布爾函數(shù) 對自變量 是線性的，當(dāng)且僅當(dāng)對任),.)nf i意 有1,.n （352 ）1(,..,ifx?1(,..,)infx其中 的取值為 0 或 1， ， ， 。()fx差分均勻函數(shù)有 個輸入 個輸出，任意若干個輸入位發(fā)生改變，導(dǎo)致輸出1發(fā)生變化的概率為 ，滿足這種差分均勻性的函數(shù)為 Bent 函數(shù)。天津科技大學(xué) 2022 屆本科生畢業(yè)論文14布爾函數(shù)的密碼學(xué)性質(zhì)除了以上討論的非線性、平衡性、相關(guān)免疫性、嚴(yán)格雪崩和擴(kuò)散準(zhǔn)則等外，還有退化性、線性結(jié)構(gòu)等 [12]。c在序列密碼系統(tǒng)中，因?yàn)槊魑男蛄信c密鑰流逐位加密，所以密鑰流的長度必須與明文序列的長度相等，但這樣的序列卻難于管理和分配，所以實(shí)際中的密鑰序列均由密鑰空間中較短的密鑰經(jīng)過某些算法生成的 [1]。其包含了相關(guān)免疫性，線性復(fù)雜度和不可預(yù)測性等很多序列密碼研究過程中的主要問題。在二元域下，非線性組合部分可以用一個布爾函數(shù)來表示，所以對密鑰流生成器的研究也就歸結(jié)為對布爾函數(shù)的研究 [12]。1,.g定義 序列 是周期序列，若存在正整數(shù) 使得{}iaT， （434 ）iTi?,2.滿足（）式的最小正整數(shù) 稱為序列 的周期。T()QxT?T當(dāng) 上的 級 LFSR 產(chǎn)生的序列 的周期為 時，稱序列 為2Fn{}iaTn??i級 序列。12n?1n?② 在一個周期圈內(nèi)，總游程數(shù)為 ，對 ，長為 的游程數(shù)為2i?i個，且 0 游程和 1 游程各一半，長為 的 0 游程有一個，長為 的 1 游12ni? n程 1 個 [10]。對全零序列 ，約定 。② 高代數(shù)次數(shù)在第 2 章我們定義了布爾函數(shù)的代數(shù)次數(shù)，得知布爾函數(shù)的線性復(fù)雜度依賴于布爾函數(shù)的代數(shù)次數(shù)，而較高的線性復(fù)雜度是密鑰流序列的基礎(chǔ)。()fxBent函數(shù)乃非線性度最高的函數(shù)，但是Bent函數(shù)的缺陷就是不平衡性，因此人們設(shè)計時只要求譜值比較均勻。一般原則是首先保證最重要的指標(biāo)達(dá)到一定強(qiáng)度的條件下，其余的指標(biāo)盡可能高。上世紀(jì) 70 年代沒過數(shù)據(jù)加密標(biāo)準(zhǔn) DES 的出臺標(biāo)志著現(xiàn)代分組密碼學(xué)的開始，分組密碼因?yàn)槠涔逃械奶攸c(diǎn)而成為標(biāo)準(zhǔn)化進(jìn)程的首選體制。② 已 知 明 文 攻 擊，攻擊者獲得當(dāng)前密鑰下的某些明文和對應(yīng)的密文。復(fù)雜度表示實(shí)施該攻擊所需的平均運(yùn)算次數(shù)?；?亂 和 擴(kuò) 散混亂的目的是使明文和密文的統(tǒng)計學(xué)特性的關(guān)系趨向復(fù)雜化。每 64 位明文加密成 64 位密文，沒有數(shù)據(jù)壓縮和擴(kuò)展，密鑰長度為 56bits，若輸入 64bits，則第 8，…… 64 是奇偶校驗(yàn)位，所以實(shí)際密鑰只有 56 位 [17]。對置換后的 分成左右兩部分，左邊記為 ,右邊記為 。 和 是第 次迭代結(jié)果的左右兩個部分，每輪變換全部相1?同，只是數(shù)據(jù)不同，這里 稱為 DES 的 函數(shù)，其中 為 32 位輸入，(,)fAJfA為 48 位輸入，在第 輪 ， ， 為由 64 位的初始密鑰（也稱種子Ji?1iiki密鑰）導(dǎo)出的第 輪子密鑰。如果給定該 盒的輸?入為 ，其輸出對應(yīng)該矩陣的第 行、 列所對應(yīng)數(shù)的二進(jìn)制表示。如此一來，每個 盒均L05bn1234bS可用一個 4 16 矩陣或數(shù)表來表示 [10]。,f的計算過程如下 [10]：(,)fA將 經(jīng)過一個擴(kuò)展運(yùn)算 （如圖 55）后為 48 位，記為 。再對1,LR0, 2,LR16,LR64 位數(shù)字 進(jìn)行初始置換的逆變換 （圖 54） ，即得密文 。實(shí)際上密鑰只用了56 位，這樣更安全。也就是說，分組密碼應(yīng)該設(shè)計成明文的每個比特和密鑰的每個比特對密文的每個比特都產(chǎn)生影響。在不知道密鑰的情況下，可以通過采用窮搜索進(jìn)行攻擊，所以，如果一個分組密碼只能使用窮搜索，那它就是安全的。當(dāng)一個密碼體制對一個擁有無限計算機(jī)資源的攻擊者來說也是安全的，則該系統(tǒng)絕對安全，同時說明破譯該密碼是不可能的。 加密算法 明文 1(,.)nx密鑰 K密文 1(,.)ny天津科技大學(xué) 2022 屆本科生畢業(yè)論文22 分組密碼的安全性如前所述，現(xiàn)代分組密碼算法的安全性取決于密鑰的安全性。流密碼是逐比特加密，而分組密碼則是將明文消息序列 12,.,.km分成等長的消息組（ ） ，,.n12(,.),.nn?在密鑰控制下按一定的算法 一組組加密，加密后輸出的等長密文組kE1(,.),.,.myy可用圖 51 來表示 [10]。④ 相關(guān)免疫性為了抵抗相關(guān)攻擊，系統(tǒng)中的布爾函數(shù)必須滿足相關(guān)免疫性。則稱)(xfn][xLn][mixLln?),(lfd][ixln??)(lfw?