# 2017q1 Team7 ( clz ) 補充資料
contributed by < `laochanlam` >, < `etc276` >, < `jack81306 `>, < `peterting` >

# 目錄
- [ ] GCM (Galois/Counter Mode) 詳細介紹
- [ ] AES (Advanced Encryption Standard) 詳細介紹
# GCM (Galois/Counter Mode) 詳細介紹
符號 | 定義
--- | ---
Ek | 使用秘鑰k對輸入做對稱加密運算
XOR | 異或運算
Mh | 將輸入與秘鑰h在有限域GF(2^128)上做乘法

在介紹 GCM 之前，必須先介紹以下幾種加密模式：

---

## CTR (Counter Mode)
<br>


<br>

如上圖所示，CTR 是 Block Cipher 的一種加密的模式（ 其他模式可見 CBC ECB OFB CFB )，先通過一定的 bit 數量對明文進行分組，再透過一個加密後的 Counter 來跟明文進行 XOR 的運算，然後得出密文。

**為什麼要用 Counter ？**
- 因為要確保同一樣的明文加密後不會得到相同的密文。
- 這樣加密可不需依賴前者，可進行同時加密加快速度。
- 若密文有部分錯誤，并不會導致整個解密出來的數據全錯誤。

可是，任何的加密方法有可能會遭到惡意修改再重新發送，那麼，我們怎樣可以保證資料的完整性及來源準確性呢？

---

## MAC (Message Authentication Code)
而這個時候，我們可以引入 MAC 的概念來確保資料的**準確性**！
<br>

<br>

如上方的流程圖所示，假設現在 A 要傳資料給 B，以下為傳送步驟：
1) A, B 雙方先共享同一組密鑰 K。
2) A 把需要被傳送的消息 (無論於之前有無加密) 用 K 計算，得出 MAC 值。
3) A 把消息連同 MAC 值一同傳送到 B。
4) B 用之前事先共享的密鑰 K 進行計算，並對比 MAC 值。

**問：為什麼會這樣做？為什麼不直接傳送 資料 + Hash 值 就好？**
- 若被有心人截取，可以把密文修改完產生 Hash 值 + 資料 送到你手中（消息來源準確性）。
- 若使用預先共享的密鑰，截取者就無法得知密鑰，無法產生對應的 MAC 值（消息完整性）。

---

## GMAC (Galois message authentication code mode)
而接下來 GMAC 則是改用 GF 的乘法運算來求出 MAC 值。
>GF 的乘法運算幫忙補充～～～
>我想這邊應該就是有用到 carry-less multiplication 的部分 (?
>[color=blue][name=laochanlam]
>

> 目前想到的就是做 GF 的 cl_mul
> 然後因為大小不能超過 2^n ，所以會用到 reduced polynomial
> 也就是兩數做完運算之後，看 clz 是否 > n 而決定要不要 reduced
> 這樣的好處是避免線性，然後也應用 clz 不會花太多時間 (?
> [color=green][name=etc276]
>

---

#### GCM (Galois/Counter Mode)
最後回來 GCM 了！ GCM 其實就是 **GMAC** + **CTR**，以下為流程圖：


簡單來說，就是用 CTR 的模式加密，再用 GMAC 的方法求出 MAC 值，再把資料和 MAC 值一併傳送給接收者。

### 參考及引用資料
[AES-GCM 加密算法](http://blog.csdn.net/t0mato_/article/details/53160772)
[分組密碼工作模式](https://zh.wikipedia.org/wiki/分组密码工作模式)

---
# AES (Advanced Encryption Standard) 詳細介紹
* 利用上面所介紹到之 Galois field 來進行運算
* 有三種通用的方式來表達一個 byte
* 用8個 bits 來表示
* 作為 F~256~ field 裡面的一個元素
* [0~255] 裡面的正整數
* 加密時，各輪 AES 加密迴圈均包含4個步驟（最後一輪除外）
* **Mixcolumns** - 對於矩陣的每一直行，與一個多項式 c(x) 進行多項式乘法。
> 此處的多項式乘法並非使用一般的乘法,而是使用不同的運算方式.例如,將某個 byte 所對應的值乘以 2，其結果就是將該值的二進制位左移一位，如果原始值的最高位為 1，則還需要將移位後的結果 xor 00011011.
> 且各個值相加的時候是使用 xor 運算.
* **SubBytes** - 透過 S-Box 函數 S 將每個 Byte 做轉換，也就是 b[i,j] = S( a[i,j] )。
> S-box 為一個矩陣,可以映射出另外一個數值.
> 另外在解密時使用 S^-1^ 來解密
* **ShiftRows** - 對於矩陣的每一橫列進行 Shift 移位的動作，移位的步伐大小與列號成正比。
* **AddRoundKey** - 資料與金鑰做 XOR 運算，也就是 b[i,j] = a[i,j] xor k[i,j]。
## 加密動作演算法
1. 對第一個區塊，進行下列動作
1. AddRoundKey()
2. 從第二個區塊開始，對每個區塊都執行下列動作
1. SubBytes()
2. ShiftRows()
3. MixColumns()
4. AddRoundKey()
3. 對最後一個區塊，執行下列動作
1. SubBytes()
2. ShiftRows()
3. AddRoundKey()

## 解密動作演算法
1. 對最後一個區塊，進行下列動作
1. AddRoundKey()
2. ShiftRows()
3. SubBytes()
2. 從倒數第二個區塊開始，對每個區塊都執行下列動作
4. AddRoundKey()
3. MixColumns()
2. ShiftRows()
1. SubBytes()
3. 對第一個區塊，執行下列動作
1. AddRoundKey()

* 在 AES 的加解密過程中，加密時採用正向的進行掃描，而解密時卻是逆向的進行掃描。
## AES Key
* AES 區塊長度固定為 16-byte，而 key 的長度則可為128、
192、256 bits
* key 的長度決定 round 的數目
* ex. 128 bits(16 bytes) 的 round = 10
* 192 bits(24 bytes) 的 round = 12
* 256 bits(36 bytes) 的 round = 14
* rounds = (key-size in 4-byte words) + 6
* 每個 round 需要 16 bytes 的 keying material (密鑰的格式、長度、數量)，所以若給一個 16-byte 的 input，經過 AES key 排程計算會產生一個 176 bytes 的 output，前 16 bytes 是自己，而剩餘的 160 bytes 會被拿來進行計算，一次 4 個 bytes，每四個 bytes 都是先前4個 bytes 經過排列得到的。

- AES 中 mixcolumn 部分設計有限體乘法操作，在使用中需要消耗較多的時間。現在的計算平台都擁有豐富的軟體資源，因此 AES 的軟體實做一般都會採用查表的方式，將所有步驟一起查表，大概消耗 8-10K byte 的存儲空間，但效率非常之高。

### 參考資料
* Implementing SSL/TLS
* [AES 對稱式加解密法](http://www.codedata.com.tw/social-coding/aes/)