AES 加密算法的原理詳解

來源：https://www.biaodianfu.com/aes.html

數據加密標準（Data Encryption Standard: DES）的密鑰長度是 56 比特，因此算法的理論安全強度是 256。但二十世紀中後期正是計算機飛速發展的階段，元器件製造工藝的進步使得計算機的處理能力越來越強，DES 將不能提供足夠的安全性。1997 年 1 月 2 號，美國國家標準技術研究所（National Institute of Standards and Technology: NIST）宣佈希望徵集高級加密標準（Advanced Encryption Standard: AES），用以取代 DES。AES 評判要求：

AES 得到了全世界很多密碼工作者的響應，先後有很多人提交了自己設計的算法。第一輪共有 15 種算法入選，其中 5 種算法入圍了決賽，分別是：Rijndael，Serpent，Twofish，RC6 和 MARS。又經過 3 年的驗證、評測及公衆討論之後 Rijndael 算法最終入選。Rijndael 是一個分組密碼算法族，由比利時學者 Joan Daemen 和 Vincent Rijmen 所提出的，算法的名字就由兩位作者的名字組合而成。其分組長度包括 128 比特、160 比特、192 比特、224 比特、256 比特，密鑰長度也包括這五種長度，但是最終 AES 只選取了分組長度爲 128 比特，密鑰長度爲 128 比特、192 比特和 256 比特的三個版本。

Rijndael 的優勢在於集安全性、性能、效率、可實現性及靈活性與一體。Rijndael 設計思想：

AES 的算法原理

加密算法的一般設計準則

對 Rijndael 算法來說解密過程就是加密過程的逆向過程。下圖爲 AES 加解密的流程，從圖中可以看出：1）解密算法的每一步分別對應加密算法的逆操作，2）加解密所有操作的順序正好是相反的。正是由於這幾點（再加上加密算法與解密算法每步的操作互逆）保證了算法的正確性。

Rijndael 算法是基於代換 - 置換網絡（SPN，Substitution-permutation network）的迭代算法。明文數據經過多輪次的轉換後方能生成密文，每個輪次的轉換操作由輪函數定義。輪函數任務就是根據密鑰編排序列（即輪密碼）對數據進行不同的代換及置換等操作。

輪函數

我們已經得知輪函數主要包含 4 種運算，但不同的運算輪所做的具體運的算組合並不相同。主要區別是初始輪（Round: 0）和最後一輪（Round: Nr），所有中間輪的運算都是相同的，會依次進行 4 種運算，即：

Rijndael 算法支持大於 128 位的明文分組，所以需要列數更多的矩陣來描述。Rijndael 輪函數的運算是在特殊定義的有限域 GF(256) 上進行的。有限域（Finite Field）又名伽羅瓦域（Galois field），簡單言之就是一個滿足特定規則的集合，集合中的元素可以進行加減乘除運算，且運算結果也是屬於此集合。根據 Rinjdael 算法的定義，加密輪數會針對不同的分組及不同的密鑰長度選擇不同的數值：

AES 標準只支持 128 位分組（Nb = 4）的情況。AES 標準算法將 128 位的明文，以特定次序生成一個 4×4 的矩陣（每個元素是一個字節，8 位），即初始狀態（state），經由輪函數的迭代轉換之後又將作爲下一輪迭代的輸入繼續參與運算直到迭代結束。

輪函數拆解：字節代換（Substitute Bytes）

字節代換（SubBytes）是對 state 矩陣中的每一個獨立元素於置換盒（Substitution-box，S 盒）中進行查找並以此替換輸入狀態的操作。字節代換是可逆的非線性變換，也是 AES 運算組中唯一的非線性變換。字節代換逆操作也是通過逆向置換盒的查找及替換來完成的，主要功能是通過 S 盒完成一個字節到另外一個字節的映射。

S 盒是由一個有限域 GF(256)上的乘法求逆並串聯線性仿射變換所構造出來的，不是一個隨意構造的簡單查詢表。S 因其運算複雜，衆多的 AES 軟件及硬件實現直接使用了查找表 (LUP, Look-up table)，但查詢表的方式並不適合所有場景，針對特定的硬件最小化面積設計需求，則要採用優化的組合邏輯以得到同價的 S 盒替換。盒是事先設計好的 16×16 的查詢表，即 256 個元素。S 盒用於提供密碼算法的混淆性。S 盒的詳細構造方法可以參考文獻。這裏直接給出構造好的結果，下圖(a) 爲 S 盒，圖 (b) 爲 S-1（S 盒的逆）。S 和 S-1 分別爲 16×16 的矩陣，完成一個 8 比特輸入到 8 比特輸出的映射，輸入的高 4-bit 對應的值作爲行標，低 4-bit 對應的值作爲列標。

輪函數拆解：行移位（Shift Rows）

行移位主要目的是實現字節在每一行的擴散，屬於線性變換。行移位是一個 4×4 的矩陣內部字節之間的置換，用於提供算法的擴散性。

  1. 正向行移位

正向行移位用於加密，其原理圖如下。其中：第一行保持不變，第二行循環左移 8 比特，第三行循環左移 16 比特，第四行循環左移 24 比特。假設矩陣的名字爲 state，用公式表示如下：state’[i][j] = state[i][(j+i)%4]; 其中 i、j 屬於 [0,3]。

  1. 逆向行移位

逆向行移位即是相反的操作，即：第一行保持不變，第二行循環右移 8 比特，第三行循環右移 16 比特，第四行循環右移 24 比特。用公式表示如下：state’[i][j] = state[i][(4+j-i)%4]; 其中 i、j 屬於 [0,3]。

輪函數拆解：列混合（Mix Columns）

列混合是通過將 state 矩陣與常矩陣 C 相乘以達成在列上的擴散，屬於代替變換。列混合是 Rijndael 算法中最複雜的一步，其實質是在有限域 GF(256) 上的多項式乘法運算。

  1. 正向列混淆

正向列混淆的原理圖如下：

根據矩陣的乘法可知，在列混淆的過程中，每個字節對應的值只與該列的 4 個值有關係。此處的乘法和加法都是定義在 GF(28) 上的，需要注意如下幾點：

下面舉一個例子，假設某一列的值如下圖，運算過程如下：

在計算 02 與 C9 的乘積時，由於 C9 對應最左邊的比特爲 1，因此需要將 C9 左移一位後的值與 (0001 1011) 求異或。同理可以求出另外幾個值。

  1. 逆向列混淆

逆向列混淆的原理圖如下：

由於：

說明兩個矩陣互逆，經過一次逆向列混淆後即可恢復原文。

輪函數拆解：輪密鑰加（Add Round Key）

密鑰加是將輪密鑰簡單地與狀態進行逐比特異或。這個操作相對簡單，其依據的原理是 “任何數和自身的異或結果爲 0”。加密過程中，每輪的輸入與輪子密鑰異或一次；因此，解密時再異或上該輪的輪子密鑰即可恢復。

密鑰擴展算法（Key Expansion）

AES 加解密中每輪的密鑰分別由種子密鑰經過密鑰擴展算法得到。算法中 16 字節的明文、密文和輪子密鑰都以一個 4×4 的矩陣表示。

密鑰擴展算法是 Rijndael 的密鑰編排實現算法，其目的是根據種子密鑰（用戶密鑰）生成多組輪密鑰。輪密鑰爲多組 128 位密鑰，對應不同密鑰長度，分別是 11，13，15 組。

密鑰擴展的原理圖如下：

密鑰擴展過程說明：

  1.  將種子密鑰按圖 (a) 的格式排列，其中 k0、k1、……、k15 依次表示種子密鑰的一個字節；排列後用 4 個 32 比特的字表示，分別記爲 w[0]、w[1]、w[2]、w[3]；

  2.  按照如下方式，依次求解 w[j]，其中 j 是整數並且屬於 [4,43]；

  3.  若 j%4=0, 則 w[j]=w[j-4]⊕g(w[j-1]), 否則 w[j]=w[j-4]⊕w[j-1]；

函數 g 的流程說明：

  1. a)  將 w 循環左移 8 比特；

  2. b)  分別對每個字節做 S 盒置換；

  3. c)  與 32 比特的常量（RC[j/4],0,0,0）進行異或，RC 是一個一維數組，其值如下。（RC 的值只需要有 10 個，而此處用了 11 個，實際上 RC[0] 在運算中沒有用到，增加 RC[0] 是爲了便於程序中用數組表示。由於 j 的最小取值是 4，j/4 的最小取值則是 1，因此不會產生錯誤。）

RC = {0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1B, 0x36}

動畫演示加密過程：

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/Q8KrgjtdcTdoaVHJaqR0mg

猜你喜歡