第1章 古典密碼

主講人：侯紅霞通信與信息工程學(xué)院第1章古典密碼密碼學(xué)的起源和發(fā)展密碼學(xué)有著悠久而神秘的歷史，人們很難對(duì)密碼學(xué)的起始時(shí)間給出準(zhǔn)確的定義。Phaistos圓盤(pán)

Phaistos圓盤(pán)，一種直徑約為160mm的Cretan-Mnoan粘土圓盤(pán)，始于公元前17世紀(jì)。表面有明顯字間空格的字母，至今還沒(méi)有破解。三個(gè)階段：1949年之前密碼學(xué)是一門(mén)藝術(shù)1949～1975年密碼學(xué)成為科學(xué)1976年以后密碼學(xué)的新方向——公鑰密碼學(xué)

第1階段—從古代到1949年這一時(shí)期可以看作是科學(xué)密碼學(xué)的前夜時(shí)期，這階段的密碼技術(shù)可以說(shuō)是一種藝術(shù)，而不是一種科學(xué)，密碼學(xué)專(zhuān)家常常是憑知覺(jué)和信念來(lái)進(jìn)行密碼設(shè)計(jì)和分析，而不是推理和證明。主要特點(diǎn)：數(shù)據(jù)的安全基于算法的保密。第1階段—從古代到1949年隱寫(xiě)術(shù)（公元前440年出現(xiàn)在古希臘戰(zhàn)爭(zhēng)中）。當(dāng)時(shí)為了安全傳送軍事情報(bào)，奴隸主剃光奴隸的頭發(fā)，將情報(bào)寫(xiě)在奴隸的光頭上，待頭發(fā)長(zhǎng)長(zhǎng)后將奴隸送到另一個(gè)部落，再次剃光頭發(fā)，原有的信息復(fù)現(xiàn)出來(lái)，從而實(shí)現(xiàn)這兩個(gè)部落之間的秘密通信。第1階段—從古代到1949年密碼學(xué)用于通信的另一個(gè)記錄是斯巴達(dá)人于公元前400年應(yīng)用Scytale加密工具在軍官間傳遞秘密信息。時(shí)間：公元前405年，雅典和斯巴達(dá)之間的伯羅奔尼撒戰(zhàn)爭(zhēng)已進(jìn)入尾聲的時(shí)候。起因：斯巴達(dá)軍隊(duì)逐漸占據(jù)了優(yōu)勢(shì)地位，準(zhǔn)備對(duì)雅典發(fā)動(dòng)最后一擊。原來(lái)站在斯巴達(dá)一邊的波斯帝國(guó)突然改變態(tài)度，停止了對(duì)斯巴達(dá)的援助，意圖使雅典和斯巴達(dá)在持續(xù)的戰(zhàn)爭(zhēng)中兩敗俱傷，以便從中漁利。截獲信使：斯巴達(dá)軍隊(duì)捕獲了一名從波斯帝國(guó)回雅典送信的雅典信使。斯巴達(dá)士兵仔細(xì)搜查這名信使，可搜查了好大一陣，除了從他身上搜出一條布滿(mǎn)雜亂無(wú)章的希臘字母的普通腰帶外，別無(wú)他獲。破譯密碼：斯巴達(dá)軍隊(duì)統(tǒng)帥萊桑德把腰帶上的字母用各種方法重新排列組合，怎么也解不出來(lái)。最后，當(dāng)他無(wú)意中把腰帶呈螺旋形纏繞在手中的劍鞘上時(shí)，奇跡出現(xiàn)了。原來(lái)腰帶上那些雜亂無(wú)章的字母，竟組成了一段文字。是雅典間諜送回的一份情報(bào)！戰(zhàn)爭(zhēng)結(jié)果：斯巴達(dá)軍隊(duì)根據(jù)這份情報(bào)馬上改變了作戰(zhàn)計(jì)劃，先以迅雷不及掩耳之勢(shì)攻擊毫無(wú)防備的波斯軍隊(duì)，并一舉將它擊潰，解除了后顧之憂(yōu)。隨后，斯巴達(dá)軍隊(duì)回師征伐雅典，終于取得了戰(zhàn)爭(zhēng)的最后勝利。影響:后來(lái)，這種密碼通信方式在希臘廣為流傳?，F(xiàn)代的密碼電報(bào)，據(jù)說(shuō)就是受了它的啟發(fā)而發(fā)明的。第1階段—從古代到1949年我國(guó)古代也早有以藏頭詩(shī)、藏尾詩(shī)、漏格詩(shī)及繪畫(huà)等形式，將要表達(dá)的真正意思或“密語(yǔ)”隱藏在詩(shī)文或畫(huà)卷中特定位置的記載，一般人只注意詩(shī)或畫(huà)的表面意境，而不會(huì)去注意或很難發(fā)現(xiàn)隱藏其中的“話(huà)外之音”。第1階段—從古代到1949年到了20世紀(jì)20年代，隨著機(jī)械和機(jī)電技術(shù)的成熟，以及電報(bào)和無(wú)線(xiàn)電需求的出現(xiàn)，引起了密碼設(shè)備方面的一場(chǎng)革命——發(fā)明了轉(zhuǎn)輪密碼機(jī)（簡(jiǎn)稱(chēng)轉(zhuǎn)輪機(jī)，Rotor），轉(zhuǎn)輪機(jī)的出現(xiàn)是密碼學(xué)發(fā)展的重要標(biāo)志之一。德國(guó)的洛倫茲密碼機(jī)恩尼格瑪密碼機(jī)(Enigma

)1.丘吉爾犧牲考文垂1940年11月12日，德軍空軍司令部按希特勒指令發(fā)出命令，派空軍機(jī)群于14—15日對(duì)英國(guó)內(nèi)陸的中心實(shí)行猛烈轟炸，具體目標(biāo)是英國(guó)的重要城市考文垂城，并將此計(jì)劃命名為“月光奏鳴曲”。所使密碼機(jī)：“英尼格碼”(又稱(chēng)“啞謎”)。但是，德國(guó)不知道的是，早在1939年8月，英情報(bào)機(jī)關(guān)就截獲并破譯了這個(gè)“超級(jí)密碼”。兩難選擇:一是采取主動(dòng)措施保衛(wèi)考文垂。不過(guò)這樣一來(lái)，德國(guó)人極有可能懷疑自己的密碼被破譯，以后就會(huì)更換新的密碼系統(tǒng)，“超級(jí)機(jī)密”將失去作用。另一種方案是讓考文垂的防務(wù)措施原封不動(dòng)，對(duì)空襲作出合乎常情的反應(yīng)，用犧牲考文垂來(lái)保住“超級(jí)機(jī)密”。14日下午，丘吉爾考慮再三，最后忍痛作出決定：考文垂不做防御疏散?？嘉拇闺m然遭受了慘重的損失，但歷史證明丘吉爾這一“丟卒保車(chē)”的辦法，為最終打敗德國(guó)法西斯做出了巨大貢獻(xiàn)。英國(guó)情報(bào)機(jī)構(gòu)利用它掌握的“超級(jí)機(jī)密”，多次截獲敵人的重大情報(bào)，給予德軍以沉重的打擊，最終迫使希特勒放棄了在英國(guó)登陸作戰(zhàn)的“海獅計(jì)劃”。1942年11月，在北非阿拉曼戰(zhàn)場(chǎng)上，“超級(jí)機(jī)密”提供的情報(bào)又發(fā)揮重大作用。由于英國(guó)蒙哥馬利將軍對(duì)德國(guó)隆美爾的非洲軍團(tuán)的戰(zhàn)略戰(zhàn)術(shù)計(jì)劃、實(shí)力部署、后勤供給事先了如指掌，僅僅13天，德軍就損失6萬(wàn)人和500多輛坦克。德國(guó)“沙漠之狐”慘敗于非洲沙漠。2.“紫色”密碼“紫色”（Purple）是美國(guó)軍隊(duì)給日本外務(wù)?。ㄍ饨徊浚┰诘诙问澜绱髴?zhàn)期間使用的一種機(jī)械式密碼所起的名字。美國(guó)人習(xí)慣用顏色來(lái)命名日本人的各種密碼。如此前日本外交官使用的密碼被稱(chēng)為“紅色”?！白仙泵艽a機(jī)由日本海軍技術(shù)研究所的技師田道一雄設(shè)計(jì)制造。據(jù)稱(chēng)曾請(qǐng)日本的著名代數(shù)學(xué)家高木貞治（1875-1960）評(píng)價(jià)，得到答復(fù)說(shuō)此機(jī)的密碼有無(wú)數(shù)的變化，不可能被破解。日本政府相信了這位其實(shí)不大懂密碼的大數(shù)學(xué)家的話(huà)，正式啟用“紫色”密碼機(jī)。事實(shí)上，“紫色”密碼很快就被美國(guó)陸軍所屬的“信號(hào)情報(bào)局”破譯，其中的關(guān)鍵人物是弗里德曼（WilliamF.Friedman,1891-1969）和羅烈（FrankByronRowlett，1908-1998）。中途島事件(1942年6月3日)山本五十六之死事件(1943年4月18日)密碼的破譯導(dǎo)致二戰(zhàn)提前兩年結(jié)束。第2階段—從1949年到1975年1949年Shannon發(fā)表了題為《CommunicationTheoryofSecrecySystems》(/wiki/files/shannon1949.pdf)的著名論文，把密碼學(xué)置于堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)之上，標(biāo)志著密碼學(xué)作為一門(mén)學(xué)科的形成，這是密碼學(xué)的第一次飛躍。主要特點(diǎn)：數(shù)據(jù)安全基于密鑰而不是算法的保密?？藙诘?香農(nóng)(ClaudeElwoodShannon，1916-2001)第3階段—從1976年至今1976年，W．Diffie和M．Hellman在發(fā)表的文章《Newdirectionsincryptography

》(

/reports/DiffieHellman.pdf)中提出了公開(kāi)密鑰的思想，從而開(kāi)創(chuàng)了公鑰密碼學(xué)的新紀(jì)元，導(dǎo)致了密碼學(xué)上的一場(chǎng)革命，這是密碼學(xué)的第二次飛躍。主要特點(diǎn)：公鑰密碼使得發(fā)送端和接收端無(wú)需密鑰傳輸?shù)谋Ｃ芡ㄐ懦蔀榭赡?。WhitfieldDiffieMartinHellman

第3階段—從1976年至今受Diffie和Hellman的思想啟迪，各種公鑰密碼體制被提出，特別是1978年RSA公鑰密碼體制的出現(xiàn)，成為公鑰密碼的杰出代表，并成為事實(shí)標(biāo)準(zhǔn)，在密碼學(xué)史上是一個(gè)里程碑。

RSA三杰

第1章古典密碼1.密碼學(xué)基本概念2.幾種典型的古典密碼體制3.古典密碼的統(tǒng)計(jì)分析1.1密碼學(xué)的基本概念密碼學(xué)（cryptology）作為數(shù)學(xué)的一個(gè)分支，是密碼編碼學(xué)和密碼分析學(xué)的統(tǒng)稱(chēng)。使消息保密的技術(shù)和科學(xué)叫做密碼編碼學(xué)（cryptography)破譯密文的科學(xué)和技術(shù)就是密碼分析學(xué)（cryptanalysis）

編碼學(xué)研究的主要內(nèi)容：序列密碼算法的編碼技術(shù)分組密碼算法的編碼技術(shù)公鑰密碼體制的編碼技術(shù)加密算法、數(shù)字簽名方案、密鑰分配方案認(rèn)證方案單向函數(shù)等傳統(tǒng)且主流的研究方向密碼分析學(xué)研究的主要內(nèi)容（1）密碼算法的安全性分析和破譯的理論、方法、技術(shù)和實(shí)踐（2）密碼協(xié)議的安全性分析的理論與方法（3）安全保密系統(tǒng)的安全性分析和攻擊的理論、方法、技術(shù)和實(shí)踐從密碼產(chǎn)生的那天起，密碼編碼和密碼破譯的斗爭(zhēng)一刻也沒(méi)有停止。雙方在相生相克的斗爭(zhēng)中此消彼長(zhǎng)，不斷地提高各自的密碼研制技術(shù)，結(jié)果大大促進(jìn)了密碼學(xué)的發(fā)展。密碼學(xué)是干什么的?密碼學(xué)要解決的基本問(wèn)題:

(1)信息的保密傳輸和存儲(chǔ)問(wèn)題;(2)信息的認(rèn)證問(wèn)題.

例:我收到你寫(xiě)給我1封信,那么我問(wèn):----信的內(nèi)容是否被改動(dòng)?----是否真是你寫(xiě)的信?----是否真是寫(xiě)給我信?----有沒(méi)有人看過(guò)這封信？密碼學(xué)能夠解決的問(wèn)題1.信息系統(tǒng)的安全與保密問(wèn)題；2.電子商務(wù)、電子政務(wù)中的安全和保密問(wèn)題；3.銀行系統(tǒng)、證券系統(tǒng)、保險(xiǎn)系統(tǒng)等的安全問(wèn)題；4.商品、票據(jù)、信用卡等的防偽與審核問(wèn)題。1.1密碼學(xué)的基本概念密碼學(xué)的基本目的是面對(duì)攻擊者Oscar，在被稱(chēng)為Alice和Bob的通信雙方之間應(yīng)用不安全的信道進(jìn)行通信時(shí)，保證通信安全。明文密文明文AliceBobOscar1.1密碼學(xué)的基本概念密碼體制的定義定義1.1.1密碼體制：密碼體制的構(gòu)成包括以下要素：（1）M：明文消息空間，表示所有可能的明文組成的有限集。（2）C：密文消息空間，表示所有可能的密文組成的有限集。（3）K：密鑰空間，表示所有可能的密鑰組成的有限集。（4）E：加密算法集合。（5）D：解密算法集合。1.1密碼學(xué)的基本概念明文密文明文AliceBob加密密匙解密密匙保密通信的一般機(jī)制1.1密碼學(xué)的基本概念密碼體制的分類(lèi)對(duì)稱(chēng)密匙密碼系統(tǒng)SymmetricKeyCryptosystem

加密密鑰=解密密鑰

非對(duì)稱(chēng)密匙密碼系統(tǒng)AsymmetricKeyCryptosystem

加密密鑰≠解密密鑰

鑰匙是保密的

加密密鑰為公鑰（PublicKey）解密密鑰為私鑰（PrivateKey）1.1密碼學(xué)的基本概念1.1密碼學(xué)的基本概念1.2古典密碼體制1.棋盤(pán)密碼2.移位密碼3.代換密碼4.維吉尼亞密碼5.仿射密碼6.置換密碼7.Hill密碼1棋盤(pán)密碼棋盤(pán)密碼是公元前2世紀(jì)前后由希臘作家Polybius提出來(lái)的，在當(dāng)時(shí)得到了廣泛的應(yīng)用。棋盤(pán)密碼的密鑰如下表所示：123451ABCDE2FGHI/JK3LMNOP4QRSTU5VWXYZ123451qwert2yui/jop3asdfg4hklzx5cvbnmsecurity3213512214231521security2移位密碼移位密碼的加密對(duì)象為英文字母，移位密碼采用對(duì)明文消息的每一個(gè)英文字母向前推移固定位的方式實(shí)現(xiàn)加密。換句話(huà)說(shuō)，移位密碼實(shí)現(xiàn)了26個(gè)英文字母的循環(huán)移位。移位密碼中，當(dāng)取密鑰k=3時(shí)，得到的移位密碼稱(chēng)為凱撒密碼，因?yàn)樵撁艽a體制首先被JuliusCaesar所使用。ABCDEFGHIJKLM00010203040506070809101112NOPQRSTUVWXYZ13141516171819202122232425假設(shè)明文為：security180402201708192425110901241502051804022017081924security加密解密zljbypcf3代換密碼定義1.2.3代換密碼體制：令是上所有可能置換構(gòu)成的集合。對(duì)任意的置換這里和互為逆置換。，定義：ABCDEFGHIJKLMqwertyuiopasdNOPQRSTUVWXYZfghjklzxcvbnm假設(shè)明文為：securityktexloznsecurity加密：解密：4維吉尼亞密碼單表代換密碼---移位密碼、仿射密碼等等多表代換密碼----維吉尼亞密碼（Vigenèrecipher），它是由法國(guó)人BlaisedeVigenère在16世紀(jì)提出的。定義1.2.4維吉尼亞密碼體制：令是一個(gè)正整數(shù)，。對(duì)任意的密鑰定義:如果已經(jīng)在26個(gè)英文字母和之間建立了一一對(duì)應(yīng)的關(guān)系，則每一個(gè)密鑰都相當(dāng)于一個(gè)長(zhǎng)度為m的字母串，被稱(chēng)為密鑰字。security18040220170819241804022017081924like110810042912122428162928Mod260312122402160302DMMYCQDC加密密文5仿射密碼仿射密碼是移位密碼的一個(gè)推廣，其加密過(guò)程中不僅包含移位操作，而且使用了乘法運(yùn)算。

令密鑰空間為定義：對(duì)任意密鑰定義1.2.5仿射密碼的密碼體制明文字符對(duì)應(yīng)的整數(shù)為假設(shè)：仿射密碼的密鑰為

13key=(11,3)加密密文為：16解密6置換密碼通過(guò)重新排列消息中元素的位置而不改變?cè)乇旧淼姆绞?，?duì)一個(gè)消息進(jìn)行變換。這種加密機(jī)制稱(chēng)為置換密碼(也稱(chēng)為換位密碼)。定義1.2.6置換密碼體制令是一個(gè)正整數(shù)，K是上所有可能置換構(gòu)成的集合。對(duì)任意的，定義：其中π和互為上的逆置換，為分組長(zhǎng)度。對(duì)于長(zhǎng)度大于分組長(zhǎng)度的明文消息，可對(duì)明文消息先按照長(zhǎng)度進(jìn)行分組，然后對(duì)每一個(gè)分組消息重復(fù)進(jìn)行同樣的置亂加密過(guò)程，最終實(shí)現(xiàn)對(duì)明文消息的加密。假設(shè)：明文為：securitysecurityeuscirty1234123422441133加密1234123433114422解密security