密碼學(xué)發(fā)展史

1、密碼學(xué)發(fā)展史,什么是密碼？,密碼是一種用來(lái)混淆的技術(shù)，它希望將正常的、可識(shí)別的信息轉(zhuǎn)變?yōu)闊o(wú)法識(shí)別的信息。,密碼學(xué)的發(fā)展歷程大致經(jīng)歷了三個(gè)階段,古典密碼（手工、機(jī)械階段 -１９４９ ）近代密碼（計(jì)算機(jī)階段１９４９-１９７５）現(xiàn)代密碼（１９７６-）,古典密碼（手工、機(jī)械階段）,古埃及,人類(lèi)文明剛剛形成的公元前2000年，古埃及就有了密碼。貴族克努姆霍特普二世的墓碑上記載了在阿梅連希第二法老王朝供職期間它所建立的功勛。上面的象形文字不

2、同于我們已知的普通埃及象形文字，而是由一位擅長(zhǎng)書(shū)寫(xiě)的人經(jīng)過(guò)變形處理之后寫(xiě)的，但是具體的使用方法已經(jīng)失傳。人們推測(cè)這是為了賦予銘文以莊嚴(yán)和權(quán)威。,姓名和頭銜的象形文字加密左：明文 右：密文,中國(guó),陰符陰書(shū),一套陰符包括尺寸不等，形狀各異的符，每只符都表示特定的含義，而陰符的形狀和表達(dá)的意思是事先約定好的，所以收信人在接到發(fā)信人的陰符后，可以明白其意思。 最初的“陰符”是竹制的，后又改用木片、銅片。。“陰符”上無(wú)文字

3、，無(wú)圖案，傳“符”人不知“符”中含義，即使被俘，叛變投敵，敵人也難以知道“符”的內(nèi)容。,大勝克敵之符，長(zhǎng)一尺； 破軍擒將之符，長(zhǎng)九寸； 降城得邑之符，長(zhǎng)八寸； 卻敵報(bào)遠(yuǎn)之符，長(zhǎng)七寸； 警眾堅(jiān)守之符，長(zhǎng)六寸； 請(qǐng)糧益兵之符，長(zhǎng)五寸； 敗軍亡將之符，長(zhǎng)四寸； 失利亡士之符，長(zhǎng)三寸。,所謂“陰書(shū)”，實(shí)際上是一種軍事文書(shū)，傳遞的方法更秘密些。其方法是：先把所要傳

4、遞的機(jī)密內(nèi)容完完整整地寫(xiě)在一編竹簡(jiǎn)或木簡(jiǎn)上，然后將這篇竹簡(jiǎn)或木簡(jiǎn)拆開(kāi)、打亂，分成三份，稱(chēng)“一合而再離”。然后派三名信使各傳遞一份到同一個(gè)目的地。“陰書(shū)”被送到目的地后，收件人再把三份“陰書(shū)”按順序拼合起來(lái)，于是“陰書(shū)”的內(nèi)容便一目了然，稱(chēng)“三發(fā)而一知”。 這種“陰書(shū)”保密性較好，且在某一角度上講類(lèi)似于移位密碼的特性。因?yàn)榧词鼓骋恍攀贡粩撤阶カ@，“陰書(shū)”落入敵方手里，也得不到完整的情報(bào)。但也有其缺陷，由于原文被分成了三份，故

5、一旦丟失一份，接受者也無(wú)法了解其原意。,美索不達(dá)米亞,在楔形文字時(shí)期，巴比倫和亞述的記述者往往用稀奇古怪的楔形文字在泥板上做記號(hào)和記日期。向后世顯示自己的學(xué)問(wèn)。在楔形文字后期，偶有記述者把人名變換成數(shù)字。,修澤遺跡出土的字碑，記載1-8 與 32-35 的數(shù)字,斯巴達(dá)的scytale,長(zhǎng)期的戰(zhàn)爭(zhēng)使得斯巴達(dá)人發(fā)展出了自己的一套加密方式，公元前5世紀(jì)，斯巴達(dá)人就使用一種名為Scytale的器械，他們把一個(gè)帶狀物，呈螺旋形緊緊地纏在一根權(quán)杖或

6、木棍上，之后再沿著棍子的縱軸書(shū)寫(xiě)文字，在這條帶狀物解開(kāi)后，上面的文字將雜亂無(wú)章，收信人需用一根同樣直徑的棍子重復(fù)這個(gè)過(guò)程，看到明文，這是人類(lèi)歷史上最早的加密器械。,公元前2世紀(jì)，一個(gè)叫Polybius的希臘人設(shè)計(jì)了一種將字母編碼成符號(hào)對(duì)的方法，他使用了一個(gè)稱(chēng)為Polybius的校驗(yàn)表，這個(gè)表中包含許多后來(lái)在加密系統(tǒng)中非常常見(jiàn)的成分。Polybius校驗(yàn)表由一個(gè)5´5的網(wǎng)格組成，網(wǎng)格中包含26個(gè)英文字母，其中I和J在同一格中。相

7、應(yīng)字母用數(shù)對(duì)表示。在古代，這種棋盤(pán)密碼被廣泛使用。,希臘,愷撒密碼 （公元前一世紀(jì)）,它是將英文字母向前推移k位。以此字母替代的密表，如k=5，則密文字母與明文與如下對(duì)應(yīng)關(guān)系 a b c d e f g h i j k l m n o p q r s t u v w x y z F G H I J K L M N O P Q R S T U V W X Y Z A B C D Ek就是最早的文字密鑰

8、,被用于高盧戰(zhàn)爭(zhēng),密碼分析的始祖——阿拉伯人,公元8世紀(jì)中葉，在阿拔斯王朝，為了統(tǒng)治一個(gè)龐大的帝國(guó)，行政系統(tǒng)中廣泛地使用了密碼，比如國(guó)家敏感事務(wù)、稅收。他們?cè)O(shè)計(jì)并且使用代替和換位加密（單表替換）。對(duì)《古蘭經(jīng)》的編年啟示了字母的字頻規(guī)律。公元9世紀(jì)，阿拉伯的密碼學(xué)家阿爾·金迪al' Kindi (801?~873年) 提出解密的頻度分析方法，通過(guò)分析計(jì)算密文字符出現(xiàn)的頻率破譯密碼。,單表替換的克星---頻度分析,密

9、碼的影響力,公元16世紀(jì)晚期，英國(guó)的菲利普斯(Philips)利用頻度分析法成功破解蘇格蘭女王瑪麗的密碼信，信中策劃暗殺英國(guó)女王伊麗莎白，這次解密將瑪麗送上了斷頭臺(tái)。1628年4月,由于一個(gè)年輕人破開(kāi)了雨格諾教徒的密碼,亨利二世孔戴親王,攻占了久攻不克的雷阿爾蒙特城。1781年，美軍破譯了克林頓將軍與康華利將軍的通訊信件，使英國(guó)艦隊(duì)增援約克敦的計(jì)劃失敗，并迫使康華利投降，確定了獨(dú)立戰(zhàn)爭(zhēng)的勝利。,多表替代,1466年或1467年初，利

10、昂·巴蒂斯塔·艾伯蒂第一個(gè)提出，后來(lái)又為許多人逐步發(fā)展成當(dāng)今大多數(shù)密碼體制所屬的一種密碼類(lèi)型。,艾伯蒂密碼圓盤(pán),多表替代,修道院院長(zhǎng)約翰內(nèi)斯·特里特米烏斯在1508年初從事寫(xiě)作一本專(zhuān)講密碼學(xué)的書(shū)，使多表代替又向前跨出了一大步，書(shū)名為“多種寫(xiě)法”，此書(shū)在他死后一年半出版，是密碼學(xué)第一本印刷書(shū)籍。書(shū)中第五章出現(xiàn)方表： Military----Mjnl。。,A B C D E F G H I J

11、 K L M N O P Q R S T U V W X Y Z 　　A -A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 　　B -B C D E F G H I J K L M N O P Q R S T U V W X Y Z A 　　C- C D E F G H I J K L M N O P Q R S T U V W X Y Z

12、 A B 　　D- D E F G H I J K L M N O P Q R S T U V W X Y Z A B C 。。。。。 Z -Z A B C D E F G H I J K L M N O P Q R S T U V W X Y,多表替代,喬范·巴蒂斯塔·貝拉索曾是紅衣主教卡皮的隨從，1553年，他出版了一本名為《喬范·巴蒂斯塔

13、3;貝拉索先生的密碼》，提出文字密鑰的應(yīng)用。即根據(jù)密鑰來(lái)決定用哪一行的密表來(lái)進(jìn)行替換，,對(duì)如下明文加密： 　　TO BE OR NOT TO BE THAT IS THE QUESTION 　　當(dāng)選定RELATIONS作為密鑰時(shí)，加密過(guò)程是：明文一個(gè)字母為T(mén)，第一個(gè)密鑰字母為R，因此可以找到在R行中代替T的為K，依此類(lèi)推,A B C D E F G H I J K L M N O P Q R S T U V W X

14、Y Z 　A -A B C D E F G H I J K L M N O P Q R S T U V W X Y Z B -B C D E F G H I J K L M N O P Q R S T U V W X Y Z A C- C D E F G H I J K L M N O P Q R S T U V W X Y Z A B 　D- D E F G H

15、 I J K L M N O P Q R S T U V W X Y Z A B C 。。。。。 R- RS T U V W X Y Z A B C D E F G H I J K L M NO P Q 。。。。。 Z -Z A B C D E F G H I J K L M N O P Q R S T U V W X Y,其他古典密碼,柵欄密

16、碼 明文：THERE IS A CIPHER 去掉空格后變?yōu)椋篢HEREISACIPHER T E E S C P EH R I A I H RTEESCPE HRIAIHR,1844年，薩米爾·莫爾斯發(fā)明了莫爾斯電碼：用一系列的電子點(diǎn)劃來(lái)進(jìn)行電報(bào)通訊。電報(bào)的出現(xiàn)第一次使遠(yuǎn)距離快速傳遞信息成為可能，事實(shí)上，它增強(qiáng)了西方各國(guó)的通訊能力。20世紀(jì)初，意大利物理學(xué)家奎里亞摩·馬可尼發(fā)明

17、了無(wú)線電報(bào)，讓無(wú)線電波成為新的通訊手段，它實(shí)現(xiàn)了遠(yuǎn)距離通訊的即時(shí)傳輸。由于通過(guò)無(wú)線電波送出的每條信息不僅傳給了己方，也傳送給了敵方，這就意味著必須給每條信息加密。隨著第一次世界大戰(zhàn)的爆發(fā)，對(duì)密碼和解碼人員的需求急劇上升，一場(chǎng)秘密通訊的全球戰(zhàn)役打響了。,有線電報(bào)產(chǎn)生了現(xiàn)代編碼學(xué)無(wú)線電報(bào)產(chǎn)生了現(xiàn)代密碼分析學(xué),齊默爾曼電報(bào),公元20世紀(jì)初，第一次世界大戰(zhàn)進(jìn)行到關(guān)鍵時(shí)刻，英國(guó)破譯密碼的專(zhuān)門(mén)機(jī)構(gòu)“40號(hào)房間”利用繳獲的德國(guó)密碼本破譯了著名的

18、“齊默爾曼電報(bào)”，促使美國(guó)放棄中立參戰(zhàn)，改變了戰(zhàn)爭(zhēng)進(jìn)程。,受計(jì)算機(jī)科學(xué)蓬勃發(fā)展刺激和推動(dòng)的結(jié)果?？焖匐娮佑?jì)算機(jī)（轉(zhuǎn)輪密碼）和現(xiàn)代數(shù)學(xué)方法一方面為加密技術(shù)提供了新的概念和工具，另一方面也給破譯者提供了有力武器。,Enigma （隱匿之王）,德國(guó)的Arthur Scherbius于1919年發(fā)明的一種加密電子器件，結(jié)合了機(jī)械系統(tǒng)與電子系統(tǒng)。它被證明是有史以來(lái)最可靠的加密系統(tǒng)之一。二戰(zhàn)期間令德軍保密通訊技術(shù)處于領(lǐng)先地位。,轉(zhuǎn)子,機(jī)械系統(tǒng)包括了

19、一個(gè)包含了字母與數(shù)字的鍵盤(pán)，相鄰地排列在一個(gè)軸上的一系列名為“轉(zhuǎn)子”的旋轉(zhuǎn)圓盤(pán),在每次按鍵后最右邊的轉(zhuǎn)子都會(huì)旋轉(zhuǎn)，并且有些時(shí)候與它相鄰的一些轉(zhuǎn)子也會(huì)旋轉(zhuǎn)。轉(zhuǎn)子持續(xù)的旋轉(zhuǎn)會(huì)造成每次按鍵后得到的加密字母都會(huì)不一樣。,反射器,反射器是恩尼格瑪機(jī)與當(dāng)時(shí)其它轉(zhuǎn)子機(jī)械之間最顯著的區(qū)別。它將最后一個(gè)轉(zhuǎn)子的其中兩個(gè)觸點(diǎn)連接起來(lái)，并將電流沿一個(gè)不同的路線導(dǎo)回。這就使加密過(guò)程與解密過(guò)程變得一致。 加密后得到的字母與輸入的字母永遠(yuǎn)不會(huì)相同。這在概念上和密碼

20、學(xué)上都是一個(gè)嚴(yán)重的錯(cuò)誤，這個(gè)錯(cuò)誤最終被盟軍解碼人員利用。,接線板,接線板上的每條線都會(huì)連接一對(duì)字母。這些線的作用就是在電流進(jìn)入轉(zhuǎn)子前改變它的方向。,密鑰的可能性,三個(gè)轉(zhuǎn)子不同的方向組成了26ｘ26ｘ26＝17576種可能性；　　三個(gè)轉(zhuǎn)子間不同的相對(duì)位置為6種可能性；　　連接板上兩兩交換6對(duì)字母的可能性則是異常龐大，有100391791500種；　　于是一共有17576ｘ6ｘ100391791500 這樣龐大的可能性，換言之

21、，即便能動(dòng)員大量的人力物力，要想靠“暴力破譯法”來(lái)逐一試驗(yàn)可能性，那幾乎是不可能的。而收發(fā)雙方，則只要按照約定的轉(zhuǎn)子方向、位置和連接板連線狀況，就可以非常輕松簡(jiǎn)單地進(jìn)行通訊了。這就是“恩尼格瑪”密碼機(jī)的保密原理。,Enigma破譯,第二次世界大戰(zhàn)中，在破譯德國(guó)著名的“Enigma”密碼機(jī)密碼過(guò)程中，原本是以語(yǔ)言學(xué)家和人文學(xué)者為主的解碼團(tuán)隊(duì)中加入了數(shù)學(xué)家和科學(xué)家。電腦之父亞倫·圖靈就是在這個(gè)時(shí)候加入了解碼隊(duì)伍，發(fā)明了一套更高明的

22、解碼方法。同時(shí)，這支優(yōu)秀的隊(duì)伍設(shè)計(jì)了人類(lèi)的第一部電腦（“炸彈”）來(lái)協(xié)助破解工作。,計(jì)算機(jī)和電子學(xué)時(shí)代的到來(lái)使得美國(guó)在1942年制造出了世界上第一臺(tái)計(jì)算機(jī).美國(guó)利用計(jì)算機(jī)輕松地破譯了日本的紫密密碼,使日本在中途島海戰(zhàn)中一敗涂地,日本海軍的主力損失殆盡. 1943年,在獲悉山本五十六將于4月18日乘中型轟炸機(jī)，由6架戰(zhàn)斗機(jī)護(hù)航，到 中途島視察時(shí),羅斯?？偨y(tǒng)親自做出決定截?fù)羯奖?山本乘坐的飛機(jī)在去往中途島的路上被美軍擊毀,山本墜機(jī)身亡,日本海

23、軍從此一蹶不振.密碼學(xué)的發(fā)展直接影響了二戰(zhàn)的戰(zhàn)局。,密碼本質(zhì)上是另一種語(yǔ)言,在二次世界大戰(zhàn)中，印第安納瓦霍土著語(yǔ)言被美軍用作密碼，美國(guó)二戰(zhàn)時(shí)候特別征摹使用印第安納瓦約(Navajo)通信兵。在二次世界大戰(zhàn)日美的太平洋戰(zhàn)場(chǎng)上，美國(guó)海軍軍部讓北墨西哥和亞歷桑那印第安納瓦約族人使用約瓦納語(yǔ)進(jìn)行情報(bào)傳遞。納瓦約語(yǔ)的語(yǔ)法、音調(diào)及詞匯都極為獨(dú)特，不為世人所知道，當(dāng)時(shí)納瓦約族以外的美國(guó)人中，能聽(tīng)懂這種語(yǔ)言的也就一二十人。這是密碼學(xué)和語(yǔ)言學(xué)的成功結(jié)合，

24、納瓦霍語(yǔ)密碼成為歷史上從未被破譯的密碼。,,有人說(shuō)密碼學(xué)至少使二戰(zhàn)的時(shí)間縮短了一年。,克勞德·香農(nóng)(Claude Elwood Shannon,1916-2001),1948年香農(nóng)發(fā)表了《A Mathematical Theory of Communication 》。 香農(nóng)理論的重要特征是熵(entropy)的概念，他證明熵與信息內(nèi)容的不確定程度有等價(jià)關(guān)系。,近現(xiàn)代密碼學(xué),Enigma的破譯歷程表示，真正保證密碼安全的不是

25、算法，而是密鑰。即使算法外泄，有密鑰的存在，密碼也不會(huì)失效。,著名的“柯克霍夫原則” 荷蘭密碼學(xué)家Kerckhoffs于1883年在其名著《軍事密碼學(xué)》中提出的密碼學(xué)的基本假設(shè)：密碼系統(tǒng)中的算法即使為密碼分析者所知，也對(duì)推導(dǎo)出明文或密鑰沒(méi)有幫助。也就是說(shuō)，密碼系統(tǒng)的安全性不應(yīng)取決于不易被改變的事物（算法），而應(yīng)只取決于可隨時(shí)改變的密鑰。,DES,1975年1月15日，對(duì)計(jì)算機(jī)系統(tǒng)和網(wǎng)絡(luò)進(jìn)行加密的DES（Data Encryption

26、Standard數(shù)據(jù)加密標(biāo)準(zhǔn)）由美國(guó)國(guó)家標(biāo)準(zhǔn)局頒布為國(guó)家標(biāo)準(zhǔn)。,DES的出現(xiàn)，推動(dòng)了密碼分析理論和技術(shù)的快速發(fā)展，出現(xiàn)了差分分析、線性分析等多種新型有效的密碼分析方法。DES的出現(xiàn)而引起的討論及附帶的標(biāo)準(zhǔn)化工作確立了安全使用分組密碼的若干準(zhǔn)則，是密碼學(xué)領(lǐng)域中的一個(gè)里程碑。,S盒運(yùn)算-----密鑰變換-----S盒運(yùn)算----- -----密鑰變換。。。。。16次,公鑰密碼體系,1976年，當(dāng)時(shí)在美國(guó)斯坦福大學(xué)的迪菲（Diffie）和赫

27、爾曼(Hellman)兩人提出了公開(kāi)密鑰密碼的新思想（論文"New Direction in Cryptography"），把密鑰分為加密的公鑰和解密的私鑰，這是密碼學(xué)的一場(chǎng)革命。,公鑰密碼體系,不對(duì)稱(chēng)密碼學(xué)中使用到一對(duì)公鑰(public key)和私鑰(private key)組合。用公鑰加密的密文只能用對(duì)應(yīng)私鑰解密，反之，用私鑰加密的密文只能用對(duì)應(yīng)公鑰解密。在操作過(guò)程中，人們把公鑰向外界發(fā)布，讓外界都知道，自己保

28、存私鑰，只有自己才能知道。如果A要發(fā)一份秘密信息給B，則A只需要得到B的公鑰，然后用B的公鑰加密秘密信息，此加密的信息只有B能用其保密的私鑰解密。反之，B也可以用A的公鑰加密保密信息給A。信息在傳送過(guò)程中，即使被第三方截取，也不可能解密其內(nèi)容。,RSA算法,1977年，美國(guó)MIT的里維斯特(Ronald Rivest)、沙米爾(Adi Shamir)和阿德勒曼(Len Adleman)提出第一個(gè)較完善的公鑰密碼體制——RSA體制，這是一

29、種建立在大數(shù)因子分解基礎(chǔ)上的算法。 RSA是被研究得最廣泛的公鑰算法，從1978年提出到現(xiàn)在已近三十年，經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。通常認(rèn)為破譯RSA的難度與大數(shù)分解難度等價(jià)。,公鑰密碼基于的數(shù)學(xué)難題,RSA加、解密算法，是一個(gè)可逆的公鑰密碼體制,該體制利用了:尋找大素?cái)?shù)是相對(duì)容易的,而分解兩個(gè)大素?cái)?shù)的積是計(jì)算上不可行的。背包問(wèn)題有限域的乘法群上的離散對(duì)數(shù)問(wèn)題(如ElGamal公鑰系統(tǒng)