第2章密碼學(xué)的基本概念和信息理論基礎(chǔ)

1主要內(nèi)容2.1基本概念2.2經(jīng)典密碼及其破譯2.3Shannon的保密系統(tǒng)信息理論2.4Simmons認(rèn)證系統(tǒng)的信息理論22.1基本概念2.1.1什么是密碼學(xué)2.1.2密碼學(xué)的發(fā)展歷史2.1.3五個(gè)術(shù)語2.1.4密碼體制的分類2.1.5密碼分析2.1.6加密的功能32.1.1什么是密碼學(xué)密碼學(xué)是研究密碼系統(tǒng)或通信系統(tǒng)的一門學(xué)科，分為密碼編碼學(xué)和密碼分析學(xué)。密碼編碼者密碼分析者42.1.2密碼學(xué)的發(fā)展歷史第1階段：1949年以前。

第2階段：從1949年到1975年。標(biāo)志：1949年Shannon發(fā)表的《保密系統(tǒng)的信息理論》一文。第3階段：1976年至今。標(biāo)志：1976年Diffie和Hellman發(fā)表了《密碼學(xué)新方向》一文。5古典加密早妝未罷暗凝眉，迎戶愁看紫燕飛，無力回天春已老，雙棲畫棟不如歸。6Shannon模型72.1.3五個(gè)術(shù)語X,明文（plain-text）：作為加密輸入的原始信息。Y,密文（cipher-text）：對明文變換的結(jié)果。E,加密（encrypt）：是一組含有參數(shù)的變換。D,解密（decrypt）：加密的逆變換。Z,密鑰（key）：是參與加密解密變換的參數(shù)。82.1.4密碼體制的分類幾種不同的分類標(biāo)準(zhǔn)按操作方式進(jìn)行分類操作方式：是明文變換成密文的方法替代操作、置換操作、復(fù)合操作按照使用密鑰的數(shù)量進(jìn)行分類對稱密鑰（單密鑰）公開密鑰（雙密鑰）按照對明文的處理方法進(jìn)行分類流密碼分組密碼9Kerckhoffs假設(shè)假定：密碼分析者知道對方所使用的密碼系統(tǒng)包括明文的統(tǒng)計(jì)特性、加密體制（操作方式、處理方法和加/解密算法）、密鑰空間及其統(tǒng)計(jì)特性。不知道密鑰。在設(shè)計(jì)一個(gè)密碼系統(tǒng)時(shí)，目標(biāo)是在Kerckhoffs假設(shè)的前提下實(shí)現(xiàn)安全。102.1.5密碼分析密碼分析：從密文推導(dǎo)出明文或密鑰。密碼分析常用的方法有以下4類：惟密文攻擊（cybertextonlyattack）；已知明文攻擊（knownplaintextattack）；選擇明文攻擊（chosenplaintextattack）；選擇密文攻擊（chosenciphertextattack）。11密碼分析惟密文攻擊:密碼分析者知道一些消息的密文（加密算法相同），并且試圖恢復(fù)盡可能多的消息明文，并進(jìn)一步試圖推算出加密消息的密鑰（以便通過密鑰得出更多的消息明文。已知明文攻擊:密碼分析者不僅知道一些消息的密文，也知道與這些密文對應(yīng)的明文，并試圖推導(dǎo)出加密密鑰或算法（該算法可對采用同一密鑰加密的所有新消息進(jìn)行解密)。

12密碼分析選擇明文攻擊:密碼分析者不僅知道一些消息的密文以及與之對應(yīng)的明文，而且可以選擇被加密的明文（這種選擇可能導(dǎo)致產(chǎn)生更多關(guān)于密鑰的信息），并試圖推導(dǎo)出加密密鑰或算法（該算法可對采用同一密鑰加密的所有新消息進(jìn)行解密）選擇密文攻擊:密碼分析者能夠選擇不同的密文并能得到對應(yīng)的明文，密碼分析的目的是推導(dǎo)出密鑰。13密碼系統(tǒng)一個(gè)好的密碼系統(tǒng)應(yīng)滿足：系統(tǒng)理論上安全，或計(jì)算上安全；系統(tǒng)的保密性是依賴于密鑰的，而不是依賴于對加密體制或算法的保密；加密和解密算法適用于密鑰空間中的所有元素；系統(tǒng)既易于實(shí)現(xiàn)又便于使用。142.1.6加密的功能保密性：基本功能，使非授權(quán)者無法知道消息的內(nèi)容。鑒別：消息的接收者應(yīng)該能夠確認(rèn)消息的來源。完整性：消息的接收者應(yīng)該能夠驗(yàn)證消息在傳輸過程中沒有被改變。不可否認(rèn)性：發(fā)送方不能否認(rèn)已發(fā)送的消息。152.2經(jīng)典密碼及其破譯2.2.1代替密碼2.2.2置換密碼16【例2．1】簡單的加密形式，基于塊加密和異或運(yùn)算。消息：0011010101000101001101010010101110010101消息塊：0011010101000101001101010010101110010101密鑰：0101010101010101010101010101010101010101密文：0110000000010000011000000111111011000000

17代替密碼（1）代替密碼（substitutioncipher）：明文中的每個(gè)字符被替換成密文中的另一個(gè)字符。簡單代替，即單字母密碼;明文中字母的出現(xiàn)頻度、重復(fù)字母的模式和字母相互之間的結(jié)合模式等統(tǒng)計(jì)特性不變，安全性差。如Caesar密碼；

多碼代替密碼；沒有隱藏明文中不同字母的統(tǒng)計(jì)特性，安全性有所提高。

18代替密碼（2）多字母代替密碼：字符塊被成組加密，有利于抗擊統(tǒng)計(jì)分析,如Playfair密碼。多表代替密碼：有多個(gè)映射表，可隱藏單字母出現(xiàn)的頻率分布,如Vigenère密碼。19【例2．2】著名的Caesar密碼：加密時(shí)26個(gè)英文字母循環(huán)后移3位，解密時(shí)則循環(huán)前移3位。該方法最早在公元前50年，被羅馬大帝JuliusCaesar使用。ABCDEFGHIJKLMNOPQRSTUVWXYZ則密文為：PRP2.設(shè)明文為：CHINA則密文為:FKLQD1.設(shè)明文為：MOM20【例2．3】代替密碼體制的一般定義，設(shè)P=C=K=Z26,

這里P,C,K,Z26分別表示明文空間，密文空間，密鑰空間和26個(gè)整數(shù)（對應(yīng)26個(gè)英文字母）組成的空間。很明顯，明文，密文和密鑰的取值范圍是一樣的，它們的空間也是相同的。對于任意的定義：加密：即明文為x，密鑰為k（實(shí)際上就是每個(gè)英文字母向后循環(huán)移k位），密文為y。

解密：使用該方法時(shí)，要求26個(gè)字母與模26的剩余類集合建立一一對應(yīng)關(guān)系，如A對應(yīng)0，B對應(yīng)1，…，Z對應(yīng)25，不區(qū)分大小寫。21ABCDEFGHI012345678JKLMNOPQR91011121314151617STUVWXYZ181920212223242522當(dāng)k=3時(shí)，即為著名的Caesar密碼設(shè)明文為：China，對應(yīng)的數(shù)字為：278130加密：C:e3(2)=2+3(mod26)=5,對應(yīng)著字母Fh：e3(7)=7+3(mod26)=10,對應(yīng)著字母KI:e3(8)=8+3(mod26)=11,對應(yīng)著字母LN:e3(13)=13+3(mod26)=16,對應(yīng)著字母Q A:e3(0)=0+3(mod26)=3,對應(yīng)著字母D所以明文“China”基于Caesar密碼被加密為“FKLQD”

23解密就是加密過程的逆過程 解密：F:d3(5)=5-3(mod26)=2,對應(yīng)著CK:d3(10)=10-3(mod26)=7,對應(yīng)著H L:d3(11)=11-3(mod26)=8,對應(yīng)著I Q:d3(16)=16-3(mod26)=13,對應(yīng)著N D:d3(3)=3-3(mod26)=0,對應(yīng)著A

即“FKLQD“經(jīng)Caesar密碼解密恢復(fù)為”China”（不區(qū)分大小寫）Caesar密碼的特點(diǎn)：明文語言集已知，并且易于識別，結(jié)構(gòu)過于簡單，所以很容易被攻擊。

24【例2．4】（簡單代替）移位密碼，即向后移k位，k是任意的，故認(rèn)為k是密鑰，共有26個(gè)密鑰，看看使用密鑰的代替加密。選用一個(gè)英文短語或單詞作為密鑰，去掉其中重復(fù)的字母得到一個(gè)無重復(fù)字母的字符串，然后將字母表中的其他字母依此寫于此字母串之后。設(shè)密鑰為：key明文：ABCDEFGHIJKLMNOPQRSTUVWXYZ對應(yīng)的密文：keyabcdfghijlmnopqrstuvwxz因此，明文“China”,對應(yīng)的密文為：“yfgmk”25【例2．5】（多字母代替）Playfair密碼，將明文中的一個(gè)字母組合作為一個(gè)單元對待，并將這些單元轉(zhuǎn)換為密文雙字母組合。Playfair密碼是基于一個(gè)5×5字母矩陣，該矩陣使用一個(gè)密鑰來構(gòu)造，構(gòu)造方法是：從左到右，從上到下依此填入密鑰的字母（去除重復(fù)的字母），然后再以字母表順序依此填入其他字母。字母I和J被算做一個(gè)字母。對每對明文字母P1,P2的加密方法如下：261）若P1,P2在同一行上，則對應(yīng)的密文C1,C2分別是緊靠在P1,P2右端的字母。其中第一列被看做是最后一列的右方（解密時(shí)反向）2)

若P1,P2在同一列上，則對應(yīng)的密文C1,C2分別是緊靠在P1,P2下方的字母，其中第一行被看做是最后一行的下方（解密時(shí)反向）3)若P1,P2不在同一行上，也不在同一列上，則C1,C2是由P1,P2確定的矩陣的其他兩角的字母。并且C1和P1，C2和P2同行。（解密時(shí)反向）4)

若P1=P2，則插入一個(gè)字母（比如Q，需要事先約定）于重復(fù)字母之間，并用前述方法處理5）若明文字母數(shù)是奇數(shù)，則在明文的末端添加某個(gè)事先約定的字母作為填充。27密鑰是:PLAYFAIRISADIGRAMCIPHER,則構(gòu)造的字母矩陣如圖所示。PLAYFI/JRSDGMCHEBKNOQTUVWXZ28如果明文是：P=playfaircipher先將明文分成兩個(gè)一組：playfaircipher基于表對應(yīng)的密文為：LAYFPYRSMRAMCDPLAYFI/JRSDGMCHEBKNOQTUVWXZ29Vigenère密碼構(gòu)成明文：每個(gè)字符惟一對應(yīng)一個(gè)0~25間的數(shù)字。密鑰：一個(gè)字符串，其中每個(gè)字符同明文一樣對應(yīng)一個(gè)數(shù)字，代表位移值，如a表示位移0，b表示位移1，c表示位移2，......）。加密過程：將明文數(shù)字串依據(jù)密鑰長度分段，并逐一與密鑰數(shù)字串相加（模26），得到密文數(shù)字串；最后，將密文數(shù)字串轉(zhuǎn)換為字母串。30ABCDEFGHI012345678JKLMNOPQR91011121314151617STUVWXYZ181920212223242531【例2．5】明文串：theywillarrivetomorrow，采用密鑰k=Monday對其加密的過程如首先，依據(jù)上表，將密鑰與明文轉(zhuǎn)化為數(shù)字串：k=(12,14,13,3,0,24)m=(19,7,4,24,22,8,11,11,0,17,17,8,21,4,19,12,14,17,17,14,22)

其次，將明文數(shù)字串依據(jù)密鑰匙長度分段，并逐一與密鑰數(shù)字串相加（模26），得到密文數(shù)字串

3219

742422811110171781214133024121413302452117122623251320176

214191412141717142212141330241214133718617121235125

33C=(5,21,17,1,22,6,23,25,13,20,17,6,7,18,6,17,12,12,3,5,1,25)最后，依據(jù)上表將密文數(shù)字串轉(zhuǎn)換為字母串c=FVRBWGXZNURGHSGRMMDFBZ

34明文密鑰35Vigenère密碼的密碼分析（1）主要方法有：Kasiski測試法；字典攻擊。36Kasiski測試法基本原理：對于密鑰長度為d的Vigenère密碼，如果利用給定的密鑰表周期性地對明文字母進(jìn)行加密，則當(dāng)明文中有兩個(gè)相同的字母組在明文序列中間隔的字母數(shù)為d的倍數(shù)時(shí)，這兩個(gè)明文字母組對應(yīng)的密文字母組一定相同；反之，如果密文中出現(xiàn)兩個(gè)相同的字母組，則其對應(yīng)的明文字母組不一定相同。找出密文中的相同字母組，并研究其相間隔的字母數(shù)，確定這些字母數(shù)的最大公因子，便有可能得到有關(guān)密鑰長度的信息37字典攻擊發(fā)送方和接收方會(huì)選擇容易記憶的詞或短語做密鑰。那么對于發(fā)送方和接收方熟悉的攻擊者就可能會(huì)嘗試這種密鑰,只需要生成一個(gè)短的多的最有可能的密鑰列表即可。如果明文和密鑰都不是沒有意義的文字時(shí)，字典攻擊就有可能成功。38置換密碼