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

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

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

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

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

單純密碼的安全性

單純密碼的安全性

相似密碼系統(tǒng)

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

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

聯(lián)合熵

幾個有用公式

消息中的冗余

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

Secrecy

完美安全對密鑰量的需求

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

模糊度的性質(zhì)

乘積密碼的模糊度

模糊度與冗余

模糊度與冗余

唯一解距離

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

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

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

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

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

蠻力搜索攻擊：分組嘗試

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