iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 7
0
Security

無趣的密碼學,有趣的加密!系列 第 7

[Day 7] 007 - 對稱密鑰演算法 - Symmetric-key algorithm(三)(下)

對稱密鑰演算法 - AES(下)

寫文章真的蠻辛苦的,尤其是收集資料、濃縮資料、整理、消化,最後才能產出一篇又一篇的文。

而且我不太想要敷衍大家,要保持一貫的高品質,至少希望大家看了能把程式碼寫出來的程度。

而且還有很多很多的話題能跟大家聊聊的,但廢話先不多說。

來我們的重點!AES 下半部分!

AES

金鑰生成

一般上課或者文章都不會講到AES的金鑰生成或金鑰擴增,想必大家也很好奇。

我先跟大家說一件事情,雖然文章上是寫了,但如果有任何錯誤都能點出來。

尤其這部份的文章說真的很少就是了。

這邊先跟大家做一個解釋『回合金鑰』跟『擴充金鑰』是不同的東西!

擴充金鑰 不等於 回合金鑰,回合金鑰才是加密用的金鑰。


我們先看一下,金鑰生成的幾個點。圖十三:


圖十三

圖片來自AES key Schedule Wiki

大家能看到矩陣,我來說一下,每一列都是32位元。
而AES-128有4行、AES-192有6行、AES-256有8行。

每做一次步驟,就會輸出我們的擴充金鑰,稱呼為W,這個W是32位元的。

然後 擴充金鑰(W) 跟上 金鑰字的長度(N) 次的回合金鑰片段做 XOR 就會生成新的回合金鑰片段
(N不是金鑰的位元喔!)

當動作的次數能被我們金鑰字的長度整除,就要拿來做了以下3個步驟:

  1. RotWord
  2. SubWord
  3. Rcon

接著將這個W如圖十三,在跟上 金鑰字的長度(N) 次的回合金鑰片段做 XOR,不斷的做出 擴充金鑰(W) 也做出回合金鑰片段


擴充金鑰生成流程

先看一下,下面條件式的圖十四:


圖十四

圖片來自AES key Schedule Wiki

圖十四中能看到,小於 金鑰字的長度(N) 的時候並不會做其他的動作,會直接輸出 原金鑰(K) 的金鑰。
直到 原金鑰(K) 長度用完後才開始有動作。

能看到i是回合數,N為金鑰字的長度(再一次提醒,不是金鑰的位元。)
這邊先列舉一下:

  • AES-128 為4個字的金鑰長度。
  • AES-192 為6個字的金鑰長度。
  • AES-256 為8個字的金鑰長度。

每一個字為32位元喔!

i的總回合數為0到4R-1次,其中R指的是:

  1. AES-128會做10次的循環,所以R這時是11。
  2. AES-192會做12次的循環,所以R這時是13。
  3. AES-256會做14次的循環,所以R這時是15。

請務必依照圖十四的條件來做RotWord、SubWord、Rcon。
而圖十三是AES-128的演示圖,而超過AES-128之後,還會在 動作次數(i) 取餘數等於4時做SubWord。


為何是0到4R-1?

很簡單,每一次做只會生出一個 擴充金鑰(W)
擴充金鑰(W) 剛剛好是32位元,並跟上 金鑰字的長度(N) 次的回合金鑰片段做XOR生成回合金鑰片段
所以一次的回合金鑰需要128位元, 擴充金鑰(W) 每XOR一次是32位元。
必需要做4次才能生成一個完整的回合金鑰

為回合數為10,R卻是11?

大家還記得嗎,AES的加密最前的步驟,會先跟金鑰做一次混合。


RotWord

這個其實沒什麼好說的,就是位移。

將金鑰向左1位元,並將最左邊的1位元,依序接在最右邊。

也就是

0 1 2 3 -> 1 2 3 0

SubWord

其實就是SubBytes的S盒子拉!

附相同的速查表圖十五:


圖十五

Rcon

這個就有點麻煩了。

Rcon的資料是這樣的[rci 0x00 0x00 0x00]

那個i的話是指N也就是循環的次數。

而rci的生成方式如圖十六:


圖十六

圖片來自AES key Schedule Wiki

給個速查表圖十七:


圖十七

圖片來自AES key Schedule Wiki


加、解密差異

除了金鑰生的成之外,邊要注意的事情很多。

  1. AddRoundKey 所需要的金鑰同樣也要由後向前解開。
  2. SubBytes 必須使用另一張反向的對照表,如圖十八:

    圖十八
  3. ShiftRows的位移,必須反著來。
  4. MixColumns 要用逆向的矩陣,如圖十九:

    圖十九

所以很多電路的重複性來說比DES來要差。

以AES來說加解密需要用到很多相反的電路,因此成本也會比較高。
目前來說有蠻多優化過的演算,能節省一些資源,並降低了成本。


AES 總結

大家上完數學課有沒有感覺到很累。

我也是,寫這篇的時候不斷地查資料,把資料整合。

目前這邊算是中文文檔中,動作解析還算有解釋的文了。

好拉,接下來我們就會進到非對稱的加密方案了。

接下來我會在下面補充一些資料。


參考資料

Announcing the ADVANCED ENCRYPTION STANDARD (AES)

Advanced Encryption Standard WiKi

Rijndael MixColumns WiKi

AES key schedule WiKi

Rijndael S-box WiKi

有限體 Galois field(GF) WiKi

進階加密標準 WiKi


補充資料

回形针PaperClip Vol.120 二維碼的秘密

這個影片中會提到GF場,並且詳細地說明了GF場的一些特性。
也可以瞭解二維碼的生成。


上一篇
[Day 6] 006 - 對稱密鑰演算法 - Symmetric-key algorithm(三)(上)
下一篇
[Day 8] 008 - 非對稱式密碼學 - Asymmetric cryptography (前言)
系列文
無趣的密碼學,有趣的加密!30

尚未有邦友留言

立即登入留言