第2章現(xiàn)代密碼學概論課件

1、第2章 現(xiàn)代密碼學概論本章要點 現(xiàn)代密碼學框架 現(xiàn)代密碼學的理論基礎 對稱加密標準：DES和AES 公鑰密碼體制：RSA和ElGamal體制2.1 現(xiàn)代密碼學框架 2.1.1 什么是密碼學 定義1 密碼學是研究與信息安全各方面有關的(比如機密性、數(shù)據(jù)完整性、實體認證及數(shù)據(jù)源認證) 數(shù)學技術的一門學科。 2.1.1 什么是密碼學(續(xù))發(fā)送者Alice密鑰源分析者Eve接收者Bob安全信道公共信道加密器Ek解密器Dk明文m密文c明文m密鑰k密鑰k圖 2.1 Shannon保密系統(tǒng) 2.1.1 什么是密碼學(續(xù)) 通信中的參與者 (1) 發(fā)送者(Alice)： 在雙方交互中合法的信息發(fā)送實體。 (2

2、) 接收者(Bob)：在雙方交互中合法的信息接收實體。 (3) 分析者(Eve)：破壞通信接收和發(fā)送雙方正常安全通信的其他實體。可以采取被動攻擊和主動攻擊的手段。 信道 (1) 信道：從一個實體向另一個實體傳遞信息的通路。 (2) 安全信道：分析者沒有能力對其上的信息進行閱讀、刪除、修改、添加的信道。 (3) 公共信道：分析者可以任意對其上的信息進行閱讀、刪除、修改、添加的信道。2.1.2 現(xiàn)代密碼學中的對稱與非對稱密碼思想加密器EK1(m)=c分析者Eve解密器DK2(c)= m明文消息源目的地mmc公共信道AliceBob# 對稱密碼的加密密鑰與解密密鑰同：K1=K2代表系統(tǒng)：DES和AE

3、S2.1.2 現(xiàn)代密碼學中的對稱與非對稱密碼思想(續(xù))若互聯(lián)網(wǎng)上有n個用戶，則需要個密鑰，若n=1000，則NK500 000。# 如此眾多的密鑰如何建立，如何保存？2.1.2 現(xiàn)代密碼學中的對稱與非對稱密碼思想(續(xù))加密器EK1(m)=c分析者Eve解密器DK2(c)= m明文消息源目的地mmc公共信道AliceBob#非對稱密碼的加密密鑰與解密密鑰不同：K1K2代表系統(tǒng)：RSA和ElGamal2.1.3 密碼學的演進及目前的狀態(tài)安全依賴于保密加密方法安全依賴于保密密鑰安全依賴于保密部分密鑰古典密碼私鑰密碼公鑰密碼#公鑰密碼體制以其強大的功能使得私鑰密碼體制顯得已經(jīng)過時，但是強大的功能不是無

4、代價獲得的，公鑰密碼的計算量遠大于相同情況下的私鑰密碼。因此，不適合加密大量數(shù)據(jù)，只適合于完成少量數(shù)據(jù)加密，如傳送私鑰密碼的密鑰、簽名等等。2.1.4 現(xiàn)代密碼學主要技術Security PrimitivesPublic-key PrimitivesSymmetric-key PrimitivesUnkeyed PrimitivesArbitrary length hash functionsSymmetric-key ciphersRandom sequencesOne-way permutationsBlock ciphersStream ciphersArbitrary length h

5、ash functions (MACs)SignaturesPseudorandom sequencesIdentification primitivesPublic-key ciphersSignaturesIdentification primitives圖2.2 密碼學本原分類2.1.4 現(xiàn)代密碼學主要技術(續(xù)) (1) 加密 加密基本術語 明文消息空間M: 某個字母表集 密文消息空間C: 可能的密文消息集 加/解密密鑰空間K: 可能的加/解密密鑰集 加/解密函數(shù)EeK (mM) / DdK (cC) : 一個 從M到C/C到M的有效變換2.1.4 現(xiàn)代密碼學主要技術(續(xù)) 加密方案 加

6、密方案是由一個加密函數(shù)集Ee: eK和解密函數(shù)集Dd: dK構成，并且滿足任意一個加密密鑰eK存在唯一一個解密密鑰dK使 Dd=Ee-1，也就是對于所有明文消息mM ，存在Dd(Ee(m)=m，(e, d)稱為密鑰對。設計加密方案就是確定M、 C、 K、Ee: eK、Dd:dK的過程。 定義2 一個加密方案可以被破譯是指，第三方在沒有事先得到密鑰對(e, d)的情況下，可以在適當?shù)臅r間里系統(tǒng)地從密文恢復出相對應的明文。 # 適當?shù)臅r間由被保護數(shù)據(jù)生命周期來確定。2.1.4 現(xiàn)代密碼學主要技術(續(xù)) 私鑰加密 定義3 一個由加密函數(shù)集Ee: eK和解密函數(shù)集Dd: dK組成加密方案，每一個相關聯(lián)

7、的密鑰對(e, d) ，如果知道了e在計算上很容易確定d，知道了d在計算上很容易確定e，那么，就是私鑰加密方案。 # 私鑰加密需要一條安全信道來建立密鑰對。 主要技術：分組密碼與流密碼 定義 4(分組密碼) 將明文消息在編碼集按照固定長度t進行分組，再一組一組地加解密明密文消息。 #著名的DES、AES都是這類密碼。2.1.4 現(xiàn)代密碼學主要技術(續(xù)) 定義5 K 是加密變換集的密鑰空間，序列 e1e2 eiK稱為密鑰流。 定義6 (流密碼) 消息m以串的形式(m1m2mi)給出，密鑰e1e2ei是K上的密鑰流。流密碼通過ci=Eei(mi)給出密文消息(c1c2ci)；如果di為ei的逆，解

8、密則通過mi=Ddi(ci)完成。 2.1.4 現(xiàn)代密碼學主要技術(續(xù)) 公鑰加密 定義 7 一個由加密函數(shù)集Ee: eK和解密函數(shù)集Dd: dK組成加密方案，每一個相關聯(lián)的加/解密密鑰對(e, d)，加密密鑰e公開，稱為公開密鑰，而解密密鑰d保密，稱為秘密密鑰。 # 顯然安全公鑰密碼系統(tǒng)要求從e計算d為不可能。2.1.4 現(xiàn)代密碼學主要技術(續(xù))公鑰加密實例Ee(m1)=c1A1Ee(m2)=c2A2Ee(m3)=c3A3Dd(c1)=m1Dd(c2)=m2Dd(c3)=m3Bobec1eec2c3# 因為存在替代攻擊問題，公鑰系統(tǒng)中公開密鑰e必須認證，一般是建立PKI。2.1.4 現(xiàn)代密碼

9、學主要技術(續(xù)) (2) 數(shù)字簽名技術 基本術語 明文消息空間M:某個字母表中串的集合 簽名空間S:可能的簽名集合 簽名密鑰空間K:用于生成簽名的可能密鑰集，具體取值k需要保密 驗證密鑰空間K:用于驗證簽名的可能密鑰集，具體取值k需要公開 簽名函數(shù)SK(mM):從M到S的有效變換 驗證函數(shù)VK(mM, s):一個從MS到輸出True, False的有效變換2.1.4 現(xiàn)代密碼學主要技術(續(xù)) 簽名過程 簽名(簽名者完成) 1) 對一條需要簽名的消息mM計算簽名s=Sk(m)。 2) 將對消息m的簽名(m, s)發(fā)送出去。 驗證 (驗證者完成) 1) 得到對應簽名者的驗證算法Vk ，計算u=Vk

10、 (m, s)。 2) 如果u=True，接受簽名；如果u=False，拒絕簽名。2.1.4 現(xiàn)代密碼學主要技術(續(xù)) 簽名和認證函數(shù)必須滿足的性質(zhì) 1) 當且僅當Vk (m, s)=True時，s是消息m的合法簽名。 2) 對于任何簽名者以外的實體在計算上不可能得到任意的一組mf和sf滿足Vk (mf , sf)=True。 數(shù)字簽名的爭議解決(不可否認) 如果簽名者和驗證者對簽名發(fā)生爭議，可由驗證者帶著簽名(m, s)提交給可信任第三方(TTP)，由TTP驗證該簽名，最后進行仲裁。2.1.4 現(xiàn)代密碼學主要技術(續(xù)) 數(shù)字簽名技術在公鑰基礎設施(PKI)中的應用 除非對密鑰產(chǎn)生的認證性和合

11、法性有足夠的信任，否則公鑰密碼的優(yōu)勢就十分有限。公鑰基礎設施或簡稱PKI是一個框架。這個框架主要由一組策略組成。策略確切定義了關于密碼系統(tǒng)運行和密鑰產(chǎn)生和發(fā)布與其證書的規(guī)則。 X.509是設計用來在大型計算機網(wǎng)絡中提供目錄認證服務的國際標準。由于它本身是ISO/ITU 的一個標準，很多實用產(chǎn)品都基于它開發(fā)出來。例如，X.509被用在Visa和Mastercard的安全電子交易標準中。2.1.4 現(xiàn)代密碼學主要技術(續(xù))圖2.3 X.509的結構原理2.1.4 現(xiàn)代密碼學主要技術(續(xù))2.1.4 現(xiàn)代密碼學主要技術(續(xù))圖2.4 證書認證過程A1A6認證VT(A6 | e6 , s6)秘密密鑰

12、d6A2, e2, ST(A2 | e2)=s2A3, e3, ST(A3 | e3)=s3A4, e4, ST(A4 | e4)=s4e6, s6Dd6(c)=mc = Ee6(m)Public fileA1, e1, ST(A1 | e1)=s1A5, e5, ST(A5 | e5)=s5A6, e6, ST(A6 | e6)=s6A2, e2, ST(A2 | e2)=s2# 證書權威負荷小(離線、非交互、存儲證書)，權限低2.1.4 現(xiàn)代密碼學主要技術(續(xù)) 公鑰證書的產(chǎn)生 情況1 可信方產(chǎn)生密鑰對。可信方為實體產(chǎn)生公鑰算法的密鑰對，并將公開密鑰和綁定身份的公鑰證書通過公共信道發(fā)給該實

13、體。實體在證明了自己的身份(例如，出示身份證或個人可信照片)后，將通過安全信道得到對應的秘密密鑰。 情況2 實體產(chǎn)生自己的密鑰對。實體產(chǎn)生自己的公鑰算法的密鑰對，并安全地將公開密鑰傳送給可信方(例如，通過可信通道或派人送達)，這里主要是保證公開密鑰的真實性。在驗證了公開密鑰來源的真實性后，可信方為公開密鑰生成證書。2.1.4 現(xiàn)代密碼學主要技術(續(xù))證書鏈和證書路徑圖2.5 證書鏈 2.1.4 現(xiàn)代密碼學主要技術(續(xù)) (3) 認證與鑒別技術 鑒別或實體認證 定義 9 鑒別或實體認證是一個過程。在這個過程中一方通過獲得一些確定的證據(jù)來確認參加實體認證的另一方的身份，而具有相應身份的實體也確實就

14、是正在參與這一認證過程的另一方。 例子1 實體A與B通電話，如果A與B認識就可以通過聲音來確定對方的真實性。 例子2 實體A通過信用卡在銀行ATM機上取錢。 # 特點：時實性。2.1.4 現(xiàn)代密碼學主要技術(續(xù)) 直觀安全目標： a 在宣稱者A和驗證者B都誠實地執(zhí)行認證時，A能向B成功地證明自己，也就是B將完成執(zhí)行并接受A所宣稱的身份。 b (不可轉移性)驗證者B不能從與宣稱者A交互中獲得的信息，成功地向第三方C來冒充A 。 c (不可冒充性)任何一個非宣稱者A的C想通過扮演A的身份，通過驗證者B的認證，讓B接受A的身份的可能性可以忽略。這里，可以忽略的含義是概率小到?jīng)]有具體的實際意義，準確的

15、度量需要根據(jù)實際應用而定。 d 即使如下情況存在，以上三個條件仍然成立。 d.1宣稱者A和驗證者B之間以前進行的多項式次認證會話且被竊聽; d.2 冒充者C以前參與了同宣稱者A或（和）驗證者B的認證執(zhí)行; d.3 冒充者C可能發(fā)起多個認證會話并行運行。2.1.4 現(xiàn)代密碼學主要技術(續(xù)) 數(shù)據(jù)源認證 定義10 數(shù)據(jù)源認證或消息認證技術，提供一方通過一些附加的證據(jù)，確定消息的產(chǎn)生一方的真實身份。 例子3 實體A向實體B發(fā)送電子郵件，電子郵件通過網(wǎng)絡傳輸并存儲，在某個時間由B接收到，由于沒有直接通信，B這時可能要求認證郵件確實來自A。2.1.4 現(xiàn)代密碼學主要技術(續(xù)) (4) 密碼Hash 函數(shù)

16、技術 定義11 Hash函數(shù)h() 是一個有效的計算方法，它將一個任意長度的二進制位串影射成固定長度的二進制位串，這個固定長度的二進制位串叫Hash值。 修改發(fā)現(xiàn)碼(MDCs) 附加性質(zhì) 1) Hash函數(shù)是單向函數(shù)，即給定y，找到任意x，滿足 y=h(x) 計算不可能。 2) 已知x，找x ，滿足h(x)=h(x) 計算不可能。 3) 找一任意對x和x ，滿足h(x)=h(x) 計算不可能。 # 修改發(fā)現(xiàn)碼可以進一步分類，單向Hash函數(shù)(1-2)(OWHFs)和碰撞抵抗Hash函數(shù)(2-3)(CRHFs)。2.1.4 現(xiàn)代密碼學主要技術(續(xù)) 消息認證碼(MACs) 消息認證碼的目的，通俗

17、講就是不附加任何其他機制，確保消息來源的真實性的Hash函數(shù)。消息認證碼有兩個不同功能的參數(shù)，即消息和秘密密鑰。 Hash函數(shù)無密鑰有密鑰修改發(fā)現(xiàn)碼(MDCs)其他應用其他應用消息認證碼(MACs)圖2.6 密碼Hash函數(shù)的簡單分類2.1.4 現(xiàn)代密碼學主要技術(續(xù)) (5) 隨機數(shù)與隨機序列 密碼中以偽隨機序列發(fā)生器代替隨機序列發(fā)生器。偽隨機序列發(fā)生器以短的隨機數(shù)做種子，以固定方式產(chǎn)生偽隨機序列。 # 偽隨機序列與真隨機序列不可區(qū)分假設，與安全數(shù)字簽名、公鑰密碼的存在性等價。2.1.5 評價現(xiàn)代密碼算法的標準 Kerckhoffs準則 在評估一個密碼系統(tǒng)安全性時，應該總是假定我們的敵人了解

18、實際使用的各種方法。 # 落實到現(xiàn)代密碼算法中就是攻擊者知道密碼算法的所有執(zhí)行細節(jié)，算法的安全不應該依賴于對算法的保密。2.1.5 評價現(xiàn)代密碼算法的標準(續(xù)) Shannon提出的“優(yōu)質(zhì)”密碼算法特征 (1) 加解密的工作量應該由所要求的安全程度決定。 (2) 密鑰集合和加密算法不應該過于復雜。 (3) 執(zhí)行過程應該盡量簡單。 (4) 密碼中的差錯不應該具有傳播性，也不應該影響報文中的其他信息。 (5) 加密后的文本大小不應該比原始報文顯著增大。2.1.5 評價現(xiàn)代密碼算法的標準(續(xù))“可信賴的”加密體制的特點(1) 有可靠的數(shù)學基礎。(2) 經(jīng)過專家的嚴格分析，證實是可靠的。(3) 經(jīng)得起

19、時間的檢驗。2.2 現(xiàn)代密碼學的理論基礎 現(xiàn)代密碼學要求很高的數(shù)學基礎，包括：數(shù)論、抽象代數(shù)與有限域、計算復雜理論、信息論、概率論等。 但是掌握基礎的密碼算法并不需要精通過多的底層數(shù)學理論。這里我們僅講述掌握本章的密碼算法所需要的計算復雜理論、數(shù)論等的基礎知識。2.2.1 計算復雜理論 如果加密算法建立在一個已知非常難解決的問題或者可能解的數(shù)目巨大的問題之上，那么攻擊者要破譯算法就注定要完成一個即便不是不可能，也是另人沮喪的任務。即使有計算機的支持，一個窮盡的暴力解答也是不可行的。NP完全問題就是這樣一類具有計算復雜特點的問題。我們用非形式化的方式來描述NP完全問題。2.2.1 計算復雜理論(

20、續(xù)) NP完全問題 幾個具體實例 例子4 可滿足問題 給定邏輯公式滿足如下條件： (1) 它由變量v1，v2，vn和它們的邏輯非v1，v2，vn 組成。 (2) 它表現(xiàn)為一系列子句，且每個子句的形式是變量以及邏輯非的邏輯或() (3) 它表示為這些子句的邏輯與() 是否存在一種變量的賦值法(賦真或假)，使得公式為真？如果存在，說這個公式是可滿足的。例如， (v1) (v2 v3) ( v1 v3) 為可滿足的， (v1) (v2 v3) ( v1 v3) ( v2)為不可滿足的。2.2.1 計算復雜理論(續(xù))例子5 背包問題2.2.1 計算復雜理論(續(xù)) 例子6 團 給定一個圖G和一個整數(shù)n，

21、是否存在一個包含n個頂點的子圖，使得子圖中的每個頂點與其他頂點之間都有一條邊每個頂點都與其他所有頂點相連的圖被稱為團(clique)? 例如，圖2.7有4頂點的團，但無5頂點的團。圖 2.7 圖的團子圖2.2.1 計算復雜理論(續(xù)) NP完全問題的特征 (1) 每個問題都有解法，且總有一個相對簡單的解法(盡管該解法也許十分耗時)。 (2) 如果要列舉所有可能性，就需要考慮2n中情況(n與問題有關) (3) 這些問題是無關的，分別來自邏輯學、數(shù)論和圖論。 (4) 如果能完全猜中，則可以在相對較少的時間內(nèi)求解每一個問題。2.2.1 計算復雜理論(續(xù)) P類和NP類 P類問題是一類問題的集合，這個集

22、合中的問題都可以在一個與問題大小相關的多項式函數(shù)時間內(nèi)完成。 NP類問題是所有這樣一類問題的集合，假設能夠完全猜中，這些問題可以在一個多項式函數(shù)時間內(nèi)得到解決(猜測函數(shù)被稱為是預言機或非確定性圖靈機)。這種猜測是非確定性的。 EXP類，它由所有存在指數(shù)時間cn內(nèi)的確定性解法的問題組成，其中，c是一個常數(shù)。 它們有如下關系，PNP EXP。2.2.1 計算復雜理論(續(xù)) NP完全的含義 Cook證明了：如果可滿足問題有一個確定性的、多項式時間的算法(不帶猜測)，那么對NP中的每個問題都會有一個確定性、多項式時間的算法，即NP=P。Karp證明了背包問題和團問題具有和可滿足問題一樣的性質(zhì)。這一問題

23、的逆否命題是：如果可以證明這些問題中的某個問題沒有在多項式時間內(nèi)完成的確定性算法，那么它們中所有問題都不存在確定性多項式時間算法。這里對一個問題的解決是要求找到一個通用算法來解決它的每個實例。2.2.1 計算復雜理論(續(xù))圖 2.8 復雜性的層次結構# P=NP或PNP2.2.1 計算復雜理論(續(xù)) 已經(jīng)有很多人對NP完全問題進行了長期研究，如果對確實存在多項式時間算法，那么有理由認為已經(jīng)有人找到了解法。目前，已經(jīng)有數(shù)以百計的問題被證明是NP完全問題。我們列舉的這類問題越多，就越有理由確信不存在一個能解決所有問題的簡單方法。2.2.1 計算復雜理論(續(xù)) NP完全性與密碼學 (1) 一個NP完

24、全問題不能保證不存在一種比指數(shù)時間更容易的算法，它僅表示我們不大可能找到這一算法。 (2) 每個NP完全問題都有一個確定性的指數(shù)時間算法，即可以與2n成比例的時間運行完成。 (3) 硬件的不斷進步，越來越大規(guī)模的問題都能計算了。 (4) 即使一個加密算法是基于難解問題的，但攻擊者未必總是去解這個難解問題才能破譯加密算法。2.2.1 計算復雜理論(續(xù)) 其他固有的難解問題 數(shù)論中存在大量難解問題，但大多數(shù)數(shù)論中的難解問題都是NP問題，不是NP完全問題。公鑰密碼體制主要依賴數(shù)論中的兩個難解問題：大整數(shù)分解問題和離散對數(shù)問題。2.2.2 數(shù)論知識(1) 基本概念整除性2.2.2 數(shù)論知識(續(xù))2.2

25、.2 數(shù)論知識(續(xù))素數(shù)2.2.2 數(shù)論知識(續(xù)) 200以內(nèi)的素數(shù)： 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 2.2.2 數(shù)論知識(續(xù))2.2.2 數(shù)論知識(續(xù))2.2.2 數(shù)論知識(續(xù))2.2.2 數(shù)論知識(續(xù))2.2.2 數(shù)論知識(續(xù))2.2.2 數(shù)論知識(續(xù))整數(shù)唯一分解定理2.2.2 數(shù)論知識(續(xù))2.2.2 數(shù)論知識

26、(續(xù))一次不定方程2.2.2 數(shù)論知識(續(xù))(2) 同余同余定義與概念2.2.2 數(shù)論知識(續(xù))2.2.2 數(shù)論知識(續(xù))剩余類和完全剩余系2.2.2 數(shù)論知識(續(xù))縮系2.2.2 數(shù)論知識(續(xù))2.2.2 數(shù)論知識(續(xù))2.2.2 數(shù)論知識(續(xù))一次同余式2.2.2 數(shù)論知識(續(xù))2.2.2 數(shù)論知識(續(xù))(3) 原根2.2.2 數(shù)論知識(續(xù))2.2.2 數(shù)論知識(續(xù))2.2.2 數(shù)論知識(續(xù))2.2.3 群環(huán)域的概念(1) 群2.2.3 群環(huán)域的概念(續(xù))2.2.3 群環(huán)域的概念(續(xù))(2) 環(huán)2.2.3 群環(huán)域的概念(續(xù))2.2.3 群環(huán)域的概念(續(xù))(3) 域2.3 對稱密碼算法：DE

27、S和AES 對稱密鑰體制的問題 (1) 在安全加密體制中，密鑰是需要經(jīng)常變更的，使得已丟失的密鑰只能泄露數(shù)量有限的信息。 (2) 密鑰的分發(fā)必須保證安全。一種方式就是對密鑰分解分發(fā)，如圖2.9。 (3) 密鑰數(shù)目的增長與交換信息的人數(shù)的平方成正比，在人數(shù)多的時候，可以考慮使用信任中心，如圖2.10 。2.3 對稱密碼算法：DES和AES(續(xù))圖2.9 密鑰的分塊分發(fā)圖2.10 加密信息分發(fā)中心2.3 對稱密碼算法：DES和AES(續(xù)) 2.3.1 DES算法描述 1974年，IBM 向國家標準局(NBS)提交了一個名為 LUCIFER的加密算法。NBS將其轉給了國家安全局 (NSA) 進行審定

28、，之后就得到了一個名為數(shù)據(jù)加密標準DES的算法。1977年，NBS 正式將其用于無限制級的政府通信。其間NBS和NSA可能存在某些誤會。NSA原本打算DES僅用于硬件執(zhí)行，但是NBS卻公布了過多的技術細節(jié)以致于人們可以根據(jù)其寫出DES加密軟件。如果NSA預料到后續(xù)的情況發(fā)展變化，他們或許不會同意公布DES。2.3.1 DES算法描述(續(xù)) DES是分組密碼，每個分組為64比特數(shù)據(jù)。 64比特明文通過加密最后成為64比特密文。 DES的密鑰通常寫為64比特，但每8比特有一位奇偶效驗位，可以忽略。因此，實際只有56比特。算法只使用不超過64位的標準算術操作和邏輯操作，所以在70年代僅使用硬件就可以

29、容易地實現(xiàn)算法。算法的重復特性非常適合專用芯片執(zhí)行。DES 的核心是一個被稱為Feistel系統(tǒng)的部件。 2.3.1 DES算法描述(續(xù))圖2.11 DES算法總體流程2.3.1 DES算法描述(續(xù))2.3.1 DES算法描述(續(xù))初始計算2.3.1 DES算法描述(續(xù))函數(shù) f(Ri-1, Ki)Ri-1擴張E(Ri-1)KiB1B2B3B4B5B6B7B8S1S2S3S4S5S6S7S8C1C2C3C4C5C6C7C8置換f(Ri-1, Ki)圖 2.12 f函數(shù)計算結構2.3.1 DES算法描述(續(xù))2.3.1 DES算法描述(續(xù))圖 2.13 DES的S盒2.3.1 DES算法描述(續(xù)

30、)2.3.1 DES算法描述(續(xù))密鑰變換2.3.1 DES算法描述(續(xù))2.3.2 DES的安全 DES存在關于密鑰長度、疊代次數(shù)、S-盒設計準則的問題。特別是S-盒以常量形式給出，但并未明確說明這些常量為何以這種形式出現(xiàn)。雖然IBM聲稱這些是經(jīng)過17年大量密碼分析得出的結果，但是人們還是十分擔心NSA的介入可能為算法安裝陷門以利于其解密。2.3.2 DES的安全(續(xù))(1) 弱密鑰與半弱密鑰圖2.14 4個DES弱密鑰即EKEK(x)=x圖2.15 6對DES半弱密鑰即EK1EK2(x)=x2.3.2 DES的安全(續(xù)) (2) 關于S盒 NSA曾公布了一些關于S盒選擇的信息： 1) 沒有

31、一個S盒的輸出是輸入的線性或仿射函數(shù)； 2) 改變S盒的一位輸入將至少引起2個輸出位的變化； 3) 固定輸入的某一位為0或1后，改變它周圍的位不應導致輸出的0或1的個數(shù)不成比例的變化。2.3.2 DES的安全(續(xù)) (3) 加密輪數(shù)與差分分析攻擊 差分分析通過微小差異的明文對，研究這些差異對所得密文的影響。如果同時更改輸入位的某些組合，輸出結果中的某些位也會以很高的概率、以特定方式變化。實踐表明，DES 在小于16輪的情況下，差分攻擊的效率將明顯快于搜索全部密鑰空間的強力攻擊。2.3.2 DES的安全(續(xù)) (4) 密鑰長度問題 密鑰長度偏小一直是DES的一個安全問題。 1) 1977年，Di

32、ffie和Hellman估計如果花費2千萬美元建造一臺機器，大約僅需一天就可以破譯DES。 2) 1993年，Wiener利用開關技術設計了更加有效的破譯DES設備。 3) 到1996年逐漸形成了3種破譯DES的基本方法。一種方法是利用分布計算；一種是設計專用攻擊芯片；折中的方法是使用可編程邏輯門陣列。2.3.2 DES的安全(續(xù)) 4) 分布計算方法破譯DES變得十分流行，特別是在Internet興起和壯大的情況下。1997年，RSA數(shù)據(jù)安全公司開展了破譯DES密鑰和其加密消息的競賽。僅僅5個月，Rocke Verser 就在搜索了25%的密鑰空間后發(fā)現(xiàn)密鑰。接下來，RSA數(shù)據(jù)安全公司又開展

33、了第二次競賽。結果用時39天搜索了密鑰空間的85%發(fā)現(xiàn)了對應密鑰。 5) 1998年，電子領域基金會(EFF)展開了一項名為DES破譯的計劃。計劃的基本思想是：一般使用的計算機對于完成破譯DES的任務來說不是最優(yōu)的。計劃使用的結構是，硬件用來判定排除大量不可能的密鑰并返回那些可能的密鑰；軟件則用來處理每一個可能的密鑰，判定這些密鑰是否確實為密碼系統(tǒng)使用的密鑰。結果是計劃使用1500個芯片平均在大約在4.5天可以完成對DES 的破譯。2.3.2 DES的安全(續(xù)) 6) 有傳言說根據(jù)預先處理的不同，NSA可以在3到5分鐘成功破譯DES。而在機器方面的開銷僅有5萬美元。 #上述結果說明對于90年代

34、晚期的計算技術而言，加密系統(tǒng)使用56比特的密鑰已經(jīng)顯得過短，不能提供強有力的安全保護。2.3.2 DES的安全(續(xù))(5) 增加安全性的DES變化2.3.2 DES的安全(續(xù))2.3.3 AES算法描述 1997年1月2日，國家標準與技術研究所(NIST)宣布，啟動設計新的對稱分組加密算法，作為新一代加密標準替代DES。新的加密標準將被命名為高級加密標準(AES)。不同于暗箱設計過程的DES，AES的設計方案于1997年9月12向全世界公開征集。2.3.3 AES算法描述(續(xù)) AES需要滿足下列要求： (1) 必須詳細和公開說明對稱加密算法的設計原理。 (2) 算法必須支持最小128比特的消

35、息分組，密鑰長度可以為128，192，256比特，而安全強度至少與三重DES相當?shù)蕬摳哂谌谼ES。 (3) 算法適合于在各種硬件設備上執(zhí)行。 (4) 如果算法被選種，不應該存在專利問題并可以在世界范圍內(nèi)使用。2.3.3 AES算法描述(續(xù)) 1998年8月20日，NIST公布了15個AES侯選算法，這些算法由遍布世界的密碼團體的成員提交。公眾對這15個算法的評論被當作初始評論(公眾的初始評論也被稱為第一輪)。第一輪于1999年4月15日截止。根據(jù)收到的分析和評論，NIST從15個算法中選出5個算法。2.3.3 AES算法描述(續(xù)) 5個參加決賽的AES侯選算法是：MARS(來自IBM，

36、在大型機上的實現(xiàn)進行了優(yōu)化，個人計算機上就不那么有效了)；RC6(來自RSA實驗室，它是RC5的延續(xù)，設計非常簡單，甚至可以靠記憶記住它)；Serpent(來自Ross Anderson，Eli Biham，和Lars Knudsen，該算法硬件實現(xiàn)很穩(wěn)定，以4位子處理器的并行操作為基礎)； Twofish(來自Bruce Schneier，John Kelsey，Doug Whiting，David Wagner，Chris Hall，和Niels Ferguson，開發(fā)者設計了一個替換表的設計方案，該方案依賴于加密密鑰而不是依賴固定的替換表) ；Rijndael(來自Joan Daemen

37、和Vincent Rijmen) 。這些參加決賽的算法在又一次更深入的評論期(第二輪)得到進一步的分析。2.3.3 AES算法描述(續(xù)) 在第二輪中，要征詢對候選算法的各方面的評論和分析，這些方面包括但不限于下面的內(nèi)容：密碼分析、知識產(chǎn)權、所有AES決賽侯選算法的剖析、綜合評價以及有關實現(xiàn)問題。在2000年5月15日第二輪公眾分析結束后，NIST匯集和研究了所有得到的信息，為最終選擇提供依據(jù)。2000年10月2日，NIST宣布它選中了Rijndael作為AES。NIST指出，之所以選擇Rijndael的原因是因為它是安全性、性能、效率、實現(xiàn)方便性和靈活性的最佳組合。2.3.3 AES算法描述(

38、續(xù))有限域GF(pn)的知識2.3.3 AES算法描述(續(xù))2.3.3 AES算法描述(續(xù))2.3.3 AES算法描述(續(xù))2.3.3 AES算法描述(續(xù))算法架構為使論述簡單，我們以使用128比特密鑰加密128比特消息為例說明，并且先對算法的整體架構予以說明。算法由10輪組成。每一輪使用一個由原始密鑰產(chǎn)生的密鑰。第0輪使用原始的128比特密鑰。每一輪都是128比特輸入128比特輸出。2.3.3 AES算法描述(續(xù)) 每一輪由四個基本步驟稱為層(layers)組成： (1)字節(jié)轉換(The Byte Sub Transformation)： 這是一個非線性層主要用于防止差分和線性分析攻擊。 (

39、2) 移動行變換(The Shift Row Transformation)：這是一個線性組合，可以導致多輪之間各個比特位間的擴散。 (3) 混合列變換(The Mix Column Transformation)： 這一層的目的與移動行變換相同。 (4) 輪密鑰加密變換(Add Round Key)：輪密鑰與上一層的結果進行異或操作。2.3.3 AES算法描述(續(xù))一輪的過程Byte Sub(BS)Shift Row(SR)Mix Column(MC)Add Round Key(ARK)Rijndael加密(1) 使用第0輪密鑰執(zhí)行ARK操作。(2) 依次使用第1輪到9輪密鑰按順序執(zhí)行BS，

40、 SR， MC，和ARK操作。(3) 使用第10輪密鑰按順序執(zhí)行BS， SR，和ARK操作。注意最后一輪忽略了混合列變換(MC)層。2.3.3 AES算法描述(續(xù))層2.3.3 AES算法描述(續(xù))(1) 字節(jié)轉換2.3.3 AES算法描述(續(xù))2.3.3 AES算法描述(續(xù))(2) 移動行變換2.3.3 AES算法描述(續(xù))(3) 混合列變換2.3.3 AES算法描述(續(xù))(4) 輪密鑰加密變換2.3.3 AES算法描述(續(xù))輪密鑰產(chǎn)生方法2.3.3 AES算法描述(續(xù)) 解密 字節(jié)轉換、移動行變換、混合列變換、輪密鑰加密變換都存在相應的逆變換： (1)字節(jié)轉換的逆變換可以通過查另一個表來完

41、成，我們稱之為逆字節(jié)轉換(IBS)。 (2) 移動行變換的逆變換可以通過字節(jié)右移來實現(xiàn)，我們稱之為逆移動行變換(ISR) 。 (3) 逆混合列變換 (IMC) 通過乘上另一個矩陣實現(xiàn)。 (4) 輪密鑰加密變換實際上是自身的逆。2.3.3 AES算法描述(續(xù))S-盒原理2.3.3 AES算法描述(續(xù))2.3.3 AES算法描述(續(xù))解密變換2.3.3 AES算法描述(續(xù))Rijndael 解密(1) 使用第10輪密鑰執(zhí)行ARK操作。(2) 依次使用第9輪到1輪密鑰按順序執(zhí)行IBS，ISR， IMC，和IARK操作。(3) 使用第0輪密鑰按順序執(zhí)行IBS， ISR，和ARK操作。# 為了保持結構的

42、一致性，在最后一輪加密中忽略了 MC操作。2.3.4 AES的安全與執(zhí)行 設計思考 (1) 由于加密和解密過程不一致，相比DES(全1密鑰，加密兩次恢復為本身)，相信AES不存在任何弱密鑰。 (2) 不同于Feistel系統(tǒng)，AES對輸入所有比特的處理相同，這使得輸入的擴展速度很快。實踐表明兩輪計算就能得到充分擴展，也就是說，所有的128比特輸出完全依賴于所有128比特輸入。 (3) AES的S-盒的建立有明晰而簡單的代數(shù)意義，這樣可以避免任何建立在算法上的門陷，較好避免存在于DES的S-盒上的神秘色彩。AES的S-盒具有良好的非線性特性，它可以很好地用來阻止差分和線性分析。2.3.4 AES

43、的安全與執(zhí)行(續(xù)) (4) 移動行這一層可以很好地阻止新發(fā)現(xiàn)的截斷攻擊和平方攻擊。 (5) 混合列可以達到字節(jié)擴散的目的。這步1個輸入字節(jié)的改變導致所有4個輸出字節(jié)改變。 (6) 輪密鑰產(chǎn)生方法使用了密鑰位的非線性組合，因為它使用了S-盒，這種非線性組合用來對付當解密者知道了部分密鑰并以此推測余下部分的攻擊。循環(huán)常量(10)(i-4)/4是用來消除在循環(huán)過程中生成每個循環(huán)差別的對稱性。2.3.4 AES的安全與執(zhí)行(續(xù)) (7) 輪次之所以選擇10，是因為在6輪情況下存在比強力搜索攻擊更好的算法。公布的密碼分析結果在7輪以上還沒有比強力搜索攻擊更好的辦法。多出4輪能夠讓人更有安全感。當然，輪次

44、還可以根據(jù)需要增加。2.3.4 AES的安全與執(zhí)行(續(xù)) 執(zhí)行思考 我們已經(jīng)看到Rijndael內(nèi)部的層是非常簡單的，它在很小的代數(shù)空間上即可完成。因此，可以高效完成這些層。從前面對Rijndael的內(nèi)部層描述可以看到，僅有SB/ISB和MC/IMC值得考慮它們的快速實現(xiàn)問題。 (1) 對于SB/ISB，我們建議使用S-盒查表方法：可以一次建立一個有28=256個字節(jié)的小表，長期使用(就是說，這個表可以“固化”在硬件或者是軟件中實現(xiàn))?！安楸矸ā辈粌H非常有效，還能阻止定時分析攻擊，這種攻擊根據(jù)不同數(shù)據(jù)的運算時間差異，來推斷運算是在比特0還是在比特1上運行。2.3.4 AES的安全與執(zhí)行(續(xù))

45、(2) 在MC操作中，有限域GF(28)上的兩個元的乘法操作也可以用“查表法”來實現(xiàn)：z = xy(有限域乘法)，這里x01，10，11和yGF(28)。我們進一步注意到字節(jié)01為有限域乘法單位元，也就是，01y=y。因而無論用軟件還是硬件執(zhí)行“查表法”時只需要存儲2256=512項，這個表是非常小的。這樣實現(xiàn)不僅速度很快，而且還能夠減少定時分析攻擊的危險。 (3) 執(zhí)行IMC操作就不像執(zhí)行MC操作那么快。這是因為IMC操作的44矩陣比MC操作的復雜得多，一般執(zhí)行IMC操作比MC操作需要多花費30%的處理時間。然而，幸運的是在一些應用中解密是不需要的。2.3.5 對稱密碼的應用 (1) 加密模

46、式 通常大多數(shù)消息的長度大于分組密碼的消息分組長度，長的消息被分成一系列連續(xù)排列的消息分組，密碼一次處理一個分組。在分組密碼的上層，不同的加密模式被開發(fā)出來，這些加密模式可以為整體消息加密提供一些希望得到的性質(zhì)。如：分組密碼的不確定性(隨機性)，將明文消息添加到任意長度(使得密文長度不必與相應的明文長度相關)，錯誤傳播控制，流密碼的密鑰流生成。等等。2.3.5 對稱密碼的應用(續(xù))密碼分組鏈接(CBC)模式C0P1EKC1P2EKC2圖2.16 CBC模式加密2.3.5 對稱密碼的應用(續(xù))2.3.5 對稱密碼的應用(續(xù)) (2) 修改發(fā)現(xiàn)碼(MDC)實例-使用DES的MDC-2 在分組密碼基

47、礎上建立Hash函數(shù)的主要動機是：如果系統(tǒng)已經(jīng)擁有了非常有效的分組密碼，那么以分組密碼作為實現(xiàn)Hash函數(shù)的主要部件，將既可以提供Hash函數(shù)的功能，又能使額外開銷最小。2.3.5 對稱密碼的應用(續(xù))2.3.5 對稱密碼的應用(續(xù))2.3.5 對稱密碼的應用(續(xù))Eg(Hi-1)Eg(Hi-1)MiCLiCRiCLiCRiCLiCRiCLiCRiHiHi圖2.17 MDC-2原理圖2.3.5 對稱密碼的應用(續(xù)) (3) 基于CBC的消息認證碼(MAC) 定義 26 消息認證碼(MAC)算法是帶有密鑰k的函數(shù)族hk，其具有如下性質(zhì)： 1) 易于計算：對于任何已知函數(shù)hk，給定值k和輸入x，值

48、hk(x)容易計算出來。這個值被稱做MAC-值或MAC。 2) 壓縮：函數(shù)hk可以將任意有限比特長度的輸入x影射為固定n比特長度的位串。進一步，給出函數(shù)族h的算法描述，對于任何一個固定符合要求的密鑰值k(攻擊者不知其值)，需要滿足如下性質(zhì)： 3) 計算抵抗：給定0個或多個消息-MAC值對(xi，hk(xi)，找到任意消息-MAC值對(x，hk(x)滿足xxi在計算上不可能(當然也包括某些i滿足hk(x)=hk(xi)的可能性) 。2.3.5 對稱密碼的應用(續(xù))2.3.5 對稱密碼的應用(續(xù))M10EkH1M2EkH2Ht-1MtEkHtEkDkHt可選圖2.18 基于CBC的MAC原理圖2.4 公鑰密碼體制：RSA和ElGamal體制 2.4.1 RSA體制 Diffie和Hellman提出了建立公鑰密碼系統(tǒng)的可能性。但是，他們并沒有提出公鑰密碼算法。接下來的幾年，一些公鑰密碼算法相繼被提出。其中最為成功的依賴大整數(shù)分解困難性的公鑰密碼算法，1977年由Rivest，Shamir，和Adleman提出。這也就是熟知的RSA算法。雖然經(jīng)過長期的密碼分析并不能證明也不能否定RSA的安全，但是這也無疑