現(xiàn)代密碼學理論與實踐01 - 概述.ppt

1、1,現(xiàn)代密碼學 理論與實踐,第一章 密碼學概述 林喜軍 ,2,學習密碼學有什么用？,學習網(wǎng)絡(luò)安全應(yīng)該具備一定的密碼學知識 僅使用計算機學科的方法無法滿足某些安全需求 密碼學提供了豐富多彩的安全保護手段，可以滿足不同的安全需求,3,實際應(yīng)用密碼技術(shù)的領(lǐng)域,電子商務(wù)、電子政務(wù) 智能卡 3G 通信 ,4,教學目標,掌握密碼學的基本知識和基本原理 了解密碼技術(shù)的應(yīng)用 了解密碼學的發(fā)展動態(tài),5,參考文獻,Modern Cryptography: Theory & Practice by Wenbo Mao (強烈推薦) 中文版網(wǎng)上可以下載,6,參考文獻(續(xù)),Handbook of Applied Cr

2、yptography by A. Menezes et al. (強烈推薦) 網(wǎng)上可以下載,7,參考文獻(續(xù)),應(yīng)用密碼學 by B.Schneier (內(nèi)容廣泛、不夠詳細，適合當字典用) 網(wǎng)上可以下載,8,參考文獻(續(xù)),Lecture Notes on Cryptography by S.Goldwasser M.Bellare (高級讀物) 麻省理工學院密碼學講義 網(wǎng)上可以下載,9,參考文獻(續(xù)),Foundations of Cryprography：Basic Tools by O. Goldreich (高級讀物) 網(wǎng)上可以下載,10,密碼學概述 古典密碼學 對稱密碼學 Hash函

3、數(shù)與消息認證 現(xiàn)代密碼學的理論基礎(chǔ) 公鑰密碼學 數(shù)字簽名 橢圓曲線與基于身份的密碼學 安全協(xié)議 密碼學發(fā)展動態(tài),授課內(nèi)容,11,第一章 密碼學概述,1.1 密碼學簡介 1.2 密碼學發(fā)展史 1.3 關(guān)于密碼分析的幾點說明,12,1.1 密碼學簡介,密碼學是信息安全的重要組成部分 信息安全三要素 機密性 完整性 可用性,13,機密性,確保信息不被非法獲取 常見威脅 竊聽 盜竊文件 社會工程學 ,14,完整性,確保系統(tǒng)或數(shù)據(jù)被惡意篡改后，我們能夠發(fā)現(xiàn) 導致破壞完整性的原因： 合法用戶的失誤 非法用戶的篡改,15,可用性,確保系統(tǒng)以足夠的能力、預(yù)期的方式、可接受的性能提供服務(wù) 導致破壞可用性的原因

4、設(shè)備故障 軟件錯誤 環(huán)境因素 人為攻擊 典型代表：DoS攻擊(拒絕服務(wù)攻擊),16,兩種攻擊形式,被動攻擊 對機密性的破壞 主動攻擊 對完整性和可用性的破壞,17,攻擊者的基本行為,竊聽-被動攻擊,攻擊者偷看到了Bob發(fā)送的信息,18,攻擊者的基本行為(續(xù)),篡改-主動攻擊,攻擊者修改了Bob發(fā)送的信息,19,攻擊者的基本行為(續(xù)),假冒-主動攻擊,攻擊者冒充Bob，與Alice通信,20,密碼學的主要功能,保證機密性 防范信息泄露 保證完整性 防范信息被篡改后，我們還被蒙在鼓里 提供非否認服務(wù) 防范抵賴 (否認自己干過的事),21,什么是密碼學,研究內(nèi)容 研究秘密通信 組成部分 密碼編碼學

5、研究如何設(shè)計密碼，以保證信息的安全 密碼分析學 研究如何破譯密碼(是一把雙刃劍) 幫助分析密碼算法的安全性 幫助非法竊取受保護的信息等破壞性工作,22,密碼學的基本術(shù)語,明文：需要保護的信息 加密：隱藏信息的過程 密文：加密后的明文 解密：從密文恢復出明文的過程 密碼分析：對密碼進行破譯的過程,23,加密 E(),解密 D(),密鑰K,明文M,明文M,密文C,密鑰 K,安全信道,加密：EK(M)=C 解密：DK(C)=M = DK(EK(M)=M,秘密通信模型,破譯,24,需要區(qū)別的兩個常用術(shù)語,口令(password) 用于“身份認證”確認對方是否是你要通信的對象 通常選擇一些容易記憶，又不

6、易被別人猜到的字符串 密鑰(key) 用于“變換明/密文”作為加解密算法的輔助輸入，以保護明文或解密密文 通常選擇一些隨機串,25,密鑰的必要性,加解密的時候，為什么需要密鑰？ 為什么不構(gòu)造一個不需要密鑰的密碼算法？ 如果沒有密鑰，當攻擊者知道了算法，他們只需執(zhí)行該算法就可以恢復你的明文。 貌似保密密碼算法就可以解決這個問題。 事實上，攻擊者總能通過各種手段發(fā)現(xiàn)你用的是哪個算法。,26,密碼學的基本原則 柯克霍夫斯原則,柯克霍夫斯原則 即使密碼算法的任何細節(jié)已為人所知，只要密鑰沒有泄漏，它也應(yīng)該是安全的。 另一種表述 密碼算法的安全性是基于密鑰的安全性，而不是基于保密算法的細節(jié)。,August

7、e Kerckhoffs 1835 1903 荷蘭語言學家、密碼學家,27,柯克霍夫斯原則的意義何在？,意義在于，密碼算法很難做到保密 知道算法的人可能會叛變歷史上這種事屢見不鮮 設(shè)計者有個人喜好 頻繁更換密鑰是可能的，但無法頻繁更換密碼算法 (因為設(shè)計安全的密碼算法相當困難),28,密碼體制的形式化描述,它是一個五元組 ( P, C, K, E, D) P(明文空間)：所有可能的明文組成的有限集 C(密文空間)：所有可能的密文組成的有限集 K(密鑰空間)：所有可能的密鑰組成的有限集 E：所有加密算法組成的有限集 D：所有解密算法組成的有限集,29,注意,加密算法(函數(shù))必須是一個單射函數(shù),W

8、hy ?,30,加密函數(shù)不是單射會怎么樣？,Ek(),Dk(),明文空間,密文空間,x1,x2,y,加密： y=Ek(x1)=Ek(x2),解密：無法判斷y究竟還原為x1還是x2 DK(y) ?= x1 ?= x2,?,31,怎樣的加密體制才算是實用的？,必須滿足以下兩條： 容易性：加密函數(shù)、解密函數(shù)都應(yīng)該易于計算 安全性：對于任何攻擊者，即使獲得了密文，也不可能恢復出明文、所用的密鑰。,32,1.2 密碼學發(fā)展史,密碼學的發(fā)展歷程大致經(jīng)歷了三個階段： 古代加密方法（手工階段） 古典密碼（機械階段） 現(xiàn)代密碼（計算機階段）,33,(1) 古代加密方法階段,存于石刻或史書中的記載表明，許多古代文

9、明，包括埃及人、希伯來人、亞述人都在實踐中逐步發(fā)明了密碼系統(tǒng)。 從某種意義上說，戰(zhàn)爭是科學技術(shù)進步的催化劑。 自從有了戰(zhàn)爭，人類就面臨著通信安全的需求，使得密碼技術(shù)源遠流長。 (密碼最早應(yīng)用于軍事和政治領(lǐng)域),34,需要區(qū)別的兩種技術(shù),隱寫術(shù) 加密術(shù),35,隱寫術(shù)洋蔥法、隱寫墨水等,36,隱寫術(shù)剃頭，寫字，等頭發(fā)變長,37,隱寫術(shù)情報傳遞(近現(xiàn)代仍在使用),傳遞情報用的火柴盒,隱寫術(shù)藏頭/藏尾詩(文章),我康宣，今年一十八歲，姑蘇人氏，身家清白，素無過犯。只 為家況清貧，鬻身華相府中，充當書僮。身價銀五十兩，自 秋節(jié)起，暫存賬房，俟三年后支取，從此承值書房，每日焚 香掃地，洗硯、磨墨等事，聽憑

10、使喚。從頭做起。立此契為憑。,38,39,隱寫術(shù)小結(jié),特點： 保護的是信息本身(把信息隱藏起來)。 缺點： 一旦發(fā)現(xiàn)隱藏的方法，信息就會暴露。 洋蔥法 用火烤 古希臘的剃頭方法 把可疑的人剃成禿瓢 情報傳遞 檢查任何可疑的東西，看是否有夾帶 藏頭詩等 檢查詩詞的開頭和結(jié)尾,40,加密術(shù),使用的兩種基本技術(shù) 置換 (易位) 代換 (替換、代替),41,加密術(shù)置換,公元前400年，斯巴達人 使用的加密工具 Scytale,42,置換的特點,明文中的字符與密文中的相同 只是出現(xiàn)的位置發(fā)生了變化 置換密碼的密鑰是什么？ 改變位置的規(guī)則,43,加密術(shù)代換,用一張(或多張)代換表，表示明文字母與密文字母的

11、對應(yīng)關(guān)系 明文字母：abcdefghijklmnopqrstuvwxyz 密文字母：XZJGLIFKHQNOPMASUTCWDYERBV 加密和解密要參照代換表的對應(yīng)關(guān)系,例： 明文：cryptography 密文：JTBSWAFTXSKB,44,代換的特點,明文中出現(xiàn)的字母不一定出現(xiàn)在密文中 代換密碼的密鑰是什么？ 代換表,45,加密術(shù)小結(jié),特點： 保護的是信息的內(nèi)容。 不知道密鑰，很難恢復出信息。 隱寫術(shù)與加密術(shù)的區(qū)別 隱寫術(shù)：傳遞的仍是原來的信息，只是被藏了起來 加密術(shù)：傳遞的不是原來的信息(明文)，而是變換后的信息(密文)。實際上，密文攜帶了明文的信息。,46,(2) 古典密碼階段,雖

12、然名字叫 “古典密碼”，但在近代得到廣泛發(fā)展和應(yīng)用 古典密碼系統(tǒng)已經(jīng)初步體現(xiàn)出現(xiàn)代密碼系統(tǒng)的雛形，它比古代加密方法更復雜。 加密方法 一般是對文字（字符）的變換 使用手工或機械變換的方式實現(xiàn) 古典密碼的典型代表：單表代換密碼、多表代換密碼、轉(zhuǎn)輪機密碼 (在近代，密碼已應(yīng)用到商業(yè)領(lǐng)域),47,(3) 現(xiàn)代密碼階段,密碼是非常古老的技術(shù)，但真正形成學科還是20世紀70年代的事，這是受計算機科學蓬勃發(fā)展的刺激和推動的結(jié)果。 計算機和電子時代的到來，使得密碼設(shè)計者輕易擺脫了原先手工設(shè)計時易犯的錯誤，也不用再面對用電子機械方式實現(xiàn)的密碼機的高額費用。 快速計算機和現(xiàn)代數(shù)學，為密碼技術(shù)提供了新的概念和工具

13、，也給攻擊者提供了有力武器。 總之，利用計算機可以設(shè)計出更為復雜的密碼系統(tǒng)。攻擊者也可以利用計算機快速破解密碼系統(tǒng)。,48,在這一階段，密碼理論蓬勃發(fā)展，密碼算法的設(shè)計與分析互相促進，出現(xiàn)了大量的密碼算法和各種攻擊方法。 密碼技術(shù)的應(yīng)用范圍也在不斷擴展，出現(xiàn)了許多通用的密碼標準(DES、AES、DSS)，促進了網(wǎng)絡(luò)和技術(shù)的不斷發(fā)展。,49,密碼學史上的重要事件,1949年，香農(nóng)發(fā)表論文保密系統(tǒng)的通信原理 它是密碼學的理論基礎(chǔ)之一 發(fā)表30年后才顯示出它的價值。 1976年，Diffie、Hellman發(fā)表論文密碼學的新方向 提出適應(yīng)網(wǎng)絡(luò)上保密通信的公鑰密碼的思想 開辟了公鑰密碼學的新領(lǐng)域 可以

14、這么說:“沒有公鑰密碼的研究就沒有現(xiàn)代密碼學”,50,密碼學史上的重要事件(續(xù)),1978年，RSA密碼體制出現(xiàn) 它是公鑰密碼領(lǐng)域最杰出的代表，成為事實上的標準，是密碼學史上的里程碑 1978年，DES(數(shù)據(jù)加密標準)出現(xiàn) NBS(美國國家標準局,即現(xiàn)在的國家標準與技術(shù)研究所NIST)公布美國的數(shù)據(jù)加密標準,公開它的具體算法，并被用于政府等非機密單位及商業(yè)上的保密通信。 上述兩篇論文和DES的實施，標志密碼學理論與技術(shù)的革命性變革，宣布了現(xiàn)代密碼學的開始。,51,1.3 關(guān)于密碼分析的幾點說明,密碼分析的分類方法： 分類依據(jù)：攻擊者知道信息的多少 唯密文攻擊：手頭只有一些密文，好的現(xiàn)代密碼系統(tǒng)

15、對此攻擊通常是免疫的。 已知明文攻擊：已有很多明文/密文對。 選擇明文攻擊：可以任意選擇明文，并可獲得相應(yīng)密文。 選擇密文攻擊：可以任意選擇密文，并可獲得相應(yīng)明文。 (上述四種方法的攻擊強度依次增強),52,在實際應(yīng)用中，破譯工作通常是多項技術(shù)綜合應(yīng)用的結(jié)果 下面就這個問題做幾點說明.,53,密碼設(shè)計 vs. 密碼實現(xiàn),即使圖紙上設(shè)計完美的樓房，施工的時候不注意，也會變成豆腐渣工程 但這與設(shè)計本身無關(guān)，完全是施工造成的 密碼也是一樣，一個設(shè)計上安全的密碼算法，在實現(xiàn)時也會引入安全漏洞 但這與算法的設(shè)計無關(guān)，完全是程序編碼造成的 在本課程中，主要討論針對算法設(shè)計的攻擊，而不去涉及算法實現(xiàn)的問題。

16、,54,恢復明文 vs. 恢復密鑰,破譯的主要目的在于恢復密鑰 因為知道了密鑰，便可恢復出該密鑰加密的所有明文 一個安全的密碼體制要求：通過密文計算密鑰，至少要和計算明文一樣困難 當然有些時候，破譯的目的也在于恢復特定的明文,55,全部破譯 vs. 部分破譯,并不一定恢復出整個明文才算成功破譯 有時候，恢復出明文的部分信息，甚至幾個關(guān)鍵單詞，也算成功破譯。 部分破譯又往往成為全部破譯的突破口 在實際應(yīng)用中，破譯往往需要綜合多項技術(shù)和多方面的信息。,56,綜合破譯舉例池步洲,生于福建省閩清縣。由于家境貧寒，直到10歲才上學，卻用3年時間完成全部小學課程。 此后考入福州英華書院（今福建師范大學附屬

17、中學）。 后留學日本，并考入早稻田大學。 抗戰(zhàn)爆發(fā)后，回國抗日。經(jīng)同學介紹加入中統(tǒng)，他是當時中統(tǒng)內(nèi)唯一的留日學生。 盡管沒學過密碼破譯，卻用統(tǒng)計、大膽猜測，以及自己對日本的了解，發(fā)現(xiàn)了日軍密碼的缺陷，破譯了大量日軍密電 珍珠港事件：東風，有雨 擊斃山本五十六 ,19082003 卒于日本神戶,57,窮舉攻擊 vs. 其他攻擊,窮舉攻擊(暴力攻擊、蠻力攻擊) 目的在于窮舉搜索密鑰 方法：依次測試密鑰空間中的每個密鑰,58,密碼體制安全的一個必要條件： 必須能抵抗密鑰窮舉攻擊，所以密鑰空間要足夠大 只要密鑰空間足夠大，窮舉攻擊將是十分低效的，甚至是不現(xiàn)實的 但這并不是充分條件，因為窮舉不是破譯密碼的唯一方法，還有效率高于窮舉攻擊的其他分析方法 各種分析方法的效率誰高誰低呢？常以窮舉攻擊的效率作為比較的標準,59,保密密鑰 vs. 保密算法,根據(jù)柯克霍夫斯原則，對密碼進行分析的前提是，在不知道密鑰的條件下，對公開的密碼算法進行分析。 但在政府或軍事應(yīng)用中，也存在保密算法的情況。