現(xiàn)代密碼學(xué)(第二版)重點概念整理

1、第一章1.被動攻擊獲取消息的真實內(nèi)容進(jìn)行業(yè)務(wù)流分析2.主動攻擊中斷、篡改、偽造3.安全業(yè)務(wù) 1、保密業(yè)務(wù)：保護(hù)數(shù)據(jù)以防被動攻擊。 2、認(rèn)證業(yè)務(wù)：用于保證通信的真實性。 3、完整性業(yè)務(wù)：防止對消息流的篡改和業(yè)務(wù)拒絕。 4、不可否認(rèn)業(yè)務(wù)：用于防止通信雙方中的某一方對所傳輸消息的否認(rèn)。 5、訪問控制：訪問控制的目的是防止對網(wǎng)絡(luò)資源的非授權(quán)訪問，控制的實現(xiàn)方式是認(rèn)證，即檢查欲訪問某一資源的用戶是否具有訪問權(quán)。4. 安全通信需考慮加密算法用于加密的秘密信息秘密信息的分布與共享安全服務(wù)所需的協(xié)議5. 信息安全可分為系統(tǒng)安全、數(shù)據(jù)安全、內(nèi)容安全，密碼技術(shù)是保障數(shù)據(jù)安全的關(guān)鍵技術(shù)。6. 密碼體制從原理上分為單

2、鑰體制和雙鑰體制，單鑰體制包括對明文消息按字符逐位加密的流密碼和將明文消息分組加密的分組密碼。雙鑰特點是將加密和解密能力分開。7. 密碼攻擊類型唯密文攻擊、已知明文攻擊、選擇明文攻擊、選擇密文攻擊8. 加密算法是無條件安全的，僅當(dāng)密鑰至少和明文一樣長時，才能達(dá)到無條件安全9. 多表代換密碼的計算問題，課后習(xí)題3、4第二章1.流密碼的概念：利用密鑰k產(chǎn)生一個密鑰流z=z0z1，并使用如下規(guī)則對明文串x=x0x1x2加密： y=y0y1y2=Ez0(x0)Ez1(x1)Ez2(x2)。 密鑰流由密鑰流發(fā)生器f產(chǎn)生： zi=f(k,i)， i:加密器中的記憶元件(存儲器)在時刻i的狀態(tài)， f:由密鑰

3、k和i產(chǎn)生的函數(shù)。2.分組密碼與流密碼的區(qū)別: 有無記憶性3.密碼設(shè)計者的最大愿望是設(shè)計出一個滾動密鑰生成器，使得密鑰經(jīng)其擴(kuò)展成的密鑰流序列具有如下性質(zhì)：極大的周期、良好的統(tǒng)計特性、抗線性分析、抗統(tǒng)計分析4.同步流密碼的關(guān)鍵是密鑰流產(chǎn)生器。5.如果移位寄存器的反饋函數(shù)f(a1,a2,an)是a1，a2，an的線性函數(shù)，則稱之為線性反饋移位寄存器LFSR（linear feedback shift register）。6.周期達(dá)到最大值2n-1，周期達(dá)到最大值的序列稱為m序列。7.若n次不可約多項式p(x)的階為2n-1，則稱p(x)是n次本原多項式。8.只能要求截獲比周期短的一段時不會泄露更多

4、信息，這樣的序列稱為偽隨機(jī)序列。9.設(shè)計一個性能良好的序列密碼是一項十分困難的任務(wù)。最基本的設(shè)計原則是“密鑰流生成器的不可預(yù)測性”，它可分解為下述基本原則： 長周期。 高線性復(fù)雜度。 統(tǒng)計性能良好。 足夠的“混亂”。 足夠的“擴(kuò)散”。 抵抗不同形式的攻擊。10. 課后習(xí)題1、3第三章1. 分組密碼設(shè)計的算法應(yīng)滿足下述要求（1） 分組長度要足夠大（2） 密鑰量要足夠大（3） 由密鑰確定置換的算法要足夠復(fù)雜（4） 加密和解密運(yùn)算簡單（5） 數(shù)據(jù)擴(kuò)展盡可能地?。?） 差錯傳播盡可能地小2. 擴(kuò)散和混淆是由香濃提出的設(shè)計密碼系統(tǒng)的兩個基本方法，成功地實現(xiàn)了分組密碼的本質(zhì)屬性，因而成為設(shè)計現(xiàn)代分組密碼的

5、基礎(chǔ)。3. Feistel加密結(jié)構(gòu)第i輪迭代的輸入為前輪輸出的函數(shù)（詳見課本P33）Li=Ri-1Ri=Li-1F（Ri-1,Ki）4. DES：分組長度64比特，密鑰長度56比特5. IDEA：分組長度64，密鑰長度1286. AES:分組長度128，密鑰長度128/192/2567. AES的設(shè)計策略是寬軌跡策略，輪函數(shù)包括：字節(jié)代換、行移位、列混合、密鑰加8. 二重DES不能抵抗中途相遇攻擊9. 課后作業(yè)習(xí)題：1、3、4、6第四章1.費(fèi)爾瑪定理定理4.2 (Fermat)若p是素數(shù)，a是正整數(shù)且gcd(a, p)=1，則ap-11 mod p。2. 歐拉函數(shù)設(shè)n是一正整數(shù)，小于n且與n互

6、素的正整數(shù)的個數(shù)稱為n的歐拉函數(shù)，記為(n)。3. 歐拉定理定理4.4（Euler） 若a和n互素，則a(n)1 mod n。4.求最大公因子Euclid算法是基于下面一個基本結(jié)論： 對任意非負(fù)整數(shù)a和正整數(shù)b，有g(shù)cd(a, b)=gcd(b, a mod b)。5. 中國剩余定理6. 定理4.6 設(shè)a的階為m，則ak1 mod n的充要條件是k為m的倍數(shù)。7. 推論：a的階m整除(n)。如果a的階m等于(n)，則稱a為n的本原根。如果a是n的本原根，則a,a2,a(n)在mod n下互不相同且都與n互素。特別地，如果a是素數(shù)p的本原根，則a, a2 , , ap-1在 mod p下都不相同

7、。8. 公鑰密碼體制提出者：W.Diffie和M.Hellman9. 勒讓德符號定義4.1 設(shè)p是素數(shù)，a是一整數(shù)，符號 的定義如下：稱符號 （a/p） 為Legendre符號。10.公鑰密碼算法應(yīng)滿足以下要求: 接收方B產(chǎn)生密鑰對（公開鑰PKB和秘密鑰SKB）在計算上是容易的。 發(fā)方A用收方的公開鑰對消息m加密以產(chǎn)生密文c，即c=EPKBm在計算上是容易的。 收方B用自己的秘密鑰對c解密，即m=DSKBc在計算上是容易的。 敵手由B的公開鑰PKB求秘密鑰SKB在計算上是不可行的。 敵手由密文c和B的公開鑰PKB恢復(fù)明文m在計算上是不可行的。 加、解密次序可換，即EPKBDSKB(m)=DSK

8、BEPKB(m)其中最后一條雖然非常有用，但不是對所有的算法都作要求。11.陷門單向函數(shù)是一族可逆函數(shù)fk，滿足 Y=fk(X)易于計算（當(dāng)k和X已知時）。 X=f-1k(Y)易于計算（當(dāng)k和Y已知時）。 X=f-1k(Y)計算上是不可行的（當(dāng)Y已知但k未知時）。12. RSA算法提出人;R.Rivest, A.Shamir和L.Adleman,安全性是基于分解大整數(shù)的困難性假定13. 計算題：課后3、4、5、6、7、8、10、14、15、17、18、19、20第五章1.假定兩個用戶A、B分別與密鑰分配中心KDC (key distribution center)有一個共享的主密鑰KA和KB，

9、A希望與B建立一個共享的一次性會話密鑰，可通過以下幾步來完成：2. 無中心的密鑰分配時，兩個用戶A和B建立會話密鑰需經(jīng)過以下3步：3. 公鑰管理機(jī)構(gòu)與公用目錄表類似，這里假定有一個公鑰管理機(jī)構(gòu)來為各用戶建立、維護(hù)動態(tài)的公鑰目錄，但同時對系統(tǒng)提出以下要求，即： 每個用戶都可靠地知道管理機(jī)構(gòu)的公開鑰，而只有管理機(jī)構(gòu)自己知道相應(yīng)的秘密鑰。 公開鑰的分配步驟如下：4.簡單分配5. Diffie-Hellman密鑰交換是W. Diffie和M. Hellman于1976年提出的第一個公鑰密碼算法算法的安全性基于求離散對數(shù)的困難性。缺點：易受中間人攻擊（Oscar圖例）6.秘密分割門限方案定義： 設(shè)秘密s

10、被分成n個部分信息，每一部分信息稱為一個子密鑰或影子，由一個參與者持有，使得：由k個或多于k個參與者所持有的部分信息可重構(gòu)s。由少于k個參與者所持有的部分信息則無法重構(gòu)s。 則稱這種方案為(k,n)-秘密分割門限方案，k稱為方案的門限值。如果一個參與者或一組未經(jīng)授權(quán)的參與者在猜測秘密s時，并不比局外人猜秘密時有優(yōu)勢，即由少于k個參與者所持有的部分信息得不到秘密s的任何信息。則稱這個方案是完善的，即(k,n)-秘密分割門限方案是完善的。7. 基于中國剩余定理的門限方案：課本P1388. 課后習(xí)題1、2、3、4、6第六章1.消息認(rèn)證用以驗證接收消息的如下屬性：真實性（的確是由它所聲稱的實體發(fā)來的：

11、消息源認(rèn)證）完整性（未被篡改、插入、刪除）消息的順序性和時間性2. 認(rèn)證符的產(chǎn)生方法：消息認(rèn)證函數(shù)MAC、雜湊函數(shù)3.雜湊函數(shù)應(yīng)滿足以下條件： 函數(shù)的輸入可以是任意長 函數(shù)的輸出是固定長 已知x，求H(x)較為容易，可用硬件或軟件實現(xiàn)前3個是雜湊函數(shù)能用于消息認(rèn)證的基本要求 已知h，求使得H(x)=h的x在計算上是不可行的，這一性質(zhì)稱為函數(shù)的單向性，稱H(x)為單向散列函數(shù)單向性對使用秘密值的認(rèn)證技術(shù)(見圖3(e)極為重要。假如不具有單向性，則攻擊者截獲M和C=H(SM)后，求C的逆SM，就可求出秘密值S 已知x，找出y(yx)使得H(y)=H(x)在計算上是不可行的 找出任意兩個不同的輸入x

12、、y，使得H(y)=H(x)在計算上是不可行的4.第I類生日攻擊已知一散列函數(shù)H有n個可能輸出，H(x)是一特定輸出，若對H隨機(jī)取k個輸入，則至少有一個輸入y使得H(y)=H(x)的概率為0.5時，k有多大？稱對散列函數(shù)H尋找上述 y 的攻擊為第I類生日攻擊5. 第類生日攻擊：設(shè)散列函數(shù)H有2m個可能的輸出（即輸出長m比特），如果H的k個隨機(jī)輸入中至少有兩個產(chǎn)生相同輸出的概率大于0.5，則稱尋找函數(shù)H的具有相同輸出的兩個任意輸入的攻擊方式為第類生日攻擊6. 大多數(shù)雜湊函數(shù)如MD5、SHA，其結(jié)構(gòu)都是迭代型的，算法的核心技術(shù)是設(shè)計無碰撞的壓縮函數(shù)f7. MD5雜湊算法Ron Rivest提出，算

13、法的輸入為小于264比特長的任意消息，分為512比特長的分組輸出為160或128比特長的消息摘要。8. 2004年山東大學(xué)王小云教授破譯了MD5，2005年，王小云等提出了對SHA-1碰撞搜索攻擊9. 雜湊函數(shù)并不是為用于MAC而設(shè)計的，由于雜湊函數(shù)不使用密鑰，因此不能直接用于MAC10. 基于密碼雜湊函數(shù)構(gòu)造的MAC的安全性取決于鑲嵌的雜湊函數(shù)的安全性第七章1.數(shù)字簽字應(yīng)滿足以下要求：（1）簽字的產(chǎn)生必須使用發(fā)方獨有的一些信息以防偽造和否認(rèn)。（2）簽字的產(chǎn)生應(yīng)較為容易。（3）簽字的識別和驗證應(yīng)較為容易。（4）對已知的數(shù)字簽字構(gòu)造一新的消息或?qū)σ阎南?gòu)造一假冒的數(shù)字簽字在計算上都是不可行的

14、。2.由簽字算法產(chǎn)生數(shù)字簽字算法的安全性在于從M和S難以推出密鑰x或偽造一個消息M使M和S可被驗證為真。4. 數(shù)字簽字標(biāo)準(zhǔn)DSS； RSA算法既能用于加密和簽字，又能用于密鑰交換。 DSS使用的算法只能提供數(shù)字簽字功能。5. DSA是在ElGamal和Schnorr兩個簽字方案的基礎(chǔ)上設(shè)計的，其安全性基于求離散對數(shù)的困難性。6. Needham-Schroeder協(xié)議KDC的密鑰分配過程，可用以下協(xié)議（稱為Needham-Schroeder協(xié)議）來描述： AKDC：IDAIDBN1 KDCA： EKAKSIDBN1EKBKSIDA AB：EKBKSIDA -弱點 BA：EKSN2 AB：EKSf(N2)7. 交互證明系統(tǒng)交互證明系統(tǒng)由兩方參與，分別稱為證明者（prover，簡記為P）和驗證者（verifier，簡記為V），其中P知道某一秘密（如公鑰密碼體制的秘密鑰或一平方剩余x的平方根），P希望使V相信自己的確掌握這一秘密。8.交互證明和數(shù)學(xué)證明的區(qū)別是：數(shù)學(xué)證明的證明者可自己獨立地完成證明，而交互證明是由P產(chǎn)生證明、V驗證證明的有效性來實現(xiàn)，因此雙方之間通過某種信道的通信是必需的。9.交互證明系統(tǒng)須滿足以下要求： 完備性: 如果P知道某一秘密，V將接受P的證明。 正確性: 如果P能以一定的概率使V相信P的證明，則P知道相應(yīng)的秘密。10.零知識證明零知識證明起源于最