AES

簡介

AES是一種對稱式加密算法

先輩知識

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

伽羅瓦域/有限域簡介

有限域中的元素集合是有限的，表示為

G F (p^{n})

，p是一個質數(素數)。EX

G F (2^{8})

，表示包含256個元素的有限域(其中元素可由0~p^n-1表示)

素域

當n=1時可稱為素域，在

G F (p)

中，所有的非0元素都有逆元素(反元素)。
其運算規則如下

加法和乘法和整數運算是一樣的，只是最後要mod p。而減法和除法就是加上/乘上其反元素
加法反元素定義為 (a + (a反元素)) mod p = 0
乘法反元素定義為 (a * (a反元素)) mod p = 1
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.表示法

在擴展域

G F (2^{n}) 中 以 係 數 為 G F (2)

的多項式表示
EX

G F (2^{8})

的每個元素都可表示為

a_{7} x^{7} + a_{6} x^{6} + . . . + a_{1} x + a_{0}, a_{i} \in G F (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}) m o d 2, (a_{6} + b_{6}) m o d 2, . . ., (a_{1} + b_{1}) m o d 2, (a_{0} + b_{0}) m o d 2))

A - B = ((a_{7} - b_{7}) m o d 2, (a_{6} - b_{6}) m o d 2, . . ., (a_{1} - b_{1}) m o d 2, (a_{0} - b_{0}) m o d 2)) = 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_{0} b_{0} m o d 2

c_{1} = (a_{1} b_{0} + a_{0} b_{1}) m o d 2

.
.
.
其實就是一般的多項式乘法(記得要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 Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

而解密就只是完全反過來而已

金鑰加法層(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

Image Not Showing Possible Reasons
The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted
Learn More →

來源:wiki https://en.wikipedia.org/wiki/Rijndael_S-box
Inv S-box

Image Not Showing Possible Reasons
The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted
Learn More →

來源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
$↓$

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矩陣(其乘法與加法在

G F (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

AES

簡介

先輩知識

伽羅瓦域/有限域簡介

素域

擴展域

1.表示法

2.加減法(基於GF(2^n))

乘法(基於GF(2^n))

AES算法

金鑰加法層(Add Round Key)

實作

位元組代換(SubByte)

實作

行位移(Shift Rows)

實作

列混淆(Mix Colume)

實作

密鑰生成

實作

ECB

pkcs7_padding

實作

完整實作

Read more

11th 初階班 上課講義

清交APCS組/交大資安組/成大資工智慧系統組 二階心得

選擇性敘述 if

學測後復建AP325練習紀錄

11th 初階班上課講義

清交APCS組/交大資安組/成大資工智慧系統組二階心得