【正文】 函數(shù)，如果對(duì)任意 n 階置換矩陣 P 有 ( ) ( )f x f xP? （ 361） 則稱 ()fx是對(duì)稱函數(shù)。 定義 對(duì)任意布爾函數(shù) ),...,()( 1 nxxfxf ? ，如果 1 1 1 1( ) ( , ... , , , ... , )i i i nf x x f x x x x???? （ 351） 則稱對(duì)變量 ix 是線性的，其中 1()fx是與 ix 無關(guān)的 1n? 元函數(shù)。 布爾函數(shù)的平衡性 我們?cè)? 節(jié)定義了平衡布爾函數(shù)： ()wf = 12?n ，即 ()fx的真值表中 0 和1 的個(gè)數(shù)相等。 當(dāng) 1m? 時(shí)，稱 ()fx為 1階相關(guān)免疫函數(shù) [10]，亦叫相關(guān)免疫函數(shù)；當(dāng) 2m? ，稱 ()fx為高階相關(guān)免疫函數(shù)。 , ..., ) 0miiI f x x x ? （ 341） 時(shí)，稱 ()fx為 m 階相關(guān)免疫函數(shù)。 相關(guān)免疫性 相關(guān)免疫性作為布爾函數(shù)的一種統(tǒng)計(jì)性質(zhì)，在布爾函數(shù)的研究中有著重要意義。 定義 設(shè)布爾函數(shù) (x)f ： 22nFF? ，對(duì)于任意給定的 2 ,naF? 且 0a? ，對(duì)任意的 2nxF? ，如果 (x) (x )f f a??恒為常數(shù)，那么稱 a 為 (x)f 的一個(gè)線性結(jié)構(gòu)。 Bent 函數(shù)乃非線性度最高的函數(shù)，對(duì)布爾函數(shù)的研究有著極其重要的作用。 由定義 可知，對(duì)任意 n 元布爾函數(shù) )(xf 有 fN ? fC n2? （ 333） 定義 設(shè) )(xf 是 n 元一個(gè)布爾函數(shù)，若比值函數(shù) 12/)( ?? nfNnq 滿足 lim (x) 1x q?? ? ，則稱布爾函數(shù) ()fx具有高非線性度。同理稱 ][max xLl n? ),( lfd （ 332） 天津科技大學(xué) 2020 屆本科生畢業(yè)論文 13 為 )(xf 的線性度，記為 fC 。 定義 設(shè) )(xf 是 n 元一個(gè)布爾函 數(shù)，記 ][xLn 為所有 n 元線性函數(shù)之集。代數(shù)次數(shù)大于一 的函數(shù)是非線性函數(shù)，雖同為非線性函數(shù)，差異卻很大 [12] 。 定理 )(xf 是部分線性的，則 )(xf 是退化的。由此可以得出如下定理： 定理 )(xf 是退化的 }0{0 ??E 。該性質(zhì)稱為與變?cè)獰o關(guān)性，最初稱 與變?cè)獰o關(guān)性為退化，定義如下： 定義 設(shè) ?)(xf ),...,( 1 nxxf ，若存在 nF2上的 kn? )( nk? 矩陣 D ,使得 ),...,()(),...,( 11 kn yygxDgxxf ?? 則稱 )(xf 是退化的。 設(shè) )(xf 是線性結(jié)構(gòu)函數(shù)，若 }0{0?E ，則稱 )(xf 為 I 型線性結(jié)構(gòu)函數(shù)；若}0{0?E ，這時(shí)必有 11?E ，則稱 )(xf 是一個(gè) II 型線性結(jié)構(gòu)函數(shù)。 天津科技大學(xué) 2020 屆本科生畢業(yè)論文 12 記 }0)()(|{0 ????? xfaxfEaE }1)()(|{1 ????? xfaxfEaE 則有如下性質(zhì)： ① ??10 EE ? , 10 EEE ?? ； ② 00,0 EE? 是 E 的子空間； ③ 若 ??1E ，則 101 , EaEaE ??? ； ④ 設(shè) rE 20 ? ，若 ??1E ，則 rE 21 ? ， 12?? rE 。若 1)()( ??? xfaxf ，稱 a 為 ()fx的恒變線性結(jié)構(gòu)。 定義 設(shè) )(xf 是 n 元布爾函數(shù)， nFa 2? ，稱 a 為 )(xf 的一個(gè)線性結(jié)構(gòu)，則對(duì)任意 nFx 2? ， )()( xfaxf ?? 為常數(shù)。 性質(zhì) 4（ Parseval 公式） 1)(12 0 )(2 ???? xSnw f （ 319） 此即能量守恒定理。 )(xf 還有另外一種展開式： )(xf ? )()(2121 120 )( xQwS ww fn???? （ 313） 其中 )()1(21)( 12 0 )()( xQwS ww xfnf n??? ?? （ 314） 為了區(qū)別，將 )(wSf 稱為 )(xf 的第一種 Walsh 譜或線性譜，而將 )()( wSf 稱為 )(xf天津科技大學(xué) 2020 屆本科生畢業(yè)論文 11 的第二種 Walsh 譜或循環(huán)譜。 210( ) ( )( 1)n wxfxf x S w?????可以看作 )(xf 在 Walsh 函數(shù)系下的展開式。 已知 210( ) ( )( 1)n wxfxf x S w????? 若記 ( ) ( 1)wxwQx?? （ 311） 則當(dāng) w 取遍 nF2 （或 120 ??? nw ）時(shí)，就得到一個(gè)函數(shù)系 [11]： )(xQw ， w ? nF2 （ 312） 此函數(shù)系是一個(gè)正交函數(shù)系，即滿足 )(xQu )(xQv ? ??? ??vu vun,0 ,2 該函數(shù)系（ 311）稱為 Walsh 函數(shù)系。本節(jié)首先討論 Walsh 變換及其性質(zhì)。本章著重介紹布爾函數(shù)的一些重要性質(zhì)。 天津科技大學(xué) 2020 屆本科生畢業(yè)論文 10 3 布爾函數(shù)的密碼學(xué)性質(zhì) 布爾函數(shù)在不同領(lǐng)域有著不同的應(yīng)用，因而衍生出了不同的函數(shù)類。 重量分析方法 對(duì)任意兩個(gè)布爾函數(shù) ),...,()( 1 nxxfxf ? 和 ),...,()( 1 nxxgxg ? ，定義 )(xf 和天津科技大學(xué) 2020 屆本科生畢業(yè)論文 9 )(xg 的距離為 )( gfw ? 記為 ),( gfd ，即 ),( gfd ? )( gfw ? 對(duì)和函數(shù)的重量有如下關(guān)系式： )( gfw ? ? )(fw ? )(gw )(2 fgw? （ 231） 重量分析方法是通過分析布爾函數(shù)的重量特征來研究布爾函數(shù)的方法，這種方法簡單易懂，很適合工程應(yīng)用。 頻譜方法 頻譜分析作為研究布爾函數(shù)的一個(gè)重要工具，通過其可以分析布爾函數(shù)的譜特性。 代數(shù)分析方法 任何可以表示為多項(xiàng)式形式的函數(shù)都可以使用代數(shù)方法進(jìn)行分析，顯然，布爾函數(shù)也不例外。布爾函數(shù)也可以通過投影空間的特征函數(shù)和狀態(tài) 圖等表示。若 1)( ?xf ，則稱 x 為 )(xf的一個(gè)特征向量，記 )(xf 的全體特征向量的集合為 D ， }.1)(|{ 2nFaafaD ??? wD? 將 D 中的 w 個(gè)向量按字典順序從大到小排列，記第 i 個(gè)向量 iw ， wi??1 ，則稱0,1 矩陣 ??????????????wnwwnnccccccccc.....................212222111211 為 )(xf 的特征矩陣，記為 fC ，或簡記為 C [11]。 跡函數(shù) 在有限域上的布爾函數(shù)的跡函數(shù) 22: FFtr n ? 表示為 天津科技大學(xué) 2020 屆本科生畢業(yè)論文 8 1 20()tnttr x x???? （ 227） 跡函數(shù)在 2F 上是線性的。此式亦即 )(xf 的 Walsh 譜表示。若 0)( ?xf ，則定義 0)( ?fdef ；若 1)( ?fdef ，則稱 )(xf 為仿射函數(shù)；當(dāng) 00?a 時(shí)，仿射函數(shù)被稱為線性函數(shù)；若 2)( ?fdef ，則稱 )(xf 為非線性函數(shù) [11]。 這就是所謂的代數(shù)范式（ ANF）。小項(xiàng)表示其實(shí)就是布爾代數(shù)表達(dá)式，亦即邏輯表達(dá)式[10]。 1在真值表中的個(gè)數(shù)稱被為 f 的漢明重量，記為 ()wf 或 fw ，如果它的真值表有相等數(shù)目的 1和 0，我們說 f 是平衡的，這意味著若， ()wf = 12?n ，此時(shí)則稱 )(xf 為平衡布爾函數(shù)。本節(jié)將簡要介紹幾種布爾函數(shù)的表示方法。如 1x ? 2x 記為21 xx? ， 1x ? 2x 記為 21xx ；但有時(shí)仍用 1x 記 1x ? 1。一般地我們定義如下映射： )(xf ： nF2 ? 2F 為 n 元布爾函數(shù)，其中 2F 為二元域， nF2 為 2F 的 n 元向量空間， ?x nF2 ，記為 f 。所有 n 元布爾函數(shù)的集合表示為 nB 。 在本文中，我們用 nF2 表示在有限域 2F = }1,0{ 上的所有 n 元組中的集合的元素。所以密碼學(xué)研究的始終，一直伴隨著對(duì)布爾函數(shù)的研究。 分組密碼和序列密碼是實(shí)現(xiàn)密碼體制的兩種基本方式，要實(shí)現(xiàn)密碼體制，不可缺少的一個(gè)重要工具就是布爾函數(shù)（亦即該課題要研究的重點(diǎn)）。如果序列密碼所使用的 密鑰并非偽 隨機(jī)方式 產(chǎn)生 的、 并 與消息流長度相同， 那么 此時(shí)的序列密碼 即 一次一密的 密碼體制 。加密后輸出的等長密文組 1 1 2( , ... , ) , ( , ... , ) , ...m m ny y y y? 序列密碼 序列密碼也稱為流密碼（ Stream Cipher） [9]， 具有實(shí)現(xiàn)簡單、加解密速度快、幾乎沒用 錯(cuò)誤傳播 的 特點(diǎn)， 所以其 在專用或機(jī)密機(jī)構(gòu)中 有很大的 優(yōu)勢(shì)， 其 應(yīng)用領(lǐng)域 主要 包括無線通信、外交通信。 序列密碼和分組密碼 根據(jù)明文消息加密方式和實(shí)現(xiàn)形式的不同，我們將密碼體制分為流密碼和分組密碼。如果公鑰系統(tǒng)被用來提供數(shù)字簽名，那么，很明顯攻擊者可以偽 造簽名者真正的簽名。另一個(gè)是對(duì)方攻擊打算替換公鑰。涉及設(shè)備濫用的攻擊必須通過良好的管理天津科技大學(xué) 2020 屆本科生畢業(yè)論文 5 或使用適當(dāng)?shù)姆来鄹脑O(shè)備進(jìn)行防御。一個(gè)是在取得相關(guān)的密鑰。 使用公鑰密碼體制的系統(tǒng)成為公鑰系統(tǒng)，它趨向于使用非常大的數(shù)字運(yùn)算處理，公鑰系統(tǒng)的兩個(gè)主要用途是提供數(shù)字簽名和作為加密密鑰為對(duì)稱密鑰系統(tǒng)分發(fā)密鑰。而私鑰密碼體制正好相反，機(jī)構(gòu)簡單，速度快，其運(yùn)行速度是公鑰密碼體制的成百上千倍。 因?yàn)殡p鑰密碼體制的特點(diǎn)是將加解密的密鑰分開，同時(shí)也就將加解密能力分開了，因此它既可用于在公共網(wǎng)絡(luò)中實(shí)現(xiàn)保密通信，也可以用于認(rèn)證系統(tǒng)中進(jìn)行發(fā)送者的身份確認(rèn)。 公鑰密碼體制 1976 年，赫爾曼（ Hellman）和狄菲（ Diffie）在其發(fā)表的“密碼學(xué)的新方向”中提出了公鑰密碼體制的概念。 在私鑰密碼體制中，由于加密密鑰和解密密鑰相互對(duì)應(yīng)，因而私鑰密碼體制的安全性取決于密鑰的安全性。 私鑰密碼體制 對(duì)于私鑰密碼體制主要研究的問題是怎么生成滿足要求的密鑰流。 密碼體制的分類 根據(jù)不同的標(biāo)準(zhǔn)，密碼體制有不同的分類。 通過以上介紹可以得出：從密文獲得消息時(shí)，加密密鑰是不重要的。 在實(shí)踐中，大多數(shù)密碼攻擊都與試圖確定解密密鑰的 行為有關(guān)，因?yàn)?，如果成功，攻擊者就?huì)有相同的信息成為預(yù)期收件人，并且攻擊者就能夠解密所有其他通信，直到密鑰改變。通常，該算法的操作將依賴于一個(gè)加密密鑰)(Ek ，其中該編碼器將加密密鑰連同消息一起輸入到算法中。經(jīng)過加密的消息稱為密文，加密該消息的編碼工具被稱為編碼器，而他們發(fā)送密碼電文的對(duì)象被稱為接收器。 密碼系統(tǒng)的 思想是以某種方式偽裝機(jī)密信息，而該方式的含義對(duì)于那些未經(jīng)授權(quán)的人來說是難以理解的 [8]。 天津科技大學(xué) 2020 屆本科生畢業(yè)論文 3 2 基本理論知識(shí) 密碼學(xué)基本概念 密碼學(xué)基本原理 密碼學(xué)是一門研究通信安全或密碼系統(tǒng)的學(xué)科，現(xiàn)代密碼學(xué)（ Cryptology）由密碼分析學(xué)（ cryptoanalytics）和密碼編碼學(xué) （ cryptography） 組成 [2]。 ③ 主要介紹布爾函數(shù)的密碼學(xué)性質(zhì)，主要有非線性、相關(guān)免疫性和嚴(yán)格雪崩等 ④ 主要介紹布爾函數(shù)在序列密碼中的應(yīng)用，如密鑰流生成器中的位移寄存器序列。 本文研究的主要內(nèi)容 本文著重討論布爾函數(shù)的密碼學(xué)性質(zhì)及其在密碼學(xué)中應(yīng)用，主要內(nèi)容安排如下： ① 主要 介紹布爾函數(shù)的研究背景和意義，以及國內(nèi)外的研究現(xiàn)狀。如 XL 算法等有效算法的出現(xiàn)，解決了被過度定義的多元代數(shù)方程的系統(tǒng)，代數(shù)攻擊成功地破譯出如 Toyocrypt 和 LILI128 等 比較有名