應用密碼學概要（一）

密碼學在計算機領域是一個較難理解的主題，充滿較多的概念、數學證明以及資訊理論等領域的知識要求，對於大多數工程師而言，從巨集觀角度上了解密碼學，基本就能應付日常的使用。但通過研究學習發現，如果能對密碼學底層的知識有足夠的瞭解，能更深刻地理解密碼學演算法的底層原理，應付更復雜領域的密碼學應用，做到知其然而知其所以然。本系列文章將嘗試深入淺出地對密碼學相關知識做一次總結，內容涵蓋： 一次性密碼本、DES與AES、分組加密及其模式與安全性探討、流加密、Hash函式與訊息驗證(HMAC)以及HTTPS應用概要。本文將介紹一次性密碼本、DES與AES，其他內容後續陸續更新。

（ 點選原文連結，可跳轉blog閱讀，獲取更好的閱讀體驗）

異或(XOR)

文章的開篇，我們從最簡單的異或說起。異或是一個二元判斷操作，當兩個輸入相同時返回0，相異時返回0。常用符號”⊕”來表示。常見操作定義如下：

1⊕1=0

除了以上定義，異或操作還具有如下屬性：

1. 順序無關性：A⊕(B⊕C)=(A⊕B)⊕C

2. 可交換：A⊕B=B⊕A

3. 任何輸入與自身異或，輸出為0：A⊕A=0

4. 任何輸入與0異或，其結果為其本身：1⊕0=1,0⊕0=0

而基於以上四個屬性，我們可以推導地五條重要的屬性：a⊕b⊕a=b

A⊕B⊕A=A⊕A⊕B(屬性1)

以上定義，除對“0”和“1”的異或操作滿足外，可以推廣到任何多個位的操作。如對兩個數字或兩個字串進行按位異或操作，也均滿足以上定義。

#定義字串按位異或的操作

一次性密碼本(One-Time Pad)

基於以上關於異或的樸素定義，我們可以得到一個“堅不可摧”的加密方式，即：一次性密碼本加密。

如上圖所示，其中P代表明文(plaintext),C代表密文(ciphertext),K代表金鑰(Key)。先通過對明文進行按位異或，將得到密文，完成加密。密文用相同的金鑰進行按位異或，將得到明文資訊，完成解密的操作。 從安全性上來看，攻擊者知道密文C的情況下，可以證明其再沒有K的資訊時，他將不能獲取任何關於明文的資訊，但前提是：

• 金鑰K必須完全隨機

如果，金鑰K不是完全隨機產生，則無法證明其安全性。因為金鑰不真隨機的情況下，明文P與密文C可能存在一定的函式關係，而非完全獨立，即使破解函式關係依舊非常困難，但是卻不是可證明安全的。

• 金鑰K不能複用

  另外一個前提是金鑰不能複用。假設攻擊者獲取了兩份明文P1、P2經用同一金鑰K加密而得到的密文C1和C2，攻擊者只需要將兩份金鑰進行異或操作，即可得到明文的的異或結果。推導如下：

C1⊕C2=(P1⊕K)⊕(P2⊕K)

儘管得到的是P1、P2的異或結果，要獨立分離出P1和P2的準確結果依舊困難，但要注意的是，兩個明文的異或結果依舊會洩漏一些資訊。如下面兩張圖片A、B進行異或，得到的結果幾乎洩漏了所有信息。

金鑰序列不能重用，這意味著每個明文的位都必須有一個金鑰位與其對應，即金鑰長度與明文長度要一樣，這一點在工程實踐上是沒有意義的，這也是一次性密碼本(OTP)在實際中很少使用的原因。

DES與AES

前文說到一次性密碼本，它需要一個與明文長度一樣長的隨機生成的金鑰來完成加密和解密，這種要求在工程實踐上難度很大，接下來我們介紹兩個可以用固定長度金鑰對明文分組進行加密的演算法。

DES

DES是一種用56位金鑰對64位長的明文分組進行加密的方式。

DES是一種對稱加密，加密和解密都使用相同的金鑰。它採取迭代演算法來進行加密，每一次加密過程都包含16輪操作，而每一輪的操作完全相同。只是每一輪的操作會使用不同的子金鑰進行，子金鑰由主金鑰推導而來，上一輪的輸出為下一輪的輸入，整個迭代加密結構被稱為 Feistel網路 ，Feistel網路結構如下：

64位的明文在完成初始轉換後，會被分割成L0與R0左右兩部分，每部分長度為32位，右半部分與生成的子金鑰作為引數傳入f函式，f函式的輸出與左部分異或後作為下一輪的右半部分，而右半部分將直接複製到下一輪的左半部分。即：

R1=f(R0,K1)⊕L0

可見DES的 每一輪只對輸入內容的左半部分加密，右半部分只是簡單複製到下一輪 。

初始置換：

關於初始轉換，本身對加密安全性沒有任何影響，其只是對輸入內容進行按位的位置變變換，如將第1位放置30位，30位放到20位等，逆轉換即為復位。為什麼要這麼做？目前沒有得到可解釋的理由。

f函式：

由上面流程可知，DES中，f函式在安全性上扮演著非常重要的角色。f函式包括以下幾步處理：

1. 位擴充

   位擴充是指將32位的輸入擴充套件為48位，使用查表的方式進行擴充，也稱為 E-盒轉換 。具體轉換方式如下圖所示。 

需要注意的是，E-盒為演算法內的靜態定義，每一次加密過程都用同一E-盒的定義進行擴充。從上圖的擴充過程可知，32個輸入位經過擴充後變為48位，其中正好有16個位出現了兩次，如圖中1號位、4號位、5號位等。但是E-盒保證了 任意一個輸入位都不會再同一個6位的輸出分組中出現兩次 ，如1號位出現在第一個6位分組和最後一個6位分組，4號位出現在第一個6位分組和第二個6位分組，這樣做可以保證一半的輸入位會影響兩個不同的輸出位置，而為什麼以6個位作為分組單位？這與第三步的S-盒替換有關。

1. 與子金鑰K進行異或操作，這一步很簡單，輸入和子金鑰長度都是48，按位異或即可。

2. S-盒替換

   經過前面兩步，輸入已經轉換為48位，而最終的輸出需要轉換為32位，這是通過S-盒轉換來完成的，它通過查表的方式將6位的輸入對映為4位的輸出。DES中定義了8個S-盒，每個S-盒包含2^6=64個4位的值（十進位制：0-15），這64個值分為4行*16列的表格進行儲存。按以下方式讀取S-盒：

• 第一個6位分組讀S-盒1、依次，第8個分組讀S-盒8

• 每個6位分組的最高位盒最低位決定要讀的行，中間四個位決定要讀取的列

如下圖，第五個6位分組的讀取方式：

S-盒轉換給DES演算法帶來了唯一的非線性轉換，即滿足：S(A)⊕S(B)!=S(A⊕B)，它是DES加密過程中最重要的部分。

子金鑰編排

DES的輸入主金鑰是64位的固定長度，而其中每第8個位為前面7個位的奇校驗位，設定奇偶校驗位除了能在金鑰傳輸過程中用於檢驗金鑰傳輸錯誤外，校驗位的存在並沒有增加金鑰空間，對於增強加密安全性沒有幫助。而金鑰完整性校驗，可以由更高階的辦法進行，所以可以認為校驗位的設定是一個比較過時的設計。

由於8位校驗碼的存在，所以DES其實是一個56位的主金鑰加密，56位的主金鑰在每一輪的加密過程中均會生成子金鑰ki，而每一輪子金鑰ki的長度固定是48位。子金鑰生成演算法如下圖所示：

子金鑰生成的演算法裡值得注意的是移位計算，移位計算會在左右兩半部分同時進行，16輪金鑰移動的位數正好為28位(左、右兩半部分的長度)，由此可得到移位前和16輪移位後的金鑰後，結果是一樣的。這為後續解密過程生成字金鑰提供了可逆支援。

解密

DES的解密的重點是， 解密演算法與加密演算法完全一致 ，這主要由金鑰編排與Feistel網路的可逆性決定的。下面分別探討金鑰編排與Feistel網路的可逆性問題。

金鑰編排可逆性

由上面子金鑰的移位計算我們得到了移位前和16輪移位後的金鑰完全一致，即C0=D16,D0=D16。而第16輪的，金鑰由（C16,D16）進行PC-2轉換得來。即：

k16=PC-2(C16,D16)

代入：C0=D16,D0=D16，得：

k16=PC-2(C0,D0)

(C0,D0)是由主金鑰k進行PC-1轉換而得來，所以：

k16=PC-2(PC-1(k))

即主金鑰進行PC-1再進行PC-2，得到第16輪金鑰k16。

k15由(C15,D15)進行PC-2轉換而來，而(C15,D15)由(C16,C16)向右移位(移2位，記R2)而得到,即：

k15=PC-2(C15,D15)

同理可計算k1、k2…k14,只是向右移位的位數有所差異，第一輪不移位，第2、9、16輪右移一位，其他輪右移兩位。

Feistel網路的可逆性

Feistel網路的一個重要特性是 第一輪解密的結果是第16輪加密的逆，並可一次類推，第二輪的解密結果是第15輪加密的逆，直至最後一輪解密結果即為明文。 通過對比DES加密的第一輪和最後一輪:

由第16輪加密過程可知，密文結果為第16輪加密後左右交換與逆初始轉換後而來，所以，對密文進行初始轉換(IP)，即可得第16輪左右交換後的結果,因為初始轉換與逆初始轉換相互抵消，所以第一輪解密結果(DL0,DR0)為：

(DL0,DR0)=IP(C)=(R16,L16)

而L16由R15平移而來，所以：

DL0=R16

接著計算下一輪加密結果(DL1,DR1)

同理，DL1由DR0平移而來，所以

DL1=DR0=R15

根據演算法計算DR1，

DR1=DL0⊕f(DR0,k16)= R16⊕f(L16,k16)

上式中，R15與f(R15,k16)進行了兩次異或，由異或屬性5(見上文， 這一點非常重要，這一點的存在使得f函式的可逆性不是必須的，因為f函式裡的S-盒變化是非線性不可逆的 )，得：

DR1=L15

以上推導即證明了第一輪解密後得到的記過與最後一輪加密前的結果是相等的，即第一輪解密的結果是最後一輪加密的逆。同理可推：

DL(i)=R(16-i）

即： 第i輪的解密結果，為第(16-i)輪的加密的逆 ，由此可知：最後一輪的解密結果即為(R0,L0),(R0,L0)進行左右變化和逆初始轉換後即得到明文。

DES的安全性

說到DES的安全性，我們得先看看DES演算法歷史。

(來源：wiki)

由上述歷史中可知，IBM和NSA共同設計了DES，但是對於金鑰長度問題眾說紛紜，到底是誰，為什麼選擇了56位的金鑰沒有定論。而 56位位的金鑰長度正是DES被認為不安全的主要原因 ，也就是說DES的不安全性不在其演算法設計上，而在於其金鑰長度過短，暴力破解的代價較小。

AES

從上述關於DES歷史的引用中可以看出，DES的演算法是IBM和NSA採取對外保密的方式進行設計的，許多關於演算法設計上的選擇原由，一直到後面才公開。而AES採取了完全相反的方式。1997年，NIST(美國國家標準與技術研究院)向社會公開徵集新的高階密碼標準(AES),並經過多輪評估競選者提交的方案，最終於2001年確認宣佈兩位比利時密碼學家設計的Rijndael方案成為新的高階密碼標準。

AES在方案徵集前確認了一下必須滿足的要求：

• 分組加密，分組塊大小固定為128位（關於分組加密的更多內容，見後文）。

• 支援三種金鑰長度:128位、192位、256位。

• 不同於DES可以在硬體上可以高效實現，在軟體上實現也應該可以高效。

Rijndael基本滿足以上要求，主要區別是Rijndael的分組大小和金鑰長度都可以為128、192和256，而AES只要求分組大小為128。即：

AES(Rijndael，下文所提AES均為Rijndael加密演算法)演算法加密過程如下圖所示：

與DES一樣，AES也採取多輪加密的方式，但是AES的加密輪數不是固定的，與金鑰長度相關， 128位長的金鑰加密輪數是10輪，192位的金鑰加密輪數是12輪，256位的金鑰加密輪數是14輪 。但是AES不具有Feistel網路結構，即加密解密的演算法是不一樣的，其中每一步都必須可以求逆運算來解密。同時AES每輪爹地啊，會加密整個分組(128位),而DES只加密分組的一半，即32位。

AES的每一輪需要經過位元組代換層、擴散層(ShiftRows&MixColumns)、金鑰加法層三層操作，但最後一層不會進行MixColumns的操作，在第一輪開始前需要也需要進行一次金鑰加法層的操作。

金鑰加法層

AES的金鑰加法層很簡單，子金鑰生成器每一輪都會根據主金鑰編排生成一個128位的子金鑰。 子金鑰與當前狀態的資料進行異或即為金鑰加法層的輸出。 由此可見，無論前文的DES，還是AES，金鑰在加密演算法中都只與加密內容進行異或運算，並不會有其他複雜的演算法。

位元組代換層

與DES類似， AES在位元組代換層，提供了非線性變換的S-盒子替換，提供了AES加密過程的唯一非線性元素。 但AES的S-盒是一個雙向對映，這是解密操作所需要的。AES的S-盒是一個256位*8位的固定項對應表，AES每8位進行查表後替換。S-盒如下圖所示：

查表舉例: 

擴散層

在加密過程中設定擴散層是位了將一個明文位變化的影響擴散到多個密文的位置，以達到隱藏明文統計屬性的目的。在AES中的擴散層主要兩個操作:ShitRows(行移位)、MixColumns(列混淆)，這兩個操作均為線性操作，即滿足:OP(A)+OP(B)=OP(A+B)。

ShiftRows操作

在進行ShiftRows操作之前，需要將進行操作的輸入分組劃分為一個矩陣4*4的矩陣，矩陣中每個元素長度為一個位元組(8bit，即128=4*4*8)，然後對矩陣的每一行進行位移。具體演算法如下所示：

MixColumns操作

MixColumn操作採取對ShiftRows後的矩陣的與一個固定矩陣進行相乘(矩陣相乘)後得到。

子金鑰編排

AES的子金鑰編排，以原始主金鑰(長度為128位、192位或156位)為輸入，輸出固定長度為128位，子金鑰的個數等於加密輪數加1，因為在第一輪加密前需要進行一次金鑰加法層的操作。即： 128位的主金鑰，加密輪數是10輪，共生成11個子金鑰，192位的主金鑰，加密輪數是12輪，共生成13個子金鑰，256位的主金鑰，加密輪數是14輪，共生成15個子金鑰。

以128位主金鑰生成為例，流程如下：

128位主金鑰的AES需要11個子金鑰，用元素長度為44的32位的陣列來儲存，表示為W0…W43，陣列中的每一個元素經過如圖中所示計算過程來生成，最終每4個元素組成一個子金鑰，子金鑰長度也正好為128位。即：

K0=(W0,W1,W2,W3)

與之類似，192位主金鑰的AES需要的13個字金鑰用W0…W51的52個元素來儲存，256位主金鑰的AES需要的15個字金鑰用W0…W59的60個元素來儲存，也是每4個元素組成一個128位的子金鑰。

由上述可知，不同的主金鑰長度，只是影響了加密輪數，而每一輪參與加密的子金鑰長度是一致的，都是128位。

從實現上來並不約束是一次性將所有元素全部計算好，還是每一輪計算4個元素來組成子金鑰，因為這是可行的，因為每一輪子金鑰只後向依賴前一輪子金鑰的4個元素。

解密

前文說到，由於AES不是Feistel網路，因此所有層裡的操作必須支援完全逆操作。即位元組代換層、ShiftRows層和MixColumns層都必須支援逆操作，同時子金鑰編排也需要支援逆操作。

金鑰加法層逆向

由於金鑰加法層只是將輸入內容與子金鑰進行異或，所以求逆運算只要將計算後的內容再與該輪子金鑰進行一次異或，即可得原來的輸入。 因為P⊕K⊕K=A。

位元組代換層逆向

位元組代換層的逆計算也很簡單，因為位元組代換層使用S-盒支援反向查詢。反向S-盒如下表：

ShiftRows層逆向

因為ShiftRows只是簡單的向右移位，所逆運算只要相反地左移相應的位即可。

MixColumns層逆向

MixColumns操作是將輸入矩陣與一個固定矩陣進行相乘而得到，而根據矩陣運演算法則，將結果乘以該固定矩陣的逆矩陣即可還原得到輸入內容。

子金鑰編排的可逆性

前文說到，AES的每一步計算都是可以進行逆計算的，在每一輪的逆計算過程中，都需要使用與對應輪的子金鑰參與解密，只是順序相反，即第一輪解密需要最後一輪加密的金鑰，依次，最後一輪解密需要第一輪加密的金鑰。由此可知，只需要在解密前重新按金鑰編排演算法將所有輪次的子金鑰計算得到，在解密時獲取相應輪次的金鑰即可。只是由於需要先計算好所有輪次的子金鑰，而不能像加密那樣動態地計運算元金鑰。