第1章 古典密碼

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

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

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

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

》(

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

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

RSA三杰

第1章古典密碼1.密碼學(xué)基本概念2.幾種典型的古典密碼體制3.古典密碼的統(tǒng)計分析1.1密碼學(xué)的基本概念密碼學(xué)（cryptology）作為數(shù)學(xué)的一個分支，是密碼編碼學(xué)和密碼分析學(xué)的統(tǒ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ù)和實踐（2）密碼協(xié)議的安全性分析的理論與方法（3）安全保密系統(tǒng)的安全性分析和攻擊的理論、方法、技術(shù)和實踐從密碼產(chǎn)生的那天起，密碼編碼和密碼破譯的斗爭一刻也沒有停止。雙方在相生相克的斗爭中此消彼長，不斷地提高各自的密碼研制技術(shù)，結(jié)果大大促進了密碼學(xué)的發(fā)展。密碼學(xué)是干什么的?密碼學(xué)要解決的基本問題:

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

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

加密密鑰=解密密鑰

非對稱密匙密碼系統(tǒng)AsymmetricKeyCryptosystem

加密密鑰≠解密密鑰

鑰匙是保密的

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

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

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