2.1 密碼學的基本概念

密碼學是一個非常龐大而復雜的信息處理系統，涉及信息的機密性、完整性、認證性、不可否認性等許多方面。密碼學中加密和解密信息的主要目的是使得授權人員以外的人無法讀取信息。

被加密的消息稱為明文，明文經過加密變換成為另一種形式，稱為密文。對明文進行加密操作時所采用的一組規則稱為加密算法，對密文進行解密操作時所采用的一組規則稱為解密算法。加密算法和解密算法都依賴于一組秘密參數，分別稱為加密密鑰和解密密鑰。加密算法和解密算法統稱為密碼算法。密碼算法可以根據密鑰的特點分為對稱密鑰算法和非對稱密鑰算法。對稱密鑰算法也稱為私鑰密碼算法，非對稱密鑰算法也稱為公鑰密碼算法。

在消息傳輸或處理系統中，除了合法的用戶以外，還存在通過各種方法竊取機密信息的攻擊者，他們通過分析已經得到的算法信息和截獲的信息，推斷出密鑰或明文，這一過程稱為密碼分析。如果攻擊者通過一定的明文和密文信息能夠獲得密鑰信息，那么密碼就是不安全的。根據密碼分析者對明文和密文掌握的程度，攻擊方式可以分為5種：唯密文攻擊、已知明文攻擊、選擇明文攻擊、選擇密文攻擊、選擇文本攻擊。

2.1.1 保密通信模型

在不安全的信道上實現安全的通信是密碼學研究的基本問題。消息發送者對需要傳送的消息進行數學變換處理，然后在不安全的信道上進行傳輸，接收者在接收端通過相應的數學變換處理得到信息的正確內容，而信道上的消息截獲者，雖然可能截獲到數學變換后的消息，但無法得到消息本身。圖2-1展示了一個基本的保密通信模型。

一般情況下，在密碼算法具體實現過程中，加密密鑰和解密密鑰是成對使用的，而且是一一對應的關系。根據由加密密鑰得到解密密鑰的算法復雜度的不同，密鑰算法又可分為對稱密鑰算法和非對稱密鑰算法。

2.1.2 密碼算法分類

密碼算法的分類方法有很多。按照是否能進行可逆的加密變換，密碼算法可以分為單向函數密碼算法和雙向函數密碼算法。如果根據對明文信息的處理方式不同，密碼算法可以分為序列密碼算法和分組密碼算法。典型的密碼算法的分類方法是按照密鑰的使用策略的不同將其分為對稱密碼算法和非對稱密碼算法。下面將分別介紹對稱密碼算法和非對稱密碼算法以及典型的加解密算法，并對典型的序列密碼算法和分組密碼算法做簡要介紹。

對稱密碼算法是一種傳統密碼算法。在對稱加密系統中，加解密過程采用相同的密鑰，即使二者不同，也能夠由其中的一個很容易地推導出另一個，所以對稱密碼算法也稱為私鑰密碼算法。對稱密碼算法的優點是運算速度比較快、具有很高的吞吐率、使用的密鑰長度相對較短、密文與明文的長度相同或擴張較小，是目前用于信息加密的主要算法。對稱密碼算法的缺點是密鑰的分發需要安全通道、密鑰量大、難管理、不能解決不可否認的問題。

非對稱密碼算法也稱為公鑰密碼算法，在這種密碼算法中，加密密鑰和解密密鑰是不同的，加密密鑰是公開的而且由加密密鑰去推導解密密鑰是不可行的。非對稱密碼算法簡化了密鑰分發和管理過程。由于在對稱密碼算法中，加解密密鑰相同，通信雙方必須妥善保管他們共同的密鑰，從而保證數據的機密性與完整性。當用戶數量龐大且分布很廣時，密鑰的分發和保存就成為問題，密鑰的安全性嚴重影響著加密系統的安全性。在非對稱密碼算法中，如果兩個用戶要交換數據，發送方會用接收方的公鑰對數據進行加密，接收方則用自己的私鑰來解密。這一過程中，公鑰是可以公開的，用戶只要保管好自己的私鑰即可，因此加密密鑰的分發將變得十分簡單。與對稱密碼算法相比，非對稱密碼算法的缺點是加密解密的算法一般比較復雜，密鑰對的生成與加解密速度也比較慢；同等安全強度下，非對稱密碼算法需要的密鑰位數要多一些。因此，實際網絡系統中的加密普遍采用非對稱和對稱密碼相結合的混合加密算法，即加解密時采用對稱密碼，密鑰傳送則采用非對稱密碼。這樣既解決了密鑰管理的難題，又提升了加解密的速度。

非對稱密碼算法在密鑰分發和管理、鑒別認證、不可否認性等方面均有廣泛應用。典型的非對稱密碼算法有RSA、橢圓曲線密碼算法（ECC）、ElGamal公鑰加密算法和NTRU公鑰加密算法等。

序列密碼一次只對明文消息的單個字符進行加解密變換。分組密碼將明文消息編碼表示后的二進制序列劃分成固定大小的組，每組分別在密鑰控制下進行加解密變換。典型的分組密碼算法有數據加密標準（Data Encryption Standard，DES）算法及其變形三重DES（Triple DES）、廣義DES（GDES）、AES（Advanced Encryption Standard）、RC6和IDEA算法等。典型的序列密碼算法有RC4、A5和HC算法等。

2.1.3 古典密碼簡介

密碼學的發展歷史大致分為3個階段：古典密碼時期、近代密碼時期和現代密碼時期。古典密碼歷史悠久，主要分為替換密碼和換位密碼兩種。替換密碼，即明文中每一個字符被替換成密文中的另外一個字符。換位密碼也稱為置換密碼，即明文的字母保持不變，但打亂其順序。盡管這些密碼大都比較簡單，但在今天仍有參考價值。

對稱密碼算法就可以看作是古典密碼算法的延伸。在本節中，我們將舉例介紹兩種典型的古典密碼。

1.凱撒密碼

凱撒密碼作為一種古老的對稱加密算法，在古羅馬的時候就已經很流行，它的基本思想是：通過把字母移動一定的位數來實現加密和解密。

比如，Alice要將明文“mobile internet security”加密成密文，傳送給Bob。為了運算方便，先把字母進行數字化。圖2-2展示了字母與數字的映射關系。

加密過程如下。

1）Alice先將明文“mobile internet security”中的字母根據圖2-2的映射關系轉換為數字：（12，14，1，8，11，4，8，13，19，4，17，13，4，19，18，4，2，20，17，8，19，24）。

2）加密之前，雙方需要協商一個密鑰。于是Alice與Bob商定加密方式為明文字母后移6位，即加密密鑰及解密密鑰同為K=6。

3）開始加密：將明文字母映射得到的數字代入加密函數E（m）=m+6（mod 26）中計算得到：（18，20，7，14，17，10，14，19，25，10，23，19，10，25，24，10，8，0，23，14，25，4），然后把這些數字根據圖2-2的映射關系替換成字母即可得到密文（s，u，h，o，r，k，o，t，z，k，x，t，k，z，y，k，i，a，x，o，z，e），這就是加密后的結果。

4）解密其實就是上述加密過程的逆過程：Bob收到密文“suhorkotzkxtkzykiaxoze”，然后將密文按照圖2-2的映射關系轉換為：（18，20，7，14，17，10，14，19，25，10，23，19，10，25，24，10，8，0，23，14，25，4）。使用解密函數D（c）=c-6（mod 26）將密文轉換后的數字代入計算，得到（12，14，1，8，11，4，8，13，19，4，17，13，4，19，18，4，2，20，17，8，19，24），即可還原出明文“mobile internet security”。

凱撒密碼繼續擴展就可以得到移位密碼，其與置換密碼是現代密碼學的基石。移位密碼可以用數學表達式表示為：E（m）=ax+b，其中a和b為整數且a與26互質。從式中可以看出，移位密碼其實就是在凱撒密碼中增加一個系數。

2.置換密碼

置換密碼是通過簡單的換位來達成加密。比如，Alice想用置換密碼來加密與Bob傳遞信息，事先約定密鑰為一串字母“KEYWORD”。圖2-3所示，把A到Z中前面的字母用KEYWORD替換，后面又補充了A到Z（去掉了KEYWORD中重復的字母）。這樣就形成了加解密的字母置換表，實際中A到Z可以置換成任意的字母。這個字母置換的過程其實就是加密。

相應的解密過程的字母置換表就如圖2-4所示，將A替換成H，B替換成I，依此類推即可實現解密。

現在，Alice想傳遞的信息明文是：M= “MONOALPHABETTICSUBSTITUTIONCIPHER”，要使用上面的置換密碼加密，對照圖2-3所示的加密過程的字母置換表就可以得到密文：C=“HJIJKGLAKEOQBYPSEPQBQSQBJIYBLAON”。如果需要對密文C進行解密，對照圖2-4所示的解密過程的字母置換表就可以得到明文M。

2.1.4 密碼算法的安全性

本節將從信息論和復雜度理論的角度來描述密碼算法的安全性。對于所有的密碼算法，安全性都是其重要的評價標準。這里所說的“安全性”，是指該密碼系統對于破譯攻擊的抵抗力強度。密碼學家一直在尋求刻畫密碼算法安全性的理論證明方法，目前評價密碼算法安全性的方法有兩種：無條件安全和有條件安全。無條件安全又稱為理論上安全性，有條件安全又稱為實際安全性。很多密碼算法的安全性并沒有在理論上得到嚴格證明，只是在算法思想得到實現之后，經過眾多密碼專家多年來的攻擊都沒有發現其弱點，沒有找到破譯它的有效方法，從而認為它在實際上是安全的。

我們定義一個五元組（P，C，K，E_k（），D_k（））來表示一個密碼系統，其中P、C和K分別代表明文空間、密文空間和密鑰空間，E_k（）代表加密函數，D_k（）代表解密函數。針對這一系統，若具有理論安全性，即具有完善保密性或無條件安全性，那么就意味著明文隨機變量P和密文隨機變量C相互獨立。

為了用數學語言描述密碼算法的保密性，下面假定明文P、密文C、密鑰K都是隨機變量；H（·）表示熵；H（·|·）表示條件熵；I（·；·）表示互信息。由于C=E_k（P）；P=D_k（C）。因此，（P，K）唯一地確定了C，而（C，K）也唯一地確定了P。用信息論的語言可表示為：

H（P|CK）=0

H（C|PK）=0

如果式I（P；C）=0成立，即P與C相互獨立，此時我們稱密碼算法是理論上安全的，根據信息論的原理，可以推導出對于完善保密的密碼算法必然滿足

H（K）≥H（P）

這一結論表明，對于完善保密的密碼算法，其密鑰的不確定性要不小于明文消息的不確定性。比如，當明文P是n位長的均勻分布隨機變量，為了達到完善保密，密鑰K的長度必須至少是n位；而且，為了用n位長的密鑰達到完善保密，密鑰也必須是均勻分布的隨機變量。這就意味著完善保密的密碼算法需要消耗大量的密鑰。

1949年，信息論創始人香農（Shannon）證明了“一次一密”算法，即密鑰長度和明文長度一樣長的密碼算法是無條件安全的，具體證明過程可參考查看現代密碼學的書籍，這里不做詳細論述。例如，當明文P與密鑰K是同長度同分布的隨機變量，加密算法為C=P⊕K，其中⊕為逐位異或運算。由于⊕是群運算，那么密文C也是具有同樣長度和分布的隨機變量，且P和C相互獨立，這就構成了一種理論上安全的密碼算法。但在“一次一密”算法中，通信雙方必須保證在每一次傳遞秘密消息時，所用的密鑰對于攻擊者來說都是完全未知的。也就是，每當傳遞一個新的消息，必須首先更換密鑰，這種密碼算法如果被正確使用，它就是理論上不可破譯的。但是，由于密鑰生成比較困難且不能重復使用，而密鑰分發又是一個非常復雜的問題，這就限制了它的商用價值。

密碼算法還有一種安全稱為“計算上是安全的”，即指破解此密碼系統是可行的，但是使用已知的算法和現有的計算工具不可能完成攻擊所需的計算量。計算安全性是將密碼算法的安全性問題與公認的數學難題掛鉤，例如，密鑰求解問題和某個NP問題。在實際場景中考慮密碼算法安全性時，還需考慮破解一個密碼系統所花費的成本不能超過被加密信息本身的價值，且破譯的時間不能超過被加密信息的有效生命周期。密碼算法是安全體系的基石，而密碼算法的安全性依賴于密鑰的安全性。從前面的介紹可知，某系統的保密強度能達到理論上的不可破譯是最好的，否則也要求能達到實際的不可破譯性，即破譯該系統所付出的代價大于破譯該系統后獲得的收益。