AES對稱密碼演算法介紹(1)——AES的內部結構

08-26

7 人贊了文章

AES密碼是目前使用最廣泛的對稱密鑰演算法。

作為AES密碼演算法的第一講，我們將從AES的內部結構開始講解。本篇將涵蓋足夠讀者自己編寫等效程序的全部細節，但不包含數學證明、安全性證明、抵抗各種攻擊之類的內容。

本文中一些部分可能需要一定的數學背景知識，如果您在閱讀本文過程中對其感到困難，可以參考本系列的第零講——必需數學知識簡介，強烈建議先看，即使我知道看數學這種東西非常讓人頭疼，不然可能看不懂本文。

請注意：在密碼學實踐中，我們並不建議用戶自己設計密碼學演算法或自己編寫程序實現(已經被更專業的團體更完善的實現過了的)密碼學演算法——因為你自己並不能保證避免各種紕漏或錯誤，這可能會引起非常嚴重的安全問題——除非你有非常專業的團隊來嚴格審計你的演算法或代碼。

但是，如果一個學習者能夠自己編寫程序實現演算法的核心功能，那麼這對他/她的演算法學習會有很大的幫助。因此，如果您按照本文自己編寫了AES的等效程序：

請勿在生產環境，或其他對信息安全性有要求的場景中使用！
在未註明「本代碼未經過安全性審計」或類似警示內容的前提下，請勿上傳至開源網站或以其他方式公開。
請遵守您所在地區的各項法律法規，禁止用於非法用途。

AES處理數據的方式是一長段數據，分為多個長度為16位元組(128 bits)的組(也叫塊，英文中多用block一詞)，然後依次處理每一個塊。因此AES不是流密碼(stream cipher)，而是分組密碼(block cipher)。

(當今的AES，是AES競賽優勝者Rijndael的精簡版，相比於原版的Rijndael，其block size即塊大小被限定為了128 bits，而192 bits和256 bits塊大小不再被支持)

AES通過密鑰來加密、解密信息，並且加密和解密過程使用的密鑰完全相同，加密過程和解密過程具有一定的對稱性，因此AES屬於密碼學中的對稱密鑰演算法(symmetric-key algorithm)。AES支持三種密鑰大小(key size)：128 bits、192 bits和256 bits。一般認為其加密強度隨密鑰長度的增大而增大。

圖1 AES的輸入與輸出：AES分組處理一長段數據(圖中只畫出了第一塊)

AES的內部結構由多個層(Layer)構成，每一層都是對整個處理塊16位元組的操作，並且循環多輪進行處理。如下圖所示，加密過程中，AES使用了四種不同類型的層：密鑰加法層(Key Addition Layer)、位元組代換層(Byte Substitution Layer)、ShiftRows層(行位移)和MixColumn層(列混合)。

(後面這兩個通常不翻譯，使用原文，所以我把中文寫到了括弧里。合稱：擴散層，Diffusion Layer)

而在解密過程中，使用的是密鑰加法層(Key Addition Layer)、逆向位元組代換層(Inverse Byte Substitution Layer)、逆向ShiftRows層和逆向MixColumn層。密鑰加法層不需要使用逆向的是因為其本質是按位異或運算(XOR)——「加」一次，再「加」一次即可復原。

圖2 AES流程框圖，左側為加密(從上往下)，右側為解密(從下往上)，中間為密鑰編排(從上往下)

AES的內部並不直接使用提供的密鑰 $k$ ，而是通過密鑰編排(Key Schedule)來產生子密鑰(subkeys) $k_0,k_1,k_2,...,k_r$ ，子密鑰的數量比操作輪數 $r$ 多1。操作輪數 $r$ 僅由密鑰 $k$ 的長度(即key size)決定：

if key_size == 128 { r = 10; }else if key_size == 192 { r = 12; }else if key_size == 256 { r = 14; }

對於加密過程而言：位元組代換層、ShiftRows層、MixColumn層和密鑰加法層依次組成了一輪操作。但是請注意：在第一輪開始前，還要先進行依次密鑰加法操作。而且在最後一輪中，不做MixColumn操作。這兩個特殊的地方，在解密過程中也需要特別留意。

從圖中可見，加密解密過程確實具有非常強的對稱性——解密過程就是加密的逆過程。一般而言，解密過程操作輪的劃分與加密過程保持相同，但順序是密鑰加法層、逆向MixColumn層、逆向ShiftRows層和逆向位元組代換層。所以通常說解密先經歷了缺少MixColumn操作的最後一輪，然後依次經歷倒數第二輪、倒數第三輪……直至正數第一輪，最後還要進行一次密鑰加法操作。(但是在一些實踐中，為了方便會有不同的劃分方式，這並不影響結果，因為只是一個概念上的劃分)

接下來我們把操作中具體的一輪單獨拿出來看看細節。

圖3 加密過程中的一個完整的操作輪

首先128 bits的數據對應16個位元組，即圖中的 $A_0,A_1,A_2,...,A_{15}$ ，每一個位元組都首先經過位元組代換層，產生 $B_0,B_1,B_2,...,B_{15}$ 。位元組代換層又被稱為S盒(S-Box)。S盒將每一個元素都使用具有特殊數學屬性的查找表進行非線性變換。這種變換向數據中引入了混淆。S盒的數學描述如下圖。

圖4 S盒(S-Box)的數學描述

一個位元組正好對應了伽羅瓦域 $GF(2^8)$ 中的一個元素。在 $GF(2^8)$ 上求元素 $A_i$ 的乘法逆元，得到 $M_i$ 。(因為 $0$ 在 $GF(2^8)$ 上沒有乘法逆元，這裡我們補充定義 $0$ 的乘法逆元還是 $0$ )

然後對 $M_i$ 做如下仿射映射，即可得到 $B_i$ ：

$egin{pmatrix}b_0\b_1\b_2\b_3\b_4\b_5\b_6\b_7\end{pmatrix} = egin{pmatrix} 1&0&0&0&1&1&1&1\ 1&1&0&0&0&1&1&1\ 1&1&1&0&0&0&1&1\ 1&1&1&1&0&0&0&1\ 1&1&1&1&1&0&0&0\ 0&1&1&1&1&1&0&0\ 0&0&1&1&1&1&1&0\ 0&0&0&1&1&1&1&1\ end{pmatrix} egin{pmatrix}m_0\m_1\m_2\m_3\m_4\m_5\m_6\m_7\end{pmatrix} + egin{pmatrix}1\1\0\0\0\1\1\0\end{pmatrix} mod 2$

這裡每一個小寫字母代表一個位元組中的一個位(bit)。通常，這裡小寫字母的角標0對應位元組中的最低有效位(least significant bit, LSB)，也是擴展域中的 $x^0$ 係數；角標7對應位元組中的最高有效位(most significant bit, MSB)，也是擴展域中的 $x^7$ 係數。

乘法逆元為AES演算法提供了很高的非線性，提升了其抵抗分析攻擊的能力。仿射變換能「破壞」伽羅瓦域的數學結構，使AES能抵抗一些針對有限域逆元的攻擊方案。

這樣就不難編寫程序來計算出下面的 $GF(2^8)$ 乘法逆元表，然後對其中每一個元素做仿射變換就得到S盒的查找表。

Table-01: GF(2^8)乘法逆元表(十六進位) | 0 1 2 3 4 5 6 7 8 9 A B C D E F---+------------------------------------------------ 0 | 00 01 8D F6 CB 52 7B D1 E8 4F 29 C0 B0 E1 E5 C7 1 | 74 B4 AA 4B 99 2B 60 5F 58 3F FD CC FF 40 EE B2 2 | 3A 6E 5A F1 55 4D A8 C9 C1 0A 98 15 30 44 A2 C2 3 | 2C 45 92 6C F3 39 66 42 F2 35 20 6F 77 BB 59 19 4 | 1D FE 37 67 2D 31 F5 69 A7 64 AB 13 54 25 E9 09 5 | ED 5C 05 CA 4C 24 87 BF 18 3E 22 F0 51 EC 61 17 6 | 16 5E AF D3 49 A6 36 43 F4 47 91 DF 33 93 21 3B 7 | 79 B7 97 85 10 B5 BA 3C B6 70 D0 06 A1 FA 81 82 8 | 83 7E 7F 80 96 73 BE 56 9B 9E 95 D9 F7 02 B9 A4 9 | DE 6A 32 6D D8 8A 84 72 2A 14 9F 88 F9 DC 89 9A A | FB 7C 2E C3 8F B8 65 48 26 C8 12 4A CE E7 D2 62 B | 0C E0 1F EF 11 75 78 71 A5 8E 76 3D BD BC 86 57 C | 0B 28 2F A3 DA D4 E4 0F A9 27 53 04 1B FC AC E6 D | 7A 07 AE 63 C5 DB E2 EA 94 8B C4 D5 9D F8 90 6B E | B1 0D D6 EB C6 0E CF AD 08 4E D7 E3 5D 50 1E B3 F | 5B 23 38 34 68 46 03 8C DD 9C 7D A0 CD 1A 41 1CTable-02: S-Box表(十六進位) | 0 1 2 3 4 5 6 7 8 9 A B C D E F---+------------------------------------------------ 0 | 63 7C 77 7B F2 6B 6F C5 30 01 67 2B FE D7 AB 76 1 | CA 82 C9 7D FA 59 47 F0 AD D4 A2 AF 9C A4 72 C0 2 | B7 FD 93 26 36 3F F7 CC 34 A5 E5 F1 71 D8 31 15 3 | 04 C7 23 C3 18 96 05 9A 07 12 80 E2 EB 27 B2 75 4 | 09 83 2C 1A 1B 6E 5A A0 52 3B D6 B3 29 E3 2F 84 5 | 53 D1 00 ED 20 FC B1 5B 6A CB BE 39 4A 4C 58 CF 6 | D0 EF AA FB 43 4D 33 85 45 F9 02 7F 50 3C 9F A8 7 | 51 A3 40 8F 92 9D 38 F5 BC B6 DA 21 10 FF F3 D2 8 | CD 0C 13 EC 5F 97 44 17 C4 A7 7E 3D 64 5D 19 73 9 | 60 81 4F DC 22 2A 90 88 46 EE B8 14 DE 5E 0B DB A | E0 32 3A 0A 49 06 24 5C C2 D3 AC 62 91 95 E4 79 B | E7 C8 37 6D 8D D5 4E A9 6C 56 F4 EA 65 7A AE 08 C | BA 78 25 2E 1C A6 B4 C6 E8 DD 74 1F 4B BD 8B 8A D | 70 3E B5 66 48 03 F6 0E 61 35 57 B9 86 C1 1D 9E E | E1 F8 98 11 69 D9 8E 94 9B 1E 87 E9 CE 55 28 DF F | 8C A1 89 0D BF E6 42 68 41 99 2D 0F B0 54 BB 16面向人類的使用說明：若輸入位元組的十六進位形式位0xXY，則在表格的縱坐標中定位X，再在縱坐標中定位Y。

在實踐中，S盒的查找表一般是提前計算好然後硬編碼儲存在程序的一個數組中。

接下來是擴散層。擴散層為所有的位提供擴散，它的兩個子層都是線性操作。首先是ShiftRows操作，在位元組級別對數據進行置換，但是看上面的流程圖可能會很混亂，那麼請看下圖。

圖5 ShiftRows操作

將16個S盒變換後的位元組，從上往下、從左到右地寫成了一個矩陣。第一行保持不動，第二行向左滑動1格，第三行向左滑動2格，第四行向左滑動3格，最後在從上往下、從左到右地「讀取」——這就很直觀了。

緊接做MixColumn操作，將每4個位元組進行混合，它的本質是一個矩陣乘法。上面流程圖中將其分開為列向量來繪製，因為每一輸出列(例如 $C_0C_1C_2C_3$ )都只取決於與它對應得那一輸入列(如 $B_0B_5B_{10}B_{15}$ )。 $egin{pmatrix} C_0&C_4&C_8&C_{12}\ C_1&C_5&C_9&C_{13}\ C_2&C_6&C_{10}&C_{14}\ C_3&C_7&C_{11}&C_{15}\ end{pmatrix} = egin{pmatrix} 02&03&01&01\ 01&02&03&01\ 01&01&02&03\ 03&01&01&02\ end{pmatrix} egin{pmatrix} B_0&B_4&B_8&B_{12}\ B_5&B_9&B_{13}&B_1\ B_{10}&B_{14}&B_2&B_6\ B_{15}&B_3&B_7&B_{11}\ end{pmatrix}$ 注意這裡每一個元素運算過程仍然是 $GF(2^8)$ 上的加法和乘法，需要使用 $GF(2^8)$ 的運演算法則，以及使用不可約多項式 $P(x)=x^8+x^4+x^3+x+1$ 進行模約。

舉個簡單又特殊的例子，如果輸入元素全部都是十六進位的25，也就是 $B_i(x)=x^5+x^2+1 (i=0,1,2,...,15)$ ，那麼就是要求解 $egin{pmatrix} C_0&C_4&C_8&C_{12}\ C_1&C_5&C_9&C_{13}\ C_2&C_6&C_{10}&C_{14}\ C_3&C_7&C_{11}&C_{15}\ end{pmatrix} = egin{pmatrix} 02&03&01&01\ 01&02&03&01\ 01&01&02&03\ 03&01&01&02\ end{pmatrix} egin{pmatrix} 25&25&25&25\ 25&25&25&25\ 25&25&25&25\ 25&25&25&25\ end{pmatrix}$

由於 $01*25= 1*(x^5+x^2+1)=x^5+x^2+1 \ 02*25= x*(x^5+x^2+1)=x^6+x^3+x \ 03*25=(x+z)*(x^5+x^2+1)=x^6+x^5+x^3+x^2+x+1$ 故 $C_i=(01+01+02+03)*25=x^5+x^2+1$ 其中 $i=0,1,2,...,15$ 。

最後，密鑰加法層非常簡單，輸入的 $C_0C_1C_2...C_{15}$ 是16位元組(128 bits)，經過密鑰編排之後產生的每一個子密鑰 $k_i$ 也是16位元組(128 bits)，將 $C_0C_1C_2...C_{15}$ 與對應此輪的子密鑰 $k_i$ 做按位異或運算(XOR，即流程圖中的 $oplus$ 符號)即可。

解密過程的操作輪，大家就可以參考下圖，自行理解學習了。

圖6 解密過程中的一個完整的操作輪

這裡給出逆向層的矩陣，注意矩陣中的直接數字是十六進位。 $egin{pmatrix} B_0&B_4&B_8&B_{12}\ B_1&B_5&B_9&B_{13}\ B_2&B_6&B_{10}&B_{14}\ B_3&B_7&B_{11}&B_{15}\ end{pmatrix} = egin{pmatrix} 0E&0B&0D&09\ 09&0E&0B&0D\ 0D&09&0E&0B\ 0B&0D&09&0E\ end{pmatrix} egin{pmatrix} C_0&C_4&C_8&C_{12}\ C_1&C_5&C_9&C_{13}\ C_2&C_6&C_{10}&C_{14}\ C_3&C_7&C_{11}&C_{15}\ end{pmatrix}$

逆向S盒可以通過反查S盒獲得。也可以計算獲得。

圖7 逆向S盒(Inverse S-Box)的數學描述

其中逆向仿射映射為 $egin{pmatrix}m_0\m_1\m_2\m_3\m_4\m_5\m_6\m_7\end{pmatrix} = egin{pmatrix} 0&0&1&0&0&1&0&1\ 1&0&0&1&0&0&1&0\ 0&1&0&0&1&0&0&1\ 1&0&1&0&0&1&0&0\ 0&1&0&1&0&0&1&0\ 0&0&1&0&1&0&0&1\ 1&0&0&1&0&1&0&0\ 0&1&0&0&1&0&1&0\ end{pmatrix} egin{pmatrix}b_0\b_1\b_2\b_3\b_4\b_5\b_6\b_7\end{pmatrix} + egin{pmatrix}1\0\1\0\0\0\0\0\end{pmatrix} mod 2$

完成後的逆向S盒查找表為：

Table-03: 逆向S-Box表(十六進位) | 0 1 2 3 4 5 6 7 8 9 A B C D E F---+------------------------------------------------ 0 | 52 09 6A D5 30 36 A5 38 BF 40 A3 9E 81 F3 D7 FB 1 | 7C E3 39 82 9B 2F FF 87 34 8E 43 44 C4 DE E9 CB 2 | 54 7B 94 32 A6 C2 23 3D EE 4C 95 0B 42 FA C3 4E 3 | 08 2E A1 66 28 D9 24 B2 76 5B A2 49 6D 8B D1 25 4 | 72 F8 F6 64 86 68 98 16 D4 A4 5C CC 5D 65 B6 92 5 | 6C 70 48 50 FD ED B9 DA 5E 15 46 57 A7 8D 9D 84 6 | 90 D8 AB 00 8C BC D3 0A F7 E4 58 05 B8 B3 45 06 7 | D0 2C 1E 8F CA 3F 0F 02 C1 AF BD 03 01 13 8A 6B 8 | 3A 91 11 41 4F 67 DC EA 97 F2 CF CE F0 B4 E6 73 9 | 96 AC 74 22 E7 AD 35 85 E2 F9 37 E8 1C 75 DF 6E A | 47 F1 1A 71 1D 29 C5 89 6F B7 62 0E AA 18 BE 1B B | FC 56 3E 4B C6 D2 79 20 9A DB C0 FE 78 CD 5A F4 C | 1F DD A8 33 88 07 C7 31 B1 12 10 59 27 80 EC 5F D | 60 51 7F A9 19 B5 4A 0D 2D E5 7A 9F 93 C9 9C EF E | A0 E0 3B 4D AE 2A F5 B0 C8 EB BB 3C 83 53 99 61 F | 17 2B 04 7E BA 77 D6 26 E1 69 14 63 55 21 0C 7D

最後一個問題：密鑰怎麼編排？

AES不直接(完全)使用原始密鑰，而要將其做一些處理後再使用。密鑰編排這個過程，有時候也被叫做密鑰漂白(key whitening)。AES支持三種不同長度的密鑰，因此有三種不同的密鑰編排方式。

首先我們看128 bits密鑰的密鑰編排方案。

圖8 128 bits密鑰的密鑰編排

原始密鑰為 $K_0K_1K_2...K_{15}$ 共16位元組(128 bits)，我們將它們每4個一組，分別記為 $W_0,W_1,W_2,W_3$ ，這裡每個 $W_i$ 就是4位元組(32 bits)了。然後進行10輪循環處理，生成44個 $W_i$ 。對於每一輪 $i=1,2,3,...,10$ 公式如下 $oplus$ ： $W_{4*i} =W_{4*i-4} oplus g(W_{4*i-1},RC[i])\ W_{4*i+1}=W_{4*i-3} oplus W_{4*i} \ W_{4*i+2}=W_{4*i-2} oplus W_{4*i+1} \ W_{4*i+3}=W_{4*i-1} oplus W_{4*i+2}$

其中函數 $g$ 和輪係數 $RC[i]$ 為

圖9 函數g和輪係數RC[i]

函數 $g$ 存在的目的是增加密鑰編排中的非線性，且消除AES結構中的對稱性。

生成44個 $W_i$ ，每4個為一組，組成一個子密鑰 $k_i$ ，共生成11個子密鑰 $k_0,k_1,k_2,...,k_{10}$ 用於加密、解密過程操作輪中的密鑰加法層。您可能已經注意到了，第一子密鑰 $k_0$ 是非常特殊的——它就是原始密鑰。

相信大家也能夠參照流程圖，自行理解192位和256位密鑰的密鑰編排了。

圖10 192 bits密鑰的密鑰編排

圖11 256 bits密鑰的密鑰編排

192 bits密鑰的密鑰編排中，共執行8輪操作(7輪6個+1輪4個)，函數 $g$ 與128 bits密鑰編排中的相同，使用前8個輪係數 $RC[1],RC[2],...,RC[8]$ ，生成52個 $W_i$ ，仍然每4個為一組，組成一個子密鑰 $k_i$ ，共生成13個子密鑰 $k_0,k_1,k_2,...,k_{12}$ 。

256 bits密鑰的密鑰編排中，共執行7輪操作(6輪8個+1輪4個)，函數 $g$ 與128 bits密鑰編排中的相同，使用前7個輪係數 $RC[1],RC[2],...,RC[7]$ ，生成60個 $W_i$ ，仍然每4個為一組，組成一個子密鑰 $k_i$ ，共生成15個子密鑰 $k_0,k_1,k_2,...,k_{14}$ 。特別留意，中間還需要使用一個函數 $h$ ，其結構非常簡單——就是對每一個位元組用S盒做變換即可。

192 bits密鑰編排生成的子密鑰中，第一個子密鑰 $k_0=W_0W_1W_2W_3$ 和第二個子密鑰 $k_1=W_4W_5W_6W_7$ 的前一半(即 $W_4W_5$ 部分)，共24位元組直接來自於原始密鑰。而256 bits密鑰編排生成的子密鑰中，第一個子密鑰 $k_0=W_0W_1W_2W_3$ 和第二個子密鑰 $k_1=W_4W_5W_6W_7$ ，共32位元組直接來自於原始密鑰。

圖12 函數h

通常AES的實踐中，加密或解密長內容，每一塊都是採用的同樣的原始密鑰，因此也就是同一套子密鑰。所有常先將密鑰做密鑰編排，然後將子密鑰儲存在一個數組中，需要時再讀取，但這中預計算的方法需要佔用一定的內存，在資源非常有限的設備(例如智能卡)上可能無法令人滿意。而如果採用動態生成的方法，需要注意解密過程和密鑰編排過程是順序相反的，這意味著解密總是會比加密稍慢。

Thats it. 有了塊輸入、密鑰編排、操作輪的工作流程，AES就可以正常工作了！

這就是AES的全部內部結構了。本講的內容到這裡也就告一段落。到了這裡，您已經擁有了自己編寫AES等效程序的全部知識(不過別忘了本文開頭的安全提示)。

下一講，我們將講解AES的一種快速軟體實現——查表法。

由於本人知識水平與精力有限，如果本文中有任何知識錯誤或遺漏等(含錯別字)，歡迎指正。

參考資料：

[1]Paar, Christof, and Jan Pelzl. Understanding cryptography: a textbook for students and practitioners. Springer Science & Business Media, 2009.

[2]Daemen, Joan, and Vincent Rijmen. "AES proposal: Rijndael." (1999).

[3]Daemen, Joan, and Vincent Rijmen.The design of Rijndael: AES-the advanced encryption standard. Springer Science & Business Media, 2013.

[4]FIPS, PUB. "197, Advanced Encryption Standard (AES), National Institute of Standards and Technology, US Department of Commerce, November 2001."Link in: http://csrc. nist. gov/publications/fips/fips197/fips-197. pdf(2009).