課件03信息安全技術(shù)第三講-密碼學(xué)概論

信息安全技術(shù)萬濤華東交通大學(xué)信息工程學(xué)院E-mail:wantao217@163.comTelQ:471387802第3講密碼學(xué)概論§3.1密碼學(xué)的基本概念§3.2代替密碼§3.3換位密碼§3.4一次一密方案§3.5密碼分析加密通信的模型:Alice加密機(jī)解密機(jī)Bob安全信道密鑰源竊聽者xyxk1密鑰源k2不安全信道密碼分析§3.1密碼學(xué)的基本概念2023/1/143離散數(shù)學(xué)密碼體制定義:它是一個(gè)五元組（P,C,K,E,D)滿足條件：（1）P是可能明文的有限集；（明文空間）（2）C是可能密文的有限集；（密文空間）（3）K是一切可能密鑰構(gòu)成的有限集；（密鑰空間）（4）任意

，有一個(gè)加密算法和相應(yīng)的解密算法，使和分別為加密、解密函數(shù)，且滿足?！?.1密碼學(xué)的基本概念2023/1/144離散數(shù)學(xué)注：1、Alice要將明文Ｘ在不安全信道上發(fā)給Bob，設(shè)X=x1x2…

xn，其中

，Alice用加密算法ek作

yi=ek(xi)(1≤i≤n)，結(jié)果的密文是Y=y1y2….yn

在信道上發(fā)送，Bob收到后解密：xi=dk(yi)

得到明文X=x1x2…

xn。2、加密函數(shù)ek必須是單射函數(shù)，就是一對(duì)一的函數(shù)。3、若P=C，則ek為一個(gè)置換。4、好的密鑰算法是唯密鑰而保密的。5、若Alice和Bob在一次通信中使用相同的密鑰，則這個(gè)加密體制為對(duì)稱的，否則稱為非對(duì)稱的?！?.1密碼學(xué)的基本概念2023/1/145離散數(shù)學(xué)消息被稱為明文，用某種方法偽裝消息以隱藏它的內(nèi)容的過程稱為加密（Encryption），被加密的消息稱為密文，而把密文轉(zhuǎn)變?yōu)槊魑牡倪^程稱為解密（Decryption）。使消息保密的技術(shù)和科學(xué)叫做密碼編碼學(xué)(Cryptography)，從事此行的叫密碼編碼者（Cryptographer），密碼分析者是從事密碼分析的專業(yè)人員，密碼分析學(xué)（Cryptanalysis）就是破譯密文的科學(xué)和技術(shù)，即揭穿偽裝。

密碼學(xué)（Cryptology）作為數(shù)學(xué)的一個(gè)分支，包括密碼編碼學(xué)和密碼分析學(xué)兩部分，密碼編碼技術(shù)和密碼分析技術(shù)是相互依存、相互支持、密不可分的兩個(gè)方面?！?.1密碼學(xué)的基本概念2023/1/146離散數(shù)學(xué)密碼學(xué)除了提供機(jī)密性外，還有以下作用：1、鑒別：消息的接收者能夠確認(rèn)消息的來源，入侵者不可能偽裝成他人。2、完整性：消息的接收者能夠驗(yàn)證在傳送過程中消息沒有被修改，入侵者不可能用假消息代替合法消息。3、抗抵賴：發(fā)送者事后不可能虛假地否認(rèn)他發(fā)送的消息。密碼算法（Algorithm）也叫密碼（Cipher），是用于加密和解密的數(shù)學(xué)函數(shù)。通常情況下，有兩個(gè)相關(guān)的函數(shù)，一個(gè)用作加密，另一個(gè)用作解密。密鑰用K表示。K可以是很多數(shù)值里的任意值。密鑰K的可能值的范圍叫做密鑰空間。加密和解密運(yùn)算都用它?！?.1密碼學(xué)的基本概念2023/1/147離散數(shù)學(xué)密碼體制在原理上分兩類：單鑰體制和雙鑰（公鑰）體制。單鑰密碼體制中，收發(fā)雙方使用同一密鑰，系統(tǒng)的保密性主要取決于密鑰的安全性。系統(tǒng)的密鑰管理、傳輸和分配是一個(gè)重要且十分復(fù)雜的問題。單鑰密碼算法按照對(duì)明文的處理方式分為：分組密碼算法和序列密碼算法。體制的缺點(diǎn)：密鑰數(shù)目大，密鑰分配困難，無法實(shí)現(xiàn)不可否認(rèn)服務(wù)。公鑰密碼體制中，加密密鑰Ke是公開的，解密密鑰Kd必須保密。公鑰體制的密鑰產(chǎn)生、分配和管理相對(duì)簡單，尤適用于計(jì)算機(jī)網(wǎng)絡(luò)系統(tǒng)中。公鑰體制的特點(diǎn)：實(shí)現(xiàn)信息公開加密，實(shí)現(xiàn)不可否認(rèn)服務(wù)。體制的缺點(diǎn)：加解密運(yùn)算復(fù)雜其速度較慢。§3.1密碼學(xué)的基本概念2023/1/148離散數(shù)學(xué)

代替密碼也稱替換密碼，是使用替換法進(jìn)行加密所產(chǎn)生的密碼。替換密碼就是明文中每一個(gè)字符被替換成密文中的另外一個(gè)字符，替換后的各字母保持原來位置。接收者對(duì)密文進(jìn)行逆替換就恢復(fù)出明文來。在替換密碼加密體制中，使用了密鑰字母表。它可以由明文字母表構(gòu)成，也可以由多個(gè)字母表構(gòu)成。在傳統(tǒng)密碼學(xué)中，有四種類型的代替密碼：1、單表（簡單）替換密碼：就是明文的一個(gè)字符用相應(yīng)的一個(gè)密文字符替代。加密過程中是從明文字母表到密文字母表的一一映射。例：愷撒（Caesar)密碼?！?.2代替密碼2023/1/149離散數(shù)學(xué)2、同音（多名碼）替換密碼：它與簡單替代密碼系統(tǒng)相似，唯一的不同是單個(gè)字符明文可以映射成密文的幾個(gè)字符之一，同音替代的密文并不唯一。3、多字母組替換密碼：字符塊被成組加密，例如“ABA”可能對(duì)應(yīng)“RTQ”，ABB可能對(duì)應(yīng)“SLL”等。例：Playfair密碼。4、多表替換密碼：由多個(gè)單字母密碼構(gòu)成，每個(gè)密鑰加密對(duì)應(yīng)位置的明文。例：維吉尼亞密碼?！?.2代替密碼2023/1/1410離散數(shù)學(xué)一、單表替換密碼1、愷撒（Caesar)密碼凱撒密碼，又叫循環(huán)移位密碼。它的加密方法就是把明文中所有字母都用它右邊的第k個(gè)字母替代，并認(rèn)為Z后邊又是A。這種映射關(guān)系表示為如下函數(shù)： F(a)=(a+k)mod26其中：a表示明文字母；k為密鑰?！?.2代替密碼2023/1/1411離散數(shù)學(xué)設(shè)k＝3，則有明文：abcdefghijklmnopqrstuvwxyz密文：defghijklmnopqrstuvwxyzabc對(duì)于明文P＝computersystems有密文C＝frpsxwhuvbvwhpv顯然，由密文C恢復(fù)明文非常容易，只要知道密鑰K，就可構(gòu)造一張映射表。其加密和解密均可根據(jù)此映射表進(jìn)行。凱撤密碼的優(yōu)點(diǎn)是密鑰簡單易記。但它的密文與明文的對(duì)應(yīng)關(guān)系過于簡單，故安全性很差?！?.2代替密碼2023/1/1412離散數(shù)學(xué)2、密鑰短語密碼選擇一組有助于記憶的英文字符串作為密鑰，從中篩選無重復(fù)的字符按原順序記下字符串，寫在明文字母表下，然后將未出現(xiàn)在字符串的字母按順序依次寫在密鑰短語后。如選擇密鑰短語networksecurity則有明文：abcdefghijklmnopqrstuvwxyz密文：networkscuiyabdfghjlmpqvxz若明文為dataaccess則密文為wnlnnttojj§3.2代替密碼2023/1/1413離散數(shù)學(xué)二、多表替換密碼多表替換密碼是一種用多組替換表依次對(duì)明文消息的字母進(jìn)行替換的加密方法。維吉尼亞（Vigenere）密碼是一種常用的多表替換密碼。這種替換法是循環(huán)的使用有限個(gè)字母來實(shí)現(xiàn)替換的一種方法。這種加密的加密表是以字母表移位為基礎(chǔ)把26個(gè)英文字母進(jìn)行循環(huán)移位，排列在一起，形成26×26的方陣。該方陣被稱為維吉尼亞表。采用的算法為 f(pi)=(pi+ki)mod26優(yōu)點(diǎn)：能抵抗簡單的字母頻率分析攻擊。§3.2代替密碼2023/1/1414離散數(shù)學(xué)Vigenere密碼表ABCDEFGHIJKLMNOPQRSTUVWXYZAABCDEFGHIJKLMNOPQRSTUVWXYZBBCDEFGHIJKLMNOPQRSTUVWXYZACCDEFGHIJKLMNOPQRSTUVWXYZAB………OOPQRSTUVWXYZABCDEFGHIJKLMN………

YYZABCDEFGHIJKLMNOPQRSTUVWXZZABCDEFGHIJKLMNOPQRSTUVWXY§3.2代替密碼2023/1/1415離散數(shù)學(xué)加密過程：以明文字母選擇列，以密鑰字母選擇行，兩者的交點(diǎn)就是加密生成的密文。解密過程：以密鑰字母選擇行，從中找到密文字母，密文字母所在列的列名即為明文字母。例：以your為密鑰，加密明文howareyou明文P=howareyou 密鑰K=youryoury密文C=fcqrpssfs§3.2代替密碼2023/1/1416離散數(shù)學(xué)三、多表替換密碼

多字母替換密碼每次加密一組（兩個(gè)以上）字母串。Playfair密碼為此類密碼，密鑰由25個(gè)英文字母（j與i相同）組成的5階方陣。密鑰方陣P導(dǎo)出取決于給定密鑰，重復(fù)不寫，余下按字母順序填充。明文劃分如下：將明文字母串按兩個(gè)字母一組進(jìn)行分組，每組中的兩個(gè)字母不同。每一對(duì)明文字母m1和m2，對(duì)應(yīng)的密文為c1和c2。§3.2代替密碼2023/1/1417離散數(shù)學(xué)每一對(duì)明文字母m1和m2，按下面的規(guī)則進(jìn)行加密。（1）若m1和m2在P的同一行，則密文c1和c2分別是m1和m2右邊的字母。第一列看作最后一列的右邊。（2）若m1和m2在P的同一列，則密文c1和c2分別是m1和m2下邊的字母。第一行看作最后一行的下邊。（3）若m1和m2在P的不同行、不同列，則密文c1和c2是m1和m2確定的長方形的另兩個(gè)頂點(diǎn)的字母。其中c1與m1同行，c2與m2同行。（4）若m1＝m2，則在m1和m2之間加一個(gè)無效字母（如x）。（5）若明文字母為奇數(shù)個(gè)，則在末尾加一個(gè)無效字母?！?.2代替密碼2023/1/1418離散數(shù)學(xué)例：以firewallsecurity為密鑰，加密明文howareyou。由密鑰導(dǎo)出密鑰矩陣為明文分組處理howareyoux密文khfuewgkcz§3.2代替密碼2023/1/1419離散數(shù)學(xué)換位密碼是采用換位法進(jìn)行加密的。它把明文中的字母重新排列，本身不變，但位置變了，換位密碼是靠重新安排字母的次序，而不是隱藏他們。常見的換位密碼主要有倒置法、列換位法、矩陣換位法?！?.3換位密碼2023/1/1420離散數(shù)學(xué)倒置法（1）完全倒置法把明文中的字母按順序倒過來寫，然后以固定長度的字母組發(fā)送或記錄。 明文：computersystems 密文：smetsysretupmoc（2）分組倒置法把明文中的字母按固定長度分組后，每組字母串倒過來寫。 明文：computersystems分組：computersystems 密文：pmocretutsyssme§3.3換位密碼2023/1/1421離散數(shù)學(xué)換位法（1）列換位法（2）矩陣換位法§3.3換位密碼2023/1/1422離散數(shù)學(xué)換位法（1）列換位法將明文字符分割成為若干個(gè)（例如5個(gè)）一行的分組，并按一組后面跟著另一組的形式排好，形式如下：

c1c2c3c4c5 c6c7c8c9c10……

最后，不全的組可以用不常使用的字符或a,b,c…填滿。密文是取各列來產(chǎn)生的：c1c6…c2c7…c3c8….c4c9….c5c10….§3.3換位密碼2023/1/1423離散數(shù)學(xué)例：明文：WHATYOUCANLEARNFROMTHISBOOK取密鑰為5，

進(jìn)行排列：

WHATYOUCANLEARNFROMTHISBOOKXXX則密文為：WOLFHOHUERIKACAOSXTARMBXYNNTOX§3.3換位密碼2023/1/1424離散數(shù)學(xué)（2）矩陣換位法把明文中的字母按給定的順序安排在一矩陣中，然后用另一種順序選出矩陣的字母來產(chǎn)生密文。例：明文ENGINEERING按行排在3×4矩陣中，最后一行不全用ABC…填充，如下所示。給定置換1234ENGINEERINGA§3.3換位密碼2023/1/1425離散數(shù)學(xué)在這個(gè)加密方案中，密鑰就是矩陣的行數(shù)m和列數(shù)n，即m*n＝3*4，以及給定的置換矩陣。也就是：k=（m*n，f）根據(jù)給定置換，按第2、4、1、3列的次序排列，得到密文：NIEGERNENAIG2413NIEGERNENAIG1234ENGINEERINGA§3.3換位密碼2023/1/1426離散數(shù)學(xué)其解密過程是將密文根據(jù)3*4矩陣，按行、列的順序?qū)懗?，再根?jù)給定置換產(chǎn)生新的矩陣，恢復(fù)明文為：ENGINEERING1234ENGINEERINGA2413NIEGERNENAIG§3.3換位密碼2023/1/1427離散數(shù)學(xué)一次一密方案是一種理想的加密方案，由AT&T公司的GilbertVernam在1917年提出。它使用的密鑰是一個(gè)大的不重復(fù)的真隨機(jī)密鑰字母集，這個(gè)密鑰字母集被寫在幾張紙上，并被粘成一個(gè)密碼本。它最初的形式是用于電傳打字機(jī)。發(fā)送者用密碼本中的每一密鑰字母準(zhǔn)確地加密一個(gè)明文字符。加密是明文字符和一次密碼本密鑰字符的模26加法。每個(gè)密鑰僅對(duì)一個(gè)消息使用一次。發(fā)送者對(duì)所發(fā)送的消息加密，然后銷毀密碼本中用過的一頁或磁帶部分。接收者有一個(gè)同樣的密碼本，并依次使用密碼本上的每個(gè)密鑰去解密密文的每個(gè)字符。接收者在解密消息后銷毀密碼本中用過的一頁或磁帶部分。新的消息則用密碼本中新的密鑰加密?！?.4一次一密方案2023/1/1428離散數(shù)學(xué)例如，如果消息是：

ONETIMEPAD而取自密碼本的密鑰序列是：TBFRGFARFM那么密文就是：IPKLPSFHGQ因?yàn)镺＋Tmode26=IN＋Bmode26=PE＋Fmode26=K

……?！?.4一次一密方案2023/1/1429離散數(shù)學(xué)密碼分析學(xué)是在不知道密鑰的情況下，恢復(fù)出明文的科學(xué)。成功的密碼分析能恢復(fù)出消息的明文或密鑰。密碼分析也可以發(fā)現(xiàn)密碼體制的弱點(diǎn)，最終得到上述結(jié)果（密鑰通過非密碼分析方式的丟失叫做泄露）。常用的密碼分析攻擊有:（1）唯密文攻擊（CipherText-OnlyAttack）。密碼分析者有一些消息的密文，這些消息都用同一加密算法加密。密碼分析者的任務(wù)是恢復(fù)盡可能多的明文，或者最好是能推算出加密消息的密鑰來，以便可采用相同的密鑰解出其他被加密的消息。§3.5密碼分析2023/1/1430離散數(shù)學(xué)（2）已知明文攻擊（Known-PlaintextAttack）。密碼分析者不僅可得到一些消息的密文，而且也知道這些消息的明文。分析者的任務(wù)就是用加密信息推