第2講-密碼學(xué)的基本概念和理論基礎(chǔ)課件

第2講

密碼學(xué)的基本概念和理論基礎(chǔ)案例：莫爾斯電碼里的愛(ài)情

早已被新科技所取代的莫爾斯密碼，卻在中國(guó)的互聯(lián)網(wǎng)世界里演繹了一段費(fèi)盡周折的愛(ài)情猜謎傳奇。一男子向一女子表白，女子卻給了一段莫爾斯密碼，以及很少的提示，并表示，破譯這個(gè)密碼，才答應(yīng)和他約會(huì)。男子死活不得求解，又在百度貼吧里將密碼貼出以求助網(wǎng)友。電碼如下：“****-/*----/----*/****-/****-/*----/---**/*----/****-/*----/-****/***--/****-/*----/----*/**---/-****/**---/**---/***--/--***/****-/”

“她唯一給我的提示就是這個(gè)是5層加密的密碼，也就是說(shuō)要破解5層密碼才是答案。最終語(yǔ)言是英語(yǔ)。

”網(wǎng)友貼出了莫爾斯密碼對(duì)照表，然后發(fā)現(xiàn)相應(yīng)密碼對(duì)應(yīng)的數(shù)字組合和英文字母組合分別是：“4194418141634192622374”、“daiddahadafcdaibfbbcgd”網(wǎng)友“片羿天使”將莫爾斯密碼對(duì)應(yīng)的數(shù)字“4194418141634192622374”轉(zhuǎn)換成了手機(jī)鍵盤(pán)字母,以41為例，它對(duì)應(yīng)的就是傳統(tǒng)手機(jī)鍵盤(pán)上的“4”的第一個(gè)字母，“94”則是“9”的第4個(gè)字母。這樣片羿天使得到了第二步的答案：“GZGTGOGXNCS”。

片羿天使說(shuō)“因?yàn)镼WE的格式是被世人所認(rèn)可的，也就有可能成為密碼的碼表。碼表QWE=ABC依次類(lèi)推?！卑凑者@樣的次序，上面的來(lái)自于手機(jī)鍵盤(pán)的字母，就轉(zhuǎn)換到了第三步答案：“OTOEOIOUYVL”。案例：莫爾斯電碼里的愛(ài)情

在第四步中，片羿天使用了包括凱撒、乘法等等方法，對(duì)第三步幾乎可以看出來(lái)的答案進(jìn)行了進(jìn)一步的解碼，最后發(fā)現(xiàn)只有柵欄密碼才能讀得通。片羿天使將這組字母分成了“OTOEOI”和“OUYVL”兩排，然后對(duì)插重組得到第四步的字母排列：“OOTUOYEVOLI”。第五步于是變得最為簡(jiǎn)單起來(lái)，那便是將“OOTUOYEVOLI”倒序排列，即“ILOVEYOUTOO”。案例：莫爾斯電碼里的愛(ài)情

2.1

基本概念2.1.1什么是密碼學(xué)密碼學(xué)是研究密碼系統(tǒng)或通信安全的一門(mén)學(xué)科，分為密碼編碼學(xué)和密碼分析學(xué)。密碼編碼學(xué)是使得消息保密的學(xué)科密碼分析學(xué)實(shí)際要研究加密消息破譯的學(xué)科密碼學(xué)的發(fā)展歷史第1階段：1949年以前。

第2階段：從1949年到1975年。標(biāo)志：1949年Shannon發(fā)表的《保密系統(tǒng)的信息理論》一文。第3階段：1976年至今。標(biāo)志：1976年Diffie和Hellman發(fā)表了《密碼學(xué)新方向》一文。Shannon模型X,明文（plain-text）：作為加密輸入的原始信息。Y,密文（cipher-text）：對(duì)明文變換的結(jié)果。E,加密（encrypt）：是一組含有參數(shù)的變換。D,解密（decrypt）：加密的逆變換。Z,密鑰（key）：是參與加密解密變換的參數(shù)。密碼系統(tǒng)（Cryptosystem）定義:(密碼體制）它是一個(gè)五元組（P,C,K,E,D)滿(mǎn)足條件：（1）P是可能明文的有限集；（明文空間）（2）C是可能密文的有限集；（密文空間）（3）K是一切可能密鑰構(gòu)成的有限集；（密鑰空間）*（4）任意,有一個(gè)加密算法和相應(yīng)的解密算法，使得和分別為加密解密函 數(shù)，滿(mǎn)足。密碼體制的分類(lèi)幾種不同的分類(lèi)標(biāo)準(zhǔn)按操作方式進(jìn)行分類(lèi)操作方式：是明文變換成密文的方法。替代操作、置換操作、復(fù)合操作。按照使用密鑰的數(shù)量進(jìn)行分類(lèi)對(duì)稱(chēng)密鑰（單密鑰）。公開(kāi)密鑰（雙密鑰）。按照對(duì)明文的處理方法進(jìn)行分類(lèi)流密碼。分組密碼?？驴嘶舴蛩?Kerckhoffs)假設(shè)假定：密碼分析者知道對(duì)方所使用的密碼系統(tǒng)包括明文的統(tǒng)計(jì)特性、加密體制（操作方式、處理方法和加/解密算法）、密鑰空間及其統(tǒng)計(jì)特性。不知道密鑰。密碼體制的安全性?xún)H應(yīng)依賴(lài)于對(duì)密鑰的保密，而不應(yīng)依賴(lài)于對(duì)算法的保密。只有在假設(shè)攻擊者對(duì)密碼算法有充分的研究，并且擁有足夠的計(jì)算資源的情況下仍然安全的密碼才是安全的密碼系統(tǒng)。一切秘密寓于密鑰之中

密碼分析密碼分析：從密文推導(dǎo)出明文或密鑰。密碼分析：常用的方法有以下4類(lèi)：惟密文攻擊（cybertextonlyattack）：密碼分析者有一個(gè)或更多的用同一個(gè)密鑰加密的密文，通過(guò)對(duì)這些截獲的密文進(jìn)行分析得出明文或密鑰已知明文攻擊（knownplaintextattack）：除要破譯的密文外，密碼分析者有一些明文和用同一密鑰加密這些明文所對(duì)應(yīng)的密文。選擇明文攻擊（chosenplaintextattack）：密碼分析者可得到所需要的任何明文所對(duì)應(yīng)的密文，這些密文與要破譯的密文是用同一個(gè)密鑰加密得來(lái)的選擇密文攻擊（chosenciphertextattack）：密碼分析者可得到所需要的任何密文所對(duì)應(yīng)的明文，解密這些密文所使用的密鑰與要破譯的密文的密鑰是相同的密碼分析

密碼系統(tǒng)一個(gè)好的密碼系統(tǒng)應(yīng)滿(mǎn)足：系統(tǒng)理論上安全，或計(jì)算上安全；系統(tǒng)的保密性是依賴(lài)于密鑰的，而不是依賴(lài)于對(duì)加密體制或算法的保密；加密和解密算法適用于密鑰空間中的所有元素；系統(tǒng)既易于實(shí)現(xià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ā)送的消息。古典加密技術(shù)從古到今有無(wú)數(shù)種加密方法，但歸類(lèi)起來(lái)，古代主要是代替密碼、置換密碼以及兩者的結(jié)合。代替密碼簡(jiǎn)單代替密碼多碼代替密碼多字母代替密碼多表代替密碼置換密碼：換位密碼2.2

傳統(tǒng)密碼及其破譯Scytale密碼和愷撒密碼最先有意識(shí)的使用一些技術(shù)的方法來(lái)加密信息的可能是公元前500年的古希臘人。他們使用的是一根叫scytale的棍子。送信人先繞棍子卷一張紙條，然后把要寫(xiě)的信息打縱寫(xiě)在上面，接著打開(kāi)紙送給收信人。如果不知道棍子的粗細(xì)是不可能解密里面的內(nèi)容的，如下圖所示。公元前50年，著名的愷撒大帝發(fā)明了一種密碼叫做愷撒密碼。在愷撒密碼中，每個(gè)字母都與其后第三位的字母對(duì)應(yīng)，然后進(jìn)行替換。如果到了字母表的末尾，就回到開(kāi)始，如此形成一個(gè)循環(huán)。當(dāng)時(shí)羅馬的軍隊(duì)就用愷撒密碼進(jìn)行通信。愷撒密碼明文字母表：ABCDEFG…XYZ愷撒密碼密文字母表：DEFGHIJ…ABC26個(gè)字符代表字母表的26個(gè)字母，從一般意義上說(shuō)，也可以使用其它字符表，一一對(duì)應(yīng)的數(shù)字也不一定要是3，可以選其它數(shù)字。Caesar密碼乘數(shù)密碼算法加密函數(shù)取形式為e(x)=ax(mod26)，

a∈Z26

要求唯一解的充要條件是gcd(a,26)=1

該算法描述為：

設(shè)P=C=Z26，K={a∈Z26|gcd(a,26)=1},對(duì)k=a∈K,

定義ek(x)=ax(mod26)和dk(y)=a-1(y)(mod26)，x,y∈Z26例子:a=9,ABCDEFGHIJKLMNOPQRSTUVWXYZAJSBKTCLUDMVENWFOXGPYHQZIR

明文密文

cipher=>SUFLKX乘數(shù)密碼分析對(duì)于乘數(shù)密碼，當(dāng)且僅當(dāng)a與26互素時(shí)，加密變換才是一一映射的，因此a的選擇有11種：

a=3,5,7,9,11,15,17,19,21,23,25可能?chē)L試的密鑰只有11個(gè)柵欄密碼所謂柵欄密碼，就是把要加密的明文分成N個(gè)一組，然后把每組的第i個(gè)字連起來(lái)，形成一段無(wú)規(guī)律的話(huà)。就是組成柵欄的字母一般不會(huì)太多。（一般不超過(guò)30個(gè)）一般比較常見(jiàn)的是2欄的柵欄密碼。比如明文：THEREISACIPHER去掉空格后變?yōu)椋篢HEREISACIPHER兩個(gè)一組，得到：THEREISACIPHER先取出第一個(gè)字母：TEESCPE再取出第二個(gè)字母：HRIAIHR連在一起就是：TEESCPEHRIAIHR解密的時(shí)候，我們先把密文從中間分開(kāi)，變?yōu)閮尚校?/p>

TEESCPE

HRIAIHR再按上下上下的順序組合起來(lái)：

THEREISACIPHER分出空格，就可以得到原文了：

THEREISACIPHER柵欄密碼仿射密碼仿射密碼是一種替換密碼。它是一個(gè)字母對(duì)一個(gè)字母的。它的加密函數(shù)是

，其中

a和m互質(zhì)。

m是字母的數(shù)目。解密函數(shù)為：例設(shè)k＝（7，3），注意到7-1(mod26)=15,加密函數(shù)是ek(x)=7x+3，相應(yīng)的解密函數(shù)是dk(y)=15(y-3)=15y-19,易見(jiàn)dk(ek(x)=dk(7x+3)=15(7x+3)-19=x+45-19=x(mod26)

若加密明文：hot，首先轉(zhuǎn)換字母h,o,t成為數(shù)字7,14,19,然后加密：解密：希爾密碼希爾密碼（HillPassword）是運(yùn)用基本矩陣論原理的多字母代換密碼，由LesterS.Hill在1929年發(fā)明。每個(gè)字母當(dāng)作26進(jìn)制數(shù)字：A=0,B=1,C=2...一串字母當(dāng)成n維向量，跟一個(gè)n×n的矩陣相乘，再將得出的結(jié)果模26。注意用作加密的矩陣（即密匙）是可逆的，否則就不可能譯碼。只有矩陣的行列式和26互質(zhì)，才是可逆的。其中所有的運(yùn)算都是在中進(jìn)行。例假定密鑰K是，則K-1=?，F(xiàn)在我們加密明文july分為兩個(gè)明文組（9，20）（相應(yīng)于ju）和（11，24）（相應(yīng)于ly）。計(jì)算如下：因此，july的加密是DELW。同理，可使用K-1進(jìn)行解密。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)換為字母串。例

設(shè)m＝6，且密鑰字是k=CIPHER,這相應(yīng)于密鑰。假定明文串是thiscryptosystemisnotsecure

首先將明文串轉(zhuǎn)化為數(shù)字串，按6個(gè)一組分段，然后模26“加”上密鑰字得：相應(yīng)的密文串將是: VPXZGIAXIVWPUBTTMJPWIZITWZT解密過(guò)程與加密過(guò)程類(lèi)似,不同的只是進(jìn)行模26減,而不是模26加。

置換密碼在簡(jiǎn)單的縱行置換密碼中，把明文按列寫(xiě)入，按行讀出，而密鑰事實(shí)上由兩方面信息組成：行寬、列高，讀出順序默認(rèn)從左到右。一個(gè)簡(jiǎn)單縱行置換密碼比如：明文：computergraphicsmaybeslow，按照列寬10個(gè)字符的方式寫(xiě)出為：computergraphicsmaybeslow可以得到密文：caeopsmhlpioucwtsemragyrb，下面是一個(gè)由密鑰確定讀出順序的例子：如果再加上密鑰：密鑰： 4 3125 6 7明文： a t t a c k p o s t p o n e d u n t i l t w o a m x y z按照密鑰大小的順利，按照列的字符得到密文：TTNAAPTMTSUOAODWCOIXPETZ。置換密碼例

假定m＝6，密鑰是以下置換：；則逆置換為：。給出明文

shesellsseashellsbytheseashore.

首先把明文分為6個(gè)字母一組：

shesel

lsseas

hellsb

ytheseashore.

每六個(gè)字母按重排，得密文：

EESLSHSALSESLSHBLEHSYEETHRAEOS

用類(lèi)似地解密。置換密碼置換密碼是Hill密碼的特例。Playfair密碼Playfair在1854年發(fā)明了Playfair密碼。在第一次世界大戰(zhàn)中英國(guó)人就使用這種密碼。Playfair將明文中的雙字母組合作為一個(gè)單元對(duì)待，并將這些單元轉(zhuǎn)換為密文的雙字母組合。I與J視為同一字符，5×5變換矩陣為

C I P H E R A B D F G K L M N O Q S T U V W X Y Z加密規(guī)則是按成對(duì)字母加密，規(guī)則為“相同對(duì)中的字母加分隔符(如x)，同行取右邊，同列取下邊，其他取交叉”。明文：balloon單詞中的ll為相同字符，所以分組為：balxloon明文：he，h和e在矩陣中同一行，都取右邊的字符，密文為：EC明文：dm，d和m在矩陣中同一列，都取下面的字符，密文為：MT明文：kt，k和t在矩陣中不同行也不同列，取交叉頂點(diǎn)上的字符，密文為：MQ明文：OD，O和D在矩陣中不同行也不同列，取交叉頂點(diǎn)上的字符，密文為：TR以這個(gè)5×5變換矩陣為例，可以對(duì)單詞進(jìn)行加密，加密結(jié)果如表2-1所示。表2-1明文分組密文balloonbalxloondbspgs

ugbookbooksr

qgfillfilxlxaespsp一次一密亂碼本如上所述的所有密碼算法均被破解，那么是否存在無(wú)法破解的理想加密方案呢？香農(nóng)證明了一種密碼屬于這種情況，它就是一次一密亂碼本（one-timepad）。一般說(shuō)來(lái)，一次一密亂碼本就是一個(gè)大的不重復(fù)的真隨機(jī)密鑰字母集，發(fā)送者用亂碼本中的每一個(gè)密鑰準(zhǔn)確地加密一個(gè)明文字符，加密是明文字符和密鑰字符進(jìn)行模26加法。比如：明文： onetimepad密鑰： TBFRGFARFM密文： IPKLPSFHGQ因?yàn)椋?O+Tmod26=I，N+Bmod26=P，E+Fmod26=K，……如果竊聽(tīng)者不能得到用來(lái)加密的一次一密亂碼本，這個(gè)方案就是完全保密的。給出的密文消息相當(dāng)于同樣長(zhǎng)度的任何可能的明文消息。隨機(jī)密鑰安全強(qiáng)度取決于密鑰的隨機(jī)性理論上不可破實(shí)際上不可行產(chǎn)生大量的隨機(jī)密鑰難密鑰分配與保護(hù)更難明文：Tobeornottobethatisthequestion,使用Vigenère加密，密鑰字取為run密鑰：runrunrunrunrunrunrunrunrunrun

明文：tobeornottobethatisthequestion密文：KIOVIEEIGKIOVNURNVJNUVKHVMGZIAKIOV，后一個(gè)相當(dāng)于前一個(gè)向后移動(dòng)了9位；NU，后一個(gè)相當(dāng)于前一個(gè)向后移動(dòng)了6位。重復(fù)明文字母串的距離正好是密鑰長(zhǎng)度的倍數(shù)。Vigenère密碼的密碼分析Vigenère密碼的密碼分析第一步：確定密鑰的長(zhǎng)度，主要方法有：Kasiski測(cè)試法；

基本原理：對(duì)于密鑰長(zhǎng)度為d的Vigenère密碼，如果利用給定的密鑰表周期性地對(duì)明文字母進(jìn)行加密，則當(dāng)明文中有兩個(gè)相同的字母組在明文序列中間隔的字母數(shù)為d的倍數(shù)時(shí)，這兩個(gè)明文字母組對(duì)應(yīng)的密文字母組一定相同；反之，如果密文中出現(xiàn)兩個(gè)相同的字母組，則其對(duì)應(yīng)的明文字母組不一定相同。重合指數(shù)法。

基本思想：對(duì)于長(zhǎng)度分別為n的密文串y=y1y2…yn，將其分為長(zhǎng)度為n/d的d個(gè)子串Yi（i=1,2,…,d),如果密鑰長(zhǎng)度為d，則Ic(Yi)≈0.065(1≤i≤d)，否則，因?yàn)椴捎貌煌拿荑€依位加密，子串Yi將更為隨機(jī)。對(duì)于一個(gè)完全隨機(jī)的密文串，Ic(y)≈26(1/26)2=0.038。由于0.038與0.065的差值足夠大，所以在一般情況下，依據(jù)重合指數(shù)法能夠判斷出正確的密鑰長(zhǎng)度。Vigenère密碼的密碼分析第二步：確定密鑰。通常采用重合互指數(shù)法。對(duì)于長(zhǎng)度分別為n及n′的字母串x=x1x2…xn和y=y1y2…yn，“重合互指數(shù)”指的是x的一個(gè)隨機(jī)元素與y的一個(gè)隨機(jī)元素相同的概率，記為MIc(x,y)。通過(guò)采用重合互指數(shù)法，可以獲得任何兩個(gè)子串Yi與Yj的相對(duì)移位。

古典密碼小結(jié)模運(yùn)算：加法、減法、乘法性質(zhì)：對(duì)稱(chēng)、傳遞、交換、結(jié)合、分配加法逆元、乘法逆元對(duì)稱(chēng)密碼的兩個(gè)基本運(yùn)算代替和置換（Substitution&permutation）密碼分析與Kerckhoff原則多輪加密數(shù)據(jù)安全基于算法的保密

古典密碼小結(jié)2.3Shannon的保密系統(tǒng)信息理論1949年，Shannon發(fā)表了一篇題為《保密系統(tǒng)的信息理論》的論文。用信息論的觀(guān)點(diǎn)對(duì)信息保密問(wèn)題進(jìn)行了全面的闡述。宣告了科學(xué)的密碼學(xué)時(shí)代的到來(lái)。什么是信息科學(xué)家說(shuō)：信息是不確定性的減少，是負(fù)熵老百姓說(shuō)：信息是讓你知道些什么的東西安全專(zhuān)家說(shuō)：信息是一種資產(chǎn)，它意味著一種風(fēng)險(xiǎn)老百姓說(shuō)：不怕賊偷，就怕賊惦記通信系統(tǒng)模型編碼器信源信道信宿譯碼器干擾器圖2.2通信系統(tǒng)模型加密器信源信道接收者解密器分析者圖2.3保密系統(tǒng)模型密鑰Shannon提出的保密模型無(wú)噪信道安全信道密鑰源加密分析者解密接收者發(fā)送者信源圖2.3Shannon的保密系統(tǒng)模型數(shù)學(xué)模型數(shù)學(xué)模型樣本空間密鑰空間密文空間概率知識(shí)討論在給定密文發(fā)生的條件下，某個(gè)明文發(fā)生的條件概率信息量和熵定義

設(shè)隨機(jī)變量，出現(xiàn)的概率為。則X的不確定性或熵（Entropy）定義為

熵反映了集中事件出現(xiàn)的平均不確定性，或?yàn)榇_定集中出現(xiàn)一個(gè)事件平均所需的信息量（觀(guān)測(cè)之前），或集中每出現(xiàn)一個(gè)事件平均給出的信息量（觀(guān)測(cè)之后）。如果從編碼的角度來(lái)考慮，熵也可以理解成用最優(yōu)的二進(jìn)制編碼形式表示所需的比特?cái)?shù)。采用以2為底的對(duì)數(shù)時(shí)，相應(yīng)的信息單位稱(chēng)作比特（Bit）。如果集X為均勻分布時(shí)，即，則。，當(dāng)X為確定性的事件時(shí)，即X概率分布為，則。例：某地某季節(jié)各種天氣情況出現(xiàn)的概率分別為晴：50%，陰：25%，大雨：12.5%，小雨：12.5%。請(qǐng)問(wèn)某人聽(tīng)到一則天氣預(yù)報(bào)后獲得的信息量是多少？（也可以理解為：這則天氣預(yù)報(bào)消除了多少人們對(duì)天氣情況認(rèn)識(shí)的不確定性？）解：=0.5×log21/0.5+0.25×log21/0.25+0.125×log21/0.125+0.125×log21/0.125=1.75bit

H=∑Pilog2

1Pi

4i=1信息量和熵案例韋小寶賭博：韋小寶擲骰子賭錢(qián)十賭九贏。計(jì)算包含的信息量？未做手腳情況：等概率事件，不確定性為：

H(S)=-log(pi)=-log(1/6)=2.5850(bit)做手腳情況：某面的概率為0.9，其他5面的概率均為1/50，則不確定性為：

H(S)=-pi

log(pi)=-0.9log(0.9)-5×0.02log(0.02)=0.7012(bit)韋小寶賭博定義設(shè)，出現(xiàn)的概率為。，出現(xiàn)的概率為，則聯(lián)合事件集，令的概率為，此時(shí)。集X和Y的聯(lián)合熵定義為集相對(duì)于事件yi∈Y的條件熵定義為集相對(duì)于集Y的條件熵定義為熵的基本特性定理，當(dāng)且僅當(dāng)X和Y獨(dú)立時(shí)等號(hào)成立。定理。推論

，當(dāng)且僅當(dāng)X和Y獨(dú)立時(shí)等號(hào)成立。密碼體制的安全性（1）無(wú)條件安全或完善保密性（unconditionallysecure）：不論提供的密文有多少，密文中所包含的信息都不足以惟一地確定其對(duì)應(yīng)的明文；具有無(wú)限計(jì)算資源（諸如時(shí)間、空間、資金和設(shè)備等）的密碼分析者也無(wú)法破譯某個(gè)密碼系統(tǒng)。完善保密性一個(gè)保密系統(tǒng)（P，C，K，E，D）稱(chēng)為完善的無(wú)條件的保密系統(tǒng)，如果H(P)=H(P|C),其中，P為明文集合，C為密文集合，K為密鑰集合，E為加密算法,D為解密算法,則完善保密系統(tǒng)存在的必要條件是H(P)≤H(K)。可見(jiàn)，要構(gòu)造一個(gè)完善保密系統(tǒng)，其密鑰量的對(duì)數(shù)（密鑰空間為均勻分布的條件下）必須不小