高中數(shù)學(xué)選修5-3(密碼學(xué)算法基礎(chǔ))選修課密碼學(xué)1課件.ppt

1、密碼學(xué)初探邢星 xing.creature_杭州第七中學(xué),Zhofrph Wr Wkh Frxuvh Ri Fubswrorjb,Welcome To The Course Of Cryptology,農(nóng)戶、雞 快吃吧，這是你最后一頓！ 雞躺倒并留遺書： 爺已吃老鼠藥，你們別想吃爺了，爺也不是好惹的。,當(dāng)對手知道了你的決定之后，就能做出對自己最有利的決定。 納什均衡理論,保密、信息安全很重要,“要讓三個人保住秘密，其中兩個人必須死亡！” 本杰明富蘭克林,電視劇暗算語錄,電視劇暗算關(guān)于破譯密碼的語錄 說到底密碼玩的是欺騙，是躲藏，是暗算。 兵不厭詐，密碼是兵器，是兵器中的暗器， 是人間最大的狡詐

2、。 研制和破譯密碼的人都是撒旦。 研制密碼的事業(yè)，就是一項接近瘋子的事業(yè)。 你越接近瘋子，你越接近天才。 葬送于密碼界的天才，是所有科學(xué)領(lǐng)域里概率 最高的。密碼是天才的屠宰場。,電視劇暗算關(guān)于破譯密碼的語錄 破譯密碼是聽死人的心跳聲。破譯密碼是男人生孩子、女人長胡子。破譯密碼是釋讀天書，看懂無字之書。 破譯密碼, 比用沙子搓一根繩子還難，比用空氣鑄一把利劍還難，比用火點燃水還難。正常情況下，這都是不可能的，我們就是要把這種不可能變成可能。 破譯密碼呢，就跟男女之間談戀愛一樣，不是說你談多了就一定能談成。關(guān)鍵是看你有沒有感情，有沒有緣份。,電視劇暗算關(guān)于破譯密碼的語錄 所有的密碼都可以演變成一道

3、或者幾道超難的數(shù)學(xué)題。 破譯技術(shù)作為一門數(shù)學(xué)科學(xué)，尖銳而深邃的數(shù)學(xué)能力，跟良好心理素質(zhì)是一樣必要又重要的。兩者猶如一對飛翔的翅膀，缺一不可。 它需要你悟出世界上最高級的謎和最低級的謎。除了必要的知識、經(jīng)驗、技術(shù)之外，還需 要遠(yuǎn)在星辰之外的好運(yùn)氣。,密 碼 學(xué),學(xué)：學(xué)科，應(yīng)用數(shù)學(xué)，數(shù)學(xué)在信息保護(hù)中的應(yīng)用 碼：編碼，信息從一種形式到另一種形式的轉(zhuǎn)變 密：秘密，目的是使信息處于秘密的狀態(tài),學(xué)科認(rèn)識,引言 密碼學(xué)簡介,密碼學(xué)是一門古老而年輕的科學(xué)，在當(dāng)今的信息時代，大量敏感信息如法庭記錄、私人文檔、軟件源代碼、銀行交易、保險單據(jù)等常常通過公共通信設(shè)施或計算機(jī)網(wǎng)絡(luò)來進(jìn)行交換。 為了保證這些信息的私密性、

4、完整性、真實性，必須使用技術(shù)手段對其進(jìn)行處理。 私密性:對信息處理后，保證讓他人不能讀懂。 真實性:對信息處理后，保證他人不能篡改信息（改了之后會被接收者發(fā)覺）。 完整性:對信息處理后，保證他人不能從原始信息中刪除或插入其它信息（刪除或插入后會被接收者發(fā)覺）。,密碼學(xué)常識,密碼學(xué)（cryptology）作為數(shù)學(xué)的一個分支，是密碼編碼學(xué)和密碼分析學(xué)的統(tǒng)稱。 使消息保密的技術(shù)和科學(xué)叫做密碼編碼學(xué) （cryptography) 破譯密文的科學(xué)和技術(shù)就是密碼分析學(xué) （cryptanalysis） 明文：是作為加密輸入的原始信息，即消息的原始形式，通常用m或p表示。所有可能明文的有限集稱為明文空間，通常

5、用M或P來表示。,密文：是明文經(jīng)加密變換后的結(jié)果，即消息被加密處理后的形式，通常用c表示。所有可能密文的有限集稱為密文空間，通常用C來表示。 密鑰：是參與密碼變換的參數(shù)，通常用k表示。一切可能的密鑰構(gòu)成的有限集稱為密鑰空間，通常用K表示。 加密算法：是將明文變換為密文的變換函數(shù)，相應(yīng)的變換過程稱為加密，即編碼的過程（通常用E表示，即c=Ek(p)）。 解密算法：是將密文恢復(fù)為明文的變換函數(shù)，相應(yīng)的變換過程稱為解密，即解碼的過程（通常用D表示，即p=Dk(c)）。,原始部落間的秘密通信,隱寫術(shù),密碼學(xué)發(fā)展歷史,信息載體：奴隸的頭,剃光, 信息傳遞：長出頭發(fā)的奴隸,密碼學(xué)的發(fā)展歷程大致經(jīng)歷了三個階

6、段：古代加密方法、古典密碼和近代密碼 一、古代加密方法（手工階段）,公元前400年，古斯巴達(dá)人 用一條帶子纏繞在一根木棍上， 沿木棍縱軸方向?qū)懞妹魑模?解下來的帶子上就只有雜亂無章的密文字母。 解密者只需找到相同直徑的木棍， 再把帶子纏上去，沿木棍縱軸方向即可讀出有意義的明文。 這種叫做“天書”的器械堪稱人類歷史上最早使用的密碼器械。,密碼學(xué)發(fā)展歷史,詩情畫意傳“密語”,早妝未罷暗凝眉， 迎戶愁看紫燕飛， 無力回天春已老， 雙棲畫棟不如歸。,密碼學(xué)發(fā)展歷史,水洗塵埃道未甞，甘于名利兩相忘。 心懷六洞丹霞客，口誦三清紫府章。 十里采蓮歌達(dá)旦，一輪明月桂飄香。 日高公子還相覓，見得山中好酒漿。,洗

7、塵埃道未甞于名利兩相忘懷六洞丹霞客誦三清紫府章里采蓮歌達(dá)旦輪明月桂飄香高公子還相覓得山中好酒漿,密碼學(xué)發(fā)展歷史,白居易游紫霄宮,王先生： 來信收悉，你的盛情真是難以報答。我已在昨天抵達(dá)廣州。秋雨連綿，每天需備傘一把方能上街，苦矣。大約本月中旬我才能返回，屆時再見。,王先生： 來信收悉，你的盛情真是難以報答。我已在昨天抵達(dá)廣州。秋雨連綿，每天需備傘一把方能上街，苦矣。大約本月中旬我才能返回，屆時再見。,密碼學(xué)發(fā)展歷史,卡丹網(wǎng)格式密碼,隱寫術(shù)（信息隱藏）的另外一些例子,悠揚(yáng)琴聲奏響“進(jìn)軍號角” 顯微鏡里傳遞情報 魔術(shù)般的密寫術(shù) 網(wǎng)絡(luò)與數(shù)字幽靈 量子技術(shù)隱形傳遞信息 ,密碼學(xué)發(fā)展歷史,隱寫術(shù)的優(yōu)點,

8、能夠被某些人使用而不容易被發(fā)現(xiàn)他們間在進(jìn)行秘密通信 加密則很容易被發(fā)現(xiàn)誰與誰在進(jìn)行秘密通信，這種發(fā)現(xiàn)本身可能具有某種意義或作用,隱寫術(shù)的缺點,形式簡單但構(gòu)造費時，要求有大量的開銷來隱藏相對較少的信息 一旦該系統(tǒng)的構(gòu)造方法被發(fā)現(xiàn)，就會變得完全沒有價值 隱寫術(shù)一般無穩(wěn)健性,代替：明文中的字母由其他字母、數(shù)字或符號所取代的一種方法，具體的代替方案稱為密鑰。,密碼學(xué)發(fā)展歷史,二、古典加密方法（代替密碼、換位密碼）,公元前1世紀(jì)，著名的愷撒密碼(古羅馬統(tǒng)帥愷撒:約公元前10044) 被用于高盧戰(zhàn)爭中， 這是一種簡單易行的單字母替代密碼。,密碼學(xué)發(fā)展歷史,9世紀(jì)，阿拉伯的阿爾.金迪 提出頻度分析的方法來解

9、密， 通過分析計算密文字符出現(xiàn)的頻率來破譯密碼。 16世紀(jì)晚期，蘇格蘭女王瑪麗 密碼信，策劃暗殺英國女王伊麗莎白。 英國的菲利普斯 利用頻度分析法成功破解 這次解密將瑪麗送上了斷頭臺。,密碼學(xué)發(fā)展歷史,16世紀(jì)中期，意大利的卡爾達(dá)諾 發(fā)明了卡爾達(dá)諾漏格板， 覆蓋在密文上，可從漏格中讀出明文， 這是較早的一種分置式密碼。,追殺令：YOU KILL AT ONCE,情書,密鑰,16世紀(jì)晚期， 法國的維吉尼亞Vigenere 提出著名的維吉尼亞方陣密表、維吉尼亞密碼， 這是一種多表加密的替代密碼， 可使阿爾.金迪和菲利普斯的頻度分析法失效。,密碼學(xué)發(fā)展歷史,密碼學(xué)發(fā)展歷史,維吉尼亞方陣密表,19世紀(jì)

10、， 英國的巴貝奇、普魯士的卡西斯基Kasiski 發(fā)展了更復(fù)雜的頻度分析法， 可破解維吉尼亞密碼,密碼學(xué)發(fā)展歷史,密碼學(xué)發(fā)展歷史,17世紀(jì)， 英國著名的哲學(xué)家 弗朗西斯培根 學(xué)問的發(fā)展 最早給密碼下了定義： “所謂密碼應(yīng)具備三個必要的條件，即 易于翻譯、第三者無法理解、在一定場合下不易引人生疑。”,密碼學(xué)發(fā)展歷史,1883年，荷蘭密碼學(xué)家A.Kerckhoffs密碼設(shè)計規(guī)則軍事密碼學(xué)： G 密碼系統(tǒng)應(yīng)該是計算安全的； G 密鑰由通信雙方事先約定好，并根據(jù)一定協(xié)議進(jìn)行更換； G 密碼系統(tǒng)應(yīng)該易于使用；G 密碼系統(tǒng)應(yīng)該精確而有效； G 除了密鑰，密碼系統(tǒng)的所有細(xì)節(jié)都為對手所知。 Kerckhoff

11、s原則在今天看來仍然具有十分重要的現(xiàn)實意義。,11世紀(jì) 兵書武經(jīng)總要 中國歷史上第一部有關(guān)密碼的記述 介紹了一個小型卻名副其實的密碼本。,密碼學(xué)發(fā)展歷史,密碼學(xué)發(fā)展歷史,劉邦打下天下之後，害怕韓信造反，所以打算把他殺了。 又怕他帶的士兵太多，所以問了一下韓信目前帶了多少兵？ 韓信感覺氣氛詭異，因此回答： 兵不知數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二 這個回答讓劉邦不知所措，連軍師張良一下子也算不出， 想到一個數(shù)136,0128 (一百多萬)，不敢輕舉妄動。 韓信所帶的兵，人數(shù)可以少到23人， 當(dāng)然也可能是千萬人， 通解為23+105t 105=3,5,7 中國剩余定理 成也蕭何，敗也蕭何

12、。呂后用蕭何誘殺韓信,密碼學(xué)發(fā)展歷史,一戰(zhàn)前，密碼研究還只限于一個小領(lǐng)域，沒有得到各國應(yīng)有的重視。 第一次世界大戰(zhàn)是世界密碼史上的第一個轉(zhuǎn)折點。 隨著戰(zhàn)爭的爆發(fā)，各國逐漸認(rèn)識到密碼在戰(zhàn)爭中發(fā)揮的巨大作用， 積極給予大力扶持，使密碼很快成為一個龐大的學(xué)科領(lǐng)域。 第一次世界大戰(zhàn)進(jìn)行到關(guān)鍵時刻， 英國破譯密碼的專門機(jī)構(gòu)“40號房間” 利用繳獲的德國密碼本破譯了著名的“齊默爾曼電報”， 促使美國放棄中立參戰(zhàn)，改變了戰(zhàn)爭進(jìn)程。,密碼學(xué)發(fā)展歷史,第二次世界大戰(zhàn)爆發(fā)后， 世界各國開始重視對密碼破譯的研究工作， 紛紛成立專門的研究和破譯機(jī)構(gòu)，在戰(zhàn)爭中發(fā)揮重要的作用。 德國潛艇指揮部德尼茨的B機(jī)關(guān)泄露了太多的軍

13、事情報。 波蘭人和英國人破譯了德國著名的“恩格瑪”密碼機(jī)密碼， 德國的許多重大軍事行動對盟軍都不成為秘密。,Enigma密碼(1),Enigma密碼(2),圖靈的貢獻(xiàn) 1937年英國對德宣戰(zhàn)，布萊切利公園 1940，“炸彈” 一小時破譯一個密碼,1944年6月4日， 德國U-505潛艇受到美海軍特遣大隊反潛深炸彈攻擊， 受傷浮起后，美軍沖入無線電室， 繳獲了密碼機(jī)和大量明、密報， 并秘密將U-505潛艇拖回美國。 德軍誤認(rèn)為U-505潛艇沉沒海底而未換密碼。 在歐戰(zhàn)結(jié)束前的11個月里，依靠破譯的密碼， 美軍和同盟國軍隊共擊沉德國潛艇300多艘，平均每天一艘， 同時大大減少了自己船只的損失，對戰(zhàn)

14、爭的勝利產(chǎn)生了重大影響。,密碼學(xué)發(fā)展歷史,美軍成功地破譯了日本的通訊密碼， 從而導(dǎo)致日本在中途島海戰(zhàn)中失利， 既報了珍珠港的一箭之仇，又使太平洋戰(zhàn)場的局面得到徹底扭轉(zhuǎn)。 二戰(zhàn)期間，美軍破譯日本海軍密碼多達(dá)75種，由于密碼被破譯， 日本總噸數(shù)約三之二的商船被美國潛艇擊沉， 給日本軍隊帶來了嚴(yán)重的戰(zhàn)爭后果。,密碼學(xué)發(fā)展歷史,山本五十六之死 “山本五十六于1943年4月13日下午5時55分到所羅門島視察”的日程 用稱為“紫密”的日本“九七式”密碼機(jī)加密，播給第一基地部隊等。 美軍截獲，通過破譯JN25密碼的專用IBM設(shè)備破譯出。 尼米茲上將經(jīng)研究決定出擊： 4月13日7時25分出動18架戰(zhàn)斗機(jī)將山本

15、座機(jī)擊落 偷襲珍珠港的元兇日本艦隊總司令山本五十六死亡 5月21日日本才廣播這一消息。,密碼學(xué)發(fā)展歷史,密碼學(xué)發(fā)展歷史,二戰(zhàn)結(jié)束后，一位深知戰(zhàn)時密碼破譯價值的美國官員說， 密碼破譯使第二次世界大戰(zhàn)縮短了幾年。這種說法雖有些夸張， 但重要情報的破譯確實影響了戰(zhàn)爭的進(jìn)程，挽救了成千上萬的生命。 第二次世界大戰(zhàn)促進(jìn)了密碼的飛速發(fā)展。 由于密碼對于戰(zhàn)爭的勝負(fù)具有越來越重要的影響， 各國不惜花大量的人力物力進(jìn)行密碼的研究和破譯。 密碼的編制結(jié)構(gòu)更加科學(xué)，編制方法愈加復(fù)雜， 各種密碼的保密性出現(xiàn)了飛躍性的提高。 在此期間，許多國家開始使用密碼機(jī)進(jìn)行加密， 密碼告別人工加密，走向機(jī)械加密的開始。,1948年

16、以前的密碼技術(shù)可以說是一種藝術(shù)，而不是一種科學(xué)， 那時的密碼專家是憑直覺和信念來進(jìn)行密碼設(shè)計和分析的， 而不是靠推理證明。 1948年，C. E. Shannon(19162002) 在貝爾系統(tǒng)技術(shù)雜志上發(fā)表論文通信的數(shù)學(xué)理論， 創(chuàng)立了著名的新理論信息論， 標(biāo)志著密碼術(shù)到密碼學(xué)的轉(zhuǎn)變。,密碼學(xué)發(fā)展歷史,20世紀(jì)70年代中期，密碼學(xué)界發(fā)生了兩件跨時代的大事： Diffie和Hellman發(fā)表的題為“密碼學(xué)新方向”文章， 提出了“公鑰密碼”新體制，沖破了傳統(tǒng)“單鑰密碼”體制的束縛。 傳統(tǒng)密碼體制主要功能是信息的保密， 雙鑰(公鑰)密碼體制不但賦予了通信的保密性， 而且還提供了消息的認(rèn)證性 新的雙鑰

17、密碼體制無需事先交換秘密鑰就 可通過不安全信道安全地傳遞信息， 大大簡化了密鑰分配的工作量。 雙鑰密碼體制適應(yīng)了通信網(wǎng)的需要， 為保密學(xué)技術(shù)應(yīng)用于商業(yè)領(lǐng)域開辟了廣闊的天地。,密碼學(xué)發(fā)展歷史,20世紀(jì)70年代中期，密碼學(xué)界發(fā)生了兩件跨時代的大事： 美國國家標(biāo)準(zhǔn)局NBS于1977年公布實施美國數(shù)據(jù)加密標(biāo)準(zhǔn)DES， 保密學(xué)史上第一次公開加密算法，并廣泛應(yīng)用于商用數(shù)據(jù)加密 這兩件引人注目的大事揭開了保密學(xué)的神秘面紗， 標(biāo)志著保密學(xué)的理論與技術(shù)的劃時代的革命性變革 為保密學(xué)的研究真正走向社會化作出了巨大貢獻(xiàn)， 同時也為保密學(xué)開辟了廣泛的應(yīng)用前景。 從此，掀起了現(xiàn)代密碼學(xué)研究的高潮。,密碼學(xué)發(fā)展歷史,自從

18、人類有了戰(zhàn)爭，就有了密碼。 自古以來，通信安全保密 在國家的軍事和安全部門 一直受到十分廣泛的關(guān)注。 從原始的手工作業(yè) 到采用機(jī)械設(shè)備、電器機(jī)械設(shè)備，進(jìn)而發(fā)展 到今天的以使用電子計算機(jī)及微電子技術(shù)為標(biāo)志的電子時代。,密碼學(xué)簡史(小結(jié)),密碼學(xué)的作用和意義,歷史上的戰(zhàn)爭，特別是兩次世界大戰(zhàn)， 對于保密學(xué)的理論與技術(shù) 的發(fā)展起了巨大的推動作用。 在通信安全、保密、密碼分析上的優(yōu)勢， 被認(rèn)為是贏得歷史上許多主要軍事沖突 (包括二次世界大 戰(zhàn))勝利的關(guān)鍵因素之一。,密碼學(xué)的作用和意義,我們正在步入一個嶄新的信息社會， 信息在社會中的地位和作用越來越重要， 信息就是生命 “9.11” 信息就是時間 “1

19、37670348315732568089372384837 mod 13” 信息就是財富 “炒股” 每個人的生活都與信息的產(chǎn)生、存儲、處理和傳遞密切相關(guān) “誰掌握了信息，控制了網(wǎng)絡(luò)，誰就將擁有整個世界！” 信息的安全與保密問題成了人人都關(guān)心的事情， 使密碼學(xué)脫去神秘的面紗， 成為大家感興趣并為更多人服務(wù)的科學(xué)。,信息空間中的偵察與反偵察、截獲和反截獲、 破譯和反破譯、破壞和反破壞 的斗爭愈演愈烈： 軍事上的電子對抗：1991年初海灣戰(zhàn)爭空前大規(guī)模的電子戰(zhàn) 信息空間中的信息大戰(zhàn)正在俏情而積極地醞釀中， 小規(guī)模的信息戰(zhàn)一直在不斷地出現(xiàn)、發(fā)展和擴(kuò)大。 信息戰(zhàn)是 信息化社會發(fā)展的必然產(chǎn)物。 商業(yè)上的情

20、報戰(zhàn) 隨著Internet、Intranet、 Extranet， 特別是電子商務(wù)的發(fā)展而步入了新的階段。 近年來，在網(wǎng)絡(luò)上所進(jìn)行的各犯罪活動出現(xiàn)了逐年上升的趨勢， 由此所造成的經(jīng)濟(jì)損失是十分巨大的。,密碼學(xué)的作用和意義,Internet的全球性、開放性、無縫連通性、共享性、動態(tài)性發(fā)展， 任何人都可以自由接入Internet，其中有善者，也有惡者。 惡者會采用各種攻擊手段進(jìn)行破壞活動： 整天在試圖穿透別人的系統(tǒng)、竊取重要情報、 搗毀別人的信箱、傾瀉信息拉圾、 散布破壞性信息、施放病毒、 進(jìn)行網(wǎng)絡(luò)欺詐、發(fā)動黑客戰(zhàn)等。 給國家、單位和個人的信息安全帶來極大的威脅。 Internet一方面成為人們離

21、不開的信息工具， 同時它也成為公開的攻擊對象目標(biāo)。,密碼學(xué)的作用和意義,全球計算機(jī)病毒已達(dá)8萬多種，每天要產(chǎn)生5-10種新病毒。 曾肆虐全球、具有里程碑意義的紅色代碼和尼姆達(dá)病毒， 改寫了病毒的形態(tài)和病毒的傳播歷史，步入了混合型病毒時代。 1999年4月26日，受CIH病毒的侵害， 我國有36萬多臺計算機(jī)受到破壞，經(jīng)濟(jì)損失達(dá)12億元。 2003年24-26日轟動世界的Slammer病毒，利用SQL漏洞發(fā)起攻擊 數(shù)小時后已使南韓網(wǎng)絡(luò)不堪負(fù)重， 亞洲、北美的Web網(wǎng)站和Internet業(yè)務(wù)提供商不能正常工作 星期六使美國最大的自動柜員機(jī)(ATM)網(wǎng)絡(luò)中斷， 直到午后很久，所有的13000 ATM都不能使用。,密碼學(xué)的作用和意義,2003下半年出現(xiàn)“沖擊波” 病毒， 受感染的主機(jī)超過40萬臺，并 曾一度使加拿大航空系統(tǒng)癱瘓。 Slammer病毒和“沖擊波” 病毒都是攻擊型混合病毒。,密碼學(xué)的作用和意義,美國的信息