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

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

本章大綱2.1基本概念

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

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

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

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

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

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

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

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

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

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

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

幾種不同的分類標準

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

Kerckhoffs假設(shè)

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

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

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

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

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

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

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

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

古典加密技術(shù)代替密碼（substitutioncipher）明文中的每個字符被替換成密文中的另一個字符。簡單代替，即單字母密碼，如Caesar密碼；多碼代替密碼；多字母代替密碼；多表代替密碼，如Vigenère密碼。置換密碼（permutationcipher）：又稱換位密碼（transpositioncipher），并沒有改變明文字母，只改變了這些字母的出現(xiàn)順序。代替密碼代替密碼的特點單字母代換密碼：明文中字母的出現(xiàn)頻度、重復(fù)字母的模式和字母相互之間的結(jié)合模式等統(tǒng)計特性不變，安全性差。多碼代替密碼：沒有隱藏明文中不同字母的統(tǒng)計特性，安全性有所提高。多字母代替密碼：字符塊被成組加密，有利于抗擊統(tǒng)計分析。多表代替密碼：有多個映射表，可隱藏單字母出現(xiàn)的頻率分布。凱撒密碼ABCDEFGHIJKLMNOPQRSTUVWXY0123456789101112131415161718192021222324Z25如：data對應(yīng)數(shù)據(jù)序列30190,當k=5時，得密文序列85245,則對應(yīng)的密文為ifyf?？砂?6個字母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評價：結(jié)構(gòu)過于簡單，極易分析破解；移位密碼很容易受到唯密文攻擊。凱撒密碼分析單表代換密碼Caesar密碼中僅有25種可能的密鑰，是很不安全的。通過允許任意代換，密鑰空間將會急劇增大。這是因為每條消息用于一個字母表(給出從明文字母到密文字母的映射)加密。如果密文行是26個字母的任意置換，那么就有26！或大于4*1026種可能密鑰。特點：窮舉攻擊很難，但是由于保留了密碼語言的規(guī)律，所以可以用密碼語言的規(guī)律進行破解，如密碼語言中的字符使用頻率、雙字符組合使用頻率等。英文字母的相對使用頻率多表代換密碼特征：1、采用相關(guān)的單表代換規(guī)則集；2、由密鑰決定給定變換的具體規(guī)則。此類算法中最著名、最簡單的是Vigenère。Vigenère密碼構(gòu)成明文：每個字符惟一對應(yīng)一個0~25間的數(shù)字。密鑰：一個字符串，其中每個字符同明文一樣對應(yīng)一個數(shù)字，代表位移值，如a表示位移0，b表示位移1，c表示位移2，......）。加密過程：將明文數(shù)字串依據(jù)密鑰長度分段，并逐一與密鑰數(shù)字串相加（模26），得到密文數(shù)字串；最后，將密文數(shù)字串轉(zhuǎn)換為字母串。解密：采用模26減運算）構(gòu)造Vigenère密碼矩陣。26個密碼水平放置，最左邊是其密鑰字母，頂部排列的是明文的標準字母表。Vigenère密碼舉例1加密過程：給定密鑰字母X和明文字母Y，密文字母是位于X行和Y列的那個字母。加密一條消息需要與消息一樣長的密鑰。通常，密鑰是一個密鑰詞的重復(fù)，比如密鑰詞是deceptive,消息是：wearediscoveredsaveyourselfVigenère密碼加密過程Vigenère密碼的特點Vigenère密碼的強度在于每個明文字母對應(yīng)著多個密文字母，且每個使用唯一的字母作為密鑰詞，因此，字母出現(xiàn)的頻率信息被隱蔽了。Vigenère密碼攻擊分析(1)區(qū)分Vigenère密碼和單表代換密碼

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

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

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

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

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