【正文】 ???????????????????????????306 結(jié)論 ??????????????????????????????????????????????????????????????????????????????????????????????????????31參考文獻(xiàn) ??????????????????????????????????????????????????????????????????????????????????????????????????36致 謝 ??????????????????????????????????????????????????????????????????????????????????????????????????????37天津科技大學(xué) 2022 屆本科生畢業(yè)論文01 前言 背景和意義在信息技術(shù)飛速發(fā)展的今天，網(wǎng)絡(luò)數(shù)據(jù)的傳輸和共享越來(lái)越復(fù)雜，信息傳遞過(guò)程中的安全性越來(lái)越被人們所重視，這在某種程度上推動(dòng)了人們對(duì)現(xiàn)代密碼學(xué)的研究。序列密碼體制的安全性取決于密鑰流，而密鑰流序列由密鑰流生成器產(chǎn)生，在密鑰流生成器中，布爾函數(shù)起著極其關(guān)鍵的作用。本文是一篇關(guān)于布爾函數(shù)的密碼學(xué)性質(zhì)及其應(yīng)用的文章。最主要的原因是布爾函數(shù)的密碼學(xué)性質(zhì)在某種程度上直接決定系統(tǒng)的安全性。最后重點(diǎn)研究了布爾函數(shù)在流密碼和分組密碼中的應(yīng)用。 block cipher； key stream generators； Sbox； Boolean function。當(dāng)消息通過(guò)開(kāi)放的網(wǎng)絡(luò)發(fā)布時(shí)，可能沒(méi)有任何保密的必要，但用戶可能需要確保收到的消息在傳輸過(guò)程中尚未改變。無(wú)論是單輸出布爾函數(shù)還是多輸出布爾函數(shù)，都在密碼算法的設(shè)計(jì)與分析中起有很大的作用，如序列密碼中常用的密鑰流生成器，既有非線性組合生成器也有非線性濾波生成器，顯然對(duì)這些生成器的分析也可歸結(jié)到對(duì)布爾函數(shù)的分析?？傊?，布爾函數(shù)在密碼學(xué)中的研究不僅具有理論價(jià)值，而且具有使用價(jià)值。在1976年，Rothaus 證明了 元布爾函數(shù)的非線性度是 ，這里n1n/2?是偶數(shù) [2]。通過(guò)降低對(duì)相關(guān)免疫性的要求，可以在非線性次數(shù)跟相關(guān)免疫階之間找到某個(gè)平衡點(diǎn)，由此提出了廣義相關(guān)免疫函數(shù)。如 XL 算法等有效算法的出現(xiàn)，解決了被過(guò)度定義的多元代數(shù)方程的系統(tǒng)，代數(shù)攻擊成功地破譯出如 Toyocrypt 和 LILI128 等比較有名的序列密碼 [6]。③ 主要介紹布爾函數(shù)的密碼學(xué)性質(zhì)，主要有非線性、相關(guān)免疫性和嚴(yán)格雪崩等④ 主要介紹布爾函數(shù)在序列密碼中的應(yīng)用，如密鑰流生成器中的位移寄存器序列。密碼系統(tǒng)的思想是以某種方式偽裝機(jī)密信息，而該方式的含義對(duì)于那些未經(jīng)授權(quán)的人來(lái)說(shuō)是難以理解的 [8]。通常，該算法的操作將依賴于一個(gè)加密密鑰 ，其中該編碼器將加密密鑰連同消息一起輸入到算法中。 加密算法 解密算法加密密鑰 解密密鑰信息 信息密碼電文天津科技大學(xué) 2022 屆本科生畢業(yè)論文3通過(guò)以上介紹可以得出：從密文獲得消息時(shí)，加密密鑰是不重要的。 私鑰密碼體制對(duì)于私鑰密碼體制主要研究的問(wèn)題是怎么生成滿足要求的密鑰流。 公鑰密碼體制1976 年，赫爾曼（Hellman）和狄菲（Diffie ）在其發(fā)表的“密碼學(xué)的新方向”中提出了公鑰密碼體制的概念。而私鑰密碼體制正好相反，機(jī)構(gòu)簡(jiǎn)單，速度快，其運(yùn)行速度是公鑰密碼體制的成百上千倍。一個(gè)是在取得相關(guān)的密鑰。另一個(gè)是對(duì)方攻擊打算替換公鑰。 序列密碼和分組密碼根據(jù)明文消息加密方式和實(shí)現(xiàn)形式的不同，我們將密碼體制分為流密碼和分組密碼。如果序列密碼所使用的密鑰并非偽隨機(jī)方式產(chǎn)生的、并與消息流長(zhǎng)度相同，那么此時(shí)的序列密碼即一次一密的密碼體制。所以密碼學(xué)研究的始終，一直伴隨著對(duì)布爾函數(shù)的研究。所有 元布爾函n2數(shù)的集合表示為 。如f 2??1記為 ， 記為 ；但有時(shí)仍用 記 。1在真值表中的個(gè)數(shù)稱被為 的漢明重量，)(xf?f記為 或 ，如果它的真值表有相等數(shù)目的 1和0，我們說(shuō) 是平衡的，這wf意味著若， = ，此時(shí)則稱 為平衡布爾函數(shù)。0ai?21Fn??2)(iiaF2?ni這就是所謂的代數(shù)范式（ANF） 。此式亦即 的 Walsh 譜表示。若 ，則稱 為)(xfnnFx2?1)(?xfx的一個(gè)特征向量，記 的全體特征向量的集合為 ，)(xf D}.1)(|{afD?w將 中的 個(gè)向量按字典順序從大到小排列，記第 個(gè)向量 ， ，則稱Dwiiw?10,1 矩陣 ??????wnwncc...212112為 的特征矩陣，記為 ，或簡(jiǎn)記為 [11]。 代數(shù)分析方法任何可以表示為多項(xiàng)式形式的函數(shù)都可以使用代數(shù)方法進(jìn)行分析，顯然，布爾函數(shù)也不例外。n2Fnw?)21(n? 重量分析方法對(duì)任意兩個(gè)布爾函數(shù) 和 ，定義 和),.()1nxfx?),.(1nxg?)(xf的距離為)(xg f?記為 ，即,fd),(gfd?)(fw對(duì)和函數(shù)的重量有如下關(guān)系式： （231 ）f?f)(2fg?重量分析方法是通過(guò)分析布爾函數(shù)的重量特征來(lái)研究布爾函數(shù)的方法，這種方法簡(jiǎn)單易懂，很適合工程應(yīng)用。本章著重介紹布爾函數(shù)的一些重要性質(zhì)。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ù)系。還有另外一種展開(kāi)式：)(f （313 ）)(xf?)(210)(xQwSfn???其中 （314 ）)()1()(20xSwwfnf??天津科技大學(xué) 2022 屆本科生畢業(yè)論文10為了區(qū)別，將 稱為 的第一種 Walsh 譜或線性譜，而將 稱為)(wSf )(xf )(wSf的第二種 Walsh 譜或循環(huán)譜。??????nbiibncl11),.( ,2??Fni定義 設(shè) 是 元布爾函數(shù)， ，稱 為 的一個(gè)線性結(jié)構(gòu)，)xf a)(xf則對(duì)任意 ， 為常數(shù)。0?Dim)(xf記 }0)((|{0 ????xfafE11則有如下性質(zhì)：① , ；??10E?0?② 是 的子空間；?③ 若 ，則 ；11,Ea?④ 設(shè) ，若 ，則 ， 。該性質(zhì)稱為與變?cè)獰o(wú)關(guān)性，最初稱與變?cè)獰o(wú)關(guān)性為退化，定義)(fi如下：定義 設(shè) ，若存在 上的 矩陣 ,使得)(xf),.1nxf nF2k?)(n?D),.((1ygD?則稱 是退化的。定理 是部分線性的，則 是退化的。定義 設(shè) 是 元一個(gè)布爾函數(shù)，記 為所有 元線性函數(shù)之集。)(xf fC)(f由定義 可知，對(duì)任意 元布爾函數(shù) 有n)(xf （333 ）fN?fCn2?定義 設(shè) 是 元一個(gè)布爾函數(shù)，若比值函數(shù) 滿足)(xf 12/)(??nfNq，則稱布爾函數(shù) 具有高非線性度。()fx()fxi定義 設(shè)布爾函數(shù) ： ，對(duì)于任意給定的 ，()f2nF2,naF?且 0?對(duì)任意的 ，如果 恒為常數(shù)，那么稱 為 的一個(gè)線性結(jié)2nF?a?()f構(gòu)。,.)0miiIf?時(shí)，稱 為 階相關(guān)免疫函數(shù)。CIIm 布爾函數(shù)的平衡性我們?cè)? 節(jié)定義了平衡布爾函數(shù)： = ，即 的真值表中 0()wf12?n()fx和 1 的個(gè)數(shù)相等。ix?i?fA 布爾函數(shù)的對(duì)稱性定義 設(shè) 是 元布爾函數(shù)，如果對(duì)任意 階置換矩陣 有()fxn P （361 ）()fxP?則稱 是對(duì)稱函數(shù)。定義 若對(duì)任意 ， ，總有 是平衡函數(shù)，2naF?()1w?())fxa?則稱 滿足嚴(yán)格雪崩準(zhǔn)則。函數(shù)滿足最/大非線性性等價(jià)于函數(shù)滿足差分分布均勻 [12]。 階 次擴(kuò)散準(zhǔn)則就是 次擴(kuò)散準(zhǔn)則。天津科技大學(xué) 2022 屆本科生畢業(yè)論文154 序列密碼與布爾函數(shù)在第 2 章我們已經(jīng)簡(jiǎn)單提到過(guò)序列密碼。所以我們假設(shè)序列密碼中的密文空間，密鑰空間和明文空間均為二進(jìn)制序列組成的集合[14]。當(dāng)密鑰流序列是完全隨機(jī)序列時(shí)（一次一密鑰） ，該系統(tǒng)是不可破的，稱之為完全保密系統(tǒng)。為了使密鑰流滿足密碼體制要求的安全性，避免遭受某些攻擊，密鑰流應(yīng)當(dāng)具備一定的偽隨機(jī)性，信道密文 0,1 序列天津科技大學(xué) 2022 屆本科生畢業(yè)論文16所以我們對(duì)密鑰流的偽隨機(jī)性提出了如下要求：① 盡可能大的周期。第四條則主要是根據(jù)密鑰流生成器的實(shí)用性考慮而提出的。密鑰流生成器通常由一個(gè)線性位移寄存器（LFSR）和非線性組合函數(shù)（布爾函數(shù)）組成。 位移寄存器位移寄存器是密鑰流生成器中不可缺少的一部分，反饋位移寄存器圖 42所示。將每個(gè)狀態(tài)看成狀態(tài)空間中fT01(,.)nx?的一個(gè)點(diǎn)，按狀態(tài)轉(zhuǎn)移關(guān)系，若從狀態(tài) 轉(zhuǎn)移到狀態(tài) ，就在狀態(tài) 和 之i 1iS?iS1i?間連一邊： ，則得位移寄存器的狀態(tài)轉(zhuǎn)換圖，簡(jiǎn)稱狀態(tài)圖。若存在 使 ，{}ia0a0n是周期序列，則稱序列 是終歸周期。長(zhǎng)為 的 0 游程和 1 游程各 1 個(gè)。為了描述 序列，下面引進(jìn)有限域上的跡函數(shù)。()mx定理 設(shè) 是 中的一個(gè)本原元， ，則序列a2n 2n??是以 為極小多項(xiàng)式的 級(jí) 序列，且 產(chǎn)生的所有序{}i?1}niTr?()a m()ax列均可表示為 ， [10]。③ 的自相關(guān)函數(shù)為二值：{}ia （4310 ）()aR??11=0T????????， 當(dāng) 時(shí)， 當(dāng) 時(shí)由定理 可見(jiàn)， 序列具有良好的隨機(jī)統(tǒng)計(jì)特性。對(duì)于一個(gè)長(zhǎng)為 的序列 ， ，顯然它可以被一個(gè) 級(jí)的N0a?1,.Na?NLFSR 產(chǎn)生，只要取 即可。q 0?序列線性復(fù)雜度的概念具有重要的密碼學(xué)意義。由于 序列有理想的隨機(jī)統(tǒng)計(jì)性，并且滿足 Golomb 隨機(jī)性公m設(shè)，所以它通常作為密鑰流序列產(chǎn)生器的基本單元，再通過(guò)非線性濾波器或非線性組合而成為密鑰流序列。③ 高非線性度設(shè) 是 元一個(gè)布爾函數(shù)，記 為所有 元線性函數(shù)之集。如l天津科技大學(xué) 2022 屆本科生畢業(yè)論文20果用譜值的觀點(diǎn)來(lái)看, 它反映了譜值的絕對(duì)值的最大值的大小, 當(dāng)然這個(gè)值越小越好, 也就是說(shuō)非線性度越大越好。由于譜值均勻和高非線性度是一致的，因此本文中我們沿用人們一直以來(lái)的術(shù)語(yǔ)——高非線性。以上根據(jù)現(xiàn)有攻擊以及對(duì)密鑰流序列的基本要求提出的準(zhǔn)則都只是必要而非充分的。天津科技大學(xué) 2022 屆本科生畢業(yè)論文215 分組密碼與布爾函數(shù) 分組密碼概述 分組密碼的原理在 節(jié)我們談到，密碼體制根據(jù)加密方式的不同，分為分組密碼和流密碼。 為明文分組長(zhǎng)度，當(dāng) 時(shí)，稱之為有數(shù)據(jù)壓縮的2tF?分組密碼；當(dāng) ， ；通常研究 時(shí)，亦即nm?稱 之 為 有 數(shù) 據(jù) 擴(kuò) 展 的 分 組 密 碼 n?分組密碼的研究就是研究從明文組 到密文組 的變1(,.)nx1(,.)y換規(guī)則。DES 算法作為數(shù)據(jù)加密標(biāo)準(zhǔn)，完全公開(kāi)，任何組織和個(gè)人都能使用，其信息安全依賴于各自密鑰的安全性，這就是現(xiàn)代分組密碼的特征。此外，安全性也與攻擊者擁有的計(jì)算機(jī)能力相關(guān)，因此，攻擊者擁有的信息越多，計(jì)算機(jī)能力越強(qiáng)，安全性越不可靠 [12]。 ③ 選 擇 明 文 攻 擊如果一個(gè)密碼能抵制選擇明文攻擊，一定能抵制其他兩種攻擊。人們通常只追求計(jì)算上的安全性，而計(jì)算上的安全性乃一相對(duì)概念，取決于攻擊者的計(jì)算能力和攻擊方式。對(duì)一個(gè)密碼安全性的評(píng)估，是根據(jù)已知的關(guān)于該密碼的最佳攻擊方法的復(fù)雜度，復(fù)雜度越高越安全。 分組密碼的設(shè)計(jì)原則通常比較好的分組密碼應(yīng)該既難破譯又易于實(shí)現(xiàn)，人們基于難破譯的要求提出分組密碼算法需遵循如下基本原則：① ，確保實(shí)施 次加密在計(jì)算上是不可能的，從而防止 分 組 長(zhǎng) 度 應(yīng) 足 夠 大 2n明文遭受窮搜索攻擊。天津科技大學(xué) 2022 屆本科生畢業(yè)論文23擴(kuò)散性是通過(guò)將每個(gè)明文數(shù)字的影響迅速擴(kuò)散到多個(gè)輸出的密文數(shù)字中，從而來(lái)隱蔽明文數(shù)字的統(tǒng)計(jì)學(xué)特性，通過(guò)將密鑰的每個(gè)數(shù)字盡量擴(kuò)散到更多密文數(shù)字中，以此防止對(duì)密鑰進(jìn)行逐段破譯 [13]。 算法描述DES( Data Encryption Standard ) 算法是 1972 年由美國(guó) IBM 公司研究的對(duì)稱密碼體制加密算法，于 1977 年獲得美國(guó)政府的正式許可，因此又被稱為美國(guó)數(shù)據(jù)加密標(biāo)準(zhǔn)。DES 工作的基本原理是：加密時(shí)，明文按 64 位進(jìn)行分組，形成明文組，加密密鑰對(duì)數(shù)據(jù)加密，解密時(shí)，解密密鑰于對(duì)數(shù)據(jù)解密 [17]。在 DES 算法中，將 56 位的密鑰和分組后的 64 位明文組按替代或交換的方法形成密文組，即用 56 位密鑰來(lái)加密 64 位數(shù)據(jù)，其密鑰的長(zhǎng)度為 56位，明文則按 64 位來(lái)進(jìn)行分組 [17]。對(duì) 施行在密x0L0R0鑰控制下的變換 ，結(jié)果記為 ,令f01()fRK，L??1(,)fK， （521 ）ii?1ii?ii?天津科技大學(xué) 2022 屆本科生畢業(yè)論文25對(duì) 施行和 同樣的過(guò)程得 ，如此循環(huán) 16 次得 。初始置換 及其逆置換 其實(shí)毫無(wú)密碼學(xué)意義，這是由于置換前后其二IP1I?者一一對(duì)應(yīng)關(guān)系是已知的。 為 32 位數(shù)字。在 輪為 ， 可CP(,)fAJi(,)iifRK?(,)fAJ用圖 57 表示。這012345bLn里 的二進(jìn)制表示為 ， 的二進(jìn)制表