AES對稱密碼演算法介紹(0)——數學知識簡介

08-20

13 人贊了文章

AES，Advanced Encryption Standard，高級加密標準，本質上是一個精簡版的Rijndael（主要砍掉了192、256 bits的塊大小，只能用128-bit塊分組）。具體的歷史就不說了，這段話里兩個超鏈接都有描述。

AES對稱密碼演算法的內部結構有很強的數學結構，要想了解AES演算法，首先要了解一些必需的數學背景知識。

當然，像矩陣乘法什麼的本文就不會講了，畢竟大學裡的公共基礎課程之一。本文的重點不是討論數學，所以本篇將側重於數學理論在AES中的應用，而不會關注於定理公式的推導證明。這也不是專業的密碼學教材，不會涉及AES的安全性證明、已知攻擊等。

AES演算法涉及的最核心的數學知識就是伽羅瓦域。但在此之前先介紹群(Group)的概念。

群指的是元素集合 $G$ 和 $G$ 內任意兩個元素的聯合操作 $circ$ 的集合。

群具有以下特徵：
1. 群操作 # 是封閉的。即對所有 ${a,b}in{G}$ ， ${a}circ{b}=cin{G}$ 恆成立。
2. 群操作是可結合的。即對所有 ${a,b,c}in{G}$ ， $acirc(bcirc c)=(acirc b)circ c$ 恆成立。
3. 存在一個元素 ${e}in{G}$ ，對於所有 ${a}in{G}$ 都有 $acirc e=ecirc a=a$ 。此元素 $e$ 被稱為中性元(或單位元)。
4. 對於每一個 ${a}in{G}$ ，都存在一個元素 ${i}in{G}$ 使得 $acirc i=icirc a=e$ ，這個 $i$ 稱為 $a$ 的逆元。
5. 如果在滿足以上特徵的基礎上，對於所有的 ${a,b}in{G}$ 都有 $acirc b=bcirc a$ ，則稱此群為阿貝爾群(或交換群)。

例如連續整數集合 ${0, 1, 2, ...... , m-1}$ 與操作加法模 $m$ 組成了一個群：中性元為0，每個元素的逆元都存在：1 + (m-1) = 0 mod m 2 + (m-2) = 0 mod m ............

但連續整數集合 ${0, 1, 2, ...... , m-1}$ 與操作乘法模 $m$ 不一定能組成一個群，因為不一定每一個元素都存在逆元。

要使一個結構能同時支持加減乘除四種基本運算，我們需要一個域(Field)：

域 $F$ 是具有以下特徵的元素的集合：
1. $F$ 中所有的元素形成一個加法交換群，對應的群操作為 $+$ ，中性元為 $0$ 。

2. $F$ 中除了 $0$ 以外的所有元素構成一個乘法交換群，對應的群操作為 $*$ ，中性元為 $1$ 。
3. 當混合使用這兩種操作時，分配律應始終成立。即對所有的 ${a,b,c}in{F}$ ，都有 $a*(b+c)=(a*b)+(a*c)$ 。

舉個簡單易懂的例子，我們熟悉的實數集就是一個域，加法群中的中性元為 $0$ ，任意元素 $a$ 的逆元為 $-a$ ；乘法群中的中性元為 $1$ ，除 $0$ 以外任意元素a的逆元為 $1/a$ 。（如果你還關心減法和除法，那麼減法可以由加上加法逆元來定義，除法可以由乘以乘法逆元來定義）

但我們只對有限個元素感興趣，這樣的域叫做有限域或伽羅瓦域。而元素的個數叫做有限域的階。

定理1：
只有當 $m$ 是一個素數的冪，即 $m=p^n$ (其中 $n$ 為正整數， $p$ 為素數)時，階為 $m$ 的域才存在。

當 $n=1$ 時該域稱為素域，當 $ngeq2$ 時稱為擴展域。

定理2：
假設 $p$ 是一個素數，那麼整數環 $Z_p$ 表示為 $GF(p)$ ，也稱為擁有素數個元素的素數域或伽羅瓦域。 $GF(p)$ 中所有的非零元素都存在逆元， $GF(p)$ 內的算術運算都是模p實現的。

以最小的有限域 $GF(2)={0,1}$ 為例：

$0 + 0 = 0 mod 2 0 * 0 = 0 mod 2 \ 0 + 1 = 1 mod 2 0 * 1 = 0 mod 2 \ 1 + 0 = 1 mod 2 1 * 0 = 0 mod 2 \ 1 + 1 = 0 mod 2 1 * 1 = 1 mod 2$

其加法恰好等價於「異或門」，乘法恰好等價於「與門」。

AES處理的最小單位是一個位元組，即一個二進位的8位無符號整數。要容納這些整數，自然而然的就是選擇 $GF(2^8)$ 這個擴展域。

但是擴展域並不使用數字來表示擴展域中的元素，而是使用多項式來表達：

在 $GF(2^8)$ 中，每個元素 $Ain{GF(2^8)}$ 都可以表示為：
$A(x)=a_7 x^7+a_6 x^6+...+a_1 x+a_0$ 其中 $a_iin{GF(2)}={0,1}$

簡單的說就是多項式的係數只能是 $0$ 或 $1$ ，且係數的運演算法則符合上面提到的 $GF(2)$ 的運演算法則。這樣 $a_7,a_6,...,a_1,a_0$ 這8個數也就正好對應了一個位元組的8個位，在計算機中只需要一定的順序將其儲存為位元組即可，而 $x^i$ 這樣的冪完全不需要儲存。

先來看看加法：對應的係數按「異或」相加就行了，非常簡單。

$A(x)=x^7+x^6+x^4 +1\ B(x)= x^4+x^2+1\ A(x)+B(x)=x^7+x^6 +x^2$

從位元組的角度看， $GF(2^8)$ 的加法就是將兩個位元組做按位異或運算即可。同時我們可以很輕鬆的發現， $GF(2^8)$ 的減法其實是和加法完全等價的。

而 $GF(2^8)$ 的乘法就比較複雜了。

還是以上面的 $A(x)*B(x)=(x^7+x^6+x^4+1)*(x^4+x^2+1)$ 為例，如果聯繫上面群和域的定義，可以用兩次分配律將其展開為這樣一個式子 $x^7*x^4+x^7*x^2+x^7*1+x^6*x^4+x^6*x^2+x^6*1+x^4*x^4+x^4*x^2+x^4*1+1*x^4+1*x^2+1*1$

首先按照計算一般多項式的方法計算，得到 $x^{11}+x^{10}+x^9+2x^8+x^7+2x^6+2x^4+x^2+1$

注意係數要模2，所以 $x^8,x^6,x^4$ 這三項的係數就為 $0$ 了，即 $x^{11}+x^{10}+x^9+x^7+x^2+1$

這裡就有問題了， $x^{11},x^{10},x^9$ 這些項超過了 $x^7$ ，無法使用 $GF(2^8)$ 的多項式來表達。所以在定義 $GF(2^8)$ 的乘法時，還要選擇一個合適的多項式用來對「傳統乘積」做模約。

在AES標準中，Rijndael設計者選擇了一個不可約多項式(irreducible polynomial)作為乘法模約用到的模，它是 $P(x)=x^8+x^4+x^3+x+1$

注意到 $x^9=x*P(x)+x^5+x^4+x^2+x$

即 $x^9=x^5+x^4+x^2+x mod P(x)$

同理 $x^{10}=x^6+x^5+x^3+x^2 mod P(x)\ x^{11}=x^7+x^6+x^4+x^3 mod P(x)$

帶入上述三式，按加法模2合併同類項，可得 $x^2+x+1$ ，即為AES規範下 $GF(2^8)$ 的乘法結果。這裡也可以嘗試用做豎式除法(長除法，long division)那樣來做，用乘積多項式除以不可約多項式，求得的餘數(余式)就是這個結果，這個比較簡單這裡不講了，只給出一個實例(但是對於後面的擴展歐幾里得演算法非常重要，建議讀者親自動手嘗試)。

$egin{array}{rl} underline{ phantom{x^{11}+x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+}x^3+x^2+x+0}\[-3pt] x^8phantom{+x^7+x^6+x^5}+x^4+x^3phantom{+x^2}+x+1 ) x^{11}+x^{10}+x^9phantom{+x^8}+x^7phantom{+x^6+x^5+x^4+x^3}+x^2phantom{+x^1}+1 \ underline{ x^{11}phantom{+x^{10}+x^9+x^8}+x^7+x^6phantom{+x^5}+x^4+x^3phantom{+x^2+x^1+1} }\ x^{10}+x^9phantom{+x^8+x^7}+x^6phantom{+x^5}+x^4+x^3+x^2phantom{+x^1}+1\ underline{ x^{10}phantom{+x^9+x^8+x^7}+x^6+x^5phantom{+x^4}+x^3+x^2phantom{+x^1+1} } \ x^9phantom{+x^8+x^7+x^6}+x^5+x^4 phantom{+x^3+x^2+x}+1 \ underline{ x^9phantom{+x^8+x^7+x^6}+x^5+x^4 phantom{+x^3}+x^2+x^phantom{1}phantom{+1} } \ x^2+x+1 end{array}$

雖然AES並不關心 $GF(2^8)$ 的除法，但是 $GF(2^8)$ 上的乘法逆元在AES的解密操作過程中至關重要。根據乘法逆元的定義，有 $A^{-1}(x)*A(x)=1 mod P(x)$ 。要求得這個式子中的 $A^{-1}(x)$ ，其實現在的方法已經很多了。

第一種方法最簡單，因為 $2^8=256$ 並不大，把 $GF(2^8)$ 的每一個非零元素用乘法遍歷，也才65025次，找出其中等於 $1$ 的，就能確定乘法逆元。但這一點兒也不數學。

第二張方法我們首先要在乘法的基礎上定義 $GF(2^8)$ 的冪運算為 $(A(x))^n=A(x)*A(x)*...*A(x)$ 其中等號右邊共有 $n$ 個 $A(x)$ 相乘。考慮到預演算法則之間的「兼容性」，對非零元素 $(A(x))^0=1$ 。

一個很有趣的現象是 $GF(2^8)$ 中的某些元素，例如 $Y(x)=x+1$ ，自身的冪次會循環地遍歷 $GF(2^8)$ 的每一個非零元素(不一定按順序)，這種元素叫做乘法群的本原元或生成元。如下，指數為0~254的範圍內無重複地遍歷了 $GF(2^8)$ 的每一個非零元素。

$(Y(x))^0=(x+1)^0=1 \ (Y(x))^1=(x+1)^1=x+1 \ (Y(x))^2=(x+1)^2=x^2+1 \ (Y(x))^3=(x+1)^3=x^3+x^2+x+1\ (Y(x))^4=(x+1)^4=x^4+1 \ ......\ (Y(x))^{253}=(x+1)^{253}=x^6+x^4+x \ (Y(x))^{254}=(x+1)^{254}=x^7+x^6+x^5+x^4+x^2+x\ (Y(x))^{255}=(x+1)^{255}=1 \ (Y(x))^{256}=(x+1)^{256}=x+1 \ ......$

易得 $A^{-1}(x)*A(x)=(Y(x))^a*(Y(x))^b=(Y(x))^{a+b}=1 mod P(x)$ ，即 $a+b=255$ 。所以，首先在計算機中算出指數與冪的對應關係表(也被稱為「對數表」)，在需要要求 $A(x)$ 的逆元時，查詢 $A(x)$ 對應的指數 $b$ ，再算出 $a=255-b$ 後查詢到對應的 $(Y(x))^b$ 即為 $A^{-1}(x)$ 。

第三種方法被稱為擴展歐幾里德演算法(Extended Euclidean Algorithm, EEA)。擴展歐幾里德演算法本身被用於求兩個正整數 $r_0,r_1$ 的最大公約數(greatest common divisor, gcd)以及方程 $gcd(r_0,r_1)=s*r_0+t*r_1$ 的兩個係數 $s,t$ 。

不妨假設 $r_0>r_1$ ，數學上已經證明對於連續自然數 ${0,1,2,...,r_0-1}$ 和操作乘法模 $r_0$ 構成的群，只有在 $gcd(r_0,r_1)=1$ 時任意元素的逆元才一定存在，此時上式可改寫為 $t*r_1=1 mod r_0$ ，即 $t$ 就是 $r_1$ 的逆元。

數學上也證明了對於有限域的情況也是一樣： $s(x)*P(x)+t(x)*A(x)=gcd(P(x),A(x))=1\ t(x)*A(x)=1 mod P(x)$

注意由於 $P(x)$ 是一個不可約多項式，故gcd總是等於1。

講了這麼多，我們還是沒有講到如何用EEA解出這個 $t(x)$ ,下面我們就以一個小型擴展域為例(考慮到篇幅原因)做講解：計算基於 $P(x)=x^3+x+1$ 的有限域 $GF(2^3)$ 中 $A(x)=x^2$ 的逆元。

首先設定出初始值 : $t_0(x)=0, t_1(x)=1\ r_0(x)=P(x), r_1(x)=A(x)$
然後迭代地處理：
第[1]輪：將 $r_0(x)$ 改寫作 $r_0(x)=q_1(x)*r_1(x)+r_2(x)$ 的形式 (就是用豎式除法，求 $r_0(x)$ 除以 $r_1(x)$ 的商式和余式，商式記作 $q_1(x)$ ，余式記作 $r_2(x)$ ) ，然後計算 $t_2(x)=t_0(x)-q_1(x)*t_1(x)$ 。

這裡： $x^3+x+1=(x)*(x^2)+(x+1), t_2(x)=0-x*1=x$
第[2]輪：將 $r_1(x)$ 改寫作 $r_1(x)=q_2(x)*r_2(x)+r_3(x)$ 的形式，然後計算 $t_3(x)=t_1(x)-q_2(x)*t_2(x)$ 。
這裡： $x^2=(x)*(x+1)+(x), t_3(x)=1-x*x=x^2+1$
第[3]輪：將 $r_2(x)$ 改寫作 $r_2(x)=q_3(x)*r_3(x)+r_4(x)$ 的形式，然後計算 $t_4(x)=t_2(x)-q_3(x)*t_3(x)$ 。
這裡： $x+1=(1)*(x)+(1), t_4(x)=x-1*(x^2+1)=x^2+x+1$
第[4]輪：將 $r_4(x)$ 改寫作 $r_3(x)=q_4(x)*r_4(x)+r_5(x)$ 的形式
這裡： $x=(x)*(1)+(0)$ ，因為 $r_5(x)=0$ ，break！
最終，最後一個 $t_i(x)$ 即為 $A^{-1}(x)$ 。本例中為 $t_4(x)=x^2+x+1$ 。

小結一下，設定初始變數後，不斷迭代：第[ $i$ ]輪中，先求 $r_{i-1}(x)=q_i(x)*r_i(x)+r_{i+1}(x)$ 中的 $q_i(x),r_{i+1}(x)$ ，再計算 $t_{i+1}(x)=t_{i-1}(x)-q_i(x)*t_i(x)$ ，直到 $r_{i+1}(x)=0$ 時停止，然後取 $t_i(x)$ 作為求逆元的結果。(最大公約數gcd就是 $r_i$ )

擴展歐幾里德演算法中係數 $s$ 的求法我們這裡並不關注，沒有寫出。如果讀者有興趣可以在超鏈接中查看。

至此，乘法逆元問題我們已經解決了。那麼AES的必需數學基礎也就到這裡了。如果您對本文的內容感興趣，可以嘗試用你熟悉的編程語言實現一個能計算 $GF(2^8)$ 上的加法、乘法、逆元的程序。

下一講，我們將以此為基礎，正式開始我們的AES之旅。

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

參考資料：Paar, Christof, and Jan Pelzl. Understanding cryptography: a textbook for students and practitioners. Springer Science & Business Media, 2009.