1.2 現代密碼學

現代密碼學的任務不再僅限于傳統密碼學的“保密通信”，而是含義更廣的“信息安全”，包括“保密通信”“數據加密”“數字簽名”等重要功能，并且其應用也遠遠突破了軍事的范圍，開始全面進入經濟、商務、科學、教育等各個領域。現代密碼學方法可分為如下5個類別。

·對稱加密：同一個密鑰可以同時用作信息的加密和解密，這種加密方法稱為對稱加密。

·非對稱加密：需要兩個密鑰來進行加密和解密，這兩個密鑰是公開密鑰（Public Key，簡稱公鑰）和私有密鑰（Private Key，簡稱私鑰）。

·密碼學哈希：哈希（Hash）函數將可變長度的數據塊作為輸入，產生固定長度的哈希值，在安全應用中使用的哈希函數被稱為密碼學哈希。

·消息認證碼：經過特定算法后產生的一小段信息，檢查某段消息的完整性，以及做身份驗證。它可以用來檢查在消息傳遞過程中，其內容是否被更改過，不管更改的原因是來自意外或是蓄意攻擊。同時可以作為消息來源的身份驗證。

·數字簽名：只有信息的發送者才能產生的別人無法偽造的一段數字串，這段數字串同時也是對信息的發送者發送信息真實性的一個有效證明。

1.2.1 現代密碼學的特點

現代密碼學研究信息從發端到收端的安全傳輸和安全存儲，是研究“知己知彼”的一門科學。其核心是密碼編碼學和密碼分析學。1949年，香農發表了一篇名為《保密系統的通信理論》的論文，把已有數千年歷史的密碼學推向了基于信息論的科學軌道。該文提出了混淆（Confusion）和擴散（Diffusion）兩大設計原則，為對稱密碼學建立了理論基礎。而密碼學真正意義上開始進入發展期還是20世紀70年代中期。1976年，美國密碼學家迪菲和赫爾曼發表了一篇名為“密碼學新方向”的論文，開啟了公鑰密碼體制（非對稱密碼體制）的新篇章。

同時，計算機科學的蓬勃發展也極大地刺激和推動了密碼學的變革。善于快速計算的電子計算機為加密技術提供了新的工具。計算機和電子學時代的到來給密碼設計者帶來了前所未有的自由。

當代密碼學具有如下基本屬性。

●信息的機密性：保證信息不被泄露給非授權者等實體。采用密碼技術中的加密保護技術可以方便地實現信息的機密性。

●信息的真實性：保證信息來源可靠、沒有被偽造和篡改。密碼中的安全認證技術可以保證信息的真實性。

●數據的完整性：數據沒有受到非授權者的篡改或破壞。密碼雜湊算法可以方便地實現數據的完整性。

●行為的不可否認性（抗抵賴性）：一個已經發生的操作行為無法否認。基于公鑰密碼算法的數字簽名技術可以有效解決行為的不可否認性問題。

依據加密和解密所使用的密鑰是否相同可將密碼分為對稱密碼體制與非對稱密碼體制。

1.2.2 對稱加密

對稱密碼體制（單鑰體制）是指加密和解密使用相同密鑰的密碼算法，如圖1-3所示。

采用對稱密碼體制的系統的保密性主要取決于密鑰的保密性，與算法的保密性無關，即算法無須保密，需要保密的僅有密鑰。

對稱密碼體制對明文消息的加密有兩種方式：一種是將明文消息分組（每組中含有多個字符），逐組對其進行加密，這種密碼體制稱為分組密碼（Block Cipher）；另一種是由明文消息按字符逐位加密，這種密碼體制稱為序列密碼或流密碼（Stream Cipher）。

1.分組密碼

利用分組密碼對明文加密時，首先需要對明文進行分組，每組的長度都相同，然后對每組明文分別加密得到密文。設n是一個分組密碼的分組長度，k是密鑰，x=x0x1…xn-1為明文，y=y0y1…ym-1為相應的密文，則：

y=Enck(x)

x=Deck(y)

其中，Enck和Deck分別表示在密鑰k控制下的加密變換和解密變換。分組密碼模型如圖1-4所示。

分組密碼有兩種常見的結構，分別為Feistel網絡（Feistel Net）和SP網絡（Substitution Permutation Net）。DES和SM4是Feistel網絡的典型例子，AES是SP網絡的典型例子。

Feistel網絡包含對稱結構和非對稱結構兩類，以它的發明者Horst Feistel命名。在Feistel網絡中，加密的各個步驟稱為輪（Round），整個加密的過程即進行若干輪次的循環。以對稱結構的Feistel網絡為例，其一輪的計算步驟如圖1-5所示。

Feistel網絡第i輪的計算步驟如下。

1）將輸入的待加密的明文x分為左（Li-1）和右（Ri-1）兩部分。

2)將輸入的右部分Ri-1直接傳送至輸出的左部分Li。

3）將輸入的右部分Ri-1與使用密鑰k生成的子密鑰ki一起輸入加密的輪函數（Round Function，RFun），也稱圈函數。

4)將輸入的左部分Li-1與加密函數RFun的輸出進行異或運算，再傳送至輸出的右部分Ri。

Feistel網絡的優點在于加密過程與解密過程相似，甚至可以使用同一個算法實現加密和解密。

SP網絡的加密思想為：設待加密的明文為x，令X0=x，且r為加密變換的迭代次數。對于1≤i≤r，在子密鑰ki的控制下，對Xi-1做替換S，再對替換結果做可逆的線性變換P，得到Xi，如圖1-6所示。

在SP網絡中，替換S通常被稱為混淆層，主要起混淆的作用；置換或可逆的線性變換P通常被稱為擴散層，主要起擴散的作用。

SP網絡加密和解密過程一般不相似，即不能用同一個算法來實現加密和解密。

上述兩種網絡描述如何根據密鑰對一段固定長度（分組長度）的數據進行加密，對于較長的數據，需要重復應用某種分組加密的操作來安全地加密數據，稱為分組密碼工作模式。常見的分組密碼工作模式有電子密碼本（Electronic Code Book，ECB）、密碼分組鏈接（Cipher Block Chaining，CBC）、密碼反饋（Cipher Feedback，CFB）、輸出反饋（Output Feedback，OFB）和計數器（Counter Mode，CTR）5種模式。

ECB模式是最簡單的工作模式。該模式一次對一個固定長度的明文進行分組加密，且每次加密所使用的密鑰均相同。ECB模式的加密操作如圖1-7所示。

CBC模式解決了ECB模式的安全缺陷，可以讓重復的明文分組產生不同的密文分組。CBC模式一次對一個明文分組進行加密，每次加密使用同一密鑰，加密算法的輸入為當前明文分組和前一次密文分組的異或，因此CBC模式能隱蔽明文的數據模式，在某種程度上能防止數據篡改，如重放、嵌入和刪除等。但是CBC模式會出現傳播錯誤，對同步差錯敏感。CBC模式的加密操作如圖1-8所示。

CFB模式和CBC模式比較相似，明文單元被鏈接在一起，使得密文是前面所有明文的函數。CFB模式中加密的輸入是64bit移位寄存器，其初值為某個初始向量IV，解密為將收到的密文單元與加密函數的輸出進行異或操作。CFB模式適于用戶數據格式的需要，能隱蔽明文數據圖樣，也能檢測出對手對于密文的篡改，但對信道錯誤較敏感，且會造成錯誤傳播。此外，CFB模式需要一個初始向量，并且需要和密鑰同時進行更換。CFB模式的加密操作如圖1-9所示。

OFB模式和CFB模式比較相似，將分組密碼算法作為一個密鑰流產生器，其輸出的k bit密鑰直接反饋至分組密碼的輸入端，同時這k bit密鑰和輸入的k bit明文段進行對應位模2相加。OFB模式克服了CBC和CFB的錯誤傳播所帶來的問題，然而OFB模式對于密文被篡改難以進行檢測，不具有自同步能力，要求系統要保持嚴格的同步。OFB模式的加密操作如圖1-10所示。

CTR模式被廣泛用于ATM網絡安全和IPSec應用中。CTR模式的加密操作如圖1-11所示。

2.序列密碼

序列密碼也稱為流密碼（Stream Cipher），是對稱密碼算法的一種，也是密碼學的一個重要分支，具有實現簡單、便于硬件實施、加解密處理速度快、沒有或只有有限的錯誤傳播等特點，因此獲得了廣泛應用。

理論上“一次一密”密碼是不可破譯的。使用盡可能長的密鑰可以使序列密碼的安全性提高，但是密鑰長度越長，存儲、分配就越困難。于是人們便想出采用一個短的種子密鑰來控制某種算法獲得長的密鑰序列的辦法，這個種子密鑰的長度較短，存儲、分配都比較容易。序列密碼的原理如圖1-12所示。

密鑰流由密鑰流生成器f產生，即zi=f（k，σi），其中σi是加密器中的記憶元件（寄存器）。在時刻i的狀態，k為種子密鑰，f是由密鑰k和σi產生的函數。序列密碼的滾動密鑰z0=f（k，σ0）由函數f、密鑰k和指定的初態σ0完全確定。輸入加密器的明文影響加密器中內部記憶元件的存儲狀態，因此σi（i>0）可能依賴于k，σ0，x0，x1，…，xi-1等參數的變化而變化。因此序列密碼是有記憶性的。

序列密碼通常被劃分為同步序列密碼和自同步序列密碼兩大類。

同步序列密碼的密鑰序列的產生獨立于明文消息和密文消息。此時，zi=f(k，σi)與明文字符無關，密文字符ci=Enczi(pi)也不依賴此前的明文字符。因此，可將同步序列密碼的加密器分成密鑰流生成器和加密變換器兩個部分，如圖1-13所示。

自同步序列密碼的密鑰序列的產生是密鑰及固定大小的以往密文位的函數，也稱非同步序列密碼，其加解密流程如圖1-14所示。自同步序列密碼的加密過程可以用下列公式來描述：

σi=(ci-t，ci-t+1，…，ci-1)

zi=g(σi，k)

ci=h(zi，mi)

其中，σi=(ci-t，ci-t+1，…，ci-1)是初始狀態；k是密鑰；g是產生密鑰序列zi的函數；h是將密鑰序列zi和明文mi組合產生密文ci的輸出函數。

1.2.3 公鑰密碼：密碼學歷史上最偉大的發明

隨著計算機和網絡通信技術的迅速發展，保密通信的需求也越來越廣泛，對稱密碼體制的局限性也日益凸顯，主要表現在密鑰分配的問題上，即發送方如何安全、高效地將密鑰傳送至接收方。此外，采用對稱密碼體制，在有多個用戶的網絡中，任何兩個用戶之間都需要有共享的密鑰，當網絡中的用戶量很大時，密鑰的產生、保存、傳遞、使用和銷毀等各個方面都變得十分復雜，存在安全隱患。

1976年，Diffie和Hellman提出了公鑰密碼的思想，基于此思想建立的密碼體制，被稱為公鑰密碼體制，也稱非對稱密碼體制。公鑰密碼算法中的加密算法也被稱為非對稱加密，因為加密和解密使用不同的鑰匙，其中一個公開的，稱為公開密鑰（Public-Key），簡稱公鑰，用于加密；另一個是用戶私有的，稱為私鑰（Private-Key），用于解密，如圖1-15所示。

公鑰密碼體制加密過程包括如下4步。

1）接收者產生一對鑰匙pk、sk，其中pk是公鑰，sk是私鑰。

2)接收者將加密的公鑰pk予以公開，解密的私鑰sk自己保存。

3)發送者使用接收者公鑰加密密文m，表示為c=Encpk(m)，其中c是密文，Enc是加密算法。

4)接收者接收到密文c后，用自己的sk解密，表示為m=Decsk(c)，其中Dec是解密算法。

因為只有接收方知道自身的私鑰sk，因此其他人都無法對c解密。公鑰密碼加密和解密結構圖如圖1-16所示。

RSA算法是經典的非對稱加密算法，由麻省理工學院三位年青學者Rivest、Shamir和Adleman在1978年用數論構造，后來被廣泛稱之為RSA體制，其安全性基于數論中大整數因式分解的困難性。

1.2.4 密碼學哈希

哈希函數（Hash Function）是密碼學中用途最多的密碼算法之一，在消息摘要、網絡協議等諸多領域得以應用。哈希函數H將任意長度的數據塊M作為輸入，生成固定長度的哈希值h=H（M）作為輸出。在密碼學中，一個性質優良的哈希函數應當具有以下特點：對于不同的輸入，哈希函數應當使輸出結果均勻分布于哈希值域，并且讓哈希結果看起來隨機。對于輸入的極小改動都會引發哈希值的極大改變。

在實際應用中，密碼學哈希函數有以下安全性需求：抗原像攻擊，給定任意的哈希值h，找到對應的哈希函數，輸入M是計算上不可行的；抗第二原像攻擊，給定輸入M1，找到M2≠M1且H(M1)=H(M2)是計算上不可行的；抗碰撞攻擊，找到任意的M1和M2，使得H(M1)=H(M2)；偽隨機性，哈希函數的輸出能滿足偽隨機判定。如果一個哈希算法滿足抗原像攻擊和抗第二原像攻擊，就稱為弱哈希函數，在此基礎上如果滿足抗碰撞攻擊，則稱為強哈希函數。

1.密碼學哈希的應用

哈希函數可以用來驗證消息或是文件的完整性。通過比對傳輸前后消息的哈希值是否一致可以快速地判斷消息或是文件是否有被篡改或是數據丟失。當哈希函數用于消息認證時，消息的哈希值通常被稱為消息摘要。同樣，這一概念可以拓展到對任意數據的認證，例如，對存儲中的文件進行快速分塊檢查，確保文件沒有被篡改，或是對于網絡下載數據進行完整性檢驗，確保文件通過網絡傳輸后的完整性。由于消息摘要的長度遠遠小于消息本身，因此通過比對消息摘要可以更快地實現消息或文件的完整性驗證。

此外，由于密碼學哈希具有抗原像攻擊和抗第二原像攻擊的良好性質，通常還被用于產生單向口令文件。在操作系統中，為了防止惡意攻擊者獲得口令文件后獲取用戶口令，需要將用戶口令的哈希值作為口令文件進行存儲。每次用戶輸入口令時，操作系統首先生成輸入口令的哈希值，再將該哈希值與口令文件中的哈希值進行比對。這樣一來，攻擊者即使掌握了口令文件，由于密碼學哈希具有抗原像攻擊的性質，攻擊者無法復現出用戶口令，使得用戶口令的安全性得到了保障。大多數系統目前都采用了這樣的口令保護機制。

除此之外，密碼學哈希還可用于偽隨機數發生器和構建偽隨機函數，在此基礎上構造的偽隨機函數可以用來生成對稱密碼中的密鑰。

2.常見的密碼學哈希

MD5是Ronald Linn Rivest在1991年設計的，用來取代以前的MD4算法，輸出128比特的哈希值。隨著近年來密碼學研究的不斷深入以及計算機硬件的不斷進步，對MD5的碰撞攻擊可以在幾秒鐘內計算出來，這使得MD5算法不適合大多數密碼學哈希的適用場景。

SHA（通常也被稱作SHA-0）是由美國國家標準與技術研究所（NIST）設計，并于1993年作為聯邦信息處理標準發布的。在隨后的應用實踐中被發現存在安全缺陷，1995年，NIST發布了SHA-0的改進版SHA-1，SHA算法的基本框架與MD4類似。2002年，NIST發布了修訂版的SHA-2算法，其中包括了SHA-256、SHA-384和SHA-512，三種算法分別產生256、384和512比特的哈希值。2010年，一項研究表明SHA-1的安全性并沒有理論上的那么可靠，大約需要280次搜索便可以找到一個碰撞，這也加速了目前應用領域從SHA-1到SHA-2的過渡。

SM3是一種中國密碼哈希函數標準，于2010年12月17日由國家密碼管理局發布。在商用密碼體系中，SM3可用于數字簽名及驗證、消息認證碼生成及驗證、隨機數生成等算法中。SM3算法作為一種公開哈希算法，其安全性及效率與SHA-256相當。

1.2.5 消息認證碼

消息認證碼（Message Authentication Code，MAC）是密碼學中的一種認證技術。MAC函數的形式化定義如下：

T=MAC(K，M)

式中，T表示生成的消息認證標記（Tag），K表示發送方與接收方的密鑰，M表示發送方發送的任意長度的消息。通常消息認證碼是一個固定長度的短數據塊，由密鑰和消息產生并附加在消息之后，與消息一起從發送方傳遞到接收方。接收方對收到的消息進行和發送方一樣的計算，通過比較計算出的消息認證碼T′與接收到的T是否相等，實現消息認證。

消息認證包含兩方面的信息確認：一方面接收方可以驗證消息本身并沒有被修改，如果存在中間攻擊者修改了消息內容，由于攻擊者不知道密鑰K，無法通過修改后的消息生成新的消息認證碼T′使得其與收到的消息認證碼T相等；另一方面，接收方驗證了消息發送方的身份，這是由于其他人都不知道消息認證碼的密鑰，因此其他人不能生成正確的T。

在MAC函數中，由于K是發送方和接收方共享的密鑰，雙方均能正向生成T，因此MAC函數不能作為數字簽名算法。這也意味著消息的發送方和接收方必須在初始化通信之前就密鑰達成一致，這與對稱加密的情況相同。

1.MAC函數的性質

在討論MAC函數的安全性時需要從多方面考慮，分析其可能面對的各種類型的攻擊。由于MAC算法往往是公開的，因此假設攻擊者知道MAC函數，卻不知道收發雙方的密鑰K，一個安全的MAC函數應當具有以下三條性質：①對于任意M和對應的T，攻擊者構造出M′使得MAC(K，M)=MAC(K，M′)=T是計算上不可行的；②對于不同的消息輸入，MAC函數應當使輸出結果T均勻地分布于消息認證碼空間，即對于隨機選擇的M1、M2，Pr［MAC(K，M1)=MAC(K，M2)］=2-n，其中n是消息認證碼的位數；③對于消息的任意變換f都保持輸出的隨機性，即Pr［MAC(K，M)=MAC(K，f(M))］=2-n。

第一條性質要求在攻擊者不知道密鑰的情況下無法構造出與給定的MAC相匹配的一個新消息。第二條性質使得針對MAC算法的窮舉攻擊代價與消息認證碼值域大小線性相關，窮舉攻擊者需要O(2n)步才能找到給定MAC對應的消息。第三條性質要求MAC函數對于消息的各個部分應當是公平的，攻擊者無法通過消息的某個部分或是消息的某個結構對MAC函數發起攻擊。

2.常見的MAC算法

常見的MAC算法主要分為兩類：基于哈希函數的MAC算法（Hash-based MAC，HMAC）和基于密碼的MAC算法（Cipher-based MAC，CMAC）。

密碼學哈希函數的執行速度比較快，并且由于密碼學哈希函數擁有廣泛的適用性，現有的哈希函數庫比較完備，HMAC算法在很長一段時間內被廣泛討論。但是由于哈希函數本身在設計時并不依賴密鑰，所以需要對原有的哈希方案進行改進。目前，基于改進后帶密鑰的HMAC方案已被廣泛應用，其作為NIST的標準（FIPS 198），是IP協議族中的重要組成部分，并且在SSL協議中也有使用。

CMAC算法（也被稱為OMAC1）是一種基于分組密碼的MAC算法，被NIST于2005年作為標準發布。它是CBC-MAC算法的改進，CBC-MAC算法只保障固定長度消息算法的安全性，而CMAC算法可以保障任意長度消息算法的安全性。

1.2.6 數字簽名：替代手寫簽名

數字簽名是公鑰密碼發展過程中的一個重要產物，不同于一般的公鑰加解密方案，數字簽名無需保證消息的機密性，卻能保證消息對發送方身份和數據完整性的認證。相較于上一節中提到的消息認證，數字簽名具有不可否認性，也就是說，只要發送方對某消息進行了數字簽名，就無法否認自己曾經發送過該條消息。

在消息認證的方案中，由于通信雙方共享消息認證碼的生成密鑰，接收方可以偽造任意消息的消息認證碼并稱消息由發送方發出。此外，由于接收方擁有偽造消息的能力，所以無法證明發送方是否發送過某條消息，進而發送方可以否認發送過的某條消息。在收發雙方不能完全誠實可信的情況下，為了實現消息認證碼所無法實現的功能，數字簽名必須具備以下的性質：能夠驗證簽名者的身份和簽名的時間戳；能夠認證被簽名的消息內容的完整性；簽名能夠被第三方所驗證。

數字簽名方案的形式化定義通常包括三個算法：密鑰生成算法、簽名算法和簽名驗證算法。密鑰生成算法從密鑰空間中隨機選擇一個私鑰，輸出私鑰和相應的公鑰。簽名算法接收消息和私鑰作為輸入，產生消息對應的簽名。簽名驗證算法以消息、公鑰和簽名作為輸入，根據簽名是否通過驗證輸出接收或拒絕。

公鑰密碼體制中數字簽名過程包括如下幾步。

1）簽名者產生一對鑰匙pk、sk，其中pk是公鑰，sk是私鑰。

2)簽名者將驗證用的公鑰pk予以公開，簽名的私鑰sk自己保存。

3)簽名者使用私鑰sk對消息m進行簽名，表示為σ=Signsk(m)，其中σ是簽名，Sign是簽名算法。驗證者接收到消息和簽名對（m，σ)后，用簽名者的公鑰pk驗證，表示為0/1=Verifypk(m，σ)，其中Verify是驗證算法，1表示驗證成功，0表示驗證失敗。

數字簽名算法（Digital Signature Algorithm，DSA）的結構如圖1-17所示。

數字簽名算法被美國NIST作為數字簽名標準（Digital Signature Standard，DSS），是Schnorr和ElGamal兩種簽名算法的變種，其安全性基于整數有限域離散對數難題。