1、第三章 密碼學基礎與應用3.1 密碼學概述3.2 古典密碼學3.3 對稱密碼學3.4 非對稱密碼學3.5 Hash算法3.6 數字簽名3.7 密碼與網絡安全協議3.1 密碼學概述密碼學包括密碼編碼學和密碼分析學。密碼算法：用于加密和解密的數學函數。明文：原本的消息。密文：加密后的消息。密碼系統：由算法以及所有可能的明文、密文和密鑰組成。C=E(M)表示加密，M=D(C)表示解密，M=D(E(M)密碼算法的分類（一）按照保密的內容分:受限制的（restricted)算法 對數據的保密性基于對算法的保密。基于密鑰（key-based)的算法 算法的保密性基于對密鑰的保密。密碼算法的分類（二）按照對

2、明文的處理方法：分組密碼（block cipher) 將明文分成固定長度的組，用同一密鑰和算法對每一塊加密，輸出也是固定長度的密文。流密碼（stream cipher) 又稱序列密碼。序列密碼每次加密一位或一字節的明文。序列密碼是手工和機械密碼時代的主流。序列密碼分組密碼XNOITPYRCNES明文I H密鑰（可選的）PO密文BAQCKDEMMC密碼算法的分類(三)在基于密鑰的算法中，按照密鑰的特點分類： 對稱密碼算法（symmetric cipher) 又稱傳統密碼算法（conventional cipher)，就是加密密鑰和解密密鑰相同，或實質上等同，即從一個易于推出另一個。又稱秘密密鑰算

3、法或單密鑰算法。非對稱密鑰算法（asymmetric cipher) 加密密鑰和解密密鑰不相同，從一個很難推出另一個。又稱公開密鑰算法（public-key cipher) 。3.2 古典密碼學密碼技術是信息安全的核心技術。密碼技術要求很高的數學基礎：群和域的理論、計算復雜性以及實時分析，更不用說概率與統計。我們希望建立這樣一種密碼算法，它對于合法的發送者和接受者來說易于操作，而對于惡意的截取者卻十分困難。可靠的密碼學建立在數學和形式化的計算機科學產生的結論之上。 密碼學的產生與發展滾筒密碼長副的那死，信長副的那死，信公市石底后讓神公市石底后讓神干長板下的人的干長板下的人的去先路埋位愜中去先路

4、埋位愜中了生上著置意國了生上著置意國，又，死離，人，又，死離，人愛興許人上也用愛興許人上也用開致多。帝讓一開致多。帝讓一玩勃石人最人種玩勃石人最人種笑勃板們近覺超笑勃板們近覺超的地上之。得越的地上之。得越市帶刻所一上語市帶刻所一上語長領著以陣帝言長領著以陣帝言和我人愿夏和的和我人愿夏和的滾筒密碼經過短暫的歡大家啟程去關鍵參數：滾筒的寬度（密鑰）愷撒密碼（Caesar）原理：把一個字母替換為它后面固定位置的另一個字母（單表代換密碼）。A B C D E F G X Y ZD E F G H I J A B C明文:Caesar cipher is a shift substitution密文:F

5、DHVDU FLSKHU LV D VKLIW VXEVWLWXWLRQ弗納姆密碼（Vernam Cipher）1918年Gilbert Vernam 為AT&T設計的一種一次一密亂碼本密碼（多表代換密碼）。原理：使用一個任意長的不重復數字序列，把它和明文組合在一起。明文： V E R N A M C I P H E R等價數字：21 4 17 13 0 12 2 8 15 7 4 17+隨機數： 76 48 16 82 44 3 58 11 60 5 48 88和mod26： 19 0 7 17 18 15 8 19 23 12 0 1密文： t a h r s p i t x m

6、a b維吉尼亞密碼m個移位代換表由m個字母組成的密鑰字確定明文：w e a r d i s c o v e r e d s a v e 密鑰：d e c e p t i v e d e c e p t i v e 對應數字：3 4 2 15 19 8 21 密文：Z I C V T WQNGRZGVTWAVZH換位密碼（置換密碼）（一）換位就是將明文中的字母的位置重排。最簡單的換位就是逆序法： 明文：computer system 密文：metsys retupmoc換位密碼（置換密碼）（二）列置換（縱行換位）：把明文中的字符按列重新排列。例如明文：THIS IS A MESSAGE. T H

7、 I S I S A M E S S A G E X密文：TSSHAAIMGSEEISX問題：1.排成的矩陣的寬度（有多少列）。 2.排成矩陣后，各列按什么順序輸出。換位密碼（置換密碼）（三）引入密鑰k，如k=COMPUTER，明文為：WHAT CAN YOU LEARN FROM THIS BOOK密文為：WORO NNSX ALMK HUOO TETX YFBX ARIX CAHX 密鑰密鑰COMPUTER順序號14358726明文WOROHUOOALMKTETXCAHXARIXNNSXYFBX現代密碼學的原理加密體系的安全性并不依賴于加密的方法本身，而是依賴于所使用的密鑰。當時的密碼體系

8、缺乏數學背景，因而也缺少測量或評價這些體系抗攻擊的能力。1948年，Shannon發表的論文通信的數學原理將數學背景加入了密碼學。對稱加密算法分為兩種：分組密碼 每次對一塊數據加密，多數網絡加密應用，如DES，IDEA，RC6，Rijndael。流密碼（序列密碼） 每次對一位或一字節加密，語音和視頻流 的加密傳輸，如Vigenre，Vernam。速度快，安全強度高，主要用做數據加密 算法。非對稱密鑰算法（公開密鑰算法）用一個密鑰進行加密，而用另一個進行解密。加密密鑰可以公開，又稱公開密鑰（public key），簡稱公鑰。解密密鑰必須保密，又稱私人密鑰（private key），簡稱私鑰。RS

9、A，ECC，ElGamal數據加密、身份認證、密鑰分發、數字簽名。加密解密速度慢。密碼分析密碼分析學是研究密鑰未知的情況下恢復明文的科學。編碼的特征：轉明文為密文的方法：代替和換位所用的密鑰數：對稱密碼、非對稱密碼處理明文的方法：分塊和單字節密碼分析可以發現密碼體制的弱點。常見的攻擊（密碼分析方法）攻擊類型攻擊類型攻擊者掌握的信息攻擊者掌握的信息唯密文攻擊加密算法截獲的部分密文已知明文攻擊截獲的部分密文一個或多個明文/密文對選擇明文攻擊截獲的部分密文自己選擇的明文及由密鑰產生的相應密文選擇密文攻擊截獲的部分密文自己選擇的密文及對應的明文密碼分析方法確定性 利用若干已知的數學關系式表示出所求的未

10、知量。統計性 利用明文的已知統計規律進行破譯。代替密碼和換位密碼計算機出現前，以字符代替或換位計算機出現后，以比特代替或換位代替密碼（substitution cipher)：就是明文中的每一個字符被替換成密文中的另一個字符。接收者對密文做反向替換就可以恢復出明文。如愷撒密碼。換位密碼（transposition cipher) ，又稱置換密碼(permutation cipher)：明文的字母保持相同，但順序被打亂了。代替密碼簡單代替密碼（單字母密碼）：明文的一個字符用相應的一個密文字符代替。如愷撒密碼（密鑰為3）。多名碼代替密碼：明文的一個字符可以映射成密文的幾個字符之一。字母代替密碼：組

11、成加密字符塊。多表代替密碼：由多個簡單的代替密碼構成。如滾動密鑰密碼。代替密碼的破譯猜測密鑰的長度利用字母頻度表進行破譯各個明文字母的概率和密文字母頻率的對照換位密碼的破譯判斷密碼類型：利用密文中字母出現的頻率判斷是否為換位密碼。根據消息的上下文猜測密鑰的長度，即列數。確定各列的順序。3.3 對稱密碼學DESDES數據加密標準數據加密標準1973年5月，美國國家標準局發出通告，公開征求對計算機數據在傳輸和存儲期間的進行數據加密的算法。要求：必須提供高度的安全性；具有相當高的復雜性，使得破譯的開銷超過獲得的利益，但同時又便于理解和掌握；安全性應當不依賴于算法的保密，加密的安全性僅以加密密鑰的保密

12、為基礎；必須適合不同的用戶和不同的應用場合； 實現算法的電子器件必須很經濟，運行有效； 必須能夠出口。1975年，IBM提出的算法被采納，并向全國公布，征求意見。1977年1月15日，美國國家標準局正式采用這個算法作為數據加密標準（同年7月15日生效）。1998年12月以后新的美國聯邦加密標準被稱為高級加密標準AES。DES的算法思想將二進制序列的輸入明文，以64位為數據分組，然后對這些明文進行替換和換位，最后形成密文。DES64位明文組56位密鑰64位密文組DES算法的基本特點對稱算法：既可用于加密，也可用于解密。64位的密鑰，使用長度為56位（64位密鑰中，有8位用于奇偶校驗）。加密算法是

13、換位與置換的結合。每個DES都在明文上實施16重相同的組合技術，這種重復性可以被理想地應用到一個專用芯片中。DES加密過程DES加密過程細化DES加密過程主要涉及如下環節（模塊）：初始換位和逆初始換位將64位明文分為32位的左右兩段：L0和R0生成每一輪的子密鑰進行16輪相同的迭代運算：混淆+異或+交換將最后左右兩段合并DES的安全性密鑰長度太小，IBM建議用112比特；差分密碼分析與線性分析；20世紀90年代，RSA公司發起對DES的三次挑戰；1999年一百多個CPU利用并行算法，用23小時左右成功破譯；1999年在互聯網上，用分割密鑰方法成功破譯。三重DES（TDES）執行3次DES算法，

14、相當于使用3倍DES的密鑰長度的密鑰，記加密密鑰為加密：解密：初始換位IP逆初始換位子密鑰的生成PC-1變換及密鑰的分割每輪左移位數壓縮置換PC-2從56位密鑰中取出48位PC-2壓縮算法f算法f算法是DES精華所在，用它來實現分組加密的擴展和混淆。在DES中，其他部分是線性的，而f算法是非線性的。f算法主要由E-盒、S-盒和P-盒組成。f算法的組成E-盒（Expansion Permutation）把數據明文的右半部分Ri從32位擴展到48位。這樣的好處有：可以與48位的密鑰進行異或運算；有利于產生雪崩效應（Avalanche Effect）盡快地使輸出（密文）的每一位依賴輸入 （明文和密鑰

15、）的每一位。E-盒擴展置換 S-盒代換對48位的輸入替代壓縮成32位的輸出。替代由8個S-盒進行。每個S-盒有6位輸入，4位輸出。P-盒置換16167 72020212129291212282817171 11515232326265 518183131101028241432273919133062211425對S-盒的32位輸出進行一次換位3.4 非對稱密碼學公鑰密碼體制的基本原理公鑰密碼體制的基本原理19761976年，年，Diffie和和Hellman提出了公鑰密碼體制提出了公鑰密碼體制密鑰公開是否有價值？密鑰公開是否有價值？對稱加密對稱加密公鑰加密公鑰加密密鑰數目12密鑰保護必須保護

16、一個密鑰必須保護，另一個可以暴露最適用于密碼機：數據的保密性和完整性從單字符到數據塊、報文、文件密鑰交換，身份認證密鑰分配復雜、難度大公鑰可用于分配其他密鑰速度快緩慢；一般比對稱加密慢10000倍基于公開密鑰的加密過程公鑰密碼體制的加密功能A向B發消息X，B的公鑰為KUb,私鑰為KRb加密 Y = EKUb(X)解密 X = DKRb(Y) 基于公開密鑰的認證過程公鑰密碼體制的認證A向B發送消息XA的公鑰為KUa，私鑰為Kra“加密”： Y = EKRa(X) （數字簽名）“解密”： X = DKUa(Y) 注意：不能保證消息的保密性 對稱密碼 公鑰密碼一般要求：一般要求：1、加密解密用相同的

17、密鑰2、收發雙方必須共享密鑰安全性要求：安全性要求：1、密鑰必須保密2、沒有密鑰，解密不可行3、知道算法和若干密文不足以確定密鑰一般要求：一般要求：1、加密解密算法相同，但使用不同的密鑰2、發送方擁有加密或解密密鑰，而接收方擁有另一個密鑰安全性要求：安全性要求：1、兩個密鑰之一必須保密2、無解密密鑰，解密不可行3、知道算法和其中一個密鑰以及若干密文不能確定另一個密鑰公鑰密碼體制實現的關鍵問題： 如何確定公鑰PK和私鑰SK及加密、解密的算法。SK與PK成對出現，需滿足如下條件：1.Dsk(Epk(X)=X2.Dpk(Epk(X)X3.在計算機上可以容易地產生成對的PK和SK4.從已知的PK實際上

18、不可能推導出SK5.加密和解密運算可以對調，即 Dsk(Epk(X)=X=Epk(Dsk(X) 如何確定PK和SK？陷門單向函數 一個函數，若計算函數值很容易，并且在缺少一些附加信息時計算函數的逆是不可行的，但是已知這些附加信息（如SK）時，可在多項式時間內計算出函數的逆，那么我們稱這樣的函數為陷門單向函數。 將特定的某類陷門單向函數記為F，隨機選取一個屬于F的函數f，作為公開加密函數，其逆函數是秘密解密函數，利用SK將可有效解密。公鑰密鑰的應用范圍加密/解密數字簽名（身份認證）密鑰交換公鑰密碼體制基于的數學難題背包問題大整數分解問題（The Integer FactorizationProb

19、lem,RSA體制）有限域的乘法群上的離散對數問題(The Discrete Logarithm Problem,ElGamal體制）橢圓曲線上的離散對數問題（The EllipticCurve Discrete Logarithm Problem,類比的ElGamal體制）目前受到廣泛認可的加密系統大整數因子分解系統（如RSA）橢圓曲線離散對數系統（ECC）離散對數系統（如DSA）RSA算法由MIT的 Rivest,Shamir & Adleman 在 1977 提出最著名的且被廣泛應用的公鑰加密體制 明文、密文是0到n-1之間的整數，通常n的大小為1024位或309位十進制數RSA

20、算法描述加密： C=Me mod N, where 0MN,N=pq解密： M=Cd mod N 公鑰為（e，N）， 私鑰為（d，p,q）必須滿足以下條件：Med = M mod N計算Me和Cd是比較容易的由e和n確定d是不可行的RSA 密鑰產生過程隨機選擇兩個大素數 p, q 計算 N=p.q注意 (N)=(p-1)(q-1) 選擇 e使得1e(N),且gcd(e,(N)=1 解下列方程求出 d e.d=1 mod (N) 且且 0dN 公布公鑰: KU=e,N 保存私鑰: KR=d,p,q RSA的使用發送方要加密明文M:獲得接收方的公鑰 KU=e,N 計算: C=Me mod N, w

21、here 0MN接收方解密密文C: 使用自己的私鑰 KR=d,p,q 計算: M=Cd mod N 注意：M必須比N小RSA Example1.選擇素數: p=17 & q=112.計算 n = pq =1711=1873.計算 (n)=(p1)(q-1)=1610=1604.選擇整數 e : gcd(e,160)=1;e=75.求d: de=1 mod 160 and d 160 因此d=23 （ 如何計算？）6.公鑰KU=7,1877.私鑰KR=23,17,11RSA Example cont利用 RSA 加解密：明文M = 88 (88187)加密:C = 887 mod 187

22、 = 11 解密:M = 1123 mod 187 = 88 信息的認證是通過認證符進行。產生認證符的方法一般分為三類：信息加密：對明文加密后以密文作為認證符。消息認證碼（MAC）：用一個公開函數作用后，產生固定長度的數值作為認證符，也稱為密碼校驗和。散列函數：定義一個函數將任意長度的消息映射為定長的散列值，用散列值作為認證符。消息認證：保證數據的完整性3.5 Hash算法散列（Hash）函數也稱雜湊函數、哈希函數，通常簡寫為H，是一個單向公開函數。它可以將任意長的消息M映射為較短的、固定長度的一個值H(M)作為消息M的認證符。 H(M)也稱消息摘要MD（message digest）或雜湊碼、散列碼。其目的是為文件、消息或其他的分組數據產生“指紋”。Hash函數的結構對不定長的輸入產生定長的輸出，且最后的結果要與所有字節有關。分塊填充鏈接模式，迭代型結構：將輸入數據分為L個固定長度為b比特的分組（分塊、填充）；散列算法中重復使用一個壓縮函數f，產生一個n比特的輸出（鏈接）。Hash函數舉例典型的Hash算法有MD5MD5（Rivest提出，1992年RFC 1321公布，碼長128比特）和安全Hash算法SHA和SHA-1SHA-1（Secure Hash Algorithm，碼長160比特）。由于SHA和SHA-1比MD5多了32比特，所以更安全，但