【正文】 為差分均勻函數(shù)。函數(shù)滿足最/大非線性性等價(jià)于函數(shù)滿足差分分布均勻 [12]。若對(duì)任意滿足n1()()2wfxa???()fxa的 ， 關(guān)于 滿足擴(kuò)散準(zhǔn)則，則稱 滿足 次擴(kuò)散準(zhǔn)則。 階 次擴(kuò)散準(zhǔn)則就是 次擴(kuò)散準(zhǔn)則。k在本章中，我們簡(jiǎn)要介紹了布爾函數(shù)的一些密碼學(xué)特性及一些簡(jiǎn)單結(jié)論。天津科技大學(xué) 2022 屆本科生畢業(yè)論文154 序列密碼與布爾函數(shù)在第 2 章我們已經(jīng)簡(jiǎn)單提到過(guò)序列密碼。在密鑰流生成器中，布爾函數(shù)起著極其關(guān)鍵的作用，所以本章著重討論布爾函數(shù)在流密碼中的應(yīng)用，對(duì)這些生成器我們并不一一介紹。所以我們假設(shè)序列密碼中的密文空間，密鑰空間和明文空間均為二進(jìn)制序列組成的集合[14]。 明文 0,1 序列 恢復(fù)的明文 0,1 序列 信源 加密器 解密器 信宿圖 41 保密通信模型在序列密碼中，序列密碼將明文消息序列 用密鑰流序列12,.m?逐位加密，通過(guò)加密變換 （通常采用二元加法運(yùn)算）得到密文序12,.k?kE列 ，因此密碼系統(tǒng)的安全性主要取決于密鑰流序列的性能。當(dāng)密鑰流序列是完全隨機(jī)序列時(shí)（一次一密鑰） ，該系統(tǒng)是不可破的，稱之為完全保密系統(tǒng)。 序列密碼對(duì)密鑰流的要求設(shè)計(jì)序列密碼的目的是為了設(shè)計(jì)一個(gè)能產(chǎn)生具有完全隨機(jī)性的密鑰流序列生成器，而我們知道，完全隨機(jī)是不可能的，所以通常主要從周期性、隨機(jī)統(tǒng)計(jì)性和不可預(yù)測(cè)性等不同角度去衡量密鑰流序列的安全性 [10]。為了使密鑰流滿足密碼體制要求的安全性，避免遭受某些攻擊，密鑰流應(yīng)當(dāng)具備一定的偽隨機(jī)性，信道密文 0,1 序列天津科技大學(xué) 2022 屆本科生畢業(yè)論文16所以我們對(duì)密鑰流的偽隨機(jī)性提出了如下要求：① 盡可能大的周期。上述要求的前兩條是為了擾亂或有效的掩蓋明文序列的統(tǒng)計(jì)隨機(jī)性，第三條是序列密碼理論的核心，決定密碼的強(qiáng)度。第四條則主要是根據(jù)密鑰流生成器的實(shí)用性考慮而提出的。 密鑰流生成器上一節(jié)我們討論了序列密碼對(duì)密鑰流的要求，一般安全性要求越高，實(shí)現(xiàn)和設(shè)計(jì)也就越復(fù)雜，因此在密鑰流生成器的設(shè)計(jì)中，除了考慮上面討論的四種要求，還應(yīng)考慮如下因素 [9]:① 密鑰 易于分配、保管和更換；k② 易于實(shí)現(xiàn)、快速 [10]。密鑰流生成器通常由一個(gè)線性位移寄存器（LFSR）和非線性組合函數(shù)（布爾函數(shù)）組成。因?yàn)轵?qū)動(dòng)部分的設(shè)計(jì)相對(duì)更容易，因此非線性組合部分的設(shè)計(jì)便成為研究密鑰流生成器的重點(diǎn)和難點(diǎn)。 位移寄存器位移寄存器是密鑰流生成器中不可缺少的一部分，反饋位移寄存器圖 42所示。 稱為反饋函數(shù)（二元 時(shí)是布爾函數(shù)） ，有時(shí)也直接稱01(,.)fx? ()fx為 級(jí)位移寄存器， 稱為初始狀態(tài)。將每個(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)圖。定理 上的一個(gè) 級(jí)位移寄存器是非奇異的，當(dāng)且僅當(dāng)反饋函數(shù)2Fn可表示為01(,.)nfx? （433 ）01(,.)nfx?0x??1(,.)ngx?其中 是與 無(wú)關(guān)的 元布爾函數(shù)。若存在 使 ，{}ia0a0n是周期序列，則稱序列 是終歸周期。定義 上 級(jí)位移寄存器產(chǎn)生的周期為 的序列稱為 級(jí) 序列。長(zhǎng)為 的 0 游程和 1 游程各 1 個(gè)。2 12n定理 設(shè)序列 的極小多項(xiàng)式為 ， ，則序列 的周期{}ia()Qx?{}ia是 整除 的最小正整數(shù) ，即 的階。為了描述 序列，下面引進(jìn)有限域上的跡函數(shù)。2q?定理 到 上的跡函數(shù) 有如下性質(zhì)：nqF1()nr① 對(duì)任何 ， ，有,???,quvF （436 ）T????1()nuT?1()nvr?② 當(dāng) 看作 上的 維線性空間時(shí)， 是從 到 上的線性變換。()mx定理 設(shè) 是 中的一個(gè)本原元， ，則序列a2n 2n??是以 為極小多項(xiàng)式的 級(jí) 序列，且 產(chǎn)生的所有序{}i?1}niTr?()a m()ax列均可表示為 ， [10]。{}ia??對(duì)獨(dú)立均勻分布的二進(jìn)隨機(jī)變量序列 ，它的自相關(guān)函數(shù) 的期望值為{}iX()xR? （439 ）[()]xER??01=?????， 當(dāng) 時(shí)， 當(dāng) 時(shí)定理 上的 級(jí) 序列 具有如下性質(zhì) [15]：2Fnm{}ia① 在一個(gè)周期內(nèi)，0,1 出現(xiàn)之次數(shù)分別為 ， 。③ 的自相關(guān)函數(shù)為二值：{}ia （4310 ）()aR??11=0T????????， 當(dāng) 時(shí)， 當(dāng) 時(shí)由定理 可見， 序列具有良好的隨機(jī)統(tǒng)計(jì)特性。天津科技大學(xué) 2022 屆本科生畢業(yè)論文19Golomb 對(duì)偽隨機(jī)周期序列提出了如下隨機(jī)性公設(shè)：； 011① 在 序 列 的 一 個(gè) 周 期 內(nèi) ， 與 的 個(gè) 數(shù) 之 差 最 多 為② 在 序 列 的 一 個(gè) 周 期 圈 內(nèi) ， 長(zhǎng) 為 的 游 程 數(shù) 占 總 游 程 數(shù) 的 ， 2長(zhǎng) 為 的 游 程 數(shù) 占總游程數(shù)的 ，總 游 程 數(shù) 的 ， 長(zhǎng) 度 為 的 游 程 數(shù) 占 /2i…， ，0，1 游程各占一半；且 在 等 長(zhǎng) 的 游 程 中但很少有偽隨機(jī)序列能嚴(yán)格滿足如上公設(shè)。對(duì)于一個(gè)長(zhǎng)為 的序列 ， ，顯然它可以被一個(gè) 級(jí)的N0a?1,.Na?NLFSR 產(chǎn)生，只要取 即可。()Nfx?定義 上的序列 ， 的線性復(fù)雜度 定義為產(chǎn)生該qF1,. ()Ca序列的 上級(jí)數(shù)最少的 LFSR 的級(jí)數(shù)。q 0?序列線性復(fù)雜度的概念具有重要的密碼學(xué)意義。{}i由定理 可見，線性復(fù)雜度是序列線性預(yù)測(cè)性的一個(gè)指標(biāo) [10]，若其線性復(fù)雜度很小，是不安全的。由于 序列有理想的隨機(jī)統(tǒng)計(jì)性，并且滿足 Golomb 隨機(jī)性公m設(shè)，所以它通常作為密鑰流序列產(chǎn)生器的基本單元，再通過(guò)非線性濾波器或非線性組合而成為密鑰流序列。布爾函數(shù)只有滿足一定的設(shè)計(jì)準(zhǔn)則，才能保證系統(tǒng)符合安全性的基本要求并可以抵抗現(xiàn)有的攻擊 從而保證系統(tǒng)的安全，為，此對(duì)流密碼中的布爾函數(shù)提出如下準(zhǔn)則，概括起來(lái)如下 [12]：① 平衡性平衡性即是為保證輸出的密鑰流序列具有良好統(tǒng)計(jì)特性而對(duì)布爾函數(shù)提出的準(zhǔn)則。③ 高非線性度設(shè) 是 元一個(gè)布爾函數(shù)，記 為所有 元線性函數(shù)之集。其中 為所有仿射函數(shù)。如l天津科技大學(xué) 2022 屆本科生畢業(yè)論文20果用譜值的觀點(diǎn)來(lái)看, 它反映了譜值的絕對(duì)值的最大值的大小, 當(dāng)然這個(gè)值越小越好, 也就是說(shuō)非線性度越大越好。12/)(??nfNqlim1xq???(x)f對(duì)任意 元布爾函數(shù) ，當(dāng)其非線性度 時(shí)，f 1/2nfN??， ，顯然布爾函數(shù)滿足高非線性度，此時(shí)，我們稱/li()x為 Bent 函數(shù)。由于譜值均勻和高非線性度是一致的，因此本文中我們沿用人們一直以來(lái)的術(shù)語(yǔ)——高非線性。⑤非退化性文獻(xiàn)中研究相關(guān)免疫的退化性時(shí)指出，退化函數(shù)可以用與其等價(jià)的非線性組合函數(shù)替代，如果替代的組合函數(shù)不再具有相關(guān)免疫性，則攻擊方法仍然有效。以上根據(jù)現(xiàn)有攻擊以及對(duì)密鑰流序列的基本要求提出的準(zhǔn)則都只是必要而非充分的。所以要求同時(shí)滿足多個(gè)準(zhǔn)則，同時(shí)也出現(xiàn)這樣的問(wèn)題，當(dāng)幾個(gè)準(zhǔn)則相互抵觸制約的時(shí)候如何尋求平衡來(lái)保證各個(gè)指標(biāo)的折中。天津科技大學(xué) 2022 屆本科生畢業(yè)論文215 分組密碼與布爾函數(shù) 分組密碼概述 分組密碼的原理在 節(jié)我們談到，密碼體制根據(jù)加密方式的不同，分為分組密碼和流密碼。 圖 51 加密算法其解密過(guò)程是其逆過(guò)程。 為明文分組長(zhǎng)度，當(dāng) 時(shí)，稱之為有數(shù)據(jù)壓縮的2tF?分組密碼；當(dāng) ， ；通常研究 時(shí)，亦即nm?稱 之 為 有 數(shù) 據(jù) 擴(kuò) 展 的 分 組 密 碼 n?分組密碼的研究就是研究從明文組 到密文組 的變1(,.)nx1(,.)y換規(guī)則。研究分組密碼就是研究這種置換，()kEX2nmF到而布爾置換由一組具有一定關(guān)系的布爾函數(shù)構(gòu)成，所以對(duì)布爾置換的研究同樣可以歸結(jié)為對(duì)布爾函數(shù)的研究 [12]。DES 算法作為數(shù)據(jù)加密標(biāo)準(zhǔn)，完全公開，任何組織和個(gè)人都能使用，其信息安全依賴于各自密鑰的安全性，這就是現(xiàn)代分組密碼的特征。密碼分析是從不知道密鑰的密文推斷明文的過(guò)程。此外，安全性也與攻擊者擁有的計(jì)算機(jī)能力相關(guān)，因此，攻擊者擁有的信息越多，計(jì)算機(jī)能力越強(qiáng)，安全性越不可靠 [12]。 ①，即攻擊者獲得當(dāng)前密鑰下的某些明文和密文對(duì)。 ③ 選 擇 明 文 攻 擊如果一個(gè)密碼能抵制選擇明文攻擊，一定能抵制其他兩種攻擊。如果一個(gè)密碼體制對(duì)于一個(gè)擁有有限計(jì)算機(jī)資源的攻擊者是安全的，則稱此密碼計(jì)算上安全的，亦即相對(duì)安全。人們通常只追求計(jì)算上的安全性，而計(jì)算上的安全性乃一相對(duì)概念，取決于攻擊者的計(jì)算能力和攻擊方式。人們通常用“復(fù)雜度”來(lái)描述這種“困難性” 。對(duì)一個(gè)密碼安全性的評(píng)估，是根據(jù)已知的關(guān)于該密碼的最佳攻擊方法的復(fù)雜度，復(fù)雜度越高越安全。對(duì)其實(shí)施窮搜索的密文攻擊，每個(gè)密鑰都得試一次，所以其復(fù)雜度可以理解成試解密鑰的次數(shù) [10]。 分組密碼的設(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 算法作為分組密碼典型代表的 DES 算法于 1977 年由美國(guó)正式公布并被廣泛用于商業(yè)加密，盡管分組密碼算法還有 FEAL,GOST 和 IDEA 等算法，但 DES 仍被廣泛使用 [10]。 算法描述DES( Data Encryption Standard ) 算法是 1972 年由美國(guó) IBM 公司研究的對(duì)稱密碼體制加密算法，于 1977 年獲得美國(guó)政府的正式許可，因此又被稱為美國(guó)數(shù)據(jù)加密標(biāo)準(zhǔn)。DES 的分組長(zhǎng)度為 64bits。DES 工作的基本原理是：加密時(shí)，明文按 64 位進(jìn)行分組，形成明文組，加密密鑰對(duì)數(shù)據(jù)加密，解密時(shí)，解密密鑰于對(duì)數(shù)據(jù)解密 [17]。DES 的運(yùn)算過(guò)程如圖 52。在 DES 算法中，將 56 位的密鑰和分組后的 64 位明文組按替代或交換的方法形成密文組，即用 56 位密鑰來(lái)加密 64 位數(shù)據(jù)，其密鑰的長(zhǎng)度為 56位，明文則按 64 位來(lái)進(jìn)行分組 [17]。1 2 3 ………………………………………………………………………64輸入明文 （64bits）x58 50 42 34 26 18 10 260 52 44 36 28 20 12 462 54 46 38 30 22 14 664 56 48 40 32 24 16 857 49 41 33 25 17 9 159 51 43 35 27 19 11 361 53 45 37 29 21 13 563 55 47 39 31 23 15 7 1 2 3 …………………………………………………………………63 64置換后的數(shù)據(jù) 1 2 3 …………………………32 33 34…………………………63 64 0(bits)L0(32bits)R圖 53 初始置換 IP即將第倒是第 1 位換到第 7 位，第倒數(shù)第二位換到第 6 位……，由此類推，第 58 位換為第 1 位。對(duì) 施行在密x0L0R0鑰控制下的變換 ，結(jié)果記為 ,令f01()fRK，L??1(,)fK， （521 ）ii?1ii?ii?天津科技大學(xué) 2022 屆本科生畢業(yè)論文25對(duì) 施行和 同樣的過(guò)程得 ，如此循環(huán) 16 次得 。6 1IP?y 1 2 3 ………………………………………………………63 6464bits 數(shù)據(jù) 1 2 3 ………………………………………………………63 64密文 (64bits)y圖 54 初始逆置換 1IP?在 16 次加密后并未交換 ，而是直接將 作為 的輸入，這樣就16LR16LR1I?使得 DES 的解密和加密完全一樣，所以以上過(guò)程只需輸入密文，即可得明文 [18]。初始置換 及其逆置換 其實(shí)毫無(wú)密碼學(xué)意義，這是由于置換前后其二IP1I?者一一對(duì)應(yīng)關(guān)系是已知的。天津科技大學(xué) 2022 屆本科生畢業(yè)論文26 函數(shù) f我們把從 到 的變換過(guò)程稱作一輪加密，所以 DES 要經(jīng)過(guò) 16 輪1iLR?i迭代（加密） 。 為 32 位數(shù)字。計(jì)算E()E()A,對(duì) 進(jìn)行 代換，此代換由 8 個(gè)代換盒構(gòu)成，這就是我們即將討論的 SJB??S盒，每個(gè) S盒都有 6 個(gè)輸入和 4 個(gè)輸出 [17]，將 依次分為 8 組，每組 6 位，記B。在 輪為 ， 可CP(,)fAJi(,)iifRK?(,)fAJ用圖 57 表示。每個(gè) 盒的變換規(guī)則是：取 上的 4 個(gè)置換，S{01}， ， … ， 5也就是它的四個(gè)排列排成 4 行，也就得一個(gè) 4 16 矩陣。這012345bLn里 的二進(jìn)制表示為 ， 的二進(jìn)制表示為 。8 個(gè) 盒的表示見表