密碼學(xué)課件 現(xiàn)代密碼學(xué)基本理論

密碼學(xué)導(dǎo)論IntroductiontoCryptology主講教師：李衛(wèi)海第2章現(xiàn)代密碼學(xué)基本理論現(xiàn)代密碼學(xué)基本理論密碼學(xué)基本概念密碼系統(tǒng)的概率模型實(shí)際安全信息度量與冗余冗余與理論安全現(xiàn)代密碼學(xué)基本理論密碼學(xué)基本概念密碼系統(tǒng)的概率模型實(shí)際安全信息度量與冗余冗余與理論安全什么是密碼學(xué)密碼學(xué)Cryptology源于希臘語(yǔ)kryptós“隱藏的”,和gráphein“書(shū)寫(xiě)”研究如何對(duì)己方信息及信息傳遞進(jìn)行保護(hù)，如何對(duì)敵方信息進(jìn)行破譯的科學(xué)。包含三個(gè)方面的內(nèi)容密碼編碼學(xué)Cryptography：研究如何將信息用秘密文字的形式加以保護(hù)密碼分析學(xué)Cryptanalysis：研究如何從秘密形式的文字中提取原始信息密碼協(xié)議CryptographyProtocol：使用密碼技術(shù)的通信協(xié)議，在網(wǎng)絡(luò)環(huán)境中提供各種安全服務(wù)攻擊模型——黑盒模型攻擊者并未實(shí)質(zhì)性地接觸到密鑰或任何內(nèi)部操作，僅能觀察到一些外部信息或操作攻擊類型攻擊者的能力唯密文攻擊COACiphtext-only待分析密文已知明文攻擊KPAKnown-plaintext用同一密鑰加密的一個(gè)或多個(gè)明文－密文對(duì)待分析密文選擇明文攻擊CPAChosen-plaintext可選擇特定明文，并獲得對(duì)應(yīng)的密文待分析密文選擇密文攻擊CCAChosen-ciphertext可選擇特定密文，并獲得對(duì)應(yīng)的明文待分析密文選擇文本攻擊

CCAChosen-text可選擇特定密文/明文，并獲得對(duì)應(yīng)明文/密文待分析密文相關(guān)密鑰攻擊Related-key有確定關(guān)系的兩個(gè)密鑰對(duì)應(yīng)的明文-密文對(duì)待分析密文攻擊者能力可以獲取加密機(jī)結(jié)果，不可以獲取解密機(jī)結(jié)果CCA1:能獲取解密機(jī)結(jié)果。但在某事件（如獲得真實(shí)密文）后，不能再訪問(wèn)解密機(jī)（午餐攻擊模型）CCA2：適應(yīng)性選擇密文攻擊（AdaptivelyChosenCiphertextAttack）任何時(shí)候都能獲取解密機(jī)的結(jié)果（凌晨攻擊模型）攻擊模型——灰盒模型、白盒模型灰盒模型：攻擊者可以實(shí)質(zhì)性地接觸到部分密鑰或泄露的信息邊信道攻擊（側(cè)信道攻擊），依賴于密碼實(shí)現(xiàn)產(chǎn)生的信息源，使得攻擊者可以觀察或測(cè)量到密碼實(shí)施時(shí)的某些特征對(duì)軟件實(shí)現(xiàn)，可以是執(zhí)行時(shí)間、返回值、錯(cuò)誤消息等對(duì)硬件實(shí)現(xiàn)，可以是電磁輻射、功率、噪聲等侵入式攻擊，成本高昂，攻擊者可以向軟件或硬件中注入干擾信息、或修改，觀察運(yùn)行的變化白盒模型：攻擊者清楚密碼實(shí)現(xiàn)的所有細(xì)節(jié)，有能力實(shí)施侵入式攻擊，可以隨意修改攻擊者往往能夠獲得一定的物理接觸權(quán)限，灰盒模型比黑盒模型更為現(xiàn)實(shí)重要場(chǎng)合下，攻擊者往往會(huì)通過(guò)社會(huì)工程學(xué)獲得所需要的細(xì)節(jié)，白盒模型比灰盒模型更為嚴(yán)謹(jǐn)現(xiàn)代密碼學(xué)基本原則柯克霍夫原則（Kerckhoffs'sprinciple，1883）系統(tǒng)必須是實(shí)際安全（即時(shí)不是被數(shù)學(xué)證明的），不可破譯的密碼系統(tǒng)不被保密，且可能落入敵手密鑰可以隨時(shí)通過(guò)通信更新、可保存、可修改可用于電信通訊設(shè)備與文檔是便攜的，不需要若干人聚在一起來(lái)操作它系統(tǒng)是便于使用的，不需要精神緊張地工作，也不需要遵守一長(zhǎng)串規(guī)則香農(nóng)箴言（Shannon'smaxim）敵人了解系統(tǒng)密碼系統(tǒng)的安全性不在于算法的保密，而在于當(dāng)對(duì)手獲知了算法和密文后，分析出密鑰或明文的難度AugusteKerckhoffs安全目標(biāo)

安全目標(biāo)/安全屬性含義單向性O(shè)WOne-Wayness攻擊者不能計(jì)算出任何密文所對(duì)應(yīng)的明文不可區(qū)分性INDIndistinguishability不可延展性NMNon-Malleability密碼系統(tǒng)的安全性無(wú)條件安全unconditionalsecurity即使有無(wú)限的資源和時(shí)間，都無(wú)法唯一地破譯確定密文安全性最強(qiáng)的，但僅有一次一密體制是無(wú)條件安全的實(shí)際安全practicalsecurity包括可證明安全和計(jì)算上安全可證明安全provablesecurity破譯密碼的難度與數(shù)學(xué)上某個(gè)困難問(wèn)題的難度相同計(jì)算上安全computationalsecurity破譯密碼的代價(jià)超出密文信息的價(jià)值；或破譯密碼的時(shí)間超出密文信息的有效生命期密碼系統(tǒng)安全性的考慮一次一密成本太高，極少使用可證明安全：難度隨著問(wèn)題的規(guī)模而改變計(jì)算能力飛速發(fā)展，使用多大的規(guī)模能保證在未來(lái)是安全的？量子技術(shù)有望解決數(shù)學(xué)難題計(jì)算安全：價(jià)值是相對(duì)的，有效生命期也是相對(duì)的為保證實(shí)際安全，必須明確系統(tǒng)所要保護(hù)的對(duì)象、所要對(duì)抗的攻擊，適當(dāng)?shù)剡x擇系統(tǒng)的計(jì)算規(guī)模保守地估計(jì)系統(tǒng)使用年限在說(shuō)明系統(tǒng)的計(jì)算安全程度時(shí)，必須列舉所假設(shè)的資源條件設(shè)計(jì)密碼系統(tǒng)時(shí)的基本要求遵從柯克霍夫原則，且是實(shí)際安全的實(shí)用性：該加密的嚴(yán)格加密，無(wú)需加密的不加密不應(yīng)使通信網(wǎng)絡(luò)的效率過(guò)分降低系統(tǒng)應(yīng)易于實(shí)現(xiàn)，使用方便從時(shí)延、成本、軟硬件出錯(cuò)概率等角度的考慮，傾向于使用數(shù)學(xué)上計(jì)算復(fù)雜，但易于實(shí)現(xiàn)的密碼系統(tǒng)便于使用，不使操作者過(guò)于勞累。否則一方面容易出錯(cuò)，另一方面會(huì)誘使操作者采取偷懶的方式，而這往往會(huì)危及整個(gè)密碼系統(tǒng)密鑰應(yīng)當(dāng)可以隨時(shí)更改加解密算法適用于密鑰空間中的所有元素，或者應(yīng)把“弱密鑰”全部列出某些密鑰對(duì)特定算法會(huì)泄漏明文信息，稱之為弱密鑰密碼體制密碼體制：整個(gè)密碼系統(tǒng)的基本工作方式密碼體制的基本要素是密碼算法和密鑰密碼算法是一些公式、法則或程序；密鑰是密碼算法中的控制參數(shù)。密碼體制的主要參數(shù)：編碼的運(yùn)算類型：代換、置亂、數(shù)域計(jì)算密鑰長(zhǎng)度；密鑰形式：加解密密鑰是否一致，是否需要保密處理明文的方法：順序地處理（序列）或一組一組地處理（分組）密文的膨脹：密文的長(zhǎng)度是否與明文長(zhǎng)度一致密文錯(cuò)誤的傳播加密和解密的運(yùn)算復(fù)雜度編碼過(guò)程是否可逆……常見(jiàn)密碼體制分類根據(jù)密鑰的形式分類：對(duì)稱密碼體制（SymmetricSystem,One-keySystem,Secret-keySystem）（單密鑰）加密密鑰與解密密鑰相同，或者可以方便地相互導(dǎo)出加密能力與解密能力是緊密結(jié)合，能加密就能解密密鑰必須嚴(yán)格保護(hù)，開(kāi)放性差非對(duì)稱密碼體制（AsymmetricSystem,Two-keySystem,Public-keySystem）（雙密鑰）加密密鑰與解密密鑰不同，并且從一個(gè)密鑰導(dǎo)出另一個(gè)密鑰是計(jì)算上不可行的加密能力與解密能力是分開(kāi)的可以公開(kāi)一個(gè)密鑰，開(kāi)放性好無(wú)密鑰算法通常是單向運(yùn)算主要用于驗(yàn)證常見(jiàn)密碼體制分類根據(jù)處理明文的方式分類：分組密碼體制（BlockCipher）以若干比特（通常大于64比特）的數(shù)據(jù)塊為處理單元加密/解密運(yùn)算相對(duì)較為復(fù)雜使用原始密鑰處理每一個(gè)數(shù)據(jù)塊同一明文塊對(duì)應(yīng)的密文塊相同序列密碼體制/流密碼體制（StreamCipher）以比特（有時(shí)也用字節(jié)）為單位進(jìn)行加密/解密運(yùn)算加密/解密運(yùn)算通常非常簡(jiǎn)單常使用一個(gè)發(fā)生器，由原始密鑰產(chǎn)生長(zhǎng)密鑰流，用密鑰流處理明文/密文同一明文對(duì)應(yīng)的密鑰流、密文一般不同常見(jiàn)密碼體制分類根據(jù)密文的唯一性分類：確定型密碼體制（DeterministicCipher）當(dāng)明文和密鑰確定后，密文唯一并不排除不同明文用不同密鑰加密會(huì)得到同一密文概率型密碼體制（ProbabilisticCipher）當(dāng)明文和密鑰確定后，密文從一個(gè)密文子集中隨機(jī)產(chǎn)生解密時(shí)，有的算法能夠唯一確定明文，有的算法需要接收者從多個(gè)可能中選出正確的明文可以增加字典攻擊的難度字典攻擊：對(duì)同一密鑰加密的明文-密文對(duì)編制一個(gè)字典，通過(guò)查表的方式得到新截獲的密文所對(duì)應(yīng)的明文常見(jiàn)密碼體制分類根據(jù)加密算法的可逆性分類：可逆變換型密碼算法（ReversibleTransformation）加密、解密變換互逆，一般用于數(shù)據(jù)的加密/解密具體算法多采用單向陷門(mén)函數(shù)，即正向變換計(jì)算簡(jiǎn)單，逆向變換在知道陷門(mén)信息的情況下計(jì)算簡(jiǎn)單，否則計(jì)算上不可行單向函數(shù)型密碼算法（One-wayfunction）只能進(jìn)行正向變換，不可逆適用于不需要解密的場(chǎng)合利用密文做口令、驗(yàn)證碼、…密碼系統(tǒng)的數(shù)學(xué)模型一般而言，密碼系統(tǒng)可以表示為一個(gè)五元組：S＝{P,C,K,E,D} P：明文空間 C：密文空間 K：密鑰空間 E：加密變換 D：解密變換 P也常用消息空間M代替。信源加密器E解密器D信息M加密密鑰kE解密密鑰kD密文C信息M

單向函數(shù)和單向陷門(mén)函數(shù)一函數(shù)f若滿足下列條件，則稱f為單向函數(shù)(One-wayFunction)：(1)對(duì)于所有屬于f定義域的任一x，容易計(jì)算y=f(x)；(2)對(duì)于幾乎所有屬于f值域的任一y，求得x，使y=f(x),則在計(jì)算上不可行。“可逆”函數(shù)F若滿足下列二條件，則稱F為單向陷門(mén)函數(shù)(One-wayTrapdoorFunction)：(1)對(duì)于所有屬于F定義域的任一x，容易計(jì)算F(x)=y；(2)對(duì)于幾乎所有屬于F值域的任一y，如果獲得暗門(mén)信息(trapdoor)，則容易求出x=F-1(y)；否則求解x=F-1(y)在計(jì)算上不可行。F-1為F之逆函數(shù)。單向陷門(mén)函數(shù)是實(shí)現(xiàn)加密器/解密器的基礎(chǔ)現(xiàn)代密碼學(xué)基本理論密碼學(xué)基本概念密碼系統(tǒng)的概率模型實(shí)際安全信息度量與冗余冗余與理論安全密碼系統(tǒng)的概率模型1948年，“AMathematicalTheoryofCommunication”在數(shù)學(xué)上奠定信息論基礎(chǔ)1949年，“CommunicationTheoryofSecrecySystems”從信息論角度奠定密碼學(xué)理論基礎(chǔ)ClaudeElwoodShannon密碼系統(tǒng)的概率模型消息空間：有限消息集合M信源以先驗(yàn)概率q1,q2,…,qr產(chǎn)生消息m1,m2,…,mr無(wú)意義消息的概率為0密鑰集空間：有限密鑰空間K密鑰源以先驗(yàn)概率p1,p2,…,ps產(chǎn)生密鑰k1,k2,…,ks密文空間：有限密文集合C密文c1,c2,…,ct的先驗(yàn)概率由消息和密鑰的先驗(yàn)概率共同決定信源加密器E解密器D信息M密鑰k密鑰k密文C信息M密碼系統(tǒng)的概率模型密碼系統(tǒng)：是一族可逆映射，從消息空間映射到密文空間。其中各映射具有一定的使用概率，由實(shí)際密鑰確定具體的映射可逆映射E1,E2,…,Es的使用概率為p1,p2,…,ps解密映射D1,D2,…,Ds分別與加密映射E1,E2,…,Es互逆密碼系統(tǒng)相同：是指映射集、消息空間、密文空間、密鑰空間相同，且相應(yīng)的先驗(yàn)概率相同信源加密器E解密器D信息M密鑰k密鑰k密文C信息M密碼系統(tǒng)概率模型下的基本原則柯克霍夫原則：公開(kāi)加密映射族、解密映射族公開(kāi)明文的先驗(yàn)概率qi和密鑰的先驗(yàn)概率pi公開(kāi)密文僅保密實(shí)際消息和實(shí)際密鑰密碼分析員利用密文和消息、密鑰的先驗(yàn)概率，計(jì)算消息和密鑰的后驗(yàn)概率當(dāng)某個(gè)消息或密鑰的后驗(yàn)概率接近為1，其它的接近0時(shí)，則該密文被破譯當(dāng)多個(gè)不可區(qū)分的消息的后驗(yàn)概率均較大時(shí)，則該密文破譯失敗密碼系統(tǒng)概率模型的映射圖左側(cè)是消息集合，右側(cè)是密文集合某消息在密鑰作用下映射用連線表示對(duì)每個(gè)消息，每個(gè)密鑰引出各自的連線m1m2m3m4c1c2c3c4333311112222若干問(wèn)題的說(shuō)明將消息視為一個(gè)整體，不考慮消息內(nèi)部文字間的關(guān)系消息可視為一個(gè)馬爾克夫鏈隨機(jī)過(guò)程，不同消息的概率由馬爾克夫鏈決定若以單字母為消息，則消息的先驗(yàn)概率即普通字母的統(tǒng)計(jì)概率若以單詞為消息，則消息的先驗(yàn)概率為詞匯的統(tǒng)計(jì)概率若以有意義的句子為消息，則先驗(yàn)概率與具體環(huán)境有關(guān)模型里將消息簡(jiǎn)化，用一個(gè)符號(hào)mi代替，并賦予一個(gè)概率基本密碼系統(tǒng)中不考慮多次加密復(fù)雜密碼系統(tǒng)可以由多個(gè)基本密碼系統(tǒng)構(gòu)成可能的密鑰與實(shí)際的密鑰同等重要存在可能的密鑰，將密文映射為與明文不同且有意義的消息。正是這些可能的密鑰提供了密碼系統(tǒng)的安全性例：英文單表代換的概率模型消息集以單字母為消息以有意義的單詞為消息以有意義的句子為消息密鑰集每個(gè)代換表是一個(gè)密鑰，有26!個(gè)可能的等概率密鑰密鑰的實(shí)際先驗(yàn)概率略高（存在部分不可用密鑰）密文集與消息和密鑰相關(guān)閉合系統(tǒng)閉合系統(tǒng)：對(duì)任意密文，都有每個(gè)密鑰所對(duì)應(yīng)的映射連入任意密文用任意密鑰解密，都對(duì)應(yīng)一個(gè)消息集中的消息性質(zhì)：對(duì)確定型密碼體制，明文和密文數(shù)相等。對(duì)任一固定密鑰，不可能有多對(duì)一映射（不唯一解密運(yùn)算），也不可能有一對(duì)多映射（不唯一加密運(yùn)算）非閉合系統(tǒng)c1c2c3m1m2132213m1m2m3m4c1c2c3c4123123123123閉合系統(tǒng)非閉合系統(tǒng)單純密碼定義：若對(duì)密碼系統(tǒng)T中任意三個(gè)映射Ti,Tj,Tk都存在映射Ts滿足TiTj-1Tk=Ts，且所有密鑰的作用是相仿的，則稱T是單純的。否則，T是混合的。單純系統(tǒng)一定是閉合的c1c2c3m1m2132213m1m2m3m4c1c2c3c4123123123123m1m2m3m4c1c2c3c41234123423413421單純密碼混合密碼混合密碼單純密碼的剩余類劃分定理：?jiǎn)渭兠艽a中，消息可以劃分為剩余類R1,R2,…,Rs，密文也可劃分為剩余類R'1,R'2,…,R's，具有如下性質(zhì)：消息剩余類（或密文剩余類）是互斥的，Ri類中任一消息對(duì)應(yīng)的密文必在R'i類中，R'i類中任一密文對(duì)應(yīng)的消息必在Ri類中剩余類劃分的規(guī)則m1m2m3m4c1c2c3c4m5m6m7c5c6c7R1R2R3R'1R'2R'3單純密碼的剩余類劃分剩余類集的例子：?jiǎn)伪泶鷵Q是單純密碼系統(tǒng)。密文c與TiTk-1c屬于同一剩余類。例如，c=XCPPGCFQ，c1=RDHHGDSN，c2=ABCCDBEF等等屬于同一剩余類。可以看到，它們有相同的字母重復(fù)模式凱撒密碼是單純密碼系統(tǒng)。字母差距恒定的密文屬于同一剩余類。c,c+1,c+2,…,c+25屬于同一剩余類。破譯時(shí)，只須列出該剩余類中的25個(gè)消息，挑出有意義的一個(gè)周期為d的維吉尼亞密碼是單純密碼系統(tǒng)。消息m與跟m周期性等差的明文屬于同一剩余類。滿足mi-mi+kd=ci-ci+kd為確定值的屬于同一剩余類周期為d的置換密碼是單純密碼系統(tǒng)。剩余類中元素的特征為：字符的移位不跨越長(zhǎng)度為d的塊；兩個(gè)距離為d的字符在置換后距離仍為d單純密碼的剩余類劃分定理：?jiǎn)渭兠艽a中，消息可以劃分為剩余類R1,R2,…,Rs，密文也可劃分為剩余類R'1,R'2,…,R's，具有如下性質(zhì)：Ri類中的消息數(shù)等于R'i類中的密文數(shù)每個(gè)剩余類都是閉合的m1m2m3m4c1c2c3c4m5m6m7c5c6c7R1R2R3R'1R'2R'3單純密碼的剩余類劃分定理：?jiǎn)渭兠艽a中，消息可以劃分為剩余類R1,R2,…,Rs，密文也可劃分為剩余類R'1,R'2,…,R's，具有如下性質(zhì)：消息（密文）數(shù)是密鑰數(shù)s的因子，記為φiRi類中的每一條消息都可以通過(guò)s/φi個(gè)不同密鑰映射到R'i類中的某一條密文；解密類似根據(jù)單純系統(tǒng)定義和剩余類劃分方法，每對(duì)消息、密文間都有映射，因此密鑰數(shù)不小于消息（密文）數(shù)密鑰作用相仿，隱含從每個(gè)消息（密文）引出的映射數(shù)相同m1m2m3m4c1c2c3c4m5m6m7c5c6c7R1R2R3R'1R'2R'3單純密碼的安全性

單純密碼的安全性

單純密碼的安全性

相似密碼系統(tǒng)

現(xiàn)代密碼學(xué)基本理論密碼學(xué)基本概念密碼系統(tǒng)的概率模型實(shí)際安全信息度量與冗余冗余與理論安全信息量與熵什么是信息？信息是消息的有效內(nèi)容信息蘊(yùn)涵于事件的不確定性之中例：事件：明年我校男生比女生多——幾乎是必然的，信息量趨于零明年我校女生比男生多——可能性很小，信息量極大獲得的信息量入學(xué)前，有大于/小于/等于三種可能，存在不確定性入學(xué)后，僅存一種結(jié)果，獲得信息，不確定性降為零信息量=消息獲得前的不確定性信息量與熵

本課程對(duì)信息論方面的公式只要求定性理解條件熵

聯(lián)合熵

幾個(gè)有用公式

消息中的冗余

消息中的冗余例：有人統(tǒng)計(jì)英語(yǔ)冗余度的上限為80%，下限為67%，平均值為73%俄語(yǔ)的冗余度平均值約為70%現(xiàn)代漢語(yǔ)冗余度的上限為73%，下限為55%，平均值為63%，文言文的冗余度就更低了例：全班45人的成績(jī)單，信息量45log2101≈299.62比特<38字節(jié)以txt文本存儲(chǔ)，約需134字節(jié)，冗余度0.72將該文件用RAR壓縮，約需91字節(jié)，冗余度0.58壓縮的意義：減少冗余冗余度給出無(wú)損壓縮比的極限1/(1-D)現(xiàn)代密碼學(xué)基本理論密碼學(xué)基本概念密碼系統(tǒng)的概率模型實(shí)際安全信息度量與冗余冗余與理論安全完美安全Perfect

Secrecy

完美安全對(duì)密鑰量的需求

密碼分析過(guò)程的概率模型在截獲消息前，給每個(gè)消息和密鑰設(shè)定一個(gè)先驗(yàn)概率待截獲長(zhǎng)度為N的消息后，計(jì)算相應(yīng)的后驗(yàn)概率通常，隨著N的增加，多數(shù)消息的后驗(yàn)概率降低，少數(shù)增加，直至最后只剩下一個(gè)消息后驗(yàn)概率接近于1，其它接近0。右表是凱撒密碼作用在英文文本上的實(shí)例及分析模糊度

模糊度的性質(zhì)

乘積密碼的模糊度

模糊度與冗余

模糊度與冗余

唯一解距離

唯一解距離例：英文單表代換密碼消息的唯一解距離約27個(gè)字母唯一解距離

密碼破譯的確認(rèn)當(dāng)宣稱某種密碼系統(tǒng)和密鑰被破譯時(shí)，若使用的密文長(zhǎng)度遠(yuǎn)大于唯一解距離，則可能是真的若使用的密文長(zhǎng)度相當(dāng)于或小于唯一解距離，則很可疑注意：唯一解距離是針對(duì)唯密文攻擊所做的分析，實(shí)際操作中往往會(huì)采用更有效的方式唯一解距離是統(tǒng)計(jì)期望的結(jié)果，實(shí)際所需的密文長(zhǎng)度通常遠(yuǎn)大于唯一解距離理想安全

理想安全系統(tǒng)的弱點(diǎn)密碼系統(tǒng)與語(yǔ)言必須緊密結(jié)合，從而消除冗余影響為實(shí)現(xiàn)理想安全，可先壓縮自然文本，去除冗余去除冗余后，任何閉合的密碼系統(tǒng)都可以達(dá)到要求壓縮技術(shù)越精細(xì)，最終的輸出就越接近理想安全壓縮的局限自然語(yǔ)言極其復(fù)雜，徹底消除冗余的壓縮映射必然非常復(fù)雜，系統(tǒng)必須花費(fèi)極大的存儲(chǔ)代價(jià)——字典語(yǔ)法結(jié)構(gòu)的輕微改變，可能使系統(tǒng)變得非常脆弱一般而言，壓縮映射算法在容錯(cuò)方面性能很差。密文字符的錯(cuò)誤，會(huì)導(dǎo)致相當(dāng)大區(qū)域（視語(yǔ)法結(jié)構(gòu)而言）的錯(cuò)誤對(duì)自然語(yǔ)言，只能近似滿足理想要求：唯一解距離設(shè)計(jì)得足夠大系統(tǒng)的復(fù)雜度隨著唯一解距離增大而迅速增加無(wú)窮大唯一解距離（理想安全）要求無(wú)窮復(fù)雜的系統(tǒng)現(xiàn)代密碼學(xué)基本理論密碼學(xué)基本概念密碼系統(tǒng)的概率模型實(shí)際安全信息度量與冗余冗余與理論安全破譯工作量定義：破譯工作量是唯密文分析確定密鑰所需的平均工作量（單位：工時(shí)）是實(shí)際安全的一個(gè)主觀量化度量定義：隨機(jī)變量X的最小熵是對(duì)X的任一次實(shí)驗(yàn)，至少能獲得的信息量。隨機(jī)變量的最小熵是它的信息量的一個(gè)下界實(shí)驗(yàn)前的最少模糊度，常用來(lái)作為一個(gè)隨機(jī)變量在最壞情況下的不可預(yù)測(cè)性度量，對(duì)應(yīng)的是敵手破譯該密碼系統(tǒng)所需要的最少平均嘗試次數(shù)（即敵手猜出最常用口令的難度）解不唯一解唯一工作量趨于穩(wěn)定英文單表代換密鑰的破譯工作量破譯工作量實(shí)際安全系統(tǒng)，要求在它所希望傳輸?shù)淖址糠秶鷥?nèi)破譯工作量足夠高具有有限資源的攻擊者在合理的時(shí)間內(nèi)不能破譯系統(tǒng)問(wèn)題是，破譯工作量W(N)多大系統(tǒng)才安全？例：假定每秒可以計(jì)算100萬(wàn)次，即10-6sec/computeNW(N)N52NN!100.1s0.001s3.6s100104s≈2.8h1.3*1024s≈4.0*1016y9.3*10151s≈3.0*10144y1000109s≈31.7y1.1*10295s≈3.4*10287y∞破譯工作量設(shè)一個(gè)好的密碼系統(tǒng)，必須將破譯工作量最大化，最小熵最大化要考慮標(biāo)準(zhǔn)密碼分析方法要確保沒(méi)有任何捷徑可以破譯密碼——很難！如何確認(rèn)一個(gè)非理想系統(tǒng)的唯一解距離足夠大，用任何方法分析都需要極大的工作量？用數(shù)學(xué)上的難題做保證——可證明安全用計(jì)算上的難題做保證——計(jì)算安全研究密碼分析員可能使用的每一種方法，總結(jié)出抵制規(guī)律，在設(shè)計(jì)密碼系統(tǒng)時(shí)應(yīng)用這些規(guī)律設(shè)計(jì)系統(tǒng)，使得它的破解工作等價(jià)于某些復(fù)雜性問(wèn)題下面我們將討論密碼分析員常用的分析方法蠻力搜索攻擊蠻力搜索（BruteForceSearch）或窮舉搜索（CompleteTrialandError）嘗試每個(gè)可能的密鑰原則上幾乎所有密碼系統(tǒng)都可以攻破是一種基本的攻擊方式，計(jì)算量與密鑰空間大小成正比假設(shè)密鑰空間大小為K，每個(gè)密鑰的概率相等，則平均需要嘗試K/2次，可以獲得結(jié)果假設(shè)一個(gè)密碼系統(tǒng)只能靠蠻力搜索破譯，且密鑰空間足夠大，是否安全？密鑰大小密鑰空間大小所需時(shí)間（設(shè)每次嘗試需1μs）32bit232=4.3*10935.8min56bit256=7.2*10161142year128bit2128=3.4*10385.4*1024year1024bit21024=1.8*103082.9*10294year26個(gè)字符26!=4.0*10266.4*1012year蠻力搜索攻擊：分組嘗試聰明的蠻力破解：從高可能性密鑰到低可能性密鑰逐步嘗試分組嘗試分組嘗試?yán)悍Q金幣問(wèn)題。有27枚金幣，

其中一個(gè)是假的。假的比真的略輕?，F(xiàn)在

有一個(gè)天平，問(wèn)最少幾次可以找出假幣？答案：三次。先分三堆，9個(gè)一堆。隨意稱兩堆。若不平衡，則假幣在輕的一堆中，若平衡，則假幣在未稱的一堆再分三堆，3個(gè)一堆。用上面做法選出一堆最后剩三個(gè)。用上面方法找出假幣蠻力搜索攻擊：分組嘗試

蠻力搜索攻擊：分組嘗試

統(tǒng)計(jì)攻擊設(shè)字頻統(tǒng)計(jì)將26個(gè)字母分為4組：2,9,9,6，則其密鑰模糊度由log226!≈88.4bits降為log22!9!9!6!≈47.4bits，減少了41bits。統(tǒng)計(jì)攻擊的一般步驟（攻擊密鑰）：選擇一個(gè)僅依賴于密鑰，而對(duì)明文不敏感的統(tǒng)計(jì)特征SK在密文中統(tǒng)計(jì)SK根據(jù)