AES&伽羅瓦域/有限域

# 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 流程圖 ![image](https://hackmd.io/_uploads/r1u7Wz4lC.png) 而解密就只是完全反過來而已 ### 金鑰加法層(Add Round Key) 明文的$4*4$矩陣和密鑰的$4*4$矩陣進行XOR運算(其實就是擴展域的加法) #### 實作 ```cpp= 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 >![image](https://hackmd.io/_uploads/HkFiriLpp.png) > 來源:wiki https://en.wikipedia.org/wiki/Rijndael_S-box >Inv S-box > ![image](https://hackmd.io/_uploads/Hk5bIiIp6.png) > 來源wiki https://en.wikipedia.org/wiki/Rijndael_S-box #### 實作 ```cpp= 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就是移回去(還原) #### 實作 ```cpp= 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的反矩陣 #### 實作 ```cpp= 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; } ``` ### 密鑰生成流程圖 >![image](https://hackmd.io/_uploads/Sk_kQUHAp.png) >來源：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 #### 實作 ```cpp= 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也是必要的 #### 實作 ```cpp= 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