密碼學

AES, SP Network與Rijndael

最近在上資訊安全，課堂上有提到 Rijndael 對稱式密碼演算法，剛好我高三時看的「密碼學與比特幣」中有提到，當時就很納悶怎麼沒有提到數學理論的部份還想了好久，剛好被我看了又有一點時間就寫下來吧

1. AES背景由來

Advanced Encryption Standard(AES)是美國國家標準技術研究所(National Institute of Standards and Technology, NIST)為了取代當時不安全的對稱式加密標準(DES)所徵選出來的。經過一系列的公開測試與評選之後，最終決定採用Rijndael作為AES。

AES有著嚴格的徵選條件，除了金鑰大小(128/192/256bits)與加密區塊大小限制(128bits)，將演算法公開以免「安全來自祕密」問題，還會交由包含密碼提案者的所有密碼使用者進行評選，而且還要能在硬體上執行(避免加/解密時間過長)等等多項要求。

這樣的競爭方式使得徵選出來的演算法得經得起世界上頂尖密碼學家的破解，也代表著爭選出演算法的強大。

2. SP Network

Subtitution-Permutation Network, 代換-置換網路，是一種區塊加密算法常用的運算，被應用於大量現代加密中(包括AES)，能夠增加密碼的混淆性(Confusion)與擴散性(Diffusion)。

SP Network 由 S-box, P-box 與回合金鑰組成，分別代表「代換」與「置換」:

-S-box

S-box 會將輸入按照一對一對應表輸出，設計良好的對應表能夠在輸入的任一位元變動時變動輸出一半以上的位元，達到「擴散」的效果。為了避免「安全來自祕密」[1]，密碼演算法通常會選用公開且良好的對應表。

-P-box

P-box 會對各 S-box 的輸出進行置換、輸出到下一層，設計良好的 P-box 應該要儘量使上一層 S-box 的輸出均勻混合。

-回合金鑰

回合金鑰會對 P-box(每回合)的輸出進行加密，產生下一輪的輸入，回合金鑰通常是以加密金鑰作為基礎。

SP Network 的設計有良好的混淆性與擴散性，明文的任一位元變動將會影響不只一位元的 S-box 輸出，經由 P-box 將變動得位元擴散後，會影響更多到下一輪的 S-box 輸出，多個回合之後便會產生出與原密文相差很大的新密文。這樣的特性使破解者即便知道某一明文-密文對，也難以從中推測出加密金鑰本身。

3. Rijndael

Rijndael 是一個基於 SP Network 衍生出的對稱式加密，由4個部份組成：

  • SubBytes
  • ShiftRows
  • MixColumn
  • AddRoundKey

其中 SubBytes 對應 S-box、ShiftRows/MixColumn 則對應 P-box, AddRoundKey 則是將回合金鑰與當回合產生之密文進行XOR運算。

Rijndael 與其他對稱式加密相比有兩大特色：首先，Rijndael 與一般線性加密不同，以 16 bytes 所組成的矩陣為單位進行加密，也因此 Rijndael 的所有運算都能以數學式表示。其次，Rijndael 的 S-box 是以 GF(2^8) 的乘法反元素所衍生出來的，與 DES 的人工 S-box 相比更加能被信賴[2]。

AES 下的 Rijndael 由 10-14 個回合所組成，當加密金鑰越大時，加密更多個回合。除了第一回合只進行 AddRoundKey 與最後一個回合不進行 MixColumns 之外[3]，每個回合都會進行 SubBytes/ShiftRows/MixColumns/AddRoundKey 4 個步驟。

-SubBytes

SubBytes 所使用的 S-box 是 Rijndael 的精隨所在，也是整個演算法唯一非線性的部份[4]。SubBytes 以位元組為單位進行替換，每種位元組有其唯一且對應的替換位元組，是將位元組視為有限體中的多項式(以 XOR 作為加法運算)、得出多項式的乘法反元素之後[5]，為了避免 0 的乘法反元素還是 0 的問題，再對該乘法反元素進行仿射運算[6]，就是替換後的值了。

a = 0x53 = 01010011_2 = x^6 + x^4 + x + 1

// p 為 Rijndael 採用的歸約多項式
p = x^8 + x^4 + x^3 + x + 1

使用擴展歐幾里得算法求 a 的反元素

回合 商 r, newr t, newt
p = x^8 + x^4 + x^3 + x + 1 0
a = x^6 + x^4 + x + 1 1
1 x^2 + 1 x^2 = p - a(x^2 + 1) x^2 + 1 = 0 - 1(x^2 + 1)
2 x^4 + x^2 x + 1 = a - x^2(x^4 + x^2) x^6 + x^2 + 1 = 1 - (x^4 + x^2)(x^2 + 1)
3 x + 1 1 = x^2 - (x + 1)(x + 1) x^7 + x^6 + x^3 + x = (x^2 + 1) - (x + 1)(x^6 + x^2 + 1) 
a^{-1} = x^7 + x^6 + x^3 + x = 11001010_2

// 相乘mod(p)證明為反元素
// 相乘
a        01010011
a^-1     11001010
-----------------
        01010011
      01010011
   01010011
+ 01010011
-----------------
   11111101111110

// mod(p)
  11111101111110
- 100011011
----------------
   111000001
-  100011011
----------------
    110110101
-   100011011
----------------
     101011101
-    100011011
----------------
       100011010
-      100011011
----------------
               1

AES 的仿射運算:

\displaystyle{\begin{bmatrix} s_{0} \\ s_{1} \\ s_{2} \\ s_{3} \\ s_{4} \\ s_{5} \\ s_{6} \\ s_{7} \end{bmatrix}} ={\begin{bmatrix}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{bmatrix}}{\begin{bmatrix} a_{0} \\ a_{1} \\ a_{2} \\ a_{3} \\ a_{4} \\ a_{5} \\ a_{6} \\ a_{7} \end{bmatrix}} + {\begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \end{bmatrix}} 
// 上式轉換為算式如下

s = a \oplus (a \lll 1) \oplus (a \lll 2) \oplus (a \lll 3) \oplus (a \lll 4) \oplus 63_{16}


    11001010
    10010101
    00101011
    01010110
    10101100
XOR 01100011
------------
    11101101 = 0xED

sbox(0x53) = 0xED

對照表驗證結果：

ShiftRows

為了不讓 Columns 可以被獨立加密，將不同 Column 混在一起。如圖，將每個 Row 依照行數進行 Shift，沒有其他的複雜運算。

MixColumns

MixColumns 是 Rijndael 擴散性的主要來源，每回合都會將一個 byte 的變動擴散至所在的 Column，再經由 ShiftRows 擴散到其他的 Column

MixColumns 和 SubBytes 一樣，將 Column 視為有限域中的多項式。Column 的 4 個 byte 會被轉換為 4 次多項式的 4 個係數，歸約多項式為m(x)=x^4+1。

不同於 SubBytes 的求出乘法反元素再進行仿射院算，MixColumns 只會將 Column 乘上特定的多項式a(x)

a(x) = \{03\}x^3 + \{01\}x^2 + \{01\}x + \{02\}

整個 MixColumns 可以表示為

s'(x)=a(x)\otimes s(x)

通常在實做時會轉換為矩陣運算，如下

\displaystyle{{\begin{bmatrix} s'_0 \\ s'_1 \\ s'_2 \\ s'_3 \end{bmatrix}} = {\begin{bmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{bmatrix}} {\begin{bmatrix} s_0 \\ s_1 \\ s_2 \\ s_3 \end{bmatrix}} }

AddRoundKey

將整個加密過後的矩陣與當回合的回合金鑰進行 XOR 運算，完成當回合的加密

總結

Rijndael 加密算法的安全性源自於統計上的安全，只要 AES 的擴散性與混淆性足夠強大，攻擊者就只能以猜測的方式來嘗試破解，n bit 的金鑰平均需要進行 2^{n-1} 次的猜測，於 AES 中就是 2^{255} 次猜測。如果進行一次猜測需要10^{-10}秒，便需要約 5.789\times 10^{66} 秒，約等於 1.835\times 10^{59} 年。

截至目前為止，只有在特定硬體上的旁道攻擊可以在短時間內成功破解 AES，目前來看 AES 還是蠻安全的。

註解：

  • [1] 「安全來自祕密」(Security through obscurity)：強大的加密機制不應該依賴「因為大家都不知道加密算法如何運作，所以沒有人能夠破解」。有人將其比喻為「把錢埋在樹下」，一旦有人知道藏匿的位置，便能拿走你的錢; 與此相反的是：「將錢放進保險櫃」，即便保險櫃被放在大馬路上，也只有你能夠拿走你的錢。

  • [2] 謠傳 DES 的 S-Box 在建立時就附加了數學上的後門，此謠言目前尚未被證實。以數學方式產生的 S-Box 相較於人工 S-Box 而言較難有這類問題發生。

  • [3] 最後回合的 MixColumns 是可以直接以密文反推回去的步驟，而且省略該 MixColumns 可以使 Rijndael 的加解密結構更相似(因為 MixColumns 可以與 AddRoundKey 互換位置而不影響結果)。

    來源：Why is MixColumns omitted from the last round of AES? StackExchange-Cryptography

  • [4] 非線性被用來抵抗差分密碼分析，一種依靠「輸入上的差別對於輸出的差異」獲取金鑰的技術，通過最小化輸入與輸出的關聯性來實現。

  • [5] 在GF(2^8) 中，a(x)的乘法反元素a^{-1}(x)被定義為a(x)*a^{-1}(x)mod(m(x))=1，m(x)為歸約多樣式，可以理解成模運算的多項式版本，元素在超過域的範圍時，會對應回原本域中的元素。好比katexmod7=18mod7=2[/katex]，最終會回到0-6之間。

    Rijndael 選定了 x^8+x^4+x^3+x+1 作為有限域 GF(2^8) 的歸約多項式，為 GF(2^8) 的 30 個歸約多項式的其中一種，每種規約多項式會分別產生不同的 S-box，據 Rijndael 的作者所述，選中該歸約多項式單純是因為它是排在參考書上的第一個，並且每種產生的 S-box 都有一致的強度。

  • [6] 在仿射運算中的常數 0x63 是為了避免 「Sbox(a) = a」和「Sbox(a)=\bar{a}」的情況發生而設計的。

參考資料來源：