第四講密碼學基礎1New

第四講密碼學基礎11基本概念密碼學(Cryptology):是研究信息系統安全保密的科學.密碼編碼學(Cryptography):主要研究對信息進行編碼,實現對信息的隱蔽.密碼分析學(Cryptanalytics):主要研究加密消息的破譯或消息的偽造.2基本術語消息被稱為明文(Plaintext)。用某種方法偽裝消息以隱藏它的內容的過程稱為加密(Encrtption)，被加密的消息稱為密文(Ciphertext)，而把密文轉變為明文的過程稱為解密(Decryption)。

對明文進行加密操作的人員稱作加密員或密碼員(Cryptographer).密碼算法(CryptographyAlgorithm):是用于加密和解密的數學函數。密碼員對明文進行加密操作時所采用的一組規則稱作加密算法(EncryptionAlgorithm).所傳送消息的預定對象稱為接收者(Receiver).接收者對密文解密所采用的一組規則稱為解密算法(DecryptionAlgorithm).3

加解密過程示意圖加密和解密算法的操作通常都是在一組密鑰的控制下進行的,分別稱為加密密鑰(EncryptionKey)和解密密鑰(DecryptionKey).明文明文密文加密算法解密算法密鑰密鑰4

密碼學的目的：Alice和Bob兩個人在不安全的信道上進行通信，而破譯者Oscar不能理解他們通信的內容。加密通信的模型

Alice加密機解密機Bob安全信道密鑰源Oscarxyxk5密碼通信系統模型6密碼體制密碼體制：它是一個五元組（P,C,K,E,D)滿足條件：（1）P是可能明文的有限集；（明文空間）（2）C是可能密文的有限集；（密文空間）（3）K是一切可能密鑰構成的有限集；（密鑰空間）*（4）任意k∈K,有一個加密算法和相應的解密算法，使得和分別為加密解密函數，滿足dk(ek(x))=x,這里x∈P。7密碼算法分類-i按照保密的內容分:受限制的（restricted)算法:算法的保密性基于保持算法的秘密。

基于密鑰（key-based)的算法:算法的保密性基于對密鑰的保密。8密碼算法分類-ii基于密鑰的算法，按照密鑰的特點分類：對稱密碼算法（symmetriccipher)：又稱傳統密碼算法（conventionalcipher)，就是加密密鑰和解密密鑰相同，或實質上等同，即從一個易于推出另一個。又稱秘密密鑰算法或單密鑰算法。非對稱密鑰算法（asymmetriccipher):加密密鑰和解密密鑰不相同，從一個很難推出另一個。又稱公開密鑰算法（public-keycipher)

。公開密鑰算法用一個密鑰進行加密,而用另一個進行解密.其中的加密密鑰可以公開,又稱公開密鑰（publickey)，簡稱公鑰.解密密鑰必須保密,又稱私人密鑰（privatekey)私鑰.簡稱私鑰。91.對稱加密

對稱加密的缺點是密鑰需要通過直接復制或網絡傳輸的方式由發送方傳給接收方，同時無論加密還是解密都使用同一個密鑰，所以密鑰的管理和使用很不安全。如果密鑰泄露，則此密碼系統便被攻破。另外，通過對稱加密方式無法解決消息的確認問題，并缺乏自動檢測密鑰泄露的能力。對稱加密的優點是加密和解密的速度快。2．非對稱加密

在非對稱加密中，加密密鑰與解密密鑰不同，此時不需要通過安全通道來傳輸密鑰，只需要利用本地密鑰發生器產生解密密鑰，并以此進行解密操作。由于非對稱加密的加密和解密不同，且能夠公開加密密鑰，僅需要保密解密密鑰，所以不存在密鑰管理問題。非對稱加密的另一個優點是可以用于數字簽名。但非對稱加密的缺點是算法一般比較復雜，加密和解密的速度較慢。10密碼算法分類-iii按照明文的處理方法：分組密碼（blockcipher):將明文分成固定長度的組，用同一密鑰和算法對每一塊加密，輸出也是固定長度的密文。序列密碼（streamcipher):又稱流密碼.序列密碼每次加密一位或一字節的明文，也可以稱為流密碼。序列密碼是手工和機械密碼時代的主流112．分組密碼分組密碼的加密方式是先將明文序列以固定長度進行分組，然后將每一組明文用相同的密碼和加密函數進行運算。為了減小存儲量，并提高運算速度，密鑰的長度一般不大，因而加密函數的復雜性成為系統安全的關鍵。分組密碼的優點是不需要密鑰同步，具有較強的適用性，適宜作為加密標準。缺點是加密速度慢。DES、DEA是典型的分組密碼。

121．序列密碼序列密碼也稱為流密碼，其思想起源于20世紀20年代，最早的二進制序列密碼系統是Vernam密碼。Vernam密碼將明文消息轉化為二進制數字序列，密鑰序列也為二進制數字序列，加密是按明文序列和密鑰序列逐位模2相加（即異或操作XOR）進行，解密也是按密文序列和密鑰序列逐位模2相加進行。當Vernam密碼中的密鑰序列是完全隨機的二進制序列時，就是著名的“一次一密”密碼（在本章隨后專門進行介紹）。一次一密密碼是完全保密的，但它的密鑰產生、分配和管理都不方便。

13密碼算法分類-iv對稱密鑰密碼又可分為：分組密碼每次對一塊數據加密多數網絡加密應用

DES,IDEA,RC6,Rijndael流密碼每次對一位或一字節加密手機

One-timepadding,Vigenére,Vernam14密碼算法分類-v公開密鑰密碼:

大部分是分組密碼，只有概率密碼體制屬于流密碼每次對一塊數據加密數字簽名,身份認證

RSA,ECC,ElGamal

加密解密速度慢15網絡加密的實現方法基于密碼算法的數據加密技術是所有網絡上的通信安全所依賴的基本技術。目前對網絡數據加密主要有鏈路加密、節點對節點加密和端對端加密3種實現方式。1．鏈路加密

鏈路加密又稱在線加密，它是對在兩個網絡節點間的某一條通信鏈路實施加密，是目前網絡安全系統中主要采用的方式。如下圖所示，在鏈路加密方式下，只對通信鏈路中的數據加密，而不對網絡節點內的數據加密。鏈路加密過程示意圖

162．節點對節點加密

節點對節點加密是為了解決在節點中的數據是明文的這一缺點，在中間節點里裝有用于加密和解密的保護裝置，由這個裝置來完成一個密鑰向另一個密鑰的交換。因而，除了在保護裝置里，即使在節點內也不會出現明文。盡管節點對節點加密能給網絡數據提供較高的安全性，但它在操作方式上與鏈路加密類似：兩者均在通信鏈路上為傳輸的消息提供安全性；都在中間節點先對消息進行解密，然后進行加密。因為要對所有傳輸的數據進行加密，所以加密過程對用戶是透明的。173．端對端加密

為了解決鏈路加密和節點對節點加密中存在的不足，人們提出了端對端加密方式。端對端加密又稱脫線加密或包加密，它允許數據在從源節點被加密后，到終點的傳輸過程中始終以密文形式存在，消息在到達終點之前不進行解密，只有消息到達目的節點后才被解密。因為消息在整個傳輸過程中均受到保護，所以即使有節點被損壞也不會使消息泄露。因此，端對端加密方式可以實現按各通信對象的要求改變加密密鑰以及按應用程序進行密鑰管理等，而且采用這種方式可以解決文件加密問題。

18軟件加密和硬件加密目前具體的數據加密實現方法主要有兩種：軟件加密和硬件加密。1．軟件加密

軟件加密一般是用戶在發送信息前，先調用信息安全模塊對信息進行加密處理，然后進行發送。到達接收端后，由用戶用相應的解密軟件進行解密處理，還原成為明文。

2．硬件加密

硬件加密是采用專門的硬件設備實現消息的加密和解密處理。隨著微電子技術的發展，現在許多加密產品都是特定的硬件加密形式。這些加、解密芯片被嵌入到通信線路中，然后對所有通過的數據進行加密和解密處理。19密碼學的起源和發展-i三個階段：1949年之前密碼學是一門藝術1949～1975年密碼學成為科學1976年以后密碼學的新方向——公鑰密碼學20密碼學的起源隱寫術(steganography):

通過隱藏消息的存在來保護消息.

隱形墨水字符格式的變化圖形圖像21example-i(象形文字的修改)ModifiedHieroglyphics,c.1900B.C.

密碼學的第一個例子是對標準書寫符號的修改例如:古埃及法老墳墓上的文字思想:代替(substitution)

22example-iiSpartanScytale,c.500B.C.

斯巴達人用于加解密的一種軍事設備發送者把一條羊皮螺旋形地纏在一個圓柱形棒上思想：置換（permutation)23example-iiiPolybius’Checkerboard,205~123B.C.

明文:POLYBIUS密文:3534315412244543

123451ABCDE2FGHIJK3LMNOP4QRSTU5VWXYZ24Example-ivCaesarCipher,c.50B.C.

ABCDEFG……XYZDEFGHIJ……ABC

明文:Caesarcipherisashiftsubstitution

密文:FDHVDUFLSKHULVDVKLIWVXEVWLWXWLRQ25Example-VNomenclator

代碼本c.1400字母、符號、單詞、短語代碼代碼字母、符號、單詞、短語應用：WorldWarII26密碼學的起源和發展-ii1949年之前:

古典密碼（classicalcryptography)

密碼學還不是科學,而是藝術出現一些密碼算法和加密設備密碼算法的基本手段(substitution&permutation)出現，針對的是字符簡單的密碼分析手段出現27密碼學的起源和發展-iii1949～1975年:計算機使得基于復雜計算的密碼成為可能1949年Shannon的“TheCommunicationTheoryofSecretSystems”1967年DavidKahn的《TheCodebreakers》1971-73年IBMWatson實驗室的HorstFeistel等的幾篇技術報告

Smith,J.L.,TheDesignofLucifer,ACryptographicDeviceforDataCommunication,1971

Smith,J.L.,…,AnExprementalApplicationofCryptogrphytoaremotelyAccessedDataSystem,Aug.1972

Feistel,H.,CryptographyandComputerPrivacy,May1973數據的安全基于密鑰而不是算法的保密28密碼學的起源和發展-iv1976年以后:

1976年Diffie&Hellman的“NewDirectionsinCryptography”提出了不對稱密鑰密碼1977年Rivest,Shamir&Adleman提出了RSA公鑰算法90年代逐步出現橢圓曲線等其他公鑰算法

公鑰密碼使得發送端和接收端無密鑰傳輸的保密通信成為可能！29密碼學的起源和發展-v1976年以后:

對稱密鑰密碼算法進一步發展1977年DES正式成為標準80年代出現“過渡性”的“postDES”算法,如IDEA,RCx,CAST等90年代對稱密鑰密碼進一步成熟Rijndael,RC6,MARS,Twofish,Serpent等出現2001年Rijndael成為DES的替代者30密碼分析假設破譯者Oscar是在已知密碼體制的前提下來破譯Bob使用的密鑰。這個假設稱為Kerckhoff原則。最常見的破解類型如下：1.唯密文攻擊：Oscar具有密文串y.2.已知明文攻擊:Oscar具有明文串x和相應的密文y.3.選擇明文攻擊：Oscar可獲得對加密機的暫時訪問，因此他能選擇明文串x并構造出相應的密文串y。4.選擇密文攻擊:Oscar可暫時接近密碼機,可選擇密文串y，并構造出相應的明文x.

這一切的目的在于破譯出密鑰或密文31密碼破譯密碼破譯的原則:遵循觀察與經驗方法:采用歸納與演繹步驟:分析、假設、推測和證實三大要素：語言的頻率特征：e連接特征:q…u,Iex,重復特征:th,tion,tious32密碼算法的安全性無條件安全（Unconditionallysecure）無論破譯者有多少密文,他也無法解出對應的明文,即使他解出了,他也無法驗證結果的正確性.Onetimepad計算上安全（Computationallysecure）破譯的代價超出信息本身的價值破譯的時間超出了信息的有效期.33古典密碼基于字符的密碼代替密碼（substitutioncipher)：就是明文中的每一個字符被替換成密文中的另一個字符。接收者對密文做反向替換就可以恢復出明文。置換密碼(permutationcipher)，又稱換位密碼（transpositioncipher)：明文的字母保持相同，但順序被打亂了。34古典密碼介紹簡單替換密碼

簡單替換密碼是古典密碼中使用最早的一種密碼機制，其實現方法是將明文按字母表中當前的位置向后移動n位，便得到加密后的密文，這里的n就是密鑰。例如，當n=3時（即以n=3為密鑰）時，字符表的替換如下（為便于表述，我們約定在明文中使用小寫字母，而在密文中使用大寫字母）：明文：abcdefghijklmnopqrstuvwxyz密文：DEFGHIJKLMNOPQRSTUVWXYZABC

當n=3時的密碼體制由于被凱撒（Caesar）成功使用，所以也稱為凱撒密碼。

35雙重置換密碼

使用雙重轉換密碼進行加密時，首先將明文寫成給定大小的矩陣形式，然后根據給定的置換規則對行和列分別進行置換。例如，對明文“attackattomorrow”寫成4×4的矩陣形式：

然后，按照（1,2,3,4）→（2,3,4,1）的規則進行行置換，然后再按照（1,2,3,4）→（3,4,2,1）的規則進行列置換。操作如下：

從而得到的密文為“ATKCMOOTOWRRTATA”。36雙重置換密碼

在雙重置換密碼體制中，密鑰由矩陣的大小以及行、列置換規則組成。接收者如果知道密鑰，就可以通過加密過程使用的矩陣大小以及行、列的置換規則來進行逆向操作，從而恢復得到明文。例如，對于前面得到的密文，可以先寫成4×4的矩陣形式，然后將列進行（3,4,2,1）→（1,2,3,4）的置換，再將行進行（2,3,4,1）→（1,2,3,4）的置換。操作如下：

于是得到明文“attackatwomorrow”。37“一次一密”密碼

最著名的序列密碼是“一次一密”密碼，也稱為“一次一密亂碼本加密機制”。其中，一次一密亂碼本是一個大的不重復的隨機密鑰字符集，這個密鑰字符集被寫在幾張紙上，并粘合成一個本子，該本子稱為亂碼本。每個密鑰僅對一個消息使用一次。發送方用亂碼本中的密鑰對所發送的消息加密，然后銷毀亂碼本中用過的一頁或用過的磁帶部分。接收方有一個同樣的亂碼本，并依次使用亂碼本上的每一個密鑰去解密密文的每個字符。接收方在解密消息后銷毀亂碼本中用過的一頁或用過的磁帶部分。新的消息則用亂碼本的新的密鑰進行加密和解密。“一次一密”密碼是一種理想的加密方案，理論上講，實現了“一次一密”密鑰管理的密碼是不可破譯的。38“一次一密”密碼39“一次一密”密碼40對稱加密—流密碼流密碼（即序列密碼）是一種類似于“一次一密”密碼體制，因為在加密過程中是將密鑰流（密鑰的二進制位）與等長的明文的二進制位進行模2運行，在解密過程中是將密鑰流與密文進行逐位模2運行，所以流密碼是一種對稱加密方式。41流密碼的工作原理

在現代計算機網絡中，由于報文、數據和圖像等消息都可以通過某一編碼技術轉化為二進制數字序列，因而可假定流密碼中的明文空間M是由所有可能的二進制數字序列組成的集合。設K為密鑰空間，由于流密碼應使用盡可能長的密鑰，而太長的密鑰在存儲、分配等方面都有一定的困難，于是研究人員采用一個短的密鑰k∈K來控制某種算法A產生出長的密鑰序列，供加密和解密使用。而短密鑰k的存儲和分配在實現方式上都比較容易。根據密碼學的約定，算法A是公開的，而密鑰k是保密的。4243A5/1444546圖2-5A5/1密鑰流生成器的工作過程47對稱加密—分組密碼流密碼和分組密碼都屬于對稱密鑰算法，流密碼的基本思想是利用密鑰產生一個密鑰流，并通過相應的規則對明文串進行加密和解密處理。而分組密碼是將明文分為固定長度的分組，然后通過若干輪（round）函數的迭代操作來產生密文。函數由于在每一輪的操作中都使用，所以稱為輪函數，其本輪的輸入是上一輪的輸出加上密鑰。48分組密碼的一般設計原理分組密碼是將明文消息編碼表示后的數字序列，劃分成長度為n的組，每組分別在密鑰的控制下變換成等長的輸出數字序列.49兩個基本設計方法擴散（Diffusion):明文的統計結構被擴散消失到密文的長程統計特性

,使得明文和密文之間的統計關系盡量復雜

混亂(confusion)：使得密文的統計特性與密鑰的取值之間的關系盡量復雜

50Feistel密碼結構51圖2-6Feistel網絡結構5253圖2-7Feistel的加密和解密過程54現代常規加密技術DES(DataEncryptionStandard)TripleDESIDEABlowfishRC5CAST-128Rijndael55DES的產生-i1973年5月15日,NBS（NationalBureauofStandards）開始公開征集標準加密算法,并公布了它的設計要求:(1)算法必須提供高度的安全性(2)算法必須有詳細的說明,并易于理解(3)算法的安全性取決于密鑰,不依賴于算法(4)算法適用于所有用戶(5)算法適用于不同應用場合(6)算法必須高效、經濟(7)算法必須能被證實有效(8)算法必須是可出口的56DES的產生-ii1974年8月27日,NBS開始第二次征集,IBM提交了算法LUCIFER，該算法由IBM的工程師在1971~1972年研制1975年3月17日,NBS公開了全部細節1976年,NBS指派了兩個小組進行評價1976年11月23日，采納為聯邦標準，批準用于非軍事場合的各種政府機構1977年1月15日,“數據加密標準”FIPSPUB46發布57DES的應用1979年，美國銀行協會批準使用1980年，美國國家標準局（ANSI）贊同DES作為私人使用的標準,稱之為DEA（ANSIX.392）

1983年，國際化標準組織ISO贊同DES作為國際標準，稱之為DEA-1該標準規定每五年審查一次，計劃十年后采用新標準最近的一次評估是在1994年1月，已決定1998年12月以后，DES將不再作為聯邦加密標準。

58DES的加密過程描述DES利用56比特串長度的密鑰K來加密長度為64位的明文，得到長度為64位的密文輸入64比特明文數據初始置換(IP函數)在密鑰控制下16輪迭代初始逆置換(IP-1)輸出64比特密文數據DES算法框圖交換左右32比特5960初始置換IP和初始逆置換IP—1

61

Li-1（32比特）Ri-1（32比特）Li（32比特）48比特寄存器選擇擴展運算E48比特寄存器子密鑰Ki（48比特）32比特寄存器選擇壓縮運算S置換運算PRi（32比特）Li=Ri-1DES的一輪迭代函數f62

選擇擴展運算E32010203040504050607080908091011121312

131415161716171819202120212223242524252627282928293031320163選擇壓縮運算SDES中的S盒

“S盒”是DES算法中的核心。正是由于S盒的重要性，所以相關技術細節一直未被公開。這也是有人懷疑DES算法留有安全后門的一個原因，不過S盒確實增加了DES算法抵抗密碼攻擊的能力。S盒在輪函數F中的作用如圖2-10所示。一次替換由一組共8個S盒組成。其中每一個S盒都接受6bit的輸入，產生4bit的輸出。這樣，48bit的輸入最后得到32bit的輸出