# AES

## 簡介
AES是一種對稱式加密算法

## 先輩知識
AES的列混淆(MixColume)中會用到伽羅瓦域的加法和乘法

### 伽羅瓦域/有限域簡介
有限域中的元素集合是有限的，表示為$GF(p^n)$，p是一個質數(素數)。EX $GF(2^8)$，表示包含256個元素的有限域(其中元素可由0~p^n-1表示)

### 素域
當n=1時可稱為素域，在$GF(p)$中，所有的非0元素都有逆元素(反元素)。
其運算規則如下
1. 加法和乘法和整數運算是一樣的，只是最後要mod p。而減法和除法就是加上/乘上其反元素
2. 加法反元素定義為 (a + (a反元素)) mod p = 0
3. 乘法反元素定義為 (a * (a反元素)) mod p = 1
4. GF(2)的加法與XOR等價，乘法與AND等價
EX GF(7)中3的加法逆元為4 (3+4)mod7 = 0，乘法逆元為4 (3*4)mod7 = 1

### 擴展域
p^n不為質數時，這樣的有限域加法和乘法就不能用整數加法和整數乘法mod p表示。擴展域有不同的規則執行運算(以下例子以AES中會用到的GF(2)舉例)
#### 1.表示法
在擴展域$GF(2^n)中以係數為GF(2)$的多項式表示
EX$GF(2^8)$的每個元素都可表示為
$a_7x^7+a_6x^6+...+a_1x+a_0, a_i\in GF(2)$(講白話就是a用0 1表示)

#### 2.加減法(基於GF(2^n))
每一位分別進行加法後mod 2(和一般二進位加法不同，不需要進位)
假設$A=(a_7,a_6,...,a_1,a_0),B(b_7,b_6,...,b_1,b_0)$ (x已省略)

則
$A+B=((a_7+b_7)mod2,(a_6+b_6)mod2,...,(a_1+b_1)mod2,(a_0+b_0)mod2))$

$A-B=((a_7-b_7)mod2,(a_6-b_6)mod2,...,(a_1-b_1)mod2,(a_0-b_0)mod2))=A+B$

在GF(2^n)下A-B和A+B是一樣的，且都與XOR等價

#### 乘法(基於GF(2^n))
設$C(x)=A(x)B(x)=(a_{n-1}x^{n-1}+...+a_0)(b_{n-1}x^{n-1}+...+b_0)$
則係數們
$c_0 = a_0b_0mod2$
$c_1 = (a_1b_0+a_0b_1)mod2$
.
.
.
其實就是一般的多項式乘法(記得要mod)

但是C(x)的次數通常會大於n，所以要化簡，和素數超過範圍時mod一個素數一樣。這裡要將乘出來的多項式除一個不能約分的多項式，算出的餘式就是最後的結果(在AES中使用的是$x^8+x^4+x^3+x+1$)

## AES算法
有四種操作，分別是金鑰加密(Add Round Key)、位元組代換(SubByte)、行位移(Shift Rows)、列混淆(Mix Column)
明文和金鑰都是128位的(密鑰也可以192位256位，下面都已128為主)，16個字節由上到下由左到右排成4*4
總共進行10輪處理，只有最後一輪少了一次MixColumn
流程圖

而解密就只是完全反過來而已
### 金鑰加法層(Add Round Key)
明文的$4*4$矩陣和密鑰的$4*4$矩陣進行XOR運算(其實就是擴展域的加法)
#### 實作

void AddRoundKey(unsigned char state[4][4], const unsigned char RoundKey[4][4]) {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            state[i][j] ^= RoundKey[i][j];
        }
    }
}

### 位元組代換(SubByte)
S_box是一個有256個字節組成的陣列
這層的功能就是將輸入通過S_box代換成另一個字節
對應方法為，將輸入字節的高4位和低4位分別作為行索引和列索引，根據這接索引在S_box中找到對應的值(實作時可以將S_Box存成一維的，這樣就直接將值作為索引就好)

加密與解密時使用的S_box不同(戶違反矩陣)
>S-box
>
> 來源:wiki https://en.wikipedia.org/wiki/Rijndael_S-box
>Inv S-box
> 
> 來源wiki https://en.wikipedia.org/wiki/Rijndael_S-box
#### 實作

unsigned char S_BOX[256] =
{
    0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
    0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
    0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
    0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
    0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
    0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
    0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
    0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
    0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
    0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
    0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
    0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
    0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
    0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
    0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
    0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16
};
unsigned char INV_S_BOX[256] =
{
    0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38, 0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB,
    0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB,
    0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D, 0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E,
    0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25,
    0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92,
    0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84,
    0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06,
    0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B,
    0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73,
    0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85, 0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E,
    0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89, 0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B,
    0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20, 0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4,
    0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31, 0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F,
    0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D, 0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF,
    0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0, 0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61,
    0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26, 0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D
};

void SubBytes(unsigned char state[4][4]) {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            state[i][j] = S_BOX[state[i][j]];
        }
    }
}

void InvSubBytes(unsigned char state[4][4]) {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            state[i][j] = INV_S_BOX[state[i][j]];
        }
    }
}

### 行位移(Shift Rows)
將4*4的矩陣進左右的位移
| | | | |
| --- | --- | --- | --- |
| p1 | p5 | p9 | p13 |
| p2 | p6 | p10 | p14 |
| p3 | p7 | p11 | p15 |
| p4 | p8 | p12 | p16 |
$\downarrow$
| | | | |
| p1 | p5 | p9 | p13 |
| p6 | p10 | p14 | p2 |
| p11 | p15 | p3 | p7 |
| p16 | p4 | p8 | p12 |

第一行不移
第二行向左移1格
第三行向左移2格
第四行向左移3格

InvShiftRows就是移回去(還原)
#### 實作

void ShiftRows(unsigned char state[4][4]) {//只有16個所以也可以直接寫對應
    for (int i = 1; i <= 3; i++) {
        unsigned char row[4];
        for (int j = 0; j < 4; j++) {
            row[j] = state[i][j];
        }
        for (int j = 0; j < 4; j++) {
            state[i][(j - i + 4) % 4] = row[j];
        }
    }
}
void InvShiftRows(unsigned char state[4][4]) {
    for (int i = 1; i <= 3; i++) {
        unsigned char row[4];
        for (int j = 0; j < 4; j++) {
            row[j] = state[i][j];
        }
        for (int j = 0; j < 4; j++) {
            state[i][(i + j) % 4] = row[j];
        }
    }
}

### 列混淆(Mix Colume)
在正向的列混淆中，要將輸入的$4*4$矩陣左乘一個$4*4$的Mix矩陣(其乘法與加法在$GF(2^8)$中進行)

逆向的做法一樣只是將左乘的矩陣換成的Mix的反矩陣

#### 實作

unsigned char Mix[4][4] = {
0x02, 0x03, 0x01, 0x01,
0x01, 0x02, 0x03, 0x01,
0x01, 0x01, 0x02, 0x03,
0x03, 0x01, 0x01, 0x02
};

unsigned char InvMix[4][4] = {
0x0E, 0x0B, 0x0D, 0x09,
0x09, 0x0E, 0x0B, 0x0D,
0x0D, 0x09, 0x0E, 0x0B,
0x0B, 0x0D, 0x09, 0x0E
};

void MixColumns(unsigned char state[4][4]) {
    unsigned char tmp[4][4];
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            tmp[i][j] = state[i][j];
        }
    }
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            //乘換成擴展域的乘法，加換成擴展域的加法(XOR)
            state[i][j] = G_Multi(Mix[i][0], tmp[0][j]) ^ G_Multi(Mix[i][1], tmp[1][j]) ^ G_Multi(Mix[i][2], tmp[2][j]) ^ G_Multi(Mix[i][3], tmp[3][j]);
        }
    }
}
void InvMixColumns(unsigned char state[4][4]) {
    unsigned char tmp[4][4];
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            tmp[i][j] = state[i][j];
        }
    }
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            //乘換成擴展域的乘法，加換成擴展域的加法(XOR)
            state[i][j] = G_Multi(InvMix[i][0], tmp[0][j]) ^ G_Multi(InvMix[i][1], tmp[1][j]) ^ G_Multi(InvMix[i][2], tmp[2][j]) ^ G_Multi(InvMix[i][3], tmp[3][j]);
        }
    }
}

unsigned char G_Multi(unsigned char a, unsigned char b) {
    unsigned char result = 0;
    for (int i = 0; i < 8; i++) {
        if (a & 1) {
            result ^= b;
        }
        bool IshHighBit1 = b & 0x80;
        b <<= 1;//模擬乘上x(因為下次和a的高一次方運算)
        if (IshHighBit1) {
            b ^= 0x1B;//模擬除以(x^8 + x^4 + x^3 + x^1 + 1)，剛剛左移丟失的高位也剛好被除掉
        }
        a >>= 1;//將高一次方移到第一位
    }
    return result;
}

### 密鑰生成
流程圖
>
>來源：https://www.slideserve.com/keegan/chapter-5#google_vignette

其中$w_0 = K_0和k_1和k_2和k_3連起來(就是四分之一長的密鑰，而w_0和w_1和w_2和w_3就是原始的密鑰)$，g函式就是實作中的KeyScheduleCore

#### 實作

unsigned char RCON[11] = { 0x8d, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36 };

void KeyExpansion(const unsigned char* key, unsigned char* ExpandKey) {
    int KeyLength = 16;
    int ExpandKeyLength = 176;
    int Pre = 16;//to previous round key
    //int m = 0;
    //this four value is depanding on the size of the key. Now it is 128bit

    for (int i = 0; i < 16; i++) {
        ExpandKey[i] = key[i];
    }

    for (int i = KeyLength, rconIt = 1; i < ExpandKeyLength; rconIt++) {
        unsigned char tmp[4];
        memcpy(tmp, ExpandKey + i - 4, 4);
        unsigned char g[4];
        KeyScheduleCore(rconIt, tmp, g);

        memcpy(tmp, ExpandKey + i - Pre, 4);
        for (int j = 0; j < 4; j++) {
            tmp[j] ^= g[j];
        }

        memcpy(ExpandKey + i, tmp, 4);
        i += 4;

        for (int j = 0; j < 3; j++) {
            memcpy(tmp, ExpandKey + i - 4, 4);

            for (int k = 0; k < 4; k++) {
                ExpandKey[i + k] = tmp[k] ^ ExpandKey[i - Pre + k];
            }
            i += 4;
        }

        //如要支援其他大小的密鑰，還有其他東西要寫

    }
}

### ECB
在加密時不可能只加密128bit，明文可能會很長
而ECB是處理這個問題最簡單的模式(除次之外還有CBC,CTR,CFB,OFB)
但也是最不安全的，因為一樣的明文塊會加密出一樣的密文

ECB的處裡方式非常簡單，就是將明文每128bit切成一塊，並分別加密。

### pkcs7_padding
加密時一定會遇到明文大小不是16的倍數的情況，這時就需要填充。
而pkcs7的填充方法也很簡單，假設現在差一個字就能成為16的倍數，那就填充0x01，差兩個就填充兩個0x02，...差15個就填充15個0x0f，比較特別的是如果剛剛好是16的倍數，擇要填充16個0x10。u因為去除填充時需要以最後一個字元作為依據，來判定需要刪除多少字，例如最後一個是0x04那就知道倒數4個字都是填充，可以刪掉，所以填充0x010也是必要的

#### 實作

void pkcs7_padding(string& str, int BlockSize) {
	int PaddingSize = BlockSize - (str.size() % BlockSize);
	unsigned char PaddingChar = (unsigned char)PaddingSize;
	for (int i = 0; i < PaddingSize; i++) {
		str.push_back(PaddingChar);
	}

	return;
}

void pkcs7_unpadding(string& str) {
	int PaddingSize = (int)((unsigned char)str[str.size() - 1]);
	str.resize(str.size() - PaddingSize);
	return;
}

### 完整實作
實際實作上還有很多細節，(包括ECB的處理、Base64的使用等)
可以到github詳細觀看:https://github.com/samsonjaw/AES