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

布爾函數(shù)在現(xiàn)代密碼學(xué)中的應(yīng)用TheapplicationoftheBooleanfunctioninmoderncryptography指導(dǎo)教師：申請(qǐng)學(xué)位級(jí)別：學(xué)士論文提交日期：2014年6月9日摘要在密碼學(xué)中扮演著重要角色的布爾函數(shù)被廣泛用于流密碼和分組密碼的分析和設(shè)計(jì)中。最主要的原因是布爾函數(shù)的密碼學(xué)性質(zhì)在某種程度上直接決定系統(tǒng)的安全性。本文是一篇關(guān)于布爾函數(shù)的密碼學(xué)性質(zhì)及其應(yīng)用的文章。文中首先介紹了布爾函數(shù)的研究背景、重要性及國(guó)內(nèi)外研究現(xiàn)狀，并概述了密碼學(xué)相關(guān)的基礎(chǔ)知識(shí)，給出了布爾函數(shù)的定義，對(duì)其各種表示方法和研究方法進(jìn)行介紹，主要介紹了真值表，小項(xiàng)表示等。其次討論了布爾函數(shù)的幾個(gè)密碼學(xué)性質(zhì)和定理，重點(diǎn)介紹了作為布爾函數(shù)研究的一個(gè)重要工具——Walsh譜，并介紹了布爾函數(shù)的密碼學(xué)性質(zhì)，主要包括非線性、平衡性、相關(guān)免疫和嚴(yán)格雪崩等。最后重點(diǎn)研究了布爾函數(shù)在流密碼和分組密碼中的應(yīng)用。序列密碼體制的安全性取決于密鑰流，而密鑰流序列由密鑰流生成器產(chǎn)生，在密鑰流生成器中，布爾函數(shù)起著極其關(guān)鍵的作用。分組密碼體制的算法中最具有代表性之一的是DES算法，其設(shè)計(jì)的關(guān)鍵是盒，而多輸出布爾函數(shù)可以很好地用來(lái)描述盒。關(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)計(jì)學(xué)特性的關(guān)系趨向復(fù)雜化。擴(kuò)散性是通過(guò)將每個(gè)明文數(shù)字的影響迅速擴(kuò)散到多個(gè)輸出的密文數(shù)字中，從而來(lái)隱蔽明文數(shù)字的統(tǒng)計(jì)學(xué)特性，通過(guò)將密鑰的每個(gè)數(shù)字盡量擴(kuò)散到更多密文數(shù)字中，以此防止對(duì)密鑰進(jìn)行逐段破譯[13]。也就是說(shuō)，分組密碼應(yīng)該設(shè)計(jì)成明文的每個(gè)比特和密鑰的每個(gè)比特對(duì)密文的每個(gè)比特都產(chǎn)生影響。5.2DES算法作為分組密碼典型代表的DES算法于1977年由美國(guó)正式公布并被廣泛用于商業(yè)加密，盡管分組密碼算法還有FEAL,GOST和IDEA等算法，但DES仍被廣泛使用[10]。雖然目前AES算法已經(jīng)逐漸取代了DES算法，但是由于DES算法對(duì)現(xiàn)代分組密碼理論的應(yīng)用和發(fā)展起到了基礎(chǔ)作用，因此它的基本理論和設(shè)計(jì)思想對(duì)我們研究分組密碼仍有重要參考價(jià)值[10]。5.2.1算法描述DES(DataEncryptionStandard)算法是1972年由美國(guó)IBM公司研究的對(duì)稱(chēng)密碼體制加密算法，于1977年獲得美國(guó)政府的正式許可，因此又被稱(chēng)為美國(guó)數(shù)據(jù)加密標(biāo)準(zhǔn)。DES加密算法特點(diǎn)：分組比較短、密鑰太短、密碼生命周期短、運(yùn)算速度較慢[16]。DES的分組長(zhǎng)度為64bits。每64位明文加密成64位密文，沒(méi)有數(shù)據(jù)壓縮和擴(kuò)展，密鑰長(zhǎng)度為56bits，若輸入64bits，則第8，……64是奇偶校驗(yàn)位，所以實(shí)際密鑰只有56位[17]。DES工作的基本原理是：加密時(shí)，明文按64位進(jìn)行分組，形成明文組，加密密鑰對(duì)數(shù)據(jù)加密，解密時(shí)，解密密鑰于對(duì)數(shù)據(jù)解密[17]。實(shí)際上密鑰只用了56位，這樣更安全。DES的運(yùn)算過(guò)程如圖5-2。輸入64bits明文初始置換16輪迭代運(yùn)算64bits明文圖5-2DES算法框圖初始置換[10]是將輸入的64位明文分為8個(gè)數(shù)組，每一組包括8位，按1至64編號(hào)。在DES算法中，將56位的密鑰和分組后的64位明文組按替代或交換的方法形成密文組，即用56位密鑰來(lái)加密64位數(shù)據(jù)，其密鑰的長(zhǎng)度為56位，明文則按64位來(lái)進(jìn)行分組[17]。DES首先對(duì)輸入的64位明文進(jìn)行一次初始置換(圖5-3)，來(lái)打亂原來(lái)的次序。123………………………64輸入明文（64bits）58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157123…………………6364置換后的數(shù)據(jù)123…………323334…………6364圖5-3初始置換即將第倒是第1位換到第7位，第倒數(shù)第二位換到第6位……，由此類(lèi)推，第58位換為第1位。對(duì)置換后的分成左右兩部分，左邊記為,右邊記為。對(duì)施行在密鑰控制下的變換，結(jié)果記為,令，，（5-2-1）對(duì)施行和同樣的過(guò)程得，如此循環(huán)16次得。再對(duì)64位數(shù)字進(jìn)行初始置換的逆變換（圖5-4），即得密文。123………636464bits數(shù)據(jù)123………6364密文圖5-4初始逆置換在16次加密后并未交換，而是直接將作為的輸入，這樣就使得DES的解密和加密完全一樣，所以以上過(guò)程只需輸入密文，即可得明文[18]。如因?yàn)榈?位經(jīng)過(guò)初始置換后，，逆置換就是要將第40位換回到第1位[18]。初始置換及其逆置換其實(shí)毫無(wú)密碼學(xué)意義，這是由于置換前后其二者一一對(duì)應(yīng)關(guān)系是已知的。它們的作用是為了打亂原來(lái)輸入明文的ASCⅡ碼值的關(guān)系，并且將原來(lái)明文的第8，……，64位（校驗(yàn)位）變成輸出的一個(gè)字節(jié)[18]。5.2.2函數(shù)我們把從到的變換過(guò)程稱(chēng)作一輪加密，所以DES要經(jīng)過(guò)16輪迭代（加密）。和是第次迭代結(jié)果的左右兩個(gè)部分，每輪變換全部相同，只是數(shù)據(jù)不同，這里稱(chēng)為DES的函數(shù)，其中為32位輸入，為48位輸入，在第輪，，為由64位的初始密鑰（也稱(chēng)種子密鑰）導(dǎo)出的第輪子密鑰。為32位數(shù)字。的計(jì)算過(guò)程如下[10]：將經(jīng)過(guò)一個(gè)擴(kuò)展運(yùn)算（如圖5-5）后為48位，記為。計(jì)算,對(duì)進(jìn)行代換，此代換由8個(gè)代換盒構(gòu)成，這就是我們即將討論的S-盒，每個(gè)S-盒都有6個(gè)輸入和4個(gè)輸出[17]，將依次分為8組，每組6位，記。12………………3232bits12………………3248bits圖5-5擴(kuò)展運(yùn)算其中作為第個(gè)-盒的輸入,的輸出為，就是代換的輸出，所以代換是一個(gè)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加密的加密過(guò)程，其核心部分是由8個(gè)-盒組成的選擇壓縮運(yùn)算。每個(gè)-盒的變換規(guī)則是：取上的4個(gè)置換，也就是它的四個(gè)排列排成4行，也就得一個(gè)416矩陣。如果給定該-盒的輸入為，其輸出對(duì)應(yīng)該矩陣的第行、列所對(duì)應(yīng)數(shù)的二進(jìn)制表示。這里的二進(jìn)制表示為，的二進(jìn)制表示為。如此一來(lái)，每個(gè)-盒均可用一個(gè)416矩陣或數(shù)表來(lái)表示[10]。8個(gè)-盒的表示見(jiàn)表5-1。表5-1-盒函數(shù)S11441312151183106125907015741421311061211953841148136211151297310501512824917511314100613S21518146113497213120510313471528141201106911501471110413158126932151381013154211671205149S31009146315511312711428137093461028514121115113649815301112125101471101306987415143115212S47131430691012851112415138115615034721211014910690121171315131452843150610113894511127214S52124171011685315130149141121247131501510398645111101378159125630141181271142136150910453S61211015926801334147511101542712956113140113891415528123704101131164321295151011141760813S74112141508133129751061130117491101435122158614111312371410156805926111381410795015142312S81328461511110931450127115138103741256110149271141912142061013153582114741081315129035611盒的設(shè)計(jì)是DES的關(guān)鍵部分，每個(gè)盒均可看成是一個(gè)從到的多輸出函數(shù)，即4個(gè)6元布爾函數(shù)組成的函數(shù)組，可通過(guò)表5-1給出的8個(gè)盒的布爾函數(shù)表示，如盒的布爾函數(shù)表示為[19]（5-2-2）是4個(gè)6元布爾函數(shù)，表達(dá)式如下：其余見(jiàn)參考文獻(xiàn)[19]，或直接由表5-1給出。可見(jiàn)，盒可用多輸出函數(shù)（布爾函數(shù)組）來(lái)表示，從而通過(guò)對(duì)多輸出函數(shù)和布爾函數(shù)的研究來(lái)分析盒的性能。綜上所述，可以看出布爾函數(shù)既是分組密碼的重要組成部分，也是其設(shè)計(jì)的重要工具之一，為使密碼系統(tǒng)具有一定的性能，布爾函數(shù)不得不滿足一定的設(shè)計(jì)準(zhǔn)則。5.3分組密碼中布爾函數(shù)的設(shè)計(jì)準(zhǔn)則根據(jù)前面對(duì)分組密碼的討論我們知道，盒的設(shè)計(jì)是分組密碼設(shè)計(jì)過(guò)程中的重要部分，且盒的性能對(duì)整個(gè)密碼系統(tǒng)的安全性起決定性作用，而盒可用多輸出布爾函數(shù)來(lái)描述[16]。因此，為保證分組密碼系統(tǒng)能滿足5.1.3節(jié)提出的設(shè)計(jì)原則，密碼系統(tǒng)設(shè)計(jì)中的布爾函數(shù)必須滿足一定的設(shè)計(jì)準(zhǔn)則，概括起來(lái)有如下幾點(diǎn)[10]：正交性定義5.3.1設(shè)，，若對(duì)任意，集合（5-3-1）中恰有個(gè)元素，則稱(chēng)是正交的。定理5.3.2設(shè)，，正交的充分必要條件是：對(duì)任意，時(shí)，是平衡函數(shù)。正交性在單輸出時(shí)即為布爾函數(shù)的平衡性，在多輸出時(shí)亦可轉(zhuǎn)化為其平衡性，所以正交性是保證盒安全性的必要條件。如果盒（為了方便，常將盒與對(duì)應(yīng)的多輸出布爾函數(shù)視為相同，本章在敘述時(shí)對(duì)二者不加其別）無(wú)正交性，那么在隨機(jī)均勻輸入的情況下，盒的某些輸出將反復(fù)出現(xiàn)，因此密碼分析者可以利用這一特點(diǎn)對(duì)基于盒的密碼體制實(shí)施攻擊。高代數(shù)次數(shù)從在第二章我們對(duì)布爾函數(shù)的代數(shù)次數(shù)的定義可以知道，代數(shù)次數(shù)低的盒是不具備安全性，因此盒必須有一定的代數(shù)次數(shù)。高非線性度要使盒能抵抗線性分析，就必須具有較高的非線性度。擴(kuò)散準(zhǔn)則和嚴(yán)格雪崩準(zhǔn)則由5.1.3節(jié)知擴(kuò)散性是對(duì)盒的一個(gè)基本要求。，擴(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ù)在對(duì)序列密碼和分組密碼的設(shè)計(jì)和分析中起著不可替代的重要作用。文中首先介紹了密碼學(xué)相關(guān)的基礎(chǔ)知識(shí)，概述了密碼學(xué)以及密碼體制的分類(lèi)；對(duì)布爾函數(shù)進(jìn)行了定義，對(duì)其各種表示方法和研究方法進(jìn)行介紹，主要介紹了真值表，小項(xiàng)表示等。同時(shí)討論了布爾函數(shù)的密碼學(xué)性質(zhì)，重點(diǎn)介紹了其Walsh譜變換，布爾函數(shù)的相關(guān)免疫性和平衡性等，利用平衡性定義了其他幾種性質(zhì)，并引出Bent函數(shù)的定義?；谝陨蟽?nèi)容，本文重點(diǎn)研究了布爾函數(shù)在密碼學(xué)中的應(yīng)用。其應(yīng)用主要在序列密碼和分組密碼。流密碼體制的安全性依賴(lài)于密鑰流，而密鑰流序列產(chǎn)生于密鑰流生成器，位移寄存器作為密鑰流生成器的重要組成部分成為我們介紹的重點(diǎn)，并得到諸多結(jié)論（詳見(jiàn)4.3節(jié)）。分組密碼算法中最具有代表性的便是DES算法，而DES算法設(shè)計(jì)的關(guān)鍵在于盒的設(shè)計(jì)，從而盒的性能對(duì)整個(gè)密碼系統(tǒng)的安全性起決定性作用，而盒可用多輸出布爾函數(shù)來(lái)描述。文中我們不僅介紹了分組密碼的設(shè)計(jì)原理，還著重介紹了DES算法中的盒，最后給出了盒的布爾函數(shù)表示，如盒表示為是4個(gè)6元布爾函數(shù)，其表達(dá)式見(jiàn)5.3節(jié)?？傊芯棵艽a學(xué)中的布爾函數(shù)，特別是分組密碼中的布爾函數(shù)是一個(gè)浩大的工程，仍有很多工作要做，一般有限域上的布爾函數(shù)很可能成為以后研究的重點(diǎn)，例如更廣義的代數(shù)免疫，能否將代數(shù)免疫性推廣到一般有限域。此外，文中多處均引用了已有著作中的結(jié)論，在此表示感謝。限于水平有限，難免有謬誤之處，望各位教授、老師和同學(xué)積極指正。參考文獻(xiàn)[1]王相生.序列密碼設(shè)計(jì)與實(shí)現(xiàn)的研究[D].中國(guó)科學(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