iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 6
2
Security

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

[Day 6] 006 - 對稱密鑰演算法 - Symmetric-key algorithm(三)(上)

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

同時光是DES就寫了不少字了,這些字都是我一個字一個字敲出來的,很累。

RC5也是,最近已經有點忙了……

我現在超怕自己斷更,而且17號到22號要去爬山,因此……必須先寫好。

但以我目前的更新進度而且完全沒有存稿,還記得吧第一天我說的,我是突然腦袋一熱參加的。

好先不說廢話了!來我們的重點!AES!!

AES

進階加密標準 - Advanced Encryption Standard(AES)

論文在這邊:Announcing the ADVANCED ENCRYPTION STANDARD (AES)

接下來我們所使用的圖片都是來自2001年11月26號所發布的,Announcing the ADVANCED ENCRYPTION STANDARD (AES) 文檔,在此標記。

AES加密在密碼學專業的領域中被稱呼為Rijndael加密法。

是以目前美國政府所使用的國家加密標準。

以標準發布的介紹來說,資料必須分割為128位元,但金鑰可以是128、192、256位元。


大綱與總覽流程

在文檔中並沒有整體流程圖的樣子,那就讓靈魂畫師的我來畫一張:請看圖一


圖一

很簡單吧?看當灰色大框框,接下來就是重複。
然後重複動作的次數試看金鑰長度而定的,看圖二。

  • 128重複10次
  • 192重複12次
  • 256重複14次


圖二

我簡單的將過程列舉一下:

  1. 第一次一開始必須先做 AddRoundKey 將資料跟回合金鑰做XOR。
  2. SubBytes 將資料作替換。
  3. ShiftRows 位移資料。
  4. MixColumns 利用GF來將資料作變化。
  5. AddRoundKey 將資料跟回合金鑰做XOR。
  6. 接著重複動作2到動作5直到回合數n-1次。
  7. 最後一次不做MixColumns。

我們可以看一下程式碼:請看圖三


圖三

作為困難理解的應該是第4個步驟了。

我們依舊慢慢看。


資料的預先處理

首先,要先把資料作處理,圖中沒有寫到,但要先把資料作排列。

在AES裡必須將資料分割成4*4的矩陣,每一個元素都帶有8位元的資料,也就是1Byte。

那怎麼排列呢?首先我們先把資料每八個分組並給一個編號,如圖四。


圖四

然後在依照圖五下的做排列


圖五

資料的前置步驟完成了。

再來就是加密的4個步驟了。

AddRoundKey

跟回合金鑰做XOR,也不難,看圖六:


圖六

能看到每列資料跟每列回合金鑰做XOR。

所以這對大家來說也不難吧?

資料跟回合金鑰來說長度是一樣的,就是做XOR。

SubBytes

替換也是很簡單的,看下圖七:


圖七

每一個區塊作每一個各自的變化,一樣把資料放入S盒子。

但這邊的S盒子跟DES的盒子不一樣喔!(S盒子只是稱呼。)

這裡就提供了非線性的轉換了,其中S盒子其實跟GF(2^8)的乘法反元素有關係。

數學證明的東西,能看一下論文中的解釋(除非你們敲碗要我上數學課)。

但我們能將其公式化,並做出矩陣來。

替換的話能看一下矩陣公式圖八:


圖八

然後其實有一個速查表圖九:


圖九

X跟Y就是資料的8byte資料的前跟後例如:0x53(大家應該會16進制,不懂的話這邊)。

行為5,列為3,對照出來的就是0xed。

寫程式的時候能直接把表做完,然後直接映射。

ShiftRows

位移的話就更加簡單了,看圖十就能懂了。


圖十

能看到圖裡面個幾個重點

  1. 第一行不變。
  2. 第二行向左1位元,並將最左邊的1位元,依序地接在最右邊。
  3. 第三行向左2位元,並將最左邊的2位元,依序地接在最右邊。
  4. 第四行向左3位元,並將最左邊的3位元,依序地接在最右邊。

MixColumns

嗯……這個我不會,跳過。(讀者傻眼,開始打作者)

好抱歉,我錯了,這部份跟數學理論蠻多關係的(密碼學哪一個環節跟數學沒關係)。

但這時候必需要跟大家說請自己去看GF了,或者找你們的數學老師(有些老師也不一定能解釋的很清楚),或者有人能提供有好的資源在跟大家分享。

其實也不難,很簡要地先看要做什麼的圖十一:


圖十一

然後給你們一個大殺器圖十二:


圖十二

你看人家矩陣的參數都幫你寫好好了。

還等什麼,直接套來用啊。


加密流程 結論

其實上述的方法都不難,但就是牽涉了很多很多很多的數學理論就是了。

GF場來說,我晚點會補充一些資料給大家,請大家不要擔心。

好了,很感謝這一次大家的收看,下一章節開始就是非對稱了。

謝謝。(突然被打)

讀者:「啊金鑰你沒說啊!」
我:「抱……抱歉……我懶了……」
讀者:「懶?你想再被打是不是阿!」
我:「抱歉…我寫,我寫!但是!請見下回分曉!。」

抱歉……事情真的有點多,本來想一次寫完的。

但就只能先分成兩部分,真的請多多見諒。


參考資料

Announcing the ADVANCED ENCRYPTION STANDARD (AES)

Advanced Encryption Standard WiKi

Rijndael MixColumns WiKi

Rijndael S-box WiKi

有限體 Galois field(GF) WiKi

進階加密標準 WiKi


上一篇
[Day 5] 005 - 對稱密鑰演算法 - Symmetric-key algorithm(二)
下一篇
[Day 7] 007 - 對稱密鑰演算法 - Symmetric-key algorithm(三)(下)
系列文
無趣的密碼學,有趣的加密!30

尚未有邦友留言

立即登入留言