【正文】 輸出1ina??2ina?? ia in? 01(,.)nfx?天津科技大學(xué) 2022 屆本科生畢業(yè)論文17圖 42 反饋移位寄存器圖中序列 由地推關(guān)系ia， （431 ）1(,.)iniinfa????0,?確定。在二元域下，非線性組合部分可以用一個布爾函數(shù)來表示，所以對密鑰流生成器的研究也就歸結(jié)為對布爾函數(shù)的研究 [12]。通常將這類生成器分解成線性位移寄存器，稱為驅(qū)動部分，和非線性組合部分組成。因為位移寄存器結(jié)構(gòu)簡單，易于實現(xiàn)且運行速度快，能滿足以上要求，所以目前密鑰流生成器大都基于位移寄存器，這種基于位移寄存器的密鑰流序列稱為位移寄存器序列 [10]。這幾條準(zhǔn)則對保證系統(tǒng)安全性必要但非充分，也就是說對保證系統(tǒng)安全性是必須的，但要保證系統(tǒng)安全性，還需要其他條件，因此，隨著對安全問題研究的深入，某種新的攻擊方法的出現(xiàn)時，為確保系統(tǒng)的安全，還會提出更強(qiáng)的要求。其包含了相關(guān)免疫性，線性復(fù)雜度和不可預(yù)測性等很多序列密碼研究過程中的主要問題。雖然隨機(jī)序列是非周期的，但無論何種算法生成的序列都具有周期性，因而要求其有盡可能大的周期 [12]；② 密鑰流應(yīng)當(dāng)具有良好的隨機(jī)統(tǒng)計特性 [12]；③ 要有很高的線性復(fù)雜度，亦即當(dāng)某一部分暴露時，無法推出它的整體結(jié)構(gòu)；④ 密鑰系列易于高速生成。實際上，密鑰序列通常是按一定算法生成的周期序列。稱但通常通過確定的算法產(chǎn)生的密鑰流序列是偽隨機(jī)序列，并非完全隨機(jī)，此時的密碼系統(tǒng)就不再完全保密了，因此為了保證密碼系統(tǒng)的安全性，密鑰流序列必須滿足一定的要求 [12]。c在序列密碼系統(tǒng)中，因為明文序列與密鑰流逐位加密，所以密鑰流的長度必須與明文序列的長度相等，但這樣的序列卻難于管理和分配，所以實際中的密鑰序列均由密鑰空間中較短的密鑰經(jīng)過某些算法生成的 [1]。通信系統(tǒng)的模型如圖 41 所示。 序列密碼概述 序列密碼原理現(xiàn)實中的各種信息或信源一般是圖像、報文、語言和數(shù)據(jù)等，一般都是經(jīng)編碼器轉(zhuǎn)化為 0,1 序列，即二進(jìn)制序列，加密是針對 0,1 序列進(jìn)行的。序列密碼體制的安全性取決于密鑰流，而密鑰流序列由密鑰流生成器產(chǎn)生，常見的密鑰流生成器有前饋序列生成器、非線性反饋位移寄存器、非線性組合序列生成器和鐘控序列生成器等 [1]。天津科技大學(xué) 2022 屆本科生畢業(yè)論文14布爾函數(shù)的密碼學(xué)性質(zhì)除了以上討論的非線性、平衡性、相關(guān)免疫性、嚴(yán)格雪崩和擴(kuò)散準(zhǔn)則等外，還有退化性、線性結(jié)構(gòu)等 [12]。擴(kuò)散() 0k準(zhǔn)則記為 ， 次擴(kuò)散準(zhǔn)則記為 ,滿足相應(yīng)準(zhǔn)則的函數(shù)稱為 函數(shù)和PC()PCPC函數(shù) [12]。如1k?(fxfk果固定 的任意 個分量后得到的全部 元函數(shù)都滿足 次擴(kuò)散準(zhǔn)則，則fmm?稱 滿足 階 次擴(kuò)散準(zhǔn)則 [12]。 擴(kuò)散準(zhǔn)則定義 若對任意 且 ，總有 是平衡函數(shù)，即2naF?0?())fxa?，則稱 關(guān)于 滿足擴(kuò)散準(zhǔn)則。()fx差分均勻函數(shù)有 個輸入 個輸出，任意若干個輸入位發(fā)生改變，導(dǎo)致輸出1發(fā)生變化的概率為 ，滿足這種差分均勻性的函數(shù)為 Bent 函數(shù)。如果固定任意 個變元后得到的全部 元函數(shù)()fx knk?都滿足嚴(yán)格雪崩準(zhǔn)則，則稱 滿足 階嚴(yán)格雪崩準(zhǔn)則 [12]。 嚴(yán)格雪崩準(zhǔn)則嚴(yán)格雪崩準(zhǔn)則由 Webster 和 Tavares 在 1986 年首次提出，它對研究 S 盒有重要意義。()fx顯然，如果 是對稱函數(shù)，那么任意交換其分量的位置， 不變，也()f ()fx就是 ，不妨設(shè) ， 。ix1定理 布爾函數(shù) 對自變量 是線性的，當(dāng)且僅當(dāng)對任),.)nf i意 有1,.n （352 ）1(,..,ifx?1(,..,)infx其中 的取值為 0 或 1， ， ， 。布爾函數(shù)的很多性質(zhì)，例如擴(kuò)散準(zhǔn)則、雪崩準(zhǔn)則和相關(guān)免疫天津科技大學(xué) 2022 屆本科生畢業(yè)論文13準(zhǔn)則等都可以用平衡性來定義，平衡性也是密碼函數(shù)的設(shè)計準(zhǔn)則之一。顯然，如果 是 階相關(guān)免疫的，則對任意()f ()f， 是 階相關(guān)免疫的，相關(guān)免疫記為 ， 階相關(guān)免疫記為r()fr CICI，相應(yīng)的函數(shù)稱為 函數(shù)和 函數(shù)。其中對任意一組 ，有()fxm1,.miix成立。定義 設(shè) 是 個彼此獨立且對稱的 元隨機(jī)變量的布),.()1nxfx?2爾函數(shù)，當(dāng)且僅當(dāng) 與 中的 個隨機(jī)變量統(tǒng)計獨立，即當(dāng)且僅當(dāng)互信f息 [13] （341 ）1()。記其中的常數(shù)為 ，則線性結(jié)構(gòu)表示為b, 。定義 對任意元布爾函數(shù) ，若 的取值不影響的),.()1nxfx?i取值，則稱 與 無關(guān)。lim(x)1q???()f對任意 元布爾函數(shù) ，當(dāng)其非線性度 時，n 1/2nf?， ，顯然布爾函數(shù)滿足高非線性度，此時，我們稱/2?li(x)1q???為 Bent 函數(shù)。 ，即 的線性度為其與所有線性函數(shù)的最長距離。xfn][xLn則稱 （331 ）][mixLln?),(lfd][ixLln??)(lfw?為 的非線性度，記為 ，即 的非線性度為其與所有線性函數(shù)的最短)(xf fN天津科技大學(xué) 2022 屆本科生畢業(yè)論文12距離，很明顯線性函數(shù)非線性度為 [10]。例如 和4321)(xxf??都是 2 次非線性函數(shù)，但 是部分線性的，而 是非退43212)(xxf??1 )(2f化的， 比 更接近線性函數(shù)，或者說 更容易用線性函數(shù)來逼近，f)(f f于是人們便引入了“非線性度”這一概念來描述一個函數(shù)非線性的程度 [10]。)(xf )(xf 布爾函數(shù)的非線性性顧名思義，非線性性和線性性是相對的。f }0{??E推論：II 型線性結(jié)構(gòu)函數(shù)是不可退化的。)(xf容易看出，若 與變元無關(guān)，則必然退化，退化性是與變元無關(guān)性的推)(f廣 [12]。}{0?1)(xf定義 設(shè) ，若 的取值不影響 的取值，則稱?)(f,.1ni )(xf與 無關(guān)。r20?r2?1?r若 ，則稱 為 的線性結(jié)構(gòu)維數(shù)，此時有如下兩種情況：??q)(xf① ；1||?E② ，即 為空集。記 {全f ?E天津科技大學(xué) 2022 屆本科生畢業(yè)論文11體線性結(jié)構(gòu)}，則 是 的一個線性子空間，若該子空間的維數(shù)為正，即EnF2，則稱 是一個線性結(jié)構(gòu)函數(shù) [10]。若 ，稱 為 的nFx2?)((fa 0)(??xf a()fx不變線性結(jié)構(gòu)。 布爾函數(shù)的線性性定義 如果 ),.(1nxf?),.(,.(11nbnxlxg??則稱 元布爾函數(shù)是部分線性的，其中n； 。)(xf定理 與 的關(guān)系如下：)(f )(f （315 ）)(wSf???????0),(21xSf Walsh 變換的性質(zhì)Walsh 變換有如下性質(zhì)：性質(zhì) 1（平穩(wěn)性） 若 在 的譜值為 ，則 在 的譜值為)(xf )(Sf )(axf?w （316 ）,(waQf性質(zhì) 2（線性姓） 若 在 的譜值為 ， 若 在 的譜值為 ，)(xf )(f )(xg)(Sg則 在 的譜值為)(xbgaf?w （317 ）)()(wbSagf?性質(zhì) 3（Plancheral 公式） （318 ）)(2)0(120 fxnfwfn ?????此性質(zhì)又稱為初值定理。 是展210()nwxfxfS???A)(xf )(Sf開式的系數(shù)，即 Walsh 譜。顯然，對給定的 ， ，有xw)(xQ?。如無特別聲明， 均)(xf指 元布爾函數(shù)。 布爾函數(shù)的 Walsh 變換及其性質(zhì) 兩種 Walsh 變換在 節(jié)中已經(jīng)介紹過布爾函數(shù)的 Walsh 譜表示和 Walsh 變換對研究布爾函數(shù)的重要性。人們對不同種類的布爾函數(shù)的研究歸結(jié)為對布爾函數(shù)某種性質(zhì)的研究。以上研究方法因為其特點不同，適用于不同的研究場景和領(lǐng)域。天津科技大學(xué) 2022 屆本科生畢業(yè)論文8 矩陣方法布爾函數(shù)最直觀的表示方法就是矩陣表示，在定序意義下，重量為 的w元布爾函數(shù)之集和 上 矩陣之間是一一對應(yīng)的。從代數(shù)的角度，分析布爾函數(shù)主要采用多項式表示和小項表示。 布爾函數(shù)的研究方法布爾函數(shù)有不同的表示方法 [10]，而不同的表示方法在不同的研究中有其各自的優(yōu)勢，所以我們要根據(jù)不同的表示方法采用不同的研究方法，以便更好地展開研究，目前主流的研究方法有以下幾種。)(xf fC由于布爾函數(shù)的特征矩陣具有唯一性，因而可以將布爾函數(shù)的某些問題轉(zhuǎn)化為矩陣問題加以研究。2F 矩陣表示定義 設(shè) 是一個 元布爾函數(shù)， 。)(wSf nF2?)(f天津科技大學(xué) 2022 屆本科生畢業(yè)論文7因為 Walsh 變換可逆，因而布爾函數(shù)的 Walsh 譜唯一。2? Walsh 譜表示設(shè) ， ， 與 的點積定義為1(,.)nx1(,.)nw?2F??2則 元布爾函數(shù) 的 Walsh 變換定義為nf （225 ）20()()nwxfxSf???A其逆變換為 （226 ） 210()()nwxfxf??A（ ）稱為 的 Walsh 譜。 的代數(shù)次數(shù)記為 ，它是具有xf )(fde非零系數(shù)的最高階項的變量的個數(shù)。 多項式表示我們知道線性空間 是同構(gòu)的有限域 ，那么在 中，任意nF2nF2210()niifxa??元布爾函數(shù) 都可以唯一表示為二元域 上的一個單變量多項式 [11]：nnBf?2..)( 110 ???xxf n???,.2,.na （224 ）???,011.其中， ， ， ， ， 。12?n)(xf 小項表示 對任意給定的 ， ，約定iic?2F，?1ii0于是 ????時， 當(dāng) 時， 當(dāng) iici cxx0設(shè)，),.(1nc?),.(1n?則有天津科技大學(xué) 2022 屆本科生畢業(yè)論文6 （222 ）?????nncx.).(,011當(dāng)當(dāng)為簡便，今后亦記 于是 （223 ）?)(xf??120)(nicxf稱為 的小項表示 [10]。 真值表 任何 元布爾函數(shù)可以被表示為一個 長度的二進(jìn)制向量，這就nn2是所謂的真值表：, （221 ）)1,()0,1(),0( ， ?????fff也稱為 的函數(shù)值向量，記為 [4]。2x21x?1?11x? 布爾函數(shù)的表示為方便布爾函數(shù)的研究和應(yīng)用，不同情況下將采用不同的表達(dá)方式。為了方便，我們用普通加、乘記號分別表示 上的“ ”、 “ ”。自然地，我們將 上的函數(shù)稱作布爾函數(shù)。然后，一個 元布爾函數(shù)被定義為一個從 到 的映射。 布爾函數(shù)的基本知識 布爾函數(shù)的定義定義 [10] 設(shè) ， 是布爾代數(shù)中的任意數(shù)，則有1x2天津科技大學(xué) 2022 屆本科生畢業(yè)論文51x?2?12,0x???當(dāng) 同 時 為 時其 他1?212,0當(dāng) 同 時 為 時其 他若用“ ”、 “ ”表示 上的加、乘運算；1,0 看做 上的元素，則有??F2F1x?2?1?2x?因此布爾代數(shù)中的運算可用 上的函數(shù)來表示。布爾函數(shù)在序列密碼中的地位顯得極為特殊而且重要。若我們能產(chǎn)生某種隨機(jī)序列（密鑰流） ，其由密鑰來確定，那么用這樣的序列則可進(jìn)行加密，也就是將密鑰、明文表示成二進(jìn)制，對應(yīng)地進(jìn)行加密,加解密時一次性處理明文中的若干個比特。只有一次一密的密碼體制是不可能被破譯的，這一結(jié)論于 1949 年已被香農(nóng)（Shannon）證明，這極大的支持了流密碼的研究，序列密碼方案的研究過程便是對一次一密系統(tǒng)的嘗試，或者說“一次一密”的密碼只是序列密碼的入門。 分組密碼分組密碼則是將明文消息序列 12,.,.km分成等長的消息組（ ） ，,.n12(,.),.nn?在密鑰控制下按固定的算法 一組組進(jìn)行加密。要解決這一系列問題，就必須了解密碼體制實現(xiàn)的具體方式。如果公鑰系統(tǒng)被用于對稱密鑰加密，那么，由于攻擊者的密鑰已經(jīng)被用于加密，公鑰系統(tǒng)將成為攻擊者，而不是獲得的對稱密鑰的預(yù)期收件人。 ） 。這個可能是由通過從公鑰計算密鑰或通過取得其存儲和/或使用該密鑰的設(shè)備來實現(xiàn)的（該計算攻擊可以通過使用合適的密鑰，或者指望攻天津科技大學(xué) 2022 屆本科生畢業(yè)論文4擊者完成必要的計算后覺得不可行而主動放棄。在每一種情況下，攻擊者有兩種不同的方法攻擊系統(tǒng)。其缺點就是保密程度相對較差，而現(xiàn)實中我們就要在他們之間找到一個平衡點，既保證一定的速度，又保證信息盡可能不泄露，所以，現(xiàn)實中通常是兩種體制交叉并相互運用，即使用公鑰密碼體制來生成和交換密鑰，而使用私鑰密碼體制來傳輸大量數(shù)據(jù)。公鑰密碼體制相對于私鑰體制對通訊環(huán)境的安全性要求較弱，因而其應(yīng)用領(lǐng)域較廣，但是其運行速度較慢 [8]。因為它有兩個不同的密鑰（公開的密鑰和秘密的密鑰） ，彼此之間很難推出對方，而且加密變換和解密變換之間可以相互交換，所以我們也稱公鑰密碼體制為雙鑰密碼體制。而且在進(jìn)行通信前，通信的雙方必須通過安全信道傳送所使用的密鑰，因而增加了用戶的使用成本。目前主要有以下兩種方法：一是把具有良好隨機(jī)性統(tǒng)計特征的偽隨機(jī)序列作為密鑰序列，二是分組加密算法。 私鑰密碼體制和公鑰密碼體制 [1]根據(jù)密碼系統(tǒng)密鑰的特點，密碼體制可以分為私鑰密碼體制和公鑰