【導(dǎo)讀】最主要的原因是布爾函數(shù)的密碼學(xué)性質(zhì)在某種程度上直接決定系統(tǒng)。本文是一篇關(guān)于布爾函數(shù)的密碼學(xué)性質(zhì)及其應(yīng)用的文章。進(jìn)行介紹，主要介紹了真值表，小項(xiàng)表示等。線性、平衡性、相關(guān)免疫和嚴(yán)格雪崩等。最后重點(diǎn)研究了布爾函數(shù)在流密碼和分組密碼中的應(yīng)用。爾函數(shù)起著極其關(guān)鍵的作用。分組密碼體制的算法中最具有代表性之一的是DES. 算法，其設(shè)計的關(guān)鍵是S盒，而多輸出布爾函數(shù)可以很好地用來描述S盒。

　　

【正文】 列的一個周期圈上。 定義 2F 上 n 級位移寄存器產(chǎn)生的周期為 2n 的序列稱為 n 級 m 序列。 定理 在 n 級 m 序列的一個周期內(nèi)， 0 與 1 的個數(shù)各是 12n? ，在 m 序列的一個周期圈中，總游程為 12n? ；對 12in? ? ? ，長為 i 的游程數(shù)為 12ni?? ，其中0,1 游程各占 1/2 ，長 1n? 的游程 0 個。長為 n 的 0 游程和 1 游程各 1 個。 定理 2F 上的 n 級 m 序列的數(shù)目為 122n n?? 。 定理 設(shè)序列 {}ia 的極小多項(xiàng)式為 ()Qx， (0) 0Q ? ，則序列 {}ia 的周期 T是 ()Qx整除 1Tx? 的最小正整數(shù) T ，即 ()Qx的階。 當(dāng) 2F 上的 n 級 LFSR 產(chǎn)生的序列 {}ia 的周期為 T 21n??時，稱序列 {}ia 為 n級 m 序列。為了描述 m 序列，下面引進(jìn)有限域上的跡函數(shù)。 定義 nqF 到 qF 上的跡函數(shù) 1()nTr x 定義為 天津科技大學(xué) 2020 屆本科生畢業(yè)論文 18 1()nTr x 10in qi x????， x? nqF （ 435） 2q? 時，和 節(jié)對跡函數(shù)的定義一致。 定理 nqF 到 qF 上的跡函數(shù) 1()nTr x 有如下性質(zhì)： ① 對任何 ,??? nqF ， , quv F? ，有 1 ()nTr u v????1 ()nuTr ? ? 1 ()nvTr ? （ 436） ② 當(dāng) nqF 看作 qF 上的 n 維線性空間時， 1()nTr x 是從 nqF 到 qF 上的線性變換。 設(shè) nqaF? ， a 在 qF 上的極小多項(xiàng)式定義為 qF 上以 a 為其 一根的最小次數(shù)多項(xiàng)式，記為 ()amx。 定理 設(shè) a 是 2nF 中的一個本原元， 2nF?? ，則序列 {}ia ? 1{ ( )}niTr a? 是以 ()amx為極小多項(xiàng)式的 n 級 m 序列，且 ()amx產(chǎn)生的所有序列均可表示為1{ ( )}niTr a? ， 2naF?[10]。 定義 2F 上的周期為 T 的序列 {}ia 的自相關(guān)函數(shù)定義 為 ()aR? ? 101 ( 1) ( 1)kkT aakT???? ???， 01T?? ? ? （ 437） 周期序列的自相關(guān)函數(shù)是序列隨機(jī)性的一個指標(biāo)，其表示序列 {}ia 與 {}ia??在一個周期內(nèi)對應(yīng)位相同的位數(shù)與對應(yīng)位相異的位數(shù)之差的一個參數(shù) [10]。對獨(dú)立均勻分布的二進(jìn)隨機(jī)變量序列 {}iX ，它的自相關(guān)函數(shù) ()xR? 的期望值為 [ ( )]xER? ? 001 = 0?? ???? ， 當(dāng) 時， 當(dāng) 時 （ 439） 定理 2F 上的 n 級 m 序列 {}ia 具有如下性質(zhì) [15]： ① 在一個周期內(nèi)， 0,1 出現(xiàn)之次數(shù)分別為 121n?? ， 12n? 。 ② 在一個周期圈內(nèi)，總游程數(shù)為 12n? ，對 12in? ? ? ，長為 i 的游程數(shù)為 12ni??個，且 0 游程和 1 游程各一半，長為 1n? 的 0 游程有一個，長為 n 的 1 游程 1 個[10]。 ③ {}ia 的自相關(guān)函數(shù)為二值： ()aR? ? 1 11 = 0TT ???? ? ?????， 當(dāng) 0 時， 當(dāng) 時 （ 4310） 由定理 可見， m 序列具有良好的隨機(jī)統(tǒng)計特性。雖然 m 序 列具有最長的序列周期 21n? 和很好的隨機(jī)統(tǒng)計特性，但仍不能直接作為密鑰流序列，通常只是一個密鑰流生成器中的組成單元 [10]。 天津科技大學(xué) 2020 屆本科生畢業(yè)論文 19 Golomb 對偽隨機(jī)周期序列提出了如下隨機(jī)性公設(shè)： 0 1 1① 在 序 列 的 一 個 周 期 內(nèi) ， 與 的 個 數(shù) 之 差 最 多 為； ② 在 序 列 的 一 個 周 期 圈 內(nèi) ，1長 為 的 游 程 數(shù) 占 總 游 程 數(shù) 的 ，2長 為 的 游 程 數(shù) 占總 游 程 數(shù) 的 ， 長 度 為 的 游 程 數(shù) 占總游程數(shù)的 1/2i ，?， 且 在 等 長 的 游 程 中， 0， 1游程各占一半； ③ 自 相 關(guān) 函 數(shù) 為 二 值 。但很少有偽隨機(jī)序列能嚴(yán)格滿足如上公設(shè)。 對于一個長為 N 的序列 0aa? ， 11,..., Naa? ，顯然它可以被一個 N 級的 LFSR產(chǎn)生，只要取 ( ) 1 Nf x x?? 即可。但通常 a 還可能由更短的 LFSR 產(chǎn)生。 定義 qF 上的序列 0aa? ， 11,..., Naa? 的線性復(fù)雜度 ()Ca定義為產(chǎn)生該序列的 qF 上級數(shù)最少的 LFSR 的級數(shù)。對全零序列 a ，約定 ()Ca 0? 。 序列線性復(fù)雜度的概念具有重要的密碼學(xué)意義。 定理 設(shè) {}iaa? 是 qF 上的周期序列，且序列 {}ia 的線性復(fù)雜度( ) L 1Ca??，那么只要知道 {}ia 中任意相繼的 2L 位，即可確定整個序列 {}ia 及產(chǎn)生 {}ia 的極小多項(xiàng)式。 由 定理 可見，線性復(fù)雜度是序列線性預(yù)測性的一個指標(biāo) [10]，若其線性復(fù)雜度很小，是不安全的。前面我們已經(jīng)提到，對于 n 級 m 序列 {}ia ，它的線性復(fù)雜度為 n ，盡管他的周期為 21n? 以及很好的隨機(jī)統(tǒng)計特性，仍不能直接用作密鑰序列。由于 m 序列有理想的隨機(jī)統(tǒng)計性，并且滿足 Golomb 隨機(jī)性公設(shè)，所 以它通常作為密鑰流序列產(chǎn)生器的基本單元，再通過非線性濾波器或非線性組合而成為密鑰流序列。 序列密碼中布爾函數(shù)的設(shè)計準(zhǔn)則 根據(jù)前面的討論我們知道，布爾函數(shù)在序列密碼系統(tǒng)中起著重要作用，其性質(zhì)直接決定密碼系統(tǒng)的安全性。布爾函數(shù)只有滿足一定的設(shè)計準(zhǔn)則，才能保證系統(tǒng)符合安全性的基本要求并可以抵抗現(xiàn)有的攻擊 ， 從而保證系統(tǒng)的安全，為此對流密碼中的布爾函數(shù)提出如下準(zhǔn)則，概括起來如下 [12]： ① 平衡性 平衡性即是為保證輸出的密鑰流序列具有良好統(tǒng)計特性而對布爾函數(shù)提出的準(zhǔn)則。 ② 高代數(shù)次數(shù) 在第 2 章我們定義了布爾函數(shù)的代數(shù)次數(shù)，得知布爾函數(shù)的線性復(fù)雜度依賴于布爾函數(shù)的代數(shù)次數(shù)，而較高的線性復(fù)雜度是密鑰流序列的基礎(chǔ)。 ③ 高非線性度 設(shè) )(xf 是 n 元一個布爾函數(shù)，記 ][xLn 為所有 n 元線性函數(shù)之集。則稱 ][min xLl n? ),( lfd ][min xLl n?? )( lfw ? 為 )(xf 的非線性度，記為 fN ，即 )(xf 的非線性度為其與所有線性函數(shù)的最短距離。其中 l 為所有仿射函數(shù)。 它反 映了該函數(shù)用仿射函數(shù)來逼近的能力。如果用天津科技大學(xué) 2020 屆本科生畢業(yè)論文 20 譜值的觀點(diǎn)來看 , 它反映了譜值的絕對值的最大值的大小 , 當(dāng)然這個值越小越好 , 也就是說非線性度越大越好。 前面我們已經(jīng)討論過，設(shè) )(xf 是 n 元一個布爾函數(shù)，若比值函數(shù)12/)( ?? nfNnq 滿足 lim ( ) 1x qx?? ?，則稱布爾函數(shù) (x)f 具有高非線性度。 對任意 n 元布爾函數(shù) ()fx，當(dāng)其非線性度 1 /2 122nnfN ????時， /2( ) 1 2 nqn ??? ，lim ( ) 1x qx?? ? ，顯然布爾函數(shù)滿足高非線性度，此時，我們稱 ()fx為 Bent 函數(shù)。 Bent函數(shù)乃非線性度最高的函數(shù)，但是 Bent函數(shù)的缺陷就是不平衡性，因此人們設(shè)計時只要求譜值比較均勻。由于譜值均勻和高非線性度是一致的，因此本文中我們沿用人們一直以來的術(shù)語 —— 高非線性。 ④ 相關(guān)免疫性 為了抵抗相關(guān)攻擊， 系統(tǒng)中的布爾函數(shù)必須滿足相關(guān)免疫性。 ⑤ 非退化性 文獻(xiàn)中研究相關(guān)免疫的退化性時指出，退化函數(shù)可以用與其等價的非線性組合函數(shù)替代，如果替代的組合函數(shù)不再具有相關(guān)免疫性，則攻擊方法仍然有效。所以可退化的相關(guān)免疫函數(shù)并不能抵制相關(guān)攻擊，要想提高系統(tǒng)的安全性，就必須盡可能使用非退化的相關(guān)免疫函數(shù)。 以上根據(jù)現(xiàn)有攻擊以及對密鑰流序列的基本要求提出的準(zhǔn)則都只是必要而非充分的。此外，僅某一個指標(biāo)并無法確保安全性，如高代數(shù)次數(shù)并無法保證高非線性度，因此也就無法保證 對線性逼近攻擊的安全性 [12]。所以要求同時滿足多個準(zhǔn)則，同時也出現(xiàn)這樣的問題，當(dāng)幾個準(zhǔn)則相互抵觸制約的時候如何尋求平衡來保證各個指標(biāo)的折中。一般原則是首先保證最重要的指標(biāo)達(dá)到一定強(qiáng)度的條件下，其余的指標(biāo)盡可能高。 天津科技大學(xué) 2020 屆本科生畢業(yè)論文 21 5 分組密碼與布爾函數(shù) 分組密碼概述 分組密碼的原理 在 節(jié)我們談到，密碼體制根據(jù)加密方式的不同，分為分組密碼和流密碼。流密碼是逐比特加密，而分組密碼則是將明文消息序列 12, ,..., ,...km m m 分 成等長的消息組 （ 12, ,..., nm m m ）， 12( ,..., ),...nnmm? 在密鑰控制下按一定的算法 kE 一組組加密，加密后輸出的等長密文組 1 1 2( , ... , ) , ( , ... , ) , ...m m ny y y y? 可用圖 51 來表示 [10]。 圖 51 加密算法 其解密過 程是其逆過程。 一般的，我們給分組密碼作如下定義： 定義 [10] 一個（私鑰）分組密碼是一種映射： 2 2 2n t mF F F?? （ 511） 記為 ( , )EX K 或 ()kEX, 2nXF? ， 2tKF? ， 2nF 稱為明文空間 ， 2mF 稱為密文空間，2tF 稱為密鑰空間。 n 為明文分組長度，當(dāng) nm? 時，稱之為有數(shù)據(jù)壓縮的分組密碼；當(dāng) nm? ， 稱 之 為 有 數(shù) 據(jù) 擴(kuò) 展 的 分 組 密 碼；通常研究 nm? 時，亦即分組密碼的研究就是研究從明文組 1( ,..., )nxx 到密文組 1( ,..., )nyy 的變換規(guī)則。由于明文組 1( ,..., )nxx 和密文組 1( ,..., )nyy 都是二元組，于是研究分組密碼即轉(zhuǎn)化為研究 22nmFF到 的映射，此時，當(dāng) nm? 且映射一一對應(yīng)時， ()kEX就是 22nmFF到 的置換，這就是布爾置換。研究分組密碼就是研究這種置換，而布爾置換由一組具有一定關(guān)系的布爾函數(shù)構(gòu)成，所以對布爾置換的研究同樣可以歸結(jié)為對布爾函數(shù)的研究 [12]。 上世紀(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)程的首選體制。 DES 算法作為數(shù)據(jù)加密標(biāo)準(zhǔn)，完全公開，任何組織和個人都能使用，其信息安 全依賴于各自密鑰的安全性，這就是現(xiàn)代分組密碼的特征。 加密算法 明文1( ,..., )nxx 密鑰 K 密文 1( ,..., )nyy 天津科技大學(xué) 2020 屆本科生畢業(yè)論文 22 分組密碼的安全性 如前所述，現(xiàn)代分組密碼算法的安全性取決于密鑰的安全性。 密碼分析是從不知道密鑰的密文推斷明文的過程。一般我們假設(shè)攻擊者可以截獲不安全信道上傳輸?shù)乃忻芪模?而 事 實(shí) 上 ，通常攻擊者也許還會截獲別的信息使得破譯更容易。此外，安全性也與攻擊者擁有的計算機(jī)能力相關(guān)，因此，攻擊者擁有的信息越多，計算機(jī)能力越強(qiáng)，安全性越不可靠 [12]。 攻擊通常分為如下三類： ① 唯密文攻擊。 ② 已 知 明 文 攻 擊，即攻擊者獲得當(dāng)前密鑰下的某些明文和密文對。 ③ 選 擇 明 文 攻 擊，攻擊者獲得當(dāng)前密鑰下的某些明文和對應(yīng)的密文。 如果一個密碼能抵制選擇明文攻擊，一定能抵制其他兩種攻擊。 當(dāng)一個密碼體制對一個擁有無限計算機(jī)資源的攻擊者來說也是安全的，則該系統(tǒng)絕對安全，同時說明破譯該密碼 是不可能的。如果一個密碼體制對于一個擁有有限計算機(jī)資源的攻擊者是安全的，則稱此密碼計算上安全的，亦即相對安全。說計算上安全，也就是說破譯該密碼較為困難，我們可以這樣理解： 李志慧 ① 破譯信息花的代價超出信息的價值； ② 破譯信息需要的時間超出信息有效期。 人們通常只追求計算上的安全性，而計算上的安全性乃一相對概念，取決于攻擊者的計算能力和攻擊方式。一般計算上的安全性指是：對該密碼的最佳攻擊方法的困難性超過了攻擊者的計算能力 [10]。人們通常用“復(fù)雜度”來描述這種“困難性”。復(fù)雜度表示實(shí)施該攻擊所需的平均運(yùn)算次數(shù)。對一個密碼安全性的評估，是根據(jù)已知的關(guān)于該密碼的最佳攻擊方法的復(fù)雜度，復(fù)雜度越高越安全。在不知道密鑰的情況下，可以通過采用窮搜索進(jìn)行攻擊，所以，如果一個分組密碼只能使用窮搜索，那它就是安全的。對其實(shí)施窮搜索的密文攻擊，每個密鑰都得試一次，所以其復(fù)雜度可以理解成試解密鑰的次數(shù) [10]。對密鑰空間為 2tF 的密文 ，試解次數(shù)為 12t? 次，所以只要密鑰空間充分大，亦即 t 足夠大，使得實(shí)施窮搜索在計算上不可行的，則該分組密碼就是安全的。 分組密碼的設(shè)計原則 通常比較好的分組密碼應(yīng)該既難破譯又易于實(shí)現(xiàn)，人們基于難破譯的要求提出分組密碼算法需遵循如下基本原則： ① 分 組 長 度 應(yīng) 足 夠 大，確保實(shí)施 2n 次加密在計算上是不可能的，從而防止明文遭受窮搜索攻擊。 ② 充 分 大 的 密 鑰 量，防止對密鑰的進(jìn)行窮搜索攻擊。 ③ 混 亂 和 擴(kuò) 散 。 混亂的目的是使明文和密文的統(tǒng)計學(xué)特性的關(guān)系趨向復(fù)雜化。 擴(kuò)散性是通過將每個明文數(shù)字的影響迅速擴(kuò)散到多個輸出的密文數(shù)字中，從天津科技大學(xué) 2020 屆本科生畢業(yè)論文 23 而來隱蔽明文數(shù)字的統(tǒng)計學(xué)特性，通過將密鑰的每個數(shù)字盡量擴(kuò)散到更多密文數(shù)字中，以此防止對密鑰進(jìn)行逐段破譯 [13]。也就是說，分組密碼應(yīng)該設(shè)計成明文的每個比特和密鑰的每個比特對密文的每個比特都產(chǎn)生影響。 DES 算法 作為分組密碼典型代表的 DES 算法于 1977 年由美國正式公布并被廣泛用于商業(yè)加密，盡管分組密碼算法還有 FEAL,GOST 和 IDEA 等算法，但 DES 仍被廣泛使 用 [10]。雖然目前 AES 算法已經(jīng)逐漸取代了 DES 算法，但是由于 DES 算法對現(xiàn)代分組密碼理論的應(yīng)用和發(fā)展起到了基礎(chǔ)作用，因此它的基本理論和設(shè)計思想對我們研究分組密碼仍有重要參考價值 [10]。 算法描述 DES( Data Encryption Standard ) 算法是 1972 年由美國 IBM公司研究的對稱密碼體制加密算法，于 1977 年獲得美國政府的正式許可，因此又被稱為美國數(shù)據(jù)加密標(biāo)準(zhǔn)。 DES 加密算法特點(diǎn)：分組比較短、 密鑰太短、 密碼生命周期短、 運(yùn)算速度較慢 [16]。 DES 的分組長度為 64bits。每 64 位明文加密成 64 位密文，沒有數(shù)據(jù)壓縮和擴(kuò)展，密鑰長度為 56bits，若輸入 64bits，則第 8，?? 64 是奇偶校驗(yàn)位，所以實(shí)際密鑰只有 56 位 [17]。 DES 工作的基本原理是：加密時，明文按 64 位進(jìn)行分組，形成明文組，加密密鑰對數(shù)據(jù)加密，解密 時，解密密鑰于對數(shù)據(jù)解密 [17]。實(shí)際上密鑰只用了 56位，這樣更安全。 DES 的運(yùn)算過程如圖 52。 輸入 64bits 明文 初始置換 IP 16 輪迭代運(yùn)算 1IP? 64bits 明文