第二章：密碼學基分析課件

《第二章：密碼學基分析課件》由會員分享，可在線閱讀，更多相關《第二章：密碼學基分析課件（49頁珍藏版）》請在裝配圖網上搜索。

1、第二章：第二章：密碼學基礎2.1、密碼學分類2.2、香濃理論2.3、認證系統的信息理論2.4、復雜度理論主講：鐘德林、薛占碩、黃良富、黃順團12.1、密碼學的基本概念密碼學密碼學(Cryptology)：研究信息系統安全保密的科學。它包含兩個分支：l密碼編碼學密碼編碼學(Cryptography)，對信息進行編碼實現隱蔽信息的一門學問。l密碼分析學密碼分析學(Cryptanalytics)，研究分析破譯密碼的學問。2密碼體制的分類密碼體制有2大類：l單鑰體制單鑰體制(One-key system)：加密密鑰和解密密鑰相同。l雙鑰體制雙鑰體制(Two key system)：加密密鑰和解密密鑰不

2、同。3現代密碼學研究的內容現代密碼學研究的相關內容保密性認證性不可否認完整性對稱加密單向函數公鑰加密Hash函數消息認證碼數字簽名身份鑒別隨機數生成器Hash函數4(1)單鑰體制（對稱密碼體制）l單鑰體制主要研究問題：密鑰產生(Key generation)，密鑰管理(Key management)。l分類：流密碼(Stream cipher)分組密碼(Block cipher)單鑰體制不僅可用于數據加密，也可用于消息的認證。5(2)雙鑰體制（非對稱密碼體制）雙鑰體制或公鑰體制(Public key system)(Diffie和Hellman,1976)每個用戶都有一對選定的密鑰(公鑰k k

3、1；私鑰k k2)，公開的密鑰k k1可以像電話號碼一樣進行注冊公布。6雙鑰體制的主要特點l加密和解密能力分開l可以實現多個用戶加密的消息只能由一個用戶解讀（用于公共網絡中實現保密通信）l只能由一個用戶加密消息而使多個用戶可以解讀（可用于認證系統中對消息進行數字簽字）l無需事先分配密鑰7密碼分析l截收者在不知道解密密鑰及通信者所采用的加密體制的細節條件下，對密文進行分析，試圖獲取機密信息。研究分析解密規律的科學稱作密碼分析學。l密碼分析在外交、軍事、公安、商業等方面都具有重要作用，也是研究歷史、考古、古語言學和古樂理論的重要手段之一。8密碼分析l密碼設計和密碼分析是共生的、又是互逆的，兩者密切

4、有關但追求的目標相反，兩者解決問題的途徑有很大差別。l密碼設計是利用數學來構造密碼l密碼分析除了依靠數學、工程背景、語言學等知識外，還要靠經驗、統計、測試、眼力、直覺判斷能力。有時還靠點運氣。9信息的安全性評價 無條件安全性和有條件安全性的區別 無條件安全性與攻擊者的計算能力和時間無關，有條件安全性是根據破解密碼系統所需要的計算量來評價安全性的。10保密體制模型l 明文(消息)(Plaintext)：被隱蔽消息l密文(Ciphertext)或密報(Cryptogram)：明文經密碼變換成的一種隱蔽形式l加密(Encryption)：將明文變換為密文的過程l解密(Decryption)：加密的逆

5、過程，即由密文恢復出原明文的過程l加密員或密碼員(Cryptographer)：對明文進行加密操作的人員11保密體制模型l加密算法(Encryption algorithm)：密碼員對明文進行加密時所采用的一組規則。l接收者(Receiver)：傳送消息的預定對象。l解密算法：接收者對密文進行解密時所采用的一組規則。l密鑰(Key)：控制加密和解密算法操作的數據處理，分別稱作加密密鑰和解密密鑰。l截收者(Eavesdropper)：在信息傳輸和處理系統中的非受權者，通過搭線竊聽、電磁竊聽、聲音竊聽等來竊取機密信息。12保密體制模型l密碼分析(Cryptanalysis)：截收者試圖通過分析從截

6、獲的密文推斷出原來的明文或密鑰。l密碼分析員(Cryptanalyst)：從事密碼分析的人。l被動攻擊(Passive attack)：對一個保密系統采取截獲密文進行分析的攻擊。l主動攻擊(Active attack)：非法入侵者(Tamper)、攻擊者(Attcker)或黑客(Hacker)主動向系統竄擾，采用刪除、增添、重放、偽造等竄改手段向系統注入假消息，達到利已害人的目的。13保密系統模型信源Mm加密器)(1mEck解密器)(2cDmk接收者m非法接入者搭線信道（主動攻擊）C 搭線信道（被動攻擊）密碼分析員m密鑰源K1k1密鑰源K2k2密鑰信道14保密系統應當滿足的要求l系統即使達不到

7、理論上是不可破的，即prm=m=0，也應當為實際上不可破的。就是說，從截獲的密文或某些已知明文密文對，要決定密鑰或任意明文在計算上是不可行的。l系統的保密性不依賴于對加密體制或算法的保密，而依賴于密鑰。這是著名的Kerckhoff原則。l加密和解密算法適用于所有密鑰空間中的元素。l系統便于實現和使用。15 密碼可能經受的攻擊攻擊類型攻擊者擁有的資源唯密文攻擊n加密算法n截獲的部分密文已知明文攻擊n加密算法，n截獲的部分密文和相應的明文選擇明文攻擊n加密算法n加密黑盒子，可加密任意明文得到相應的密文選擇密文攻擊n加密算法n解密黑盒子，可解密任意密文得到相應的明文16認證與認證系統l認證系統(Au

8、thentication system)：防止消息被竄改、刪除、重放和偽造的一種有效方法,使發送的消息具有被驗證的能力，使接收者或第三者能夠識別和確認消息的真偽。實現這類功能的密碼系統稱作認證系統。l保密性：保密性是使截獲者在不知密鑰條件下不能解讀密文的內容。l認證性：使任何不知密鑰的人不能構造一個密報，使意定的接收者解密成一個可理解的消息(合法的消息)。17認證與認證系統目前的認證系統分類：一、無仲裁者的認證系統模型；二、有仲裁者的認證系統模型。認證系統模型的目標：能使發送者通過一個公開無干擾信道將消息發送給接收者，接收者能夠確認消息是否來自發送者以及消息是否被敵手篡改。18安全認證系統應滿

9、足下述條件l意定的接收者能夠檢驗和證實消息的合法性和真實性。l消息的發送者對所發送的消息不能抵賴。l除了合法消息發送者外，其它人不能偽造合法的消息。而且在已知合法密文c和相應消息m下，要確定加密密鑰或系統地偽造合法密文在計算上是不可行的。l必要時可由第三者作出仲裁。192.2、香農理論 香農(1916,2001),生于密執安州的加洛德。1940年獲得麻省理工學院數學博士學位和電子工程碩士學位。1941年他加入了貝爾實驗室數學部，在此工作了15年。20熵及其性質l例3 設電腦彩票由8個10進制數組成，在開獎之前，108個可能號碼成為特等獎的概率相同,都是10-8.一旦開獎,我們就知道了特等獎的8

10、個具體號碼,因而就獲得了8個十進制數的信息。l 我們獲得的信息量與開獎前每個可能號碼成為特等獎的概率10-8有何關系?l 顯然,有 8=-log10 10-8l 信息量的定量刻劃:21熵的數學定義定義1：設p(xi)是一個實驗中事件xi發生的概率,則稱I(xi)=log2p(xi)為事件xi包含的自信息量。定義2(隨機事件的熵)：設一個實驗X有x1,x2,.,xn共n個可能的結果，則稱H(x)=為實驗X的熵(Entropy),其中約定 0log0=0。11()()()log()nniiiiiiP x I xP xP x 22熵的數學定義引理3.1(Jensen不等式)設f是區間I上的一個連續的

11、嚴格凸函數，并且ai0,a1+a2+.+an=1,xiI,1in,則有且上式成立的充要條件是 x1=x2=.=xn11()()nniiiiiia f xfa x23熵的數學定義推論1：在區間x0時是嚴格凸的，因而當實數P1,P2,.,Pn滿足Pi0且P1+P2+.+Pn=1時有且上式成立的充要條件是 P1=P2=.=Pn()log(1)bf xx b1loglognibibiPpn24熵的數學定義定義3(聯合熵)：實驗X與實驗Y的可能結果分別為 和 定義X和Y的聯合熵為因此,實驗X與實驗Y的聯合熵(Joint Entropy)就是事件(xi,yj)的自信息量的數學期望，它反映了聯合分布P(x,

12、y)包含的信息量。12,.,nx xx12,.,ny yy11(|)(,)(|)nmijijijH X YP x y I xy11(,)log(|)nmijijijP x yP xy 25熵的數學定義定義5(條件熵)：實驗X與實驗Y的可能結果分別為 和 定義X與Y的條件熵：(1)稱 為在實驗Y的結果為 yj的條件下,事件xi的條件自信息量。(2)稱 為在實驗Y的結果為yj的條件下,實驗X的條件熵。12,.,nx xx12,.,ny yy(|)lo g(|)ijijIxyPxy11(|)()(|)()log(|)nnH Xyp xI xyp xp xyjiijiijii 26熵的數學定義(3)稱

13、為在實驗X關于實驗Y的條件熵。反映了Y的結果是yj條件下,實驗X包含的信息量。反應了Y的結果已知條件下,實驗X平均包含的信息量。1111(|)(,)(|)(,)log(|)nmijijijnmijijijH X Yp xyI xyp xyp xy (|)HXyj(|)H X Y27聯合熵與各自的熵的關系定理3.2：且等號成立，充要條件是X與Y獨立。直觀含義直觀含義:兩個實驗提供的信息總量一定不超過這兩個實驗分別提供的信息量之和;當且僅當兩個實驗獨立時,二者才相等。(,)()()H X YH XH Y 28聯合熵與條件熵的關系定理3.3直觀含義直觀含義:兩個實驗提供的信息總量等于第一個信息提供的

14、信息量加上在第一個實驗的結果已知條件下,第二個實驗提供的信息量.(,)()(|)()(|)H X YH YH X YH XH Y X 29聯合熵與熵的關系定理3.2指出:定理3.3指出：故有推論3.1 且等號成立 X與Y獨立(,)()()H X YH XH Y (,)()(|)H X YH YH X Y ()(|)()()HYH X YHYH X (|)()H X YH X(|)()H X YH X 30熵的數學定義定義3.3(平均互信息):稱為實驗X與實驗Y的平均信息。結論：直觀地含義：將X包含的未知信息量減去在實驗Y的結果已知條件下，X仍具有的未知信息量。就是實驗Y提供的X的信息了。(;)

15、()()(,)I XYHXHYHXY (;)()(|)()(|)I X YH XH X YH YH Y X 31完善保密性的熵的定義l一個密碼體制稱為完善保密的，如果對于任意的xP和yC,有Pr(x|y)=Pr(x)。l一個保密系統（P，C，K，E，D）稱為完善的無條件的保密系統，如果H(P)=H(P|C),其中，P為明文集合，C為密文集合，K為密鑰集合，E為加密算法,D為解密算法.32完善保密性的熵的定義l完善保密系統存在的必要條件是H(P)H(K)。l可見，要構造一個完善保密系統，其密鑰量的對數（密鑰空間為均勻分布的條件下）必須不小于明文集的熵。從熵的基本性質可推知，保密系統的密鑰量越小，

16、其密文中含有的關于明文的信息量就越大。33偽密鑰定義：若H(K|C)=0，則意味著密鑰已找到密碼體制被攻破。若H(K|C)0，則意味著，給一段密文y，則存在兩個或以上的密鑰可被用來產生同一個密文y。一般來說，Eve能排除某些密鑰，但仍存在許多可能的密鑰，這其中只有一個密鑰是正確的。我們稱那些可能的但不正確的密鑰稱為偽密鑰。34偽密鑰定理2.11：假設(P,C,K,E,D)是一個密碼體制，|C|=|P|并且密鑰是等概率選取的，設RL表示 明文的自然語言的冗余度，則給定一個充分長（長n）的密文串，偽密鑰的期望滿足1|LnnRKsP 35偽密鑰密碼體制的唯一解距離，就是使得偽密鑰的期望數等于0的n的

17、值，記為：即在給定充足的時間下，密碼分析者能唯一計算出密鑰所需密文的平均量。202log|log|LKnRP 362.3、認證系統的信息理論認證理論的主要研究目標：一是推導攻擊者成功欺騙的概率下界；二是構造攻擊者欺騙成功的概率盡可能小的認證碼。認證碼是保證消息完整性、認證性的重要工具，也就是保證消息沒有被篡改。37認證矩陣的定義認證矩陣是一個 矩陣，它的行由密鑰來標記，列由信源狀態來標記，對每一個kK和 sS，該矩陣的第 k行第 s列的元素是 。|*|ks()se s38認證碼攻擊中的兩個量認證碼中攻擊者欺騙成功的概率Pd0和Pd1來度量。為了構造一個使欺騙率盡可能小的認證碼，通常期望它能達到

18、以下幾個目標。l（1）欺騙概率Pd0和Pd1必須足夠小，以便獲得期望的安全水平。l（2）信源狀態的數目必須足夠大，以便能通過在一個信源狀態后附加一個標簽來傳送期望的信息。l（3）密鑰空間盡可能小，因為密鑰的值需要在一個安全的信道上傳送。39相關定理定理 2.16：設 是一個驗證碼，則(1)(2)證明略。)()|(log02KHMKHpd,KAS)|()|(log221MKHMKHpd40完善認證系統定理 2.17：完善認證系統存在。定義 2.19：完善認證是使 成立的認證系統。顯然，每一個具有 的系統是完善認證系統。.)()|(2KHMKHdp)()|(KHMKH412.4、復雜性理論本節主要

19、內容l算法復雜度定義及分類lP問題和NP問題l密碼算法的計算安全性主要知識點l算法的復雜度定義及分類l密碼算法的計算復雜度42算法復雜度的定義l算法是指完成一個任務所需的具體步驟方法。l時間（計算）復雜性：考慮算法的主要操作步驟，計算執行中所需的總操作次數。l空間復雜性：執行過程中所需存儲器的單元數目。l數據復雜性：信息資源。43算法復雜度的定義 不同的編程語言，不同的編譯器導致執行一次操作的時間各不相同，為了方便不同算法比較，通常假定所有計算機執行相同的一次基本操作所需時間相同，而把算法中基本操作執行的最大次數作為執行時間。運行時間=基本操作數量機器速度44算法復雜度的定義定義：假設一個算法

20、的計算復雜度為O(nt)，其中t為常數，n為輸入問題的長度，則稱這算法的復雜度是多項式的。具有多項式時間復雜度的算法為多項式時間算法。定義：非多項式時間算法：算法的計算復雜性寫不成O(P(n)形式，其中P(n)表示n的多項式函數。45P問題和NP問題l定義(P問題)如果一個判定問題存在解它的多項式時間的算法，則稱該問題屬于P類.l定義(NP問題)如果一個判定問題不存在解它的多項式時間的算法，且對于一個解答可以在多項式時間驗證其是否正確，則稱該問題屬于NP類.46密碼算法的計算安全性 當問題輸入長度足夠大，分析密碼體制的算法的復雜度較大，可能的計算能力下，在保密的期間內可以保證算法不被攻破，這就

21、是密碼體制的計算安全性思想。注：分析方法是無窮無盡的，類似于解決問題的算法，目前不存在非多項式時間的分析方法，將來可能存在，即算法將來可能不堪一擊.如差分分析出現。47密碼算法的計算安全性密碼系統設計：合法用戶易（多項式）攻擊者難（非多項式）注：計算模型-圖靈機 量子計算機出現導致分解因子問題容易，從而RSA等密碼系統不再安全，緣由是計算模型不同。48總結：l密碼學基礎內容廣泛，也是學習現代密碼學教程的核心。l 包括我學們日后學習到的古典密碼體制、分組密碼、序列密碼、Hash函數和消息認證、公鑰密碼、數字簽名、密鑰管理等都屬于密碼學的基礎內容。l 本章節主要講述密碼學的組成結構及相關理論為同學們日后學習相關加密、解密算法做鋪墊。49