第二章：密碼學(xué)基

第二章：密碼學(xué)基礎(chǔ)2.1、密碼學(xué)分類2.2、香濃理論2.3、認(rèn)證系統(tǒng)的信息理論2.4、復(fù)雜度理論主講：鐘德林、薛占碩、黃良富、黃順團(tuán)12.1、密碼學(xué)的基本概念密碼學(xué)(Cryptology)：研究信息系統(tǒng)安全保密的科學(xué)。它包含兩個分支：密碼編碼學(xué)(Cryptography)，對信息進(jìn)行編碼實(shí)現(xiàn)隱蔽信息的一門學(xué)問。密碼分析學(xué)(Cryptanalytics)，研究分析破譯密碼的學(xué)問。2密碼體制的分類密碼體制有2大類：單鑰體制(One-keysystem)：加密密鑰和解密密鑰相同。雙鑰體制(Twokeysystem)：加密密鑰和解密密鑰不同。3現(xiàn)代密碼學(xué)研究的內(nèi)容現(xiàn)代密碼學(xué)研究的相關(guān)內(nèi)容保密性認(rèn)證性不可否認(rèn)完整性對稱加密單向函數(shù)公鑰加密Hash函數(shù)消息認(rèn)證碼數(shù)字簽名身份鑒別隨機(jī)數(shù)生成器Hash函數(shù)4(1)單鑰體制（對稱密碼體制）單鑰體制主要研究問題：密鑰產(chǎn)生(Keygeneration)，密鑰管理(Keymanagement)。分類：流密碼(Streamcipher)分組密碼(Blockcipher)單鑰體制不僅可用于數(shù)據(jù)加密，也可用于消息的認(rèn)證。5(2)雙鑰體制（非對稱密碼體制）雙鑰體制或公鑰體制(Publickeysystem)(Diffie和Hellman,1976)

每個用戶都有一對選定的密鑰(公鑰k1；私鑰k2)，公開的密鑰k1可以像電話號碼一樣進(jìn)行注冊公布。6雙鑰體制的主要特點(diǎn)加密和解密能力分開可以實(shí)現(xiàn)多個用戶加密的消息只能由一個用戶解讀（用于公共網(wǎng)絡(luò)中實(shí)現(xiàn)保密通信）只能由一個用戶加密消息而使多個用戶可以解讀（可用于認(rèn)證系統(tǒng)中對消息進(jìn)行數(shù)字簽字）無需事先分配密鑰7密碼分析截收者在不知道解密密鑰及通信者所采用的加密體制的細(xì)節(jié)條件下，對密文進(jìn)行分析，試圖獲取機(jī)密信息。研究分析解密規(guī)律的科學(xué)稱作密碼分析學(xué)。密碼分析在外交、軍事、公安、商業(yè)等方面都具有重要作用，也是研究歷史、考古、古語言學(xué)和古樂理論的重要手段之一。8密碼分析密碼設(shè)計和密碼分析是共生的、又是互逆的，兩者密切有關(guān)但追求的目標(biāo)相反，兩者解決問題的途徑有很大差別。密碼設(shè)計是利用數(shù)學(xué)來構(gòu)造密碼密碼分析除了依靠數(shù)學(xué)、工程背景、語言學(xué)等知識外，還要靠經(jīng)驗(yàn)、統(tǒng)計、測試、眼力、直覺判斷能力。有時還靠點(diǎn)運(yùn)氣。9信息的安全性評價

無條件安全性和有條件安全性的區(qū)別

無條件安全性與攻擊者的計算能力和時間無關(guān)，有條件安全性是根據(jù)破解密碼系統(tǒng)所需要的計算量來評價安全性的。10保密體制模型

明文(消息)(Plaintext)：被隱蔽消息密文(Ciphertext)或密報(Cryptogram)：明文經(jīng)密碼變換成的一種隱蔽形式加密(Encryption)：將明文變換為密文的過程解密(Decryption)：加密的逆過程，即由密文恢復(fù)出原明文的過程加密員或密碼員(Cryptographer)：對明文進(jìn)行加密操作的人員11保密體制模型加密算法(Encryptionalgorithm)：密碼員對明文進(jìn)行加密時所采用的一組規(guī)則。接收者(Receiver)：傳送消息的預(yù)定對象。解密算法：接收者對密文進(jìn)行解密時所采用的一組規(guī)則。密鑰(Key)：控制加密和解密算法操作的數(shù)據(jù)處理，分別稱作加密密鑰和解密密鑰。截收者(Eavesdropper)：在信息傳輸和處理系統(tǒng)中的非受權(quán)者，通過搭線竊聽、電磁竊聽、聲音竊聽等來竊取機(jī)密信息。12保密體制模型密碼分析(Cryptanalysis)：截收者試圖通過分析從截獲的密文推斷出原來的明文或密鑰。密碼分析員(Cryptanalyst)：從事密碼分析的人。被動攻擊(Passiveattack)：對一個保密系統(tǒng)采取截獲密文進(jìn)行分析的攻擊。主動攻擊(Activeattack)：非法入侵者(Tamper)、攻擊者(Attcker)或黑客(Hacker)主動向系統(tǒng)竄擾，采用刪除、增添、重放、偽造等竄改手段向系統(tǒng)注入假消息，達(dá)到利已害人的目的。13保密系統(tǒng)模型信源Mm加密器解密器接收者m非法接入者搭線信道（主動攻擊）C’搭線信道（被動攻擊）密碼分析員m‘密鑰源K1k1密鑰源K2k2密鑰信道14保密系統(tǒng)應(yīng)當(dāng)滿足的要求系統(tǒng)即使達(dá)不到理論上是不可破的，即pr{m’=m}=0，也應(yīng)當(dāng)為實(shí)際上不可破的。就是說，從截獲的密文或某些已知明文密文對，要決定密鑰或任意明文在計算上是不可行的。系統(tǒng)的保密性不依賴于對加密體制或算法的保密，而依賴于密鑰。這是著名的Kerckhoff原則。加密和解密算法適用于所有密鑰空間中的元素。系統(tǒng)便于實(shí)現(xiàn)和使用。15密碼可能經(jīng)受的攻擊攻擊類型攻擊者擁有的資源唯密文攻擊加密算法截獲的部分密文已知明文攻擊加密算法，截獲的部分密文和相應(yīng)的明文選擇明文攻擊加密算法加密黑盒子，可加密任意明文得到相應(yīng)的密文選擇密文攻擊加密算法解密黑盒子，可解密任意密文得到相應(yīng)的明文16認(rèn)證與認(rèn)證系統(tǒng)認(rèn)證系統(tǒng)(Authenticationsystem)：防止消息被竄改、刪除、重放和偽造的一種有效方法,使發(fā)送的消息具有被驗(yàn)證的能力，使接收者或第三者能夠識別和確認(rèn)消息的真?zhèn)?。?shí)現(xiàn)這類功能的密碼系統(tǒng)稱作認(rèn)證系統(tǒng)。保密性：保密性是使截獲者在不知密鑰條件下不能解讀密文的內(nèi)容。認(rèn)證性：使任何不知密鑰的人不能構(gòu)造一個密報，使意定的接收者解密成一個可理解的消息(合法的消息)。17認(rèn)證與認(rèn)證系統(tǒng)目前的認(rèn)證系統(tǒng)分類：一、無仲裁者的認(rèn)證系統(tǒng)模型；二、有仲裁者的認(rèn)證系統(tǒng)模型。認(rèn)證系統(tǒng)模型的目標(biāo)：

能使發(fā)送者通過一個公開無干擾信道將消息發(fā)送給接收者，接收者能夠確認(rèn)消息是否來自發(fā)送者以及消息是否被敵手篡改。18安全認(rèn)證系統(tǒng)應(yīng)滿足下述條件意定的接收者能夠檢驗(yàn)和證實(shí)消息的合法性和真實(shí)性。消息的發(fā)送者對所發(fā)送的消息不能抵賴。除了合法消息發(fā)送者外，其它人不能偽造合法的消息。而且在已知合法密文c和相應(yīng)消息m下，要確定加密密鑰或系統(tǒng)地偽造合法密文在計算上是不可行的。必要時可由第三者作出仲裁。192.2、香農(nóng)理論

香農(nóng)(1916,2001),生于密執(zhí)安州的加洛德。1940年獲得麻省理工學(xué)院數(shù)學(xué)博士學(xué)位和電子工程碩士學(xué)位。1941年他加入了貝爾實(shí)驗(yàn)室數(shù)學(xué)部，在此工作了15年。20熵及其性質(zhì)例3設(shè)電腦彩票由8個10進(jìn)制數(shù)組成，在開獎之前，108個可能號碼成為特等獎的概率相同,都是10-8.一旦開獎,我們就知道了特等獎的8個具體號碼,因而就獲得了8個十進(jìn)制數(shù)的信息。

我們獲得的信息量與開獎前每個可能號碼成為特等獎的概率10-8有何關(guān)系?顯然,有8=-log1010-8

信息量的定量刻劃:21熵的數(shù)學(xué)定義定義1：設(shè)p(xi)

是一個實(shí)驗(yàn)中事件xi發(fā)生的概率,則稱I(xi)=log2p(xi)

為事件xi包含的自信息量。定義2(隨機(jī)事件的熵)：設(shè)一個實(shí)驗(yàn)X有x1,x2,...,xn共n個可能的結(jié)果，則稱H(x)=為實(shí)驗(yàn)X的熵(Entropy),其中約定0log0=0。22熵的數(shù)學(xué)定義引理3.1(Jensen不等式)設(shè)f是區(qū)間I上的一個連續(xù)的嚴(yán)格凸函數(shù)，并且ai>0,a1+a2+...+an=1,xi∈I,1≤i≤n,則有且上式成立的充要條件是x1=x2=...=xn23熵的數(shù)學(xué)定義推論1：在區(qū)間x>0時是嚴(yán)格凸的，因而當(dāng)實(shí)數(shù)P1,P2,...,Pn滿足Pi≥0且P1+P2+...+Pn=1時有且上式成立的充要條件是P1=P2=...=Pn24熵的數(shù)學(xué)定義定義3(聯(lián)合熵)：實(shí)驗(yàn)X與實(shí)驗(yàn)Y的可能結(jié)果分別為

和定義X和Y的聯(lián)合熵為因此,實(shí)驗(yàn)X與實(shí)驗(yàn)Y的聯(lián)合熵(JointEntropy)就是事件(xi,yj)的自信息量的數(shù)學(xué)期望，它反映了聯(lián)合分布P(x,y

)包含的信息量。

25熵的數(shù)學(xué)定義定義5(條件熵)：實(shí)驗(yàn)X與實(shí)驗(yàn)Y的可能結(jié)果分別為

和

定義X與Y的條件熵：(1)稱為在實(shí)驗(yàn)Y的結(jié)果為yj的條件下,事件xi的條件自信息量。(2)稱為在實(shí)驗(yàn)Y的結(jié)果為yj的條件下,實(shí)驗(yàn)X的條件熵。26熵的數(shù)學(xué)定義(3)稱為在實(shí)驗(yàn)X關(guān)于實(shí)驗(yàn)Y的條件熵。

反映了Y的結(jié)果是yj條件下,實(shí)驗(yàn)X包含的信息量。

反應(yīng)了Y的結(jié)果已知條件下,實(shí)驗(yàn)X平均包含的信息量。

27聯(lián)合熵與各自的熵的關(guān)系定理3.2：且等號成立，充要條件是X與Y獨(dú)立。直觀含義:

兩個實(shí)驗(yàn)提供的信息總量一定不超過這兩個實(shí)驗(yàn)分別提供的信息量之和;當(dāng)且僅當(dāng)兩個實(shí)驗(yàn)獨(dú)立時,二者才相等。28聯(lián)合熵與條件熵的關(guān)系定理3.3直觀含義:兩個實(shí)驗(yàn)提供的信息總量等于第一個信息提供的信息量加上在第一個實(shí)驗(yàn)的結(jié)果已知條件下,第二個實(shí)驗(yàn)提供的信息量.29聯(lián)合熵與熵的關(guān)系定理3.2指出:

定理3.3指出：故有推論3.1且等號成立X與Y獨(dú)立

30熵的數(shù)學(xué)定義定義3.3(平均互信息):稱為實(shí)驗(yàn)X與實(shí)驗(yàn)Y的平均信息。結(jié)論：直觀地含義：將X包含的未知信息量減去在實(shí)驗(yàn)Y的結(jié)果已知條件下，X仍具有的未知信息量。

就是實(shí)驗(yàn)Y提供的X的信息了。31完善保密性的熵的定義一個密碼體制稱為完善保密的，如果對于任意的x∈P和y∈C,有Pr(x|y)=Pr(x)。一個保密系統(tǒng)（P，C，K，E，D）稱為完善的無條件的保密系統(tǒng)，如果H(P)=H(P|C),其中，P為明文集合，C為密文集合，K為密鑰集合，E為加密算法,D為解密算法.32完善保密性的熵的定義完善保密系統(tǒng)存在的必要條件是H(P)≤H(K)?？梢姡獦?gòu)造一個完善保密系統(tǒng)，其密鑰量的對數(shù)（密鑰空間為均勻分布的條件下）必須不小于明文集的熵。

從熵的基本性質(zhì)可推知，保密系統(tǒng)的密鑰量越小，其密文中含有的關(guān)于明文的信息量就越大。33偽密鑰定義：

若H(K|C)=0，則意味著密鑰已找到密碼體制被攻破。若H(K|C)>0，則意味著，給一段密文y，則存在兩個或以上的密鑰可被用來產(chǎn)生同一個密文y。一般來說，Eve能排除某些密鑰，但仍存在許多可能的密鑰，這其中只有一個密鑰是正確的。我們稱那些可能的但不正確的密鑰稱為偽密鑰。34偽密鑰定理2.11：假設(shè)(P,C,K,E,D)是一個密碼體制，|C|=|P|并且密鑰是等概率選取的，設(shè)RL表示明文的自然語言的冗余度，則給定一個充分長（長n）的密文串，偽密鑰的期望滿足35偽密鑰密碼體制的唯一解距離，就是使得偽密鑰的期望數(shù)等于0的n的值，記為：即在給定充足的時間下，密碼分析者能唯一計算出密鑰所需密文的平均量。362.3、認(rèn)證系統(tǒng)的信息理論認(rèn)證理論的主要研究目標(biāo)：一是推導(dǎo)攻擊者成功欺騙的概率下界；二是構(gòu)造攻擊者欺騙成功的概率盡可能小的認(rèn)證碼。認(rèn)證碼是保證消息完整性、認(rèn)證性的重要工具，也就是保證消息沒有被篡改。37認(rèn)證矩陣的定義認(rèn)證矩陣是一個矩陣，它的行由密鑰來標(biāo)記，列由信源狀態(tài)來標(biāo)記，對每一個k∈K和s∈S，該矩陣的第k行第s列的元素是。38認(rèn)證碼攻擊中的兩個量認(rèn)證碼中攻擊者欺騙成功的概率Pd0和Pd1來

度量。為了構(gòu)造一個使欺騙率盡可能小的認(rèn)證碼，通常期望它能達(dá)到以下幾個目標(biāo)。（1）欺騙概率Pd0和Pd1必須足夠小，以便獲得期望的安全水平。（2）信源狀態(tài)的數(shù)目必須足夠大，以便能通過在一個信源狀態(tài)后附加一個標(biāo)簽來傳送期望的信息。（3）密鑰空間盡可能小，因?yàn)槊荑€的值需要在一個安全的信道上傳送。39相關(guān)定理定理2.16：設(shè)是一個驗(yàn)證碼，則(1)(2)

證明略。

40完善認(rèn)證系統(tǒng)定理2.17：完善認(rèn)證系統(tǒng)存在。定義2.19：完善認(rèn)證是使成立的認(rèn)證系統(tǒng)。顯然，每一個具有的系統(tǒng)是完善認(rèn)證系統(tǒng)。

.412.4、復(fù)雜性理論本節(jié)主要內(nèi)容算法復(fù)雜度定義及分類P問題和NP問題密碼算法的計算安全性主要知識點(diǎn)算法的復(fù)雜度定義及分類密碼算法的計算復(fù)雜度42算法復(fù)雜度的定義算法是指完成一個任務(wù)所需的具體步驟方法。時間（計算）復(fù)雜性：考慮算法的主要操作步驟，計算執(zhí)行中所需的總操作次數(shù)?？臻g復(fù)雜性：執(zhí)行過程中所需存儲器的單元數(shù)目。數(shù)據(jù)復(fù)雜性：信息資源。43算法復(fù)雜度的定義不同的編程語言，不同的編譯器導(dǎo)致執(zhí)行一次操作的時間各不相同，為了方便不同算法比較，通常假定所有計算機(jī)執(zhí)行相同的一次基本操作所需時間相同，而把算法中基本操作執(zhí)行的最大次數(shù)作為執(zhí)行時間。運(yùn)行時間=44算法復(fù)雜度的定義定義：

假設(shè)一個算法的計算復(fù)雜度為O(nt)，其中t為常