第2章密碼學(xué)的基本概念和信息

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

本章大綱2.1基本概念

2.2傳統(tǒng)密碼及其破譯

2.3Shannon的保密系統(tǒng)信息理論

2.4Simmons認(rèn)證系統(tǒng)的信息理論

2.5概率論基礎(chǔ)2.1基本概念2.1.2密碼學(xué)的發(fā)展歷史第1階段：1949年以前,憑直覺(jué)和信念，一種藝術(shù)。第2階段：從1949年到1975年。標(biāo)志：1949年Shannon發(fā)表的《保密系統(tǒng)的信息理論》一文。第3階段：1976年至今。標(biāo)志：1976年Diffie和Hellman發(fā)表了《密碼學(xué)新方向》一文，密碼學(xué)上的一場(chǎng)革命。首次證明了在發(fā)送端和接收端不需要傳輸密鑰的保密通信的可能性，開(kāi)創(chuàng)了公鑰密碼新紀(jì)元。第4個(gè)階段:1982年姚期智提出姚氏百萬(wàn)富翁-安全多方計(jì)算2000年圖靈獎(jiǎng),唯一一位華人及亞洲人

謝爾比烏斯發(fā)明的加密電子機(jī)械名ENIGMA，在以后的年代里，它將被證明是有史以來(lái)最為可靠的加密系統(tǒng)之一亞瑟·謝爾比烏斯ENIGMA

史海鉤沉馬里安·雷杰夫斯基破譯ENIGMA機(jī)的功臣

漢斯—提羅·施密特(Hans-Thilo波蘭人，1888年出生在柏林的一個(gè)中產(chǎn)階級(jí)家庭里）

史海鉤沉2.1.1密碼學(xué)的概念

密碼學(xué)是研究密碼系統(tǒng)或通信安全的一門(mén)學(xué)科,分為密碼編碼學(xué)和密碼分析學(xué)。密碼編碼學(xué)是使得消息保密的學(xué)科，從事此行的稱為密碼編碼者。密碼分析學(xué)是研究加密消息的破譯的學(xué)科，從事此行的稱為密碼分析者，精于此道的人被稱為密碼學(xué)家，現(xiàn)代的密碼學(xué)家通常是理論數(shù)學(xué)家。2.1.33個(gè)術(shù)語(yǔ)Shannon模型組成部分X,明文（plain-text）：作為加密輸入的原始信息。Y,密文（cipher-text）：對(duì)明文變換的結(jié)果。E,加密（encrypt）：是一組含有參數(shù)的變換。D,解密（decrypt）：加密的逆變換。Z,密鑰（key）：是參與加密解密變換的參數(shù)。2.1.4密碼體制的分類(lèi)

密碼學(xué)分類(lèi)密碼學(xué)(Cryptology):是研究如何實(shí)現(xiàn)秘密通信的科學(xué)。包括密碼編碼學(xué)和密碼分析學(xué)。密碼編碼學(xué)(Cryptography):

主要研究對(duì)信息進(jìn)行編碼,實(shí)現(xiàn)信息保密性的科學(xué)。密碼分析學(xué)(Cryptanalytics):主要研究、分析、破譯密碼的科學(xué)。密碼編碼學(xué)的分類(lèi)

幾種不同的分類(lèi)標(biāo)準(zhǔn)

按操作方式進(jìn)行分類(lèi)操作方式：是明文變換成密文的方法。替代操作、置換操作、復(fù)合操作。按照使用密鑰的數(shù)量進(jìn)行分類(lèi)對(duì)稱密鑰（單密鑰）。公開(kāi)密鑰（雙密鑰）。按照對(duì)明文的處理方法進(jìn)行分類(lèi)流密碼。分組密碼。古典密碼算法現(xiàn)代密碼算法代換算法換位算法愷撒密碼滾輪密碼維吉尼亞密碼希爾密碼縱行換位對(duì)稱算法公鑰算法DESAES…RSA橢圓曲線…密碼算法分類(lèi)2.1.5密碼分析

Kerckhoffs假設(shè)

假定：密碼分析者知道對(duì)方所使用的密碼系統(tǒng)包括明文的統(tǒng)計(jì)特性、加密體制（操作方式、處理方法和加/解密算法）、密鑰空間及其統(tǒng)計(jì)特性。不知道密鑰。在設(shè)計(jì)一個(gè)密碼系統(tǒng)時(shí)，目標(biāo)是在Kerckhoffs假設(shè)的前提下實(shí)現(xiàn)安全。密碼分析分類(lèi)密碼分析：從密文推導(dǎo)出明文或密鑰。密碼分析：常用的方法有以下4類(lèi)：惟密文攻擊（cybertextonlyattack）；已知明文攻擊（knownplaintextattack）；選擇明文攻擊（chosenplaintextattack）；選擇密文攻擊（chosenciphertextattack）。目前，最常見(jiàn)的是已知明文和選擇明文攻擊惟密文攻擊

密碼分析者知道一些消息的密文（加密算法相同），并且試圖恢復(fù)盡可能多的消息明文，并進(jìn)一步試圖推算出加密消息的密鑰（以便通過(guò)密鑰得出更多的消息明文。

已知：C1=EK（M1），C2=EK（M2），……，Ci=EK（Mi）推導(dǎo)出：M1，M2，，Mi；K或者找出一個(gè)算法從Ci+1=EK（Mi+1）推出Mi+1。比如，pstscript格式加密文件總是以相同的格式開(kāi)頭；電子金融消息往往有標(biāo)準(zhǔn)化的文件頭或標(biāo)志。已知明文攻擊

密碼分析者不僅知道一些消息的密文，也知道與這些密文對(duì)應(yīng)的明文，并試圖推導(dǎo)出加密密鑰或算法（該算法可對(duì)采用同一密鑰加密的所有新消息進(jìn)行解密。

已知：M1，C1=EK（M1）；M2，C2=EK（M2）；……，Mi，Ci=EK（Mi）；推導(dǎo)出：K或者找出一個(gè)算法從Ci+1=EK（Mi+1）推出Mi+1的算法。選擇明文攻擊

選擇明文攻擊的破譯者除了知道加密算法外，他還可以選定明文消息，并可以知道對(duì)應(yīng)的加密得到的密文，即知道選擇的明文和對(duì)應(yīng)的密文。例如，公鑰密碼體制中，攻擊者可以利用公鑰加密他任意選定的明文，這種攻擊就是選擇明文攻擊。已知：M1，C1=EK（M1）；M2，C2（M2）；……，Mi，Ci=EK（Mi）；其中M1，M2，……,Mi是由密碼分析者選擇的。推導(dǎo)：K或者找出一個(gè)算法從Ci+1=EK（Mi+1）推出Mi+1的算法。與選擇明文攻擊相對(duì)應(yīng)，破譯者除了知道加密算法外，還包括他自己選定的密文和對(duì)應(yīng)的、已解密的原文，即知道選擇的密文和對(duì)應(yīng)的明文。

需要掌握的內(nèi)容：加密算法截獲的部分密文自己選擇的密文消息相應(yīng)的被解密的明文選擇密文攻擊基于加密信息的攻擊類(lèi)型密碼系統(tǒng)一個(gè)好的密碼系統(tǒng)應(yīng)滿足：系統(tǒng)理論上安全，或計(jì)算上安全；系統(tǒng)的保密性是依賴于密鑰的，而不是依賴于對(duì)加密體制或算法的保密；加密和解密算法適用于密鑰空間中的所有元素；系統(tǒng)既易于實(shí)現(xiàn)又便于使用。2.1.6鑒別、完整性和不可否認(rèn)性

加密的要求保密性：基本功能，使非授權(quán)者無(wú)法知道消息的內(nèi)容。鑒別：消息的接收者應(yīng)該能夠確認(rèn)消息的來(lái)源。完整性：消息的接收者應(yīng)該能夠驗(yàn)證消息在傳輸過(guò)程中沒(méi)有被改變。不可否認(rèn)性：發(fā)送方不能否認(rèn)已發(fā)送的消息。2.2傳統(tǒng)密碼及其破譯

古典加密技術(shù)代替密碼（substitutioncipher）明文中的每個(gè)字符被替換成密文中的另一個(gè)字符。簡(jiǎn)單代替，即單字母密碼，如Caesar密碼；多碼代替密碼；多字母代替密碼；多表代替密碼，如Vigenère密碼。置換密碼（permutationcipher）：又稱換位密碼（transpositioncipher），并沒(méi)有改變明文字母，只改變了這些字母的出現(xiàn)順序。代替密碼代替密碼的特點(diǎn)單字母代換密碼：明文中字母的出現(xiàn)頻度、重復(fù)字母的模式和字母相互之間的結(jié)合模式等統(tǒng)計(jì)特性不變，安全性差。多碼代替密碼：沒(méi)有隱藏明文中不同字母的統(tǒng)計(jì)特性，安全性有所提高。多字母代替密碼：字符塊被成組加密，有利于抗擊統(tǒng)計(jì)分析。多表代替密碼：有多個(gè)映射表，可隱藏單字母出現(xiàn)的頻率分布。凱撒密碼ABCDEFGHIJKLMNOPQRSTUVWXY0123456789101112131415161718192021222324Z25如：data對(duì)應(yīng)數(shù)據(jù)序列30190,當(dāng)k=5時(shí)，得密文序列85245,則對(duì)應(yīng)的密文為ifyf?？砂?6個(gè)字母A~Z看作是數(shù)字0~25，密鑰k看作是循環(huán)右移若干位(0~25之間)，則愷撒密碼的加密可表示為c=(m+k)mod26，c為密文序列；則解密可表示為P=(c-k)mod26，P為原文序列代換密碼舉例愷撒密碼的效果是使字母以統(tǒng)一偏移量循環(huán)移位試能破譯下面這段話。密文：VjkukuEcguctEqfgABCDEFGHIJKLMLOPQRSTUVWXYZYZABCDEFGHIJKLMLOPQRSTUVWX

設(shè)偏移量k為24(-2)，解密是逆變換，k也是24明文：ThisisCaesarCode評(píng)價(jià)：結(jié)構(gòu)過(guò)于簡(jiǎn)單，極易分析破解；移位密碼很容易受到唯密文攻擊。凱撒密碼分析單表代換密碼Caesar密碼中僅有25種可能的密鑰，是很不安全的。通過(guò)允許任意代換，密鑰空間將會(huì)急劇增大。這是因?yàn)槊織l消息用于一個(gè)字母表(給出從明文字母到密文字母的映射)加密。如果密文行是26個(gè)字母的任意置換，那么就有26！或大于4*1026種可能密鑰。特點(diǎn)：窮舉攻擊很難，但是由于保留了密碼語(yǔ)言的規(guī)律，所以可以用密碼語(yǔ)言的規(guī)律進(jìn)行破解，如密碼語(yǔ)言中的字符使用頻率、雙字符組合使用頻率等。英文字母的相對(duì)使用頻率多表代換密碼特征：1、采用相關(guān)的單表代換規(guī)則集；2、由密鑰決定給定變換的具體規(guī)則。此類(lèi)算法中最著名、最簡(jiǎn)單的是Vigenère。Vigenère密碼構(gòu)成明文：每個(gè)字符惟一對(duì)應(yīng)一個(gè)0~25間的數(shù)字。密鑰：一個(gè)字符串，其中每個(gè)字符同明文一樣對(duì)應(yīng)一個(gè)數(shù)字，代表位移值，如a表示位移0，b表示位移1，c表示位移2，......）。加密過(guò)程：將明文數(shù)字串依據(jù)密鑰長(zhǎng)度分段，并逐一與密鑰數(shù)字串相加（模26），得到密文數(shù)字串；最后，將密文數(shù)字串轉(zhuǎn)換為字母串。解密：采用模26減運(yùn)算）構(gòu)造Vigenère密碼矩陣。26個(gè)密碼水平放置，最左邊是其密鑰字母，頂部排列的是明文的標(biāo)準(zhǔn)字母表。Vigenère密碼舉例1加密過(guò)程：給定密鑰字母X和明文字母Y，密文字母是位于X行和Y列的那個(gè)字母。加密一條消息需要與消息一樣長(zhǎng)的密鑰。通常，密鑰是一個(gè)密鑰詞的重復(fù)，比如密鑰詞是deceptive,消息是：wearediscoveredsaveyourselfVigenère密碼加密過(guò)程Vigenère密碼的特點(diǎn)Vigenère密碼的強(qiáng)度在于每個(gè)明文字母對(duì)應(yīng)著多個(gè)密文字母，且每個(gè)使用唯一的字母作為密鑰詞，因此，字母出現(xiàn)的頻率信息被隱蔽了。Vigenère密碼攻擊分析(1)區(qū)分Vigenère密碼和單表代換密碼

單表代換密碼中密文統(tǒng)計(jì)特性應(yīng)與明文統(tǒng)計(jì)特性相同；(2)密鑰詞長(zhǎng)度的確認(rèn)如果兩個(gè)相同的明文序列之間的距離是密鑰詞長(zhǎng)度的整數(shù)倍，那么產(chǎn)生的密文序列也是相同的；反之，密文中出現(xiàn)兩個(gè)相同的字母組，則對(duì)應(yīng)的明文字母組不一定相同。(3)密鑰詞長(zhǎng)度整數(shù)倍位置是單表代換如果密鑰詞長(zhǎng)度是N，那么密碼實(shí)際上包含了N個(gè)單表代換。一次一密使用與消息一樣長(zhǎng)且無(wú)重復(fù)的隨機(jī)密鑰來(lái)加密消息，它是不可攻破的。它產(chǎn)生隨機(jī)數(shù)出與明文沒(méi)有任何統(tǒng)計(jì)關(guān)系。假設(shè)使用27個(gè)字符(第27個(gè)字符是空格)的Vigenère密碼,但是這里使用的一次密鑰和消息一樣長(zhǎng)。密文:ankyodkyurepfjbyojdsplreyiunofdoiuerfpluyts密鑰:pxlmvmsydoftyrvzwctnlebnecvgdupahfzzlmnyih明文:mrmustardwiththecandlestickinthehall密文:ankyodkyurepfjbyojdsplreyiunofdoiuerfpluyts密鑰:mfugpmiydgaxgoufhklllmhsqdqogtewbqfgyovuhwt明文:missscarletwiththeknifeinthelibrary一次一密的分析如果給出任何長(zhǎng)度與密文一樣的銘文，都存在著一個(gè)密鑰產(chǎn)生這個(gè)明文。一次一密的安全性完全取決于密鑰的隨機(jī)性。實(shí)際中使用一次一密的基本難點(diǎn)：(1)產(chǎn)生大規(guī)模隨機(jī)密鑰的實(shí)際困難。(2)更令人擔(dān)憂的是密鑰的分配和保護(hù)。代替密碼的特點(diǎn)單字母代換密碼：明文中字母的出現(xiàn)頻度、重復(fù)字母的模式和字母相互之間的結(jié)合模式等統(tǒng)計(jì)特性不變，安全性差。多碼代替密碼：沒(méi)有隱藏明文中不同字母的統(tǒng)計(jì)特性，安全性有所提高。(明文攻擊,抗唯密文攻擊)多字母代替密碼：字符塊被成組加密，有利于抗擊統(tǒng)計(jì)分析。(已知明文攻擊)多表代替密碼：有多個(gè)映射表，可隱藏單字母出現(xiàn)的頻率分布。置換密碼謎底信，方成安息息息深式為全安化技刻，世的全發(fā)術(shù)地推界研保展的改動(dòng)性究障的發(fā)變著問(wèn)和能當(dāng)展了社題發(fā)力務(wù)與人會(huì)。展也之廣們文加，是急泛的明速加我。應(yīng)生，信強(qiáng)國(guó)用活已息信信活已息信信信，方成安息息息深式為全安化技刻，世的全發(fā)術(shù)地推界研保展的改動(dòng)性究障的發(fā)變著問(wèn)和能當(dāng)展了社題發(fā)力務(wù)與人會(huì)。展也之廣們文加，是急泛的明速加我。應(yīng)生，信強(qiáng)國(guó)用活已息信信原文"猜猜看？滾筒密碼置換技術(shù)——柵欄技術(shù)柵欄技術(shù):按照對(duì)角線的順序?qū)懭朊魑?而按行的順序讀出作為密文。例如:深度為2的柵欄技術(shù)加密”meetmeafterthetogaparty”密文：mematrhtgpryetefeteoaat置換技術(shù)——矩形塊置換把消息一行一行地寫(xiě)成矩形塊,然后按列的次序讀出，但是列的次序被打亂。列的次序就是算法密鑰。明文：attackpostphoneduntiltwoamxyz密鑰：4312567密文：ttnaaptmtsuoaodwcoixknlypetz與原始明文相同的字母頻率特性置換技術(shù)——多步置換可以通過(guò)對(duì)前面的消息在用相同的算法再加密一次。明文：attackpostphoneduntiltwoamxyz密鑰：4312567密文：nscyauopttwltmdnaoiepaxttokz隱寫(xiě)術(shù)隱寫(xiě)術(shù)可以隱藏信息的存在，而密碼學(xué)則是通過(guò)對(duì)文本信息的不同轉(zhuǎn)換而實(shí)現(xiàn)的對(duì)外不可讀。一種簡(jiǎn)單卻很耗時(shí)的隱寫(xiě)術(shù)可由一段無(wú)傷大雅文本的字詞重新排列而成。偵探Morse的疑惑YourpackagereadyFriday21stroomthreepleasedestroythisimmediately2.3Shannon的保密系統(tǒng)信息理論

1949年，Shannon發(fā)表了一篇題為《保密系統(tǒng)的信息理論》的論文。用信息論的觀點(diǎn)對(duì)信息保密問(wèn)題進(jìn)行了全面的闡述。宣告了科學(xué)的密碼學(xué)時(shí)代的到來(lái)。香農(nóng)用統(tǒng)計(jì)的觀點(diǎn)研究信息的傳輸和保密問(wèn)題。Shannon的保密系統(tǒng)信息理論目的：在信道有干擾的情況下，使接收的信息無(wú)錯(cuò)誤或差錯(cuò)盡可能小。通信系統(tǒng)模型目的：使竊聽(tīng)者即使在完全準(zhǔn)確地收到了接收信號(hào)的情況下也無(wú)法恢復(fù)出原始消息。保密系統(tǒng)模型一個(gè)保密系統(tǒng)（P，C，K，E，D）稱為完善的無(wú)條件的保密系統(tǒng)，如果H(P)=H(P|C),其中，P為明文集合，C為密文集合，K為密鑰集合，E為加密算法,D為解密算法,則完善保密系統(tǒng)存在的必要條件是H(P)≤H(K)。(唯密文攻擊條件下)要構(gòu)造一個(gè)完善保密系統(tǒng)，其密鑰量的對(duì)數(shù)（密鑰空間為均勻分布的條件下）必須不小于明文集的熵。從熵的基本性質(zhì)可推知，保密系統(tǒng)的密鑰量越小，其密文中含有的關(guān)于明文的信息量就越大。存在完善保密系統(tǒng)如：一次一密（one-timepad）方案；不實(shí)用。信息熵完善保密性下節(jié)課內(nèi)容實(shí)際上安全計(jì)算上是安全：算出和估計(jì)出破譯它的計(jì)算量下限，利用已有的最好的方法破譯該密碼系統(tǒng)所需要的努力超出了破譯者的破譯能力（諸如時(shí)間、空間、資金等資源）?？勺C明安全：從理論上證明破譯它的計(jì)算量不低于解已知難題的計(jì)算量。密碼體制的安全性（2）偽密鑰和惟一解距離

當(dāng)分析者截獲到密文c時(shí)，他首先利用所有的密鑰對(duì)其進(jìn)行解密，并得到明文m′＝Dk(c)，k∈K。接下來(lái)，對(duì)于所有有意義的消息m′，他記錄下與之對(duì)應(yīng)的密鑰。這些密鑰構(gòu)成的集合通常含有多個(gè)元素，并且至少含有一個(gè)元素，即正確的密鑰。人們把那些可能在這個(gè)集合中出現(xiàn)但并不正確的密鑰稱為偽密鑰（spuriouskey）。一個(gè)保密系統(tǒng)的惟一解距離定義為使得偽密鑰的期望數(shù)等于零的n的值，記為n0，即在給定的足夠的計(jì)算時(shí)間下分析者能惟一地計(jì)算出密鑰所需要的密文的平均量。用于衡量在惟密文攻擊下破譯一個(gè)密碼系統(tǒng)時(shí)，密碼分析者必須處理的密文量的理論下界。2.4Simmons認(rèn)證系統(tǒng)的信息理論

Simmons認(rèn)證系統(tǒng)的信息理論1984年，Simmons首次提出了認(rèn)證系統(tǒng)的理論。內(nèi)容：將信息論用于研究認(rèn)證系統(tǒng)的理論安全性和實(shí)際安全性問(wèn)題，指出認(rèn)證系統(tǒng)的性能極限以及設(shè)計(jì)認(rèn)證碼所必須遵循的原則。地位:保密系統(tǒng)中shannon理論。認(rèn)證理論的主要研究目標(biāo)：(1)推導(dǎo)欺騙者欺騙成功的概率的下界；(2)構(gòu)造欺騙者欺騙成功的概率盡可能小認(rèn)證碼。認(rèn)證碼基本要素有3個(gè)：信源集合；消息集合；編碼規(guī)則集合，其中每一個(gè)編碼規(guī)則由一個(gè)秘密密鑰來(lái)控制。發(fā)送者的任何一個(gè)編碼規(guī)則都是從信源集合到消息集合的一個(gè)映射，這個(gè)映射的每一個(gè)原像可能有一個(gè)像，也可能有幾個(gè)像。如果發(fā)送者的每個(gè)編碼規(guī)則的每一個(gè)原像只有一個(gè)像，則稱這種認(rèn)證碼為無(wú)分裂的認(rèn)證碼。如果發(fā)送者的每個(gè)編碼規(guī)則的每一個(gè)原像不只一個(gè)，則稱這種認(rèn)證碼為有分裂的認(rèn)證碼。

認(rèn)證系統(tǒng)模型一種是無(wú)仲裁者的認(rèn)證系統(tǒng)模型。在這種模型中，只有3種參加者，即消息的發(fā)送者、接收者和入侵者。消息的發(fā)送者和接收者之間相互信任，他們擁有同樣的秘密信息。另一種是有仲裁者的認(rèn)證系統(tǒng)模型。在這種模型中，有4種參加者，即消息的發(fā)送者、接收者、入侵者和仲裁者，信息的發(fā)送者和接收者之間相互不信任，但他們都信任仲裁者，仲裁者擁有所有的秘密信息并且不進(jìn)行欺騙。本節(jié)主要研究無(wú)分裂的、沒(méi)有保密功能的、無(wú)仲裁者認(rèn)證系統(tǒng)模型。無(wú)仲裁者的認(rèn)證系統(tǒng)模型無(wú)仲裁者的認(rèn)證系統(tǒng)特點(diǎn)發(fā)送者和接收者之間相互信任，共同對(duì)付入侵。最終目的：能使發(fā)送者通過(guò)一個(gè)公開(kāi)的無(wú)干擾信道將消息發(fā)送給接受者，接收者不僅能收到消息本身，而且還能驗(yàn)證消息是否來(lái)自于發(fā)送者以及消息是否被入侵者竄改過(guò)