布爾函數(shù)在現(xiàn)代密碼學(xué)中的應(yīng)用

布爾函數(shù)在現(xiàn)代密碼學(xué)中的應(yīng)用TheapplicationoftheBooleanfunctioninmoderncryptography指導(dǎo)教師：申請學(xué)位級別：學(xué)士論文提交日期：2014年6月9日摘要在密碼學(xué)中扮演著重要角色的布爾函數(shù)被廣泛用于流密碼和分組密碼的分析和設(shè)計中。最主要的原因是布爾函數(shù)的密碼學(xué)性質(zhì)在某種程度上直接決定系統(tǒng)的安全性。本文是一篇關(guān)于布爾函數(shù)的密碼學(xué)性質(zhì)及其應(yīng)用的文章。文中首先介紹了布爾函數(shù)的研究背景、重要性及國內(nèi)外研究現(xiàn)狀，并概述了密碼學(xué)相關(guān)的基礎(chǔ)知識，給出了布爾函數(shù)的定義，對其各種表示方法和研究方法進(jìn)行介紹，主要介紹了真值表，小項表示等。其次討論了布爾函數(shù)的幾個密碼學(xué)性質(zhì)和定理，重點介紹了作為布爾函數(shù)研究的一個重要工具——Walsh譜，并介紹了布爾函數(shù)的密碼學(xué)性質(zhì)，主要包括非線性、平衡性、相關(guān)免疫和嚴(yán)格雪崩等。最后重點研究了布爾函數(shù)在流密碼和分組密碼中的應(yīng)用。序列密碼體制的安全性取決于密鑰流，而密鑰流序列由密鑰流生成器產(chǎn)生，在密鑰流生成器中，布爾函數(shù)起著極其關(guān)鍵的作用。分組密碼體制的算法中最具有代表性之一的是DES算法，其設(shè)計的關(guān)鍵是盒，而多輸出布爾函數(shù)可以很好地用來描述盒。關(guān)鍵詞：序列密碼；分組密碼；密鑰流生成器；DES算法；盒；布爾函數(shù)；Walsh譜ABSTRACTTheBooleanfunctionplayinganimportantroleincryptologyiswidelyusedintheanalysesanddesignsofstreamcipherorblockcipher.ThemainreasonisthatatsomedegreethecryptographicpropertiesofBooleanfunctiondirectlydecidethesecurityofsystem.ThisdissertationisdevotedtothecryptographicpropertiesandapplicationsoftheBooleanfunctionsinmoderncryptography.FirstlytheresearchbackgroundandsignificanceofBooleanfunction,andthestatus-quoofthisresearchbothathomeandabroadareintroduced.Andthebasicknowledgeofcryptographyaresummarized,andtheBooleanfunctionisdefinited,furthermorethedenotationmethodsandtheresearchmethodsofthepropertiesofBooleanfunction,mainlyincludingthetruthtableandpolynomialdenotation,etcaresummarized.SecondlyseveralcryptographicpropertiesandtheoremabouttheBooleanfunctionarediscussed,WalshspectrumwhichisthoughtasanimportanttoolofstudyingtheBooleanfunctionareintroduced,andthecryptographicpropertiesoftheBooleanfunction,mainlyincludingnonlinear,balance,relatedimmuneandstrictavalanche,etcareintroduced.FinallywefocuseontheapplicationsoftheBooleanfunctioninstreamcipherandblockcipher.ThesecurityofstreamcipherdependsonthekeystreamfurthermorethekeystreamsequencesaregeneratedbythekeystreamgeneratorswheretheBooleanfunctionplaysanimportantrole.OneofthemostrepresentativeblockcipheralgorithmisDESalgorithms,whichthekeyondesigningisS-box,whichcanbedescribedbymultipleoutputBooleanfunction.Keyword：Streamcipher;blockcipher；keystreamgenerators；S-box；Booleanfunction;Walshspectrum目錄TOC\o"1-2"\h\u187001前言 ③?；靵y的目的是使明文和密文的統(tǒng)計學(xué)特性的關(guān)系趨向復(fù)雜化。擴(kuò)散性是通過將每個明文數(shù)字的影響迅速擴(kuò)散到多個輸出的密文數(shù)字中，從而來隱蔽明文數(shù)字的統(tǒng)計學(xué)特性，通過將密鑰的每個數(shù)字盡量擴(kuò)散到更多密文數(shù)字中，以此防止對密鑰進(jìn)行逐段破譯[13]。也就是說，分組密碼應(yīng)該設(shè)計成明文的每個比特和密鑰的每個比特對密文的每個比特都產(chǎn)生影響。5.2DES算法作為分組密碼典型代表的DES算法于1977年由美國正式公布并被廣泛用于商業(yè)加密，盡管分組密碼算法還有FEAL,GOST和IDEA等算法，但DES仍被廣泛使用[10]。雖然目前AES算法已經(jīng)逐漸取代了DES算法，但是由于DES算法對現(xiàn)代分組密碼理論的應(yīng)用和發(fā)展起到了基礎(chǔ)作用，因此它的基本理論和設(shè)計思想對我們研究分組密碼仍有重要參考價值[10]。5.2.1算法描述DES(DataEncryptionStandard)算法是1972年由美國IBM公司研究的對稱密碼體制加密算法，于1977年獲得美國政府的正式許可，因此又被稱為美國數(shù)據(jù)加密標(biāo)準(zhǔn)。DES加密算法特點：分組比較短、密鑰太短、密碼生命周期短、運(yùn)算速度較慢[16]。DES的分組長度為64bits。每64位明文加密成64位密文，沒有數(shù)據(jù)壓縮和擴(kuò)展，密鑰長度為56bits，若輸入64bits，則第8，……64是奇偶校驗位，所以實際密鑰只有56位[17]。DES工作的基本原理是：加密時，明文按64位進(jìn)行分組，形成明文組，加密密鑰對數(shù)據(jù)加密，解密時，解密密鑰于對數(shù)據(jù)解密[17]。實際上密鑰只用了56位，這樣更安全。DES的運(yùn)算過程如圖5-2。輸入64bits明文初始置換16輪迭代運(yùn)算64bits明文圖5-2DES算法框圖初始置換[10]是將輸入的64位明文分為8個數(shù)組，每一組包括8位，按1至64編號。在DES算法中，將56位的密鑰和分組后的64位明文組按替代或交換的方法形成密文組，即用56位密鑰來加密64位數(shù)據(jù)，其密鑰的長度為56位，明文則按64位來進(jìn)行分組[17]。DES首先對輸入的64位明文進(jìn)行一次初始置換(圖5-3)，來打亂原來的次序。123………………………64輸入明文（64bits）58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157123…………………6364置換后的數(shù)據(jù)123…………323334…………6364圖5-3初始置換即將第倒是第1位換到第7位，第倒數(shù)第二位換到第6位……，由此類推，第58位換為第1位。對置換后的分成左右兩部分，左邊記為,右邊記為。對施行在密鑰控制下的變換，結(jié)果記為,令，，（5-2-1）對施行和同樣的過程得，如此循環(huán)16次得。再對64位數(shù)字進(jìn)行初始置換的逆變換（圖5-4），即得密文。123………636464bits數(shù)據(jù)123………6364密文圖5-4初始逆置換在16次加密后并未交換，而是直接將作為的輸入，這樣就使得DES的解密和加密完全一樣，所以以上過程只需輸入密文，即可得明文[18]。如因為第1位經(jīng)過初始置換后，，逆置換就是要將第40位換回到第1位[18]。初始置換及其逆置換其實毫無密碼學(xué)意義，這是由于置換前后其二者一一對應(yīng)關(guān)系是已知的。它們的作用是為了打亂原來輸入明文的ASCⅡ碼值的關(guān)系，并且將原來明文的第8，……，64位（校驗位）變成輸出的一個字節(jié)[18]。5.2.2函數(shù)我們把從到的變換過程稱作一輪加密，所以DES要經(jīng)過16輪迭代（加密）。和是第次迭代結(jié)果的左右兩個部分，每輪變換全部相同，只是數(shù)據(jù)不同，這里稱為DES的函數(shù)，其中為32位輸入，為48位輸入，在第輪，，為由64位的初始密鑰（也稱種子密鑰）導(dǎo)出的第輪子密鑰。為32位數(shù)字。的計算過程如下[10]：將經(jīng)過一個擴(kuò)展運(yùn)算（如圖5-5）后為48位，記為。計算,對進(jìn)行代換，此代換由8個代換盒構(gòu)成，這就是我們即將討論的S-盒，每個S-盒都有6個輸入和4個輸出[17]，將依次分為8組，每組6位，記。12………………3232bits12………………3248bits圖5-5擴(kuò)展運(yùn)算其中作為第個-盒的輸入,的輸出為，就是代換的輸出，所以代換是一個48位的輸入，32位輸出的選擇壓縮運(yùn)算，將結(jié)果再進(jìn)行置換（如圖5-6），即得[18]。在輪為，可用圖5-7表示。32bits12……………3232bits：圖5-6置換運(yùn)算JE+1…67…12…………48…………12……32…圖5-7運(yùn)算框圖5.2.3-盒的布爾函數(shù)表示上一節(jié)我們介紹了DES加密的加密過程，其核心部分是由8個-盒組成的選擇壓縮運(yùn)算。每個-盒的變換規(guī)則是：取上的4個置換，也就是它的四個排列排成4行，也就得一個416矩陣。如果給定該-盒的輸入為，其輸出對應(yīng)該矩陣的第行、列所對應(yīng)數(shù)的二進(jìn)制表示。這里的二進(jìn)制表示為，的二進(jìn)制表示為。如此一來，每個-盒均可用一個416矩陣或數(shù)表來表示[10]。8個-盒的表示見表5-1。表5-1-盒函數(shù)S11441312151183106125907015741421311061211953841148136211151297310501512824917511314100613S21518146113497213120510313471528141201106911501471110413158126932151381013154211671205149S31009146315511312711428137093461028514121115113649815301112125101471101306987415143115212S47131430691012851112415138115615034721211014910690121171315131452843150610113894511127214S52124171011685315130149141121247131501510398645111101378159125630141181271142136150910453S61211015926801334147511101542712956113140113891415528123704101131164321295151011141760813S74112141508133129751061130117491101435122158614111312371410156805926111381410795015142312S81328461511110931450127115138103741256110149271141912142061013153582114741081315129035611盒的設(shè)計是DES的關(guān)鍵部分，每個盒均可看成是一個從到的多輸出函數(shù)，即4個6元布爾函數(shù)組成的函數(shù)組，可通過表5-1給出的8個盒的布爾函數(shù)表示，如盒的布爾函數(shù)表示為[19]（5-2-2）是4個6元布爾函數(shù)，表達(dá)式如下：其余見參考文獻(xiàn)[19]，或直接由表5-1給出。可見，盒可用多輸出函數(shù)（布爾函數(shù)組）來表示，從而通過對多輸出函數(shù)和布爾函數(shù)的研究來分析盒的性能。綜上所述，可以看出布爾函數(shù)既是分組密碼的重要組成部分，也是其設(shè)計的重要工具之一，為使密碼系統(tǒng)具有一定的性能，布爾函數(shù)不得不滿足一定的設(shè)計準(zhǔn)則。5.3分組密碼中布爾函數(shù)的設(shè)計準(zhǔn)則根據(jù)前面對分組密碼的討論我們知道，盒的設(shè)計是分組密碼設(shè)計過程中的重要部分，且盒的性能對整個密碼系統(tǒng)的安全性起決定性作用，而盒可用多輸出布爾函數(shù)來描述[16]。因此，為保證分組密碼系統(tǒng)能滿足5.1.3節(jié)提出的設(shè)計原則，密碼系統(tǒng)設(shè)計中的布爾函數(shù)必須滿足一定的設(shè)計準(zhǔn)則，概括起來有如下幾點[10]：正交性定義5.3.1設(shè)，，若對任意，集合（5-3-1）中恰有個元素，則稱是正交的。定理5.3.2設(shè)，，正交的充分必要條件是：對任意，時，是平衡函數(shù)。正交性在單輸出時即為布爾函數(shù)的平衡性，在多輸出時亦可轉(zhuǎn)化為其平衡性，所以正交性是保證盒安全性的必要條件。如果盒（為了方便，常將盒與對應(yīng)的多輸出布爾函數(shù)視為相同，本章在敘述時對二者不加其別）無正交性，那么在隨機(jī)均勻輸入的情況下，盒的某些輸出將反復(fù)出現(xiàn)，因此密碼分析者可以利用這一特點對基于盒的密碼體制實施攻擊。高代數(shù)次數(shù)從在第二章我們對布爾函數(shù)的代數(shù)次數(shù)的定義可以知道，代數(shù)次數(shù)低的盒是不具備安全性，因此盒必須有一定的代數(shù)次數(shù)。高非線性度要使盒能抵抗線性分析，就必須具有較高的非線性度。擴(kuò)散準(zhǔn)則和嚴(yán)格雪崩準(zhǔn)則由5.1.3節(jié)知擴(kuò)散性是對盒的一個基本要求。，擴(kuò)散性強(qiáng)，所以Bent函數(shù)是完全非線性函數(shù)。以上這些準(zhǔn)則并不是滿足的越多越好，而是希望在一定條件下，可以滿足更多的性質(zhì)[16]。6結(jié)論本文主要討論了現(xiàn)代密碼學(xué)中布爾函數(shù)的性質(zhì)及其應(yīng)用，布爾函數(shù)的密碼學(xué)性質(zhì)直接關(guān)系到密碼體制的安全性，特別是布爾函數(shù)在對序列密碼和分組密碼的設(shè)計和分析中起著不可替代的重要作用。文中首先介紹了密碼學(xué)相關(guān)的基礎(chǔ)知識，概述了密碼學(xué)以及密碼體制的分類；對布爾函數(shù)進(jìn)行了定義，對其各種表示方法和研究方法進(jìn)行介紹，主要介紹了真值表，小項表示等。同時討論了布爾函數(shù)的密碼學(xué)性質(zhì)，重點介紹了其Walsh譜變換，布爾函數(shù)的相關(guān)免疫性和平衡性等，利用平衡性定義了其他幾種性質(zhì)，并引出Bent函數(shù)的定義。基于以上內(nèi)容，本文重點研究了布爾函數(shù)在密碼學(xué)中的應(yīng)用。其應(yīng)用主要在序列密碼和分組密碼。流密碼體制的安全性依賴于密鑰流，而密鑰流序列產(chǎn)生于密鑰流生成器，位移寄存器作為密鑰流生成器的重要組成部分成為我們介紹的重點，并得到諸多結(jié)論（詳見4.3節(jié)）。分組密碼算法中最具有代表性的便是DES算法，而DES算法設(shè)計的關(guān)鍵在于盒的設(shè)計，從而盒的性能對整個密碼系統(tǒng)的安全性起決定性作用，而盒可用多輸出布爾函數(shù)來描述。文中我們不僅介紹了分組密碼的設(shè)計原理，還著重介紹了DES算法中的盒，最后給出了盒的布爾函數(shù)表示，如盒表示為是4個6元布爾函數(shù)，其表達(dá)式見5.3節(jié)。總之，研究密碼學(xué)中的布爾函數(shù)，特別是分組密碼中的布爾函數(shù)是一個浩大的工程，仍有很多工作要做，一般有限域上的布爾函數(shù)很可能成為以后研究的重點，例如更廣義的代數(shù)免疫，能否將代數(shù)免疫性推廣到一般有限域。此外，文中多處均引用了已有著作中的結(jié)論，在此表示感謝。限于水平有限，難免有謬誤之處，望各位教授、老師和同學(xué)積極指正。參考文獻(xiàn)[1]王相生.序列密碼設(shè)計與實現(xiàn)的研究[D].中國科學(xué)院上海冶金研究所，2001.[2]張串絨.密碼學(xué)中布爾函數(shù)的性質(zhì)和構(gòu)造[D].西安:西安電子科技大學(xué),2001.[3]溫巧燕,張劼,鈕心忻等.現(xiàn)代密碼學(xué)中的布爾函數(shù)研究綜述[J].北京郵電大學(xué),2004(12):44-46.[4]CourtoisN,MeierW.Algebraicattacksonstreamcipherswithlinearfeedback.AdvancesinCryptology:ProceedingsoftheInternationalConferenceontheTheoryandApplicationsofCryptographicTechniques(EUROCRYPT’03)[J],May4-8,2003,Warsaw,Poland.LNCS2656.Berlin,Germany:Springer-Verlag,2003:345-359.[5]ArmknechtF,KrauseM.Algebraicattacksoncombinerswithmemory.AdvancesinCceedingsofthe23rdAnnualInternationalCryptologyConferenceCRYPTO2003LectureNotesinComputerSciencevolume[J],2729.2003.Pages162-17.[6]JieZHANG,Qiao-yanWEN.Ontheconstructionofodd-variablebooleanfunctionswithoptimalalgebraicimmunity[J].TheJournalofChinaUniversitiesofPostsandTelecommunications,Volume20,Issue3,June2013,Pages73-77.[7]BattenLM.AlgebraicattacksoverGF(q).ProgressinCryptology:Proceedingsofthe5thInternationalConferenceonCryptologyinIndia(INDOCRYPT’04)[C],Dec20-22,2004,Chennai,India.LNCS3348.Berlin.Germany:Springer-Verlag,2004:84-91.[8]PaulGarrett.IntroductiontoCryptology[M].Texas.Pearsonpress.2000:10-13.[9]羅啟彬,張健.流密碼的現(xiàn)狀和發(fā)展[J].信息與電子工程.2006(01):75-79.[10]溫巧燕,楊義先,HYPERLINK"/kcms/detail/search.aspx?dbcode=CJFQ&sfield=au&skey=%C5%A5%D0%C4%D0%C3&code=05965465;05971528;05969080;064205