信息論與編碼密碼學

1、近代密碼學的發(fā)展史保密學的理論基礎序列（流）密碼分組（塊）密碼-DES-RSA密碼學的發(fā)展前沿密碼學Cryptography-目錄1近代密碼學發(fā)展史準確的現(xiàn)代術語為“密碼編制學”簡稱為“編密學” 與之相對的研究的專門研究如何破解密碼的學問稱為“密碼分析學”(Cryptanalysis). Cryptography=希臘文的Kruptos + grapheinhiddento write2 密碼學密碼編制學密碼分析學近代密碼學發(fā)展史-23近代密碼學發(fā)展史-3 20世紀60年代一部與眾不同的著作-David Kahn 的破譯者出現(xiàn)了雖然此書沒有任何新的技術思想，但它的意義在于它涉及到的相當廣泛的領

2、域，而且在于它使成千上萬原本不知道密碼學的人了解密碼學。從而使新的密碼學文章慢慢地開始源源不斷地被編寫出來了。4近代密碼學發(fā)展史-4 第一次世界大戰(zhàn)結束時，公開的密碼學文獻幾乎殆盡。只有一個突出 的例外，仙農(Claude Shannon）的文章保密系統(tǒng)的通信理論出現(xiàn)在1949 年貝爾系統(tǒng)技術雜志上，是戰(zhàn)時工作的產物。這 篇文章在第二次世界大戰(zhàn)結束后即被解密。5近代密碼學發(fā)展史-5 Alan Turing 數(shù)理邏輯天才、現(xiàn)代計算機設計思想的創(chuàng)始人，第二次世界大戰(zhàn)在年僅26歲Turing領導下完成了一部針對德國“謎”型機的密碼破譯機，每秒鐘可處理2000個字符，人們給它起了個綽號叫“炸彈（Bom

3、b)”。6近代密碼學發(fā)展史-6一個傳統(tǒng)的密碼體制S定義為： S (M, C, K, E, D)； message space 代表的是明文空間 key space 代表的是密鑰空間 cipher space 代表的是密文空間MKC加密映射族： E = fk: M C | k K 脫密映射族： E = gk: C M | k K 7安全性的含義：1）接收端防止竊聽；2）發(fā)送端防止偽造。數(shù)學模型保密學的理論基礎 明文源MA加密T1m加密T2信道C解密T2解密T1明文宿MB密鑰源K1密鑰源K偽造者竊聽者密鑰源K-1密鑰源K28基本定理保密學的理論基礎-29惟一解距離和明文冗余度惟一解距離ud：當竊聽

4、者獲取的密文長度大于之，則密碼成為可破譯的；反之，小于它時，密碼理論上是不可破譯的，因為它具有多個解的可能性。實現(xiàn)理想保密，則ud趨向無窮大，有兩種可能：1）完全保密體制：密鑰熵H(K)無窮大2）理想保密體制：密鑰熵有限，但信源的冗余度D=0，即完全隨機。這樣，就得到兩個啟示：1）實現(xiàn)保密的過程實質上是使密文隨機化的過程，可通過增大密鑰，2)或減少明文的冗余度。保密學的理論基礎-3 10實際保密系統(tǒng)一、減少冗余度：1）直接法，采用信源編碼的方法；2）間接法，采用擴散和混淆的方法將信源的冗余度在更大的范圍上擴散開或加以擾亂混淆，間接實現(xiàn)減少信源冗余度的目的。序列加密（擴散法）、DES（混淆與擴散

5、）二、增大密鑰量保密學的理論基礎-4 11優(yōu)點適合實時加密，如實時的數(shù)字話音等理論成熟，其設計、分析較易較分組密碼易于實現(xiàn)基本概念序列流密碼 12經典算法介紹DESDES算法的歷史回顧DES算法如何實現(xiàn)？DES算法的基本思想DES算法如何被破解？13DES-21973年美國國家標準局NBS (National Bureau of Standard)正式向社會公開征集加密算法。1974年IBM正式向NBS提交了應征方案。NBS會同美國國家保密局（NSA National Security Agency)研究發(fā)現(xiàn)這是唯一滿足各項要求的方案。在此方案基礎上形成的數(shù)據(jù)加密標準DES (data enc

6、ryption standard)于1977年1月15日頒布，同年7月正式生效成為美國聯(lián)邦標準FIPS (Federal Information Processing Standard )。其后大約每5年對DES的安全性進行一次審查評估，最后一次是1993年進行的，批準DES的使用終結日期是1998年的12月。14DES-3 DES (Data Encryption Standard)算法是美國政府機關為了保護信息處理中的計算機數(shù)據(jù)而使用的一種加密方式，是一種常規(guī)密碼體制的密碼算法，目前已廣泛用于電子商務系統(tǒng)中。 ：加解密雙方在加解密過程中要使用完全相同的一個密鑰，密鑰就經過安全的密鑰信道由發(fā)

7、方傳給收方。什么是DES？ 基本思想15DES-416DES-5 該算法輸入的是64比特的明文，在64比特密鑰的控制下產生64比特的密文；反之64比特的密文在解密的過程下產生64位的明文。64比特的密鑰中含有8個比特的奇偶校驗位，所以實際有效密鑰長度為56比特。具體算法實現(xiàn)17DES-618DES-7 窮舉法破譯DES 密碼的問題。設已知一段密碼文C及與它對應的明碼文M，用一切可能的密鑰K加密M，直到得到E（M）=C，這時所用的密鑰K即為要破譯的密碼的密鑰。窮舉法的時間復雜性是T=O（n）DES 算法破解19DES-8 對于DES密碼n=25671016，即使使用每秒種可以計算一百萬個密鑰的大

8、型計算機，也需要算106天才能求得所使用的密鑰，因此看來是很安全的。但是到了1997美國有一程序員采用Sever-Client方式在眾多網上志愿者的幫助下利用Internet 96天成功破密獲取密鑰。20DES-91999年1月，EFF（Electronic Frontier Foundation)用DES Crack (內含1856塊芯片)和網絡分布式計算，在22小時15分鐘內破解了RSA數(shù)據(jù)安全公司提出的“DES 挑戰(zhàn)者III”21經典算法RSARSA算法的歷史回顧RSA算法的基本思想RSA算法如何實現(xiàn)？22經典算法RSA1976年，W.diffie和M.hellman首次提出了公開密鑰密

9、碼體制的概念，其中最關鍵的思想是尋找一個“單向函數(shù)”23經典算法RSA什么叫“單向函數(shù)”呢？ X YY=F(x) Y XX=F-1(y)不能實現(xiàn)241977年R.Rivest A.Shamir L.Adleman 提出了第一個比較完善的公開密鑰密碼體制，即著名的RSA體制。25經典算法RSA 選擇兩個大質數(shù) 和 ,每個都大于 ；計算 和 ； 選擇一個與 有關的質數(shù),令其為 ；找到一個 滿足 保密 ; 算法步驟：qp10100 n=p*qz=(p-1)*(q-1) zdede*d=1(mod z)26經典算法RSA 將明碼（當作位串看待）劃分成塊，使得每個明碼報文 落在 之間，這可以通過將明碼分

10、成每塊有 位的組來實現(xiàn)，并且使得 是使 成立的最大整數(shù)。P0Pnkzknk27C=Pe( mod n) P=Cd ( mod n)28經典算法RSA RSA的安全性在于加密變換： C=F(P)=Pe（mod n）的單向性 ：敵方從e和n中無法求出脫密的密鑰d，產生這種單向性的原因是基于大整數(shù)分解在計算上的困難。RSA的安全性29經典算法RSA 如果能有效的分解出n=p*q,則能很容易的求出z=(p-1)*(q-1)最后使用窮盡的方法來找出與z有關的所有質數(shù)d使其能與公鑰e之間有如下的關系： d*e=1(mod n)RSA的安全性30公共密鑰算法RSA 現(xiàn)在我們就來看這個簡單的例子。 我們選擇了

11、p=3，q=11，則n=33，z=20。d的一個適合的值是d=7，因為7和20沒有公共因子，e可以通過求解式7e1（模20）得出，即e=3。明碼報文P的一個密碼C，則由C=P3（模33）將密文解密。給出明碼“SUZANNE”的加密作為例子。因質數(shù)選擇得很小，所以P必須小于33，因此，每個明碼塊只能包含一個字符。結果形成了一個單一字母表代換密碼。這個例子安全嗎？3132密碼學的發(fā)展前沿PKI算法如何實現(xiàn)？PKI算法的基本思想33密碼學的發(fā)展前沿PKI（Public Key infrastructure，公鑰基礎設施）從字面上理解，PKI就是利用公鑰理論和技術建立的提供安全服務的基礎設施。PKI技

12、術是信息安全技術的核心，也是電子商務的關鍵和基礎技術。由于通過網絡進行的電子商務、電子政務、電子事務等活動缺少物理的接觸，因而使得用電子方式驗證信任關系變得至關重要。什么是PKI技術? 34密碼學的發(fā)展前沿 PKI技術恰好是一種適合電子商務、電子政務、電子事務的密碼技術，它能夠有效地解決電子商務應用中的機密性、真實性、完整性、不可否認性和存取控制等安全問題。 一個實用的PKI體系應該是安全的、易用的、靈活的和經濟的。它必須充分考慮互操作性和可擴展性。它包含: 35密碼學的發(fā)展前沿CARA KCASA認證機構 （Certification Authority）注冊機構 （Registration

13、 Authority）策略管理 （strategy administration）密鑰、證書管理 （key & certification administration）36密碼學的發(fā)展前沿 CA（Certificate Authority） 電子簽證機關，CA擁有一個證書（內含公鑰）當然，它也有自己的私鑰，所以它有簽字的能力。網上的公眾用戶通過驗證CA的簽字從而信任CA，任何人都應該可以得到CA的證書（含公鑰），用以驗證它所簽發(fā)的證書。 如果用戶想得到一份屬于自己的證書，他應先向CA提出申請。在CA判明申請者的身份后，便為他分配一個公鑰，并且CA將該公鑰與申請者的身份信息綁在一起，并為之簽字

14、后，便形成證書發(fā)給那個用戶（申請者）。37密碼學的發(fā)展前沿 RA（Registration Authority） 是用戶和CA的接口，它所獲得的用戶標識的準確性是CA頒發(fā)證書的基礎。RA不僅要支持面對面的登記，也必須支持遠程登記，如通過電子郵件、瀏覽器等方式登記。38密碼學的發(fā)展前沿 數(shù)字簽名是防止網上交易時進行偽造和欺騙的一種有效手段。發(fā)送者在自己要公布或發(fā)送的電子文檔上“簽名”，接收者通過驗證簽名的真實性確認文檔是否被篡改過。在公布一份電子文檔時，發(fā)送者首先對要公布的文檔進行哈希（Hash）運算，然后發(fā)送者就可以用自己的簽名私鑰對Hash運算得出的簡潔數(shù)據(jù)進行加密簽名；PKI算法思想： 39密碼學的發(fā)展前沿40密碼學的發(fā)展前