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

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

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

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

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

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

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

7、應(yīng)字母用數(shù)對表示。在古代，這種棋盤密碼被廣泛使用。,希臘,愷撒密碼 （公元前一世紀(jì)）,它是將英文字母向前推移k位。以此字母替代的密表，如k=5，則密文字母與明文與如下對應(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)爭,密碼分析的始祖——阿拉伯人,公元8世紀(jì)中葉，在阿拔斯王朝，為了統(tǒng)治一個龐大的帝國，行政系統(tǒng)中廣泛地使用了密碼，比如國家敏感事務(wù)、稅收。他們設(shè)計并且使用代替和換位加密（單表替換）。對《古蘭經(jīng)》的編年啟示了字母的字頻規(guī)律。公元9世紀(jì)，阿拉伯的密碼學(xué)家阿爾·金迪al' Kindi (801?~873年) 提出解密的頻度分析方法，通過分析計算密文字符出現(xiàn)的頻率破譯密碼。,單表替換的克星---頻度分析,密

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

10、昂·巴蒂斯塔·艾伯蒂第一個提出，后來又為許多人逐步發(fā)展成當(dāng)今大多數(shù)密碼體制所屬的一種密碼類型。,艾伯蒂密碼圓盤,多表替代,修道院院長約翰內(nèi)斯·特里特米烏斯在1508年初從事寫作一本專講密碼學(xué)的書，使多表代替又向前跨出了一大步，書名為“多種寫法”，此書在他死后一年半出版，是密碼學(xué)第一本印刷書籍。書中第五章出現(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ù)密鑰來決定用哪一行的密表來進(jìn)行替換，,對如下明文加密： 　　TO BE OR NOT TO BE THAT IS THE QUESTION 　　當(dāng)選定RELATIONS作為密鑰時，加密過程是：明文一個字母為T，第一個密鑰字母為R，因此可以找到在R行中代替T的為K，依此類推,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)劃來進(jìn)行電報通訊。電報的出現(xiàn)第一次使遠(yuǎn)距離快速傳遞信息成為可能，事實(shí)上，它增強(qiáng)了西方各國的通訊能力。20世紀(jì)初，意大利物理學(xué)家奎里亞摩·馬可尼發(fā)明

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

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

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

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

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

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

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

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

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

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

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

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

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