1、信息安全概論電子科技大學出版社2007年8月2022/8/201第2章 密碼學概述 2.1 密碼學簡介 2.2 密碼學基本概念 2.3 古典密碼 2.4 基礎數論 2022/8/2022.1 密碼學概述2.1.1 密碼學與數學的聯系2.1.2 密碼學的發展歷史返回本章目錄2022/8/2032.1.1 密碼學與數學的聯系基礎數論在密碼學中的作用基礎數論作為一門古老的數學學科，在整個數學學科中占有非常重要的地位。古典密碼機制，如加法、乘法密碼，實質上就用到了數論中同余的概念。數論理論在近代密碼學的研究中發揮了前所未有的生命力。最典型的是影響廣泛的RSA公鑰密碼體制，它的基礎是數論的歐拉定理，其安

2、全性依賴于大數的因素分解的困難性。數論中的許多基本內容，如同余理論、中國剩余定理、高次剩余理論等，在新型密碼體制、密鑰分配與管理、數字簽名、身份認證等方面有直接的應用。 2022/8/2042.1.1 密碼學與數學的聯系近代數學對現代密碼學的影響近代數學在現代密碼研究中的應用比比皆是 ，如群論在分組密碼中的應用，利用置換概念實現輪函數的擴散性等。（對稱密碼體制）有限域上橢圓曲線理論，多項式理論和陷門單向函數等使密碼學與數學的關系越來越緊密。 （非對稱密碼體制）在生成密鑰序列的對象中，布爾函數的一些特殊結構起到了很大的作用。就數理邏輯來說，BAN邏輯已延伸到網絡協議的邏輯認證等方面，如網絡安全協

3、議以及電子交易的防抵賴協議的形式化分析。返回本節目錄2022/8/2052.1.2 密碼學的發展歷史樸素密碼時代密碼學的淵源可追溯到古代社會中的行幫暗語、黑幫行話和隱寫術等。古典密碼時代隨著戰爭的出現，通信的保密性成為必然的需求。古典密碼采用手工或機械變換的方式實現。古典密碼體制可分為單表替代密碼和多表替代密碼。單表替代密碼： Caesar密碼（據傳為凱撒使用）。多表替代密碼： Engima密碼（二戰時德國使用）。2022/8/2062.1.2 密碼學的發展歷史電子計算時代1949年Shannon發表保密系統的通信理論，為密碼學奠定了理論基礎。1976年Diffe和Hellman發表了密碼學的

4、新方向，提出了一種嶄新的密碼設計思想公鑰加密體制。1977年美國國家標準局正式公布了數據加密標準 (DES)。網絡計算時代隨著網絡技術的迅速發展和高性能計算機的問世，密碼學重新引起了人們的極大關注。1997年美國開始征集新一代數據加密標準AES。2022/8/2072.2 密碼學的基本概念 2.2.1 基本術語 2.2.2 密碼系統模型 2.2.3 密碼分析攻擊 2.2.5 密碼系統的安全性 返回本章目錄2022/8/2082.2.1 基本術語明文與明文空間需要加密的信息稱為明文。明文的取值范圍稱為明文空間。密文與密文空間明文經過隱藏（加密）形成密文。密文的取值范圍稱為密文空間。密鑰與密鑰空間

5、在明文轉換為密文或將密文轉換為明文的算法中輸入的參數。密鑰的取值范圍稱為密鑰空間。2022/8/2092.2.1 基本術語加密和解密（算法）為了隱藏明文，對明文實施的一系列變換過程，稱為加密（算法），所使用的密鑰稱為加密密鑰。反之，為還原明文對密文施加的一系列逆變換，稱為解密（算法），所使用的密稱鑰為解密密鑰。密碼算法加密算法和解密算法統稱為密碼算法。密碼系統密碼算法、明文空間、密文空間以及密鑰空間。2022/8/20102.2.2 密碼系統模型加密：C=E(K1,M)解密：M=D(K2,C)密碼等式：M=D(K2, E(K1,M)加密密鑰K1和解密密鑰K2是否相同是密碼算法的分類依據之一。2

6、022/8/20112.2.2 密碼系統模型加密算法通常采用的兩個基本方法替換法(Substitution)：將明文消息的每個字母（單詞）替換為其它字母（單詞）。變換法(Transposition)：將明文消息的字母重新排列組合而得到密文。密碼算法的保密性必須是基于保持密鑰的秘密，而不是基于加解密算法的秘密。（現代密碼vs古典密碼）。若是基于加解密算法的秘密，則成為受限制的算法，如換位密碼。2022/8/20122.2.3 密碼分析密碼學是研究編制密碼和破譯密碼的技術科學密碼編碼學:研究如何對消息進行變換，防止明文被竊取，進而被解讀和利用。密碼分析學:研究在不知道密鑰的情況下，如何盡快恢復出明

7、文或密鑰。密碼分析也可以發現密碼體制的弱點。密碼學中亙古不變的真理只有密碼分析家才能評判密碼體制的安全性！2022/8/20132.2.3 密碼分析的攻擊方法窮舉攻擊法（強力攻擊）對截獲到的密文嘗試遍歷所有可能的密鑰，直到獲得了一種從密文到明文的可理解的轉換；使用不變的密鑰對所有可能的明文加密，直到得到與截獲到的密文一致為止。統計分析法指密碼分析者根據明文、密文和密鑰的統計規律來破譯密碼的方法。數學分析法指密碼分析者針對加解密算法的數學基礎和某些密碼學特性，通過數學求解的方法來破譯密碼。2022/8/20142.2.3 密碼分析的攻擊類型惟密文攻擊(Cipher text-only attac

8、k)在惟密文攻擊中，密碼分析者知道密碼算法，但僅能根據截獲的密文進行分析，以得出明文或密鑰。由于密碼分析者所能利用的數據資源僅為密文，這是對密碼分析者最不利的情況。已知明文攻擊 (Known-plain text attack)已知明文攻擊是指密碼分析者除了有截獲的密文外，還有一些已知的“明文密文對”來破譯密碼。密碼分析者的任務目標是推出用來加密的密鑰或某種算法，這種算法可以對用該密鑰加密的任何新的消息進行解密。2022/8/20152.2.3 密碼分析的攻擊類型選擇明文攻擊(Chosen-plain text attack)指密碼分析者不僅可得到一些“明文密文對”，還可以選擇被加密的明文，并

9、獲得相應的密文。密碼分析者能夠選擇特定的明文數據塊去加密，并比較明文和對應的密文，已分析和發現更多的與密鑰相關的信息。選擇密文攻擊(Chosen-cipher text attack)指密碼分析者可以選擇一些密文，并得到相應的明文。密碼分析者的任務目標是推出密鑰。這種密碼分析多用于攻擊公鑰密碼體制。2022/8/20162.2.3 密碼分析衡量密碼攻擊的復雜度數據復雜度：為了實施攻擊所需輸入的數據量。處理復雜度：完成攻擊所需要花費的時間。存儲量：進行攻擊所需要的數據存儲空間大小。攻擊的復雜性取決于以上三個因素的最小復雜度。密碼系統的密鑰空間必須足夠地大。如果密鑰空間太小的話，攻擊者可以采用已知

10、明文攻擊，甚至唯密文攻擊，來窮舉整個密鑰空間從而攻破密碼系統。 2022/8/20172.2.4 密碼系統的安全性無條件安全性假定攻擊者擁有無限的計算資源，但仍然無法破譯該密碼系統。計算安全性指使用目前最好的方法攻破它所需要的計算遠遠超出攻擊者的計算資源水平，則可以定義這個密碼體制是安全的?？勺C明安全性將密碼系統的安全性歸結為某個經過深入研究的數學難題（如大整數素因子分解、計算離散對數等），數學難題被證明求解困難。2022/8/20182.2.4 密碼系統的安全性密碼系統要達到實際安全性，就要滿足以下準則：破譯該密碼系統的實際計算量（包括計算時間或費用）十分巨大，以致于在實際上是無法實現的。

11、破譯該密碼系統所需要的計算時間超過被加密信息有用的生命周期。（作戰命令、重要新聞消息）破譯該密碼系統的費用超過被加密信息本身的價值。2022/8/20192.2.4 密碼系統的安全性一個提供機密性服務的密碼系統是實際可用的，必須滿足的基本要求：系統的保密性不依賴于對加密體制或算法的保密，而僅依賴于密鑰的安全性。 “一切秘密寓于密鑰之中”是密碼系統設計的一個重要原則。滿足實際安全性，使破譯者取得密文后在有效時間和成本范圍內，確定密鑰或相應明文在計算上是不可行的。加密和解密算法應適用于明文空間、密鑰空間中的所有元素。 加密和解密算法能有效地計算，密碼系統易于實現和使用。 2022/8/2020影響

12、密碼系統安全性的因素所使用密碼算法本身的保密強度。密碼算法的保密強度取決于密碼設計的水平、破譯技術水平等。（技術保證）密碼算法之外的不安全因素。如：操作系統、網絡協議和應用軟件的漏洞、人為管理失誤。密碼算法的保密強度并不等價于密碼系統整體的安全性。個密碼系統必須同時完善技術與管理要求，才能保證整個密碼系統的安全。2.2.4 密碼系統的安全性2022/8/20212.3 古典密碼 2.3.1 字符或字符串的多維變序 2.3.2 單表古典密碼中的置換運算 2.3.3 多表代替 2.3.4 古典密碼的統計分析 返回本章目錄2022/8/20222.3.1 字符或字符串的多維變序一維倒置根據對明文是分

13、段或分組處理的不同，可分為報文倒置法和分組倒置法。報文倒置法：將一段明文整體倒置，并截成固定長度的字母組，形成密文。分組倒置法：首先將明文分成固定長度的字母串，然后對每組明文的字母分別進行倒置，形成密文。2022/8/20232.3.1 字符或字符串的多維變序二維易位在一個空表內，根據約定的書寫順序填入所要加密的明文。如橫向從上向下填寫明文，則需約定列數。空表填充后，再按照約定的抄寫順序寫出規定長度的密碼。2022/8/20242.3.2 單表古典密碼中的置換運算基本思想明文字母所對應的密文字母在密文中保持不變，即同一明文字母唯一對應著一致的密文字母。加法密碼（凱撒加密法）定義P=p0,p1,

14、pn-1為明文字母表,加密變換為：ci=Ek(pi)=(pi+k) mod n. 乘法密碼加密變換：ci=Ek(pi)=(pi*k) mod n. (gcd(k, n)=1) 仿射密碼加密變換：ci=Ek(pi)=(pi*k1+k2) mod n. (gcd(k1, n)=1) 加法密碼和乘法密碼都是仿射密碼的特殊情況。2022/8/20252.3.3 多表代替 多表代替密碼是一個由多個代替表依次對明文字母進行替換。與單表密碼不同的是，明文字母與密文字母之間不再存在一一對應的關系，明文中的字母統計特征不會在多表密碼中體現出來。例子：Vigenere密碼設密鑰K=k0k1kd-1，加密變換： c

15、i=EK(pi)=(pi+kj) mod n. 其中，j=i mod d.2022/8/20262.3.3 多表代替 謝爾比烏斯發明的加密電子機械名叫ENIGMA，在當時，它被認為是有史以來最為可靠的加密系統之一。德軍對ENIGMA加密機的過分信賴，也是德國戰敗的重要因素之一。2022/8/20272.3.4 古典密碼的統計分析 單表密碼體制中，由于明文字母與密文字母呈現出一一對應的關系，則明文字母的統計特性在密文中能夠體現出來。當截獲的密文足夠多時，可以通過統計密文字母的出現頻率，來確定明文字母與密文字母之間的對應關系。多表密碼體制中，明文中的字母統計特征不會在密文中體現出來。但知道多字母的

16、統計特性對于密文的破譯非常有用。2022/8/20282.4 基礎數論 2.4.1 數的整除性 2.4.2 歐拉(Euler)函數 2.4.3 歐幾里德(Euclid)算法 2.4.4 模運算 返回本章目錄2022/8/20292.4.1 數的整除性 素數（質數）在一個大于1的自然數中，除了1和此整數自身外，不能被其他自然數整除的數。公約（因）數、互素公約數是幾個整數同時均能整除的整數，公約數中最大的稱為最大公約數，簡寫為gcd(greatest common divisor)。如果兩個整數a和b的最大公約數為1，即gcd(a, b)=1，則稱a和b互素。2022/8/20302.4.2 歐拉

17、(Euler)函數 歐拉函數的定義歐拉函數(n) ：與n互素、且小于n的整數的個數。歐拉函數的性質若n為素數，則(n) = n-1；若p為素數，k0，則(pk) = pk-1(p-1)；若gcd(p, q)=1，則(pq) = (p) (q)。若p和q均為素數，則(pq) = (p-1) (q-1)；2022/8/20312.4.3 歐幾里德(Euclid)算法 帶余除法設 ，若存在唯一確定的整數q和r，使得a =bq+r, 。則稱q為a除以b所得的商，稱r為a除以b所得的余數，記為r = a mod b。歐幾里德算法利用帶余除法計算兩個整數的最大公約數。設有正整數a, b，且ab，則gcd(a, b)=gcd(a, a mod b)。算法應用該算法可以快速求得給定整數a和b的最大公因數 gcd(a, b)，因此可用來計算