【正文】 鑰流，而密鑰流序列由密鑰流生成器產(chǎn)生，在密鑰流生成器中，布爾函數(shù)起著極其關(guān)鍵的作用。其次討論了布爾函數(shù)的幾個密碼學(xué)性質(zhì)和定理，重點介紹了作為布爾函數(shù)研究的一個重要工具——Walsh 譜，并介紹了布爾函數(shù)的密碼學(xué)性質(zhì)，主要包括非線性、平衡性、相關(guān)免疫和嚴(yán)格雪崩等。本文是一篇關(guān)于布爾函數(shù)的密碼學(xué)性質(zhì)及其應(yīng)用的文章。 布爾函數(shù)在現(xiàn)代密碼學(xué)中的應(yīng)用THE APPLICATION OF THE BOOLEAN FUNCTION IN MODERN CRYPTOGRAPHY 指 導(dǎo) 教 師：申請學(xué)位級別：學(xué)士論文提交日期：2022 年 6 月 9 日摘 要在密碼學(xué)中扮演著重要角色的布爾函數(shù)被廣泛用于流密碼和分組密碼的分析和設(shè)計中。最主要的原因是布爾函數(shù)的密碼學(xué)性質(zhì)在某種程度上直接決定系統(tǒng)的安全性。文中首先介紹了布爾函數(shù)的研究背景、重要性及國內(nèi)外研究現(xiàn)狀，并概述了密碼學(xué)相關(guān)的基礎(chǔ)知識，給出了布爾函數(shù)的定義，對其各種表示方法和研究方法進(jìn)行介紹，主要介紹了真值表，小項表示等。最后重點研究了布爾函數(shù)在流密碼和分組密碼中的應(yīng)用。分組密碼體制的算法中最具有代表性之一的是DES 算法，其設(shè)計的關(guān)鍵是 盒，而多輸出布爾函數(shù)可以很好地用來描述 盒。 block cipher； key stream generators； Sbox； Boolean function。從第二次世界大戰(zhàn)以來，密碼學(xué)理論和技術(shù)的應(yīng)用已經(jīng)不在局限于某個領(lǐng)域，不僅涵蓋了軍事、國防和金融，而且包含了政府、文教和商業(yè)的各個領(lǐng)域 [1]。當(dāng)消息通過開放的網(wǎng)絡(luò)發(fā)布時，可能沒有任何保密的必要，但用戶可能需要確保收到的消息在傳輸過程中尚未改變。所以，如何保證通過互聯(lián)網(wǎng)傳來的信息來源的可靠性、完整性和安全性就顯得極為重要，密碼學(xué)正是能在這一問題上提供保障的重要手段之一，由于布爾函數(shù)在流密碼和分組密碼的加密系統(tǒng)中起著重要作用，而這些系統(tǒng)的安全性主要由布爾函數(shù)的密碼學(xué)性質(zhì)決定 [2]。無論是單輸出布爾函數(shù)還是多輸出布爾函數(shù)，都在密碼算法的設(shè)計與分析中起有很大的作用，如序列密碼中常用的密鑰流生成器，既有非線性組合生成器也有非線性濾波生成器，顯然對這些生成器的分析也可歸結(jié)到對布爾函數(shù)的分析。所以，為保障信息來源的完整性可靠性，必須有效地構(gòu)造具有良好的加密特性的布爾函數(shù)?？傊紶柡瘮?shù)在密碼學(xué)中的研究不僅具有理論價值，而且具有使用價值。但是1949年到1975年這段時間密碼學(xué)的研究發(fā)展比較緩慢。在1976年，Rothaus 證明了 元布爾函數(shù)的非線性度是 ，這里n1n/2?是偶數(shù) [2]。相關(guān)免疫性作為布爾函數(shù)的一種統(tǒng)計性質(zhì)，在布爾函數(shù)的研究中有著重要意義，它首先由 Tsiegenthaler 于 1984 年在研究流密碼系統(tǒng)安全性時提出。通過降低對相關(guān)免疫性的要求，可以在非線性次數(shù)跟相關(guān)免疫階之間找到某個平衡點，由此提出了廣義相關(guān)免疫函數(shù)。在 2022 年，Courtois [4]和 Armknecht[5]提出的強大代數(shù)攻擊使用了一個新的設(shè)計準(zhǔn)則，即代數(shù)免疫。如 XL 算法等有效算法的出現(xiàn)，解決了被過度定義的多元代數(shù)方程的系統(tǒng)，代數(shù)攻擊成功地破譯出如 Toyocrypt 和 LILI128 等比較有名的序列密碼 [6]。 本文研究的主要內(nèi)容本文著重討論布爾函數(shù)的密碼學(xué)性質(zhì)及其在密碼學(xué)中應(yīng)用，主要內(nèi)容安排如下：① 主要介紹布爾函數(shù)的研究背景和意義，以及國內(nèi)外的研究現(xiàn)狀。③ 主要介紹布爾函數(shù)的密碼學(xué)性質(zhì)，主要有非線性、相關(guān)免疫性和嚴(yán)格雪崩等④ 主要介紹布爾函數(shù)在序列密碼中的應(yīng)用，如密鑰流生成器中的位移寄存器序列。天津科技大學(xué) 2022 屆本科生畢業(yè)論文22 基本理論知識 密碼學(xué)基本概念 密碼學(xué)基本原理密碼學(xué)是一門研究通信安全或密碼系統(tǒng)的學(xué)科，現(xiàn)代密碼學(xué)（Cryptology）由密碼分析學(xué)（cryptoanalytics ）和密碼編碼學(xué)（ cryptography）組成 [2]。密碼系統(tǒng)的思想是以某種方式偽裝機密信息，而該方式的含義對于那些未經(jīng)授權(quán)的人來說是難以理解的 [8]。經(jīng)過加密的消息稱為密文，加密該消息的編碼工具被稱為編碼器，而他們發(fā)送密碼電文的對象被稱為接收器。通常，該算法的操作將依賴于一個加密密鑰 ，其中該編碼器將加密密鑰連同消息一起輸入到算法中。在實踐中，大多數(shù)密碼攻擊都與試圖確定解密密鑰的行為有關(guān)，因為，如果成功，攻擊者就會有相同的信息成為預(yù)期收件人，并且攻擊者就能夠解密所有其他通信，直到密鑰改變。 加密算法 解密算法加密密鑰 解密密鑰信息 信息密碼電文天津科技大學(xué) 2022 屆本科生畢業(yè)論文3通過以上介紹可以得出：從密文獲得消息時，加密密鑰是不重要的。 密碼體制的分類根據(jù)不同的標(biāo)準(zhǔn)，密碼體制有不同的分類。 私鑰密碼體制對于私鑰密碼體制主要研究的問題是怎么生成滿足要求的密鑰流。在私鑰密碼體制中，由于加密密鑰和解密密鑰相互對應(yīng)，因而私鑰密碼體制的安全性取決于密鑰的安全性。 公鑰密碼體制1976 年，赫爾曼（Hellman）和狄菲（Diffie ）在其發(fā)表的“密碼學(xué)的新方向”中提出了公鑰密碼體制的概念。因為雙鑰密碼體制的特點是將加解密的密鑰分開，同時也就將加解密能力分開了，因此它既可用于在公共網(wǎng)絡(luò)中實現(xiàn)保密通信，也可以用于認(rèn)證系統(tǒng)中進(jìn)行發(fā)送者的身份確認(rèn)。而私鑰密碼體制正好相反，機構(gòu)簡單，速度快，其運行速度是公鑰密碼體制的成百上千倍。使用公鑰密碼體制的系統(tǒng)成為公鑰系統(tǒng)，它趨向于使用非常大的數(shù)字運算處理，公鑰系統(tǒng)的兩個主要用途是提供數(shù)字簽名和作為加密密鑰為對稱密鑰系統(tǒng)分發(fā)密鑰。一個是在取得相關(guān)的密鑰。涉及設(shè)備濫用的攻擊必須通過良好的管理或使用適當(dāng)?shù)姆来鄹脑O(shè)備進(jìn)行防御。另一個是對方攻擊打算替換公鑰。如果公鑰系統(tǒng)被用來提供數(shù)字簽名，那么，很明顯攻擊者可以偽造簽名者真正的簽名。 序列密碼和分組密碼根據(jù)明文消息加密方式和實現(xiàn)形式的不同，我們將密碼體制分為流密碼和分組密碼。加密后輸出的等長密文組kE1(,.),.,.myy 序列密碼序列密碼也稱為流密碼（Stream Cipher ） [9]，具有實現(xiàn)簡單、加解密速度快、幾乎沒用錯誤傳播的特點，所以其在專用或機密機構(gòu)中有很大的優(yōu)勢，其應(yīng)用領(lǐng)域主要包括無線通信、外交通信。如果序列密碼所使用的密鑰并非偽隨機方式產(chǎn)生的、并與消息流長度相同，那么此時的序列密碼即一次一密的密碼體制。分組密碼和序列密碼是實現(xiàn)密碼體制的兩種基本方式，要實現(xiàn)密碼體制，不可缺少的一個重要工具就是布爾函數(shù)（亦即該課題要研究的重點） 。所以密碼學(xué)研究的始終，一直伴隨著對布爾函數(shù)的研究。2在本文中，我們用 表示在有限域 = 上的所有 元組中的集合的元nF2F}1,0{n素。所有 元布爾函n2數(shù)的集合表示為 。一般地我們定nB義如下映射：：)(xfn2?為 元布爾函數(shù)，其中 為二元域， 為 的 元向量空間， ，記為n2FF?xnF2。如f 2??1記為 ， 記為 ；但有時仍用 記 。本節(jié)將簡要介紹幾種布爾函數(shù)的表示方法。1在真值表中的個數(shù)稱被為 的漢明重量，)(xf?f記為 或 ，如果它的真值表有相等數(shù)目的 1和0，我們說 是平衡的，這wf意味著若， = ，此時則稱 為平衡布爾函數(shù)。小項表示其實就是布爾代數(shù)表達(dá)式，亦即邏輯表達(dá)式)(xf[10]。0ai?21Fn??2)(iiaF2?ni這就是所謂的代數(shù)范式（ANF） 。若 ，則定義 ；若0)(?0?，則稱 為仿射函數(shù)；當(dāng) 時，仿射函數(shù)被稱為線性函數(shù)；若)(?fde)(xf，則稱 為非線性函數(shù) [11]。此式亦即 的 Walsh 譜表示。 跡函數(shù)在有限域上的布爾函數(shù)的跡函數(shù) 表示為2:Ftrn? （227 ）10()ttx???跡函數(shù)在 上是線性的。若 ，則稱 為)(xfnnFx2?1)(?xfx的一個特征向量，記 的全體特征向量的集合為 ，)(xf D}.1)(|{afD?w將 中的 個向量按字典順序從大到小排列，記第 個向量 ， ，則稱Dwiiw?10,1 矩陣 ??????wnwncc...212112為 的特征矩陣，記為 ，或簡記為 [11]。布爾函數(shù)也可以通過投影空間的特征函數(shù)和狀態(tài)圖等表示。 代數(shù)分析方法任何可以表示為多項式形式的函數(shù)都可以使用代數(shù)方法進(jìn)行分析，顯然，布爾函數(shù)也不例外。 頻譜方法頻譜分析作為研究布爾函數(shù)的一個重要工具，通過其可以分析布爾函數(shù)的譜特性。n2Fnw?)21(n? 重量分析方法對任意兩個布爾函數(shù) 和 ，定義 和),.()1nxfx?),.(1nxg?)(xf的距離為)(xg f?記為 ，即,fd),(gfd?)(fw對和函數(shù)的重量有如下關(guān)系式： （231 ）f?f)(2fg?重量分析方法是通過分析布爾函數(shù)的重量特征來研究布爾函數(shù)的方法，這種方法簡單易懂，很適合工程應(yīng)用。天津科技大學(xué) 2022 屆本科生畢業(yè)論文93 布爾函數(shù)的密碼學(xué)性質(zhì)布爾函數(shù)在不同領(lǐng)域有著不同的應(yīng)用，因而衍生出了不同的函數(shù)類。本章著重介紹布爾函數(shù)的一些重要性質(zhì)。本節(jié)首先討論 Walsh 變換及其性質(zhì)。n已知 210()()nwxfxfS???A若記 （311 ）()1wxwQA則當(dāng) 取遍 （或 ）時，就得到一個函數(shù)系 [11]：wnF2120??n， （312 ）)(xw?nF2此函數(shù)系是一個正交函數(shù)系，即滿足 )(Quv?????vun,0該函數(shù)系（311 ）稱為 Walsh 函數(shù)系。)(wQx可以看作 在 Walsh 函數(shù)系下的展開式。還有另外一種展開式：)(f （313 ）)(xf?)(210)(xQwSfn???其中 （314 ）)()1()(20xSwwfnf??天津科技大學(xué) 2022 屆本科生畢業(yè)論文10為了區(qū)別，將 稱為 的第一種 Walsh 譜或線性譜，而將 稱為)(wSf )(xf )(wSf的第二種 Walsh 譜或循環(huán)譜。性質(zhì) 4（Parseval 公式） （319 ）1)(120???xSnwf此即能量守恒定理。??????nbiibncl11),.( ,2??Fni定義 設(shè) 是 元布爾函數(shù)， ，稱 為 的一個線性結(jié)構(gòu)，)xf a)(xf則對任意 ， 為常數(shù)。若 ，稱 為 的恒變線性結(jié)構(gòu)。0?Dim)(xf記 }0)((|{0 ????xfafE11則有如下性質(zhì)：① , ；??10E?0?② 是 的子空間；?③ 若 ，則 ；11,Ea?④ 設(shè) ，若 ，則 ， 。,01設(shè) 是線性結(jié)構(gòu)函數(shù)，若 ，則稱 為 I 型線性結(jié)構(gòu)函數(shù)；若)(xf }0{?E)(xf，這時必有 ，則稱 是一個 II 型線性結(jié)構(gòu)函數(shù)。該性質(zhì)稱為與變元無關(guān)性，最初稱與變元無關(guān)性為退化，定義)(fi如下：定義 設(shè) ，若存在 上的 矩陣 ,使得)(xf),.1nxf nF2k?)(n?D),.((1ygD?則稱 是退化的。由此可以得出如下定理：定理 是退化的 。定理 是部分線性的，則 是退化的。代數(shù)次數(shù)大于一的函數(shù)是非線性函數(shù)，雖同為非線性函數(shù)，差異卻很大 [12]。定義 設(shè) 是 元一個布爾函數(shù)，記 為所有 元線性函數(shù)之集。同理稱0 （332 ）][maxLln?),(lfd為 的線性度，記為 。)(xf fC)(f由定義 可知，對任意 元布爾函數(shù) 有n)(xf （333 ）fN?fCn2?定義 設(shè) 是 元一個布爾函數(shù)，若比值函數(shù) 滿足)(xf 12/)(??nfNq，則稱布爾函數(shù) 具有高非線性度。()fxBent 函數(shù)乃非線性度最高的函數(shù)，對布爾函數(shù)的研究有著極其重要的作用。()fx()fxi定義 設(shè)布爾函數(shù) ： ，對于任意給定的 ，()f2nF2,naF?且 0?對任意的 ，如果 恒為常數(shù)，那么稱 為 的一個線性結(jié)2nF?a?()f構(gòu)。2{|())}nExfxb???2 相關(guān)免疫性相關(guān)免疫性作為布爾函數(shù)的一種統(tǒng)計性質(zhì)，在布爾函數(shù)的研究中有著重要意義。,.)0miiIf?時，稱 為 階相關(guān)免疫函數(shù)。?當(dāng) 時，稱 為 階相關(guān)免疫函數(shù) [10]，亦叫相關(guān)免疫函數(shù)；當(dāng) ，?()fx1 2?稱 為高階相關(guān)免疫函數(shù)。CIIm 布爾函數(shù)的平衡性我們在 節(jié)定義了平衡布爾函數(shù)： = ，即 的真值表中 0()wf12?n()fx和 1 的個數(shù)相等。定義 對任意布爾函數(shù) ，如果),.()1nxfx? （351 ）(,.iif???則稱對變量 是線性的，其中 是與 無關(guān)的 元函數(shù)。ix?i?fA 布爾函數(shù)的對稱性定義 設(shè) 是 元布爾函數(shù)，如果對任意 階置換矩陣 有()fxn P （361 ）()fxP?則稱 是對稱函數(shù)。所以，ij??ij?1(,..,)ijnfx1(,..,jinf對任意 ，只要 ，則 ，也就是說當(dāng)布爾函數(shù)輸出2,nyF?y)wx?(yf?向量的漢明重量相同時，產(chǎn)生的輸出值也不變，這就是布爾函數(shù)的線性不變性，亦稱仿射不變性。定義 若對任意 ， ，總有 是平衡函數(shù)，2naF?()1w?())fxa?則稱 滿足嚴(yán)格雪崩準(zhǔn)則。()fx定義 若對任意 ， ，總有 是平衡函數(shù)，則稱2n0?())f