实验目的

通过用AES算法对实际的数据进行加密和解密来深刻了解AES的运行原理。

实验原理

AES算法本质上是一种对称分组密码体制，采用代替/置换网络，每轮由三 层组成：线性混合层确保多轮之上的高度扩散，非线性层由16个S盒并置起到混淆的作用，密钥加密层将子密钥异或到中间状态。Rijndael是一个迭代分组密码，其分组长度和密钥长度都是可变的，只是为了满足AES的要求才限定处理的分组大小为128位，而密钥长度为128位、192位或256位，相应的迭代轮数N，为10轮、12轮、14轮。AES汇聚了安全性能、效率、可实现性、灵活性等优点。最大的优点是可以给出算法的最佳差分特征的概率，并分析算法抵抗差分密码分析及线性密码分析的能力。其实现的加密流程图如图-1所示。

加密的主要过程包括：对明文状态的一次密钥加，N_r-1轮轮加密和末尾轮轮加密，最后得到密文。其中N_r-1轮轮加密每一轮有四个部件，包括字节代换部件ByteSub、行移位变换ShiftRow、列混合变换NixColumn和一个密钥加AddRoundKey部件，末尾轮加密和前面轮加密类似，只是少了一个列混合变换NixColumn部件。

AES算法流程

实验过程

总体设计

在本次实验中，密钥、明文、密文遍码均为string类型，将输入的128bit的数据分为四个部分，每32bit一组，变为十六进制的话就是8个十六进制数（4个字节）一组，所以一组明文（密文）需要用string[4]数组记录。本程序中的明文用全局变量string ming[4]记录，密文用全局变量string ci[4]记录，密钥由于扩展后会得到44个，所以用string k[44]记录。

程序流程

密钥扩展

密钥扩展流程

密钥扩展过程说明：

  1. 将初始密钥以列为主，转化为4个32 bits的字，分别记为w[0...3]；

  2. 按照如下方式，依次求解w[j]，其中j是整数并且属于[4,43]；

  3. 若j%4=0,则w[j]=w[j-4]^T(w[j-1]),否则w[j]=w[j-4]^w[j-1]；

函数T由3部分组成：字循环、字节代换和轮常量异或，这3部分的作用分别如下:

  1. 字循环：将1个字中的4个字节循环左移1个字节。即将输入字[b0, b1, b2, b3]变换成[b1,b2,b3,b0]。

  2. 字节代换：对字循环的结果使用S盒进行字节代换。

  3. 轮常量异或：将前两步的结果同轮常量Rcon[j]进行异或，其中j表示轮数。

1
2
3
4
5
6
7
//T函数
string T(string a, int i) {
    a = left_one(a);
    a = key_S(a);
    a = key_xor(a, i);
    return a;
}

T函数的组成部分如上述代码，接下来将对每个函数进行介绍盒分析。

字循环

在本实验中，通过讲密钥记录为string类型，然后传入以下函数实现左移：这个函数实现了左移一位，具体的实现方法是循环获取到前两位之后的字符，然后把前两位贴到最后，从而实现左移。

1
2
3
4
5
6
7
8
9
10
11
//左移一位
string left_one(string a) {
    string b ="";
    for (int i = 2; i < 8; i++) {
        b += a[i];
    }
    b += a[0];
    b += a[1];
    //cout << "左移后：\t" << b << endl;
    return b;
}

字节代换

分别对每个字节按S盒进行映射，每个字节中的前四位代表S盒中的行，后四位代表S盒中的列，通过这样的映射关系实现字节的代换。

AES算法流程

下列代码中，ctode()函数表示将字符转化为数字，htos()表示将数字重新转换回字符，最后通过a1记录所有转化过来的字符，从而实现字节代换。

1
2
3
4
5
6
7
8
9
//S盒置换
string key_S(string a) {
    string a1 = "";
    for (int i = 0; i < a.length(); i+=2) {
        a1 += htos(S[ctode((a[i]))][ctode((a[i+1]))]);
    }
    //cout << "S盒置换：\t" << a1 << endl;
    return a1;
}

轮常量异或

将前两步的结果同轮常量Rcon[j]进行异或，其中j表示轮数。 轮常量Rcon[j]是一个字，其值见下表。

轮常量Rcon 
1
2
3
4
5
6
7
8
9
10
//key和常量表异或
string key_xor(string a,int n) {
    string b = "";
    for (int i = 0; i < a.length(); i++) {
        string c = htoc(ctode(a[i]) ^ ctode(Rcon[n][i]));
        b += c;
    }
    //cout << "kr异或后：\t" << b<<endl;
    return b;
}

整体代码

将上述代码整合得到Getkeys()函数，该函数的作用为将输入密钥当作参数，最后将密钥扩展后得到的44个密钥存入到全局变量k[44]中，留给之后的加密、解密函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Getkeys(string key) {
    key = cin_check(key);
    for (int i = 0; i < 4; i++) {
        k[i] = "";
        for (int j = i * 8; j < i * 8 + 8; j++) {
            k[i] += key[j];
        }
        //cout << "k[" << i << "]：" << k[i] << endl;
    }
    int o = 0;
    for (int i = 4; i < 44; i++) {
        if (i % 4 != 0) {
            //不是4的倍数
            k[i] = keys_xor(k[i - 4], k[i - 1]);
        }
        else {
            k[i] = keys_xor(k[i - 4], T(k[i - 1],o));
            o++;
        }
    }
    //cout << "已生成44个密钥！" << endl;
}

AES明文加密

AES加密过程涉及到4种操作：字节替代（SubBytes）、行移位（ShiftRows）、列混淆（MixColumns）和轮密钥加（AddRoundKey）。解密过程分别为对应的逆操作。由于每一步操作都是可逆的，按照相反的顺序进行解密即可恢复明文。加解密中每轮的密钥分别由初始密钥扩展得到。算法中16字节的明文、密文和轮密钥都以一个4x4的矩阵表示。

字节替代

字节替代的过程和密钥扩展中S盒替代的过程相同，此处不再赘述。

行移位

行移位的功能是实现一个4x4矩阵内部字节之间的置换，但是注意这里的第一列表示按顺序输入的密钥。行移位需要将第二行左移一位，第三行左移两位，第四行左移三位。

正向行移位

在本程序中，ming[4]输入存储下来的是按顺序获得的明文，所以首先需要拿到列数据并进行存储(也就是行移位中对应的行数据)，然后通过在密钥左移中的letf_one()函数来实现左移。将每一行需要移位的数目记下并放入循环中，左移一位会调用一次letf_one()、左移两位会调用两次letf_one()，以此类推实现行移位功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
string ming_l[4] = { "" };
//拿到列数据
for (int n = 0; n < 4; n++) {
    //第n列
    for (int i = 0; i < 4; i++) {
        //第i行
        for (int j = n * 2; j < n * 2 + 2; j++) {
            ming_l[n] += ming[i][j];
        }
    }
    //cout << "ming_l[" << n << "]：" << ming_l[n] << endl;
}

//左移
for (int i = 0; i < 4; i++) {
    int j = i;
    while (j != 0) {
        ming_l[i] = left_one(ming_l[i]);
        j--;
    }
    //cout << ming_l[i] << endl;
}

列混淆

根据矩阵的乘法可知，在列混淆的过程中，每个字节对应的值只与该列的4个值有关系。

正向列混淆

此处的乘法和加法都是定义在GF(\(2^{8}\))上的，需要注意如下几点：

  • 将某个字节所对应的值乘以2，其结果就是将该值的二进制位左移一位，如果该值的最高位为1（表示该数值不小于128），则还需要将移位后的结果异或00011011；

  • 乘法对加法满足分配率

  • 此处的矩阵乘法与一般意义上矩阵的乘法有所不同，各个值在相加时使用的是模2加法（相当于是异或运算）

所以相当于进行以下运算：

定义在GF上

首先先完成对上述GF(\(2^{8}\))上"*"和"+"操作的实现：

  1. 首先记录传入的一组明文(32bit)和其需要相乘的数据(32bit)，然后通过两个数组分别获取到传入一组数据的每个字节，对每个相乘数据(例如："02""03""01""01")字节的值进行判断，通过sum来记录其二进制中是否为"01"。

  2. 若该数为"01"，直接获取该字节;

  3. 若该数为其他数字，则用mult2[3]数组记录明文字节分别和"02""04""08"进行运算的值。

  4. 然后再判断相乘数据字节的的具体数据可以由哪些字节异或得到(例如"0C"由"04"、"08"组成)，就需要将对象的mult2[3]中对应的字节进行异或。这里需要注意加密和解密过程中相乘数据字节的不同，本程序中引入了lock标志位来标识。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
string ming_xor(string a, string b) {
    string m[4] = { "" };
    string f[4] = { "" };
    for (int i = 0; i < 4; i++) {
        for (int j = i * 2; j < i * 2 + 1; j++) {
            m[i] += a[j];
            m[i] += a[j + 1];
            f[i] += b[j];
            f[i] += b[j + 1];
        }
        //cout << "m[i]: " << m[i] << "  f[i]：" << f[i] << endl;
    }
    int c[4];
    //两两相乘 再相加
    for (int i = 0; i < 4; i++) {
        c[i] = stode(m[i]);
        int p = stode(f[i]);
        int sum = (p / 8) + (p % 8 / 4) + (p % 8 % 4 / 2);
       // cout << "sum:" << sum << endl;
        int mult2[3] = { 0 };
        int lock = 1;

        int temp = c[i];
        if (sum != 0) {
            for (int j = 0; j < 3; j++) {
                c[i] = (c[i] << 1);
                //cout << "左移一位c[i]：" << c[i] << endl;
                if (c[i] >= 256) {

                    c[i] = c[i] & 0xff;
                    c[i] = c[i] ^ 0b00011011;
                    //cout << "大于256的c[i]：" << c[i] << endl;
                }
                mult2[j] = c[i];
                //cout << "mult2：" << mult2[j] << endl;
            }
            //算和
            if (p / 8 == 1) { c[i] = mult2[2]; lock = 0; }
            else { c[i] = mult2[0]; }

            if (p % 8 / 4 == 1) { c[i] ^= mult2[1]; }
            if (p % 8 % 4 / 2 == 1 && lock == 0) { c[i] ^= mult2[0]; }
            if (p % 2 == 1) { c[i] ^= temp; }
        }
        else { c[i] = temp; }
       // cout << "c[i]" << c[i] << endl;
    }
    int aq = c[0] ^ c[1] ^ c[2] ^ c[3];
    return htos(aq);
}

在程序实现的过程中，q表示当前轮数，需要注意在最后一轮的时候不用进行列混淆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//列混淆
string Mix[4] = {
   "02030101",
   "01020301",
   "01010203",
   "03010102"
};

string ming_3[4] = { "" };
if (q == 10) {
    for (int n = 0; n < 4; n++) {
        //第n列
        for (int i = 0; i < 4; i++) {
            //第i行
            for (int j = n * 2; j < n * 2 + 2; j++) {
                ming_3[n] += ming_2[i][j];
            }
        }
        //cout << "ming_3[" << n << "]：" << ming_3[n] << endl;
    }
}
else {
    for (int i = 0; i < 4; i++) {
        //第一行 mix 四列ming->第一行
        for (int j = 0; j < 4; j++) {
            ming_3[i] += ming_xor(ming_2[j], Mix[i]);
        }
        //cout << ming_3[i] << endl;
    }
}

轮密钥加

轮密钥加是将128位轮密钥Ki同状态矩阵中的数据进行逐位异或操作，其中的异或函数与在密钥扩展中的异或函数相同。

1
2
3
4
5
6
7
8
9
void AddRoundKey(int n) {
    //行数据
    //cout << "轮密钥加:" << endl;
    int j = n * 4;
    for (int i = 0; i < 4; i++) {
        ming[i] = keys_xor(ming[i], k[j]);
        j++;
    }
}

AES密文解密

AES解密的过程实际上就是AES加密的逆过程，例如在轮函数中，AES加密的某一轮的过程是字节替代->行移位->列混淆->轮密钥加，所以AES解密的对应这一轮的操作就应该是轮密钥加->逆列混淆->逆行移位->逆字节替换。

逆向行移位

行移位的逆变换是将状态矩阵中的每一行执行相反的移位操作，例如AES-128中，状态矩阵的第0行右移0字节，第1行右移1字节，第2行右移2字节，第3行右移3字节。在本程序中的实现，采用使用左移3位替换右移1位的方法，接着使用left_one()函数，与实现行移位功能大致相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
string ming_l[4] = { "" };
//拿到列数据
for (int n = 0; n < 4; n++) {
    //第n列
    for (int i = 0; i < 4; i++) {
        //第i行
        for (int j = n * 2; j < n * 2 + 2; j++) {
            ming_l[n] += ci[i][j];
        }
    }
    //cout << "ming_l[" << n << "]：" << ming_l[n] << endl;
}

//右移
//cout << "进行右移：" << endl;
for (int i = 0; i < 4; i++) {
    int j = 4-i;
    while (j != 0) {
        ming_l[i] = left_one(ming_l[i]);
        j--;
    }
    //cout << ming_l[i] << endl;
}

逆字节替换

逆字节替换的过程与字节替换的过程完全相同，只不过是将S盒换成了逆S盒。

逆S盒 
1
2
3
4
5
6
7
8
9
10
//逆S盒置换
string key_SR(string a) {
    string a1 = "";

    for (int i = 0; i < a.length(); i += 2) {
        a1 += htos(SR[ctode((a[i]))][ctode((a[i + 1]))]);
    }
    //cout << "S盒置换：\t" << a1 << endl;
    return a1;
}

轮密钥加

轮密钥加的过程与加密过程中的完全相同，但是对应的密钥与加密过程中相反，例如加密过程在最后一轮使用k[40...43],解密过程就需要在第一轮使用k[40...43]。

1
2
3
4
5
6
7
8
void AddRoundKeyR(int n) {
    //行数据
    //cout << "轮密钥加:" << endl;
    int j = n * 4;
    for (int i = 0; i < 4; i++) {
        ci[i] = keys_xor(ci[i], k[j]);
        j++;
    }

逆向列混淆

逆向列混合变换可由下图的矩阵乘法定义：

逆向列混淆

逆向列混淆完全可以调用与正向列混淆相同的函数，因为当时在实现过程中考虑到了"09"、"0B"、"0D"、"0E"的有限域*和+。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//列混合-R
string Mix[4] = {
   "0E0B0D09",
   "090E0B0D",
   "0D090E0B",
   "0B0D090E"
};
//cout << "将要进行逆列混淆：" << endl;

string ming_3[4] = { "" };
if (q == 0) {
    for (int n = 0; n < 4; n++) {
        //第n列
        for (int i = 0; i < 4; i++) {
            //第i行
            for (int j = n * 2; j < n * 2 + 2; j++) {
                ming_3[n] += ming_2[i][j];
            }
        }
        //cout << "ming_3[" << n << "]：" << ming_3[n] << endl;
    }
}
else {
    for (int i = 0; i < 4; i++) {
        //第一行 mix 四列ming->第一行
        for (int j = 0; j < 4; j++) {
            ming_3[i] += ming_xor(ming_2[j], Mix[i]);
        }
        //cout << ming_3[i] << endl;
    }
}

雪崩效应-改变密钥

实现过程如下：

  1. 输入明文和密钥并获得密文，存储得到的密文。

  2. 将输入密钥key的每个字符拿出(4bit)，通过将它变为二进制数实现比特位翻转。

  3. 将翻转后的字符替换原来的字符。

  4. 重新进行AES加密，将新得到的密文记录。

  5. 使用编写函数changenum()对比新密文和旧密文的比特位变化。

  6. 使用变量all记录这128次变化总共的比特位变化，最后除以128得到改变的平均值。

对比新密文和旧密文比特位变化的函数changenum():

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int changenum(string init, string later) {
    sum = 0;
    //cout << init << " " << later << endl;;
    for (int i = 0; i < init.length(); i++) {
        //拿到第i位的数字->string 4位二进制数
        string a = htob(init[i]);
        string b = htob(later[i]);
        //cout << "a:" << a << "b:" << b << endl;
        for (int j = 0; j < a.length(); j++) {
            if (a[j] != b[j]) { sum++; }
        }
    }
    all += sum;
    return sum;
}

整体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
cout << "输入明文：\t" ;
cin >> m;
cout << "输入密钥：\t" ;
cin >> key;
key = cin_check(key);
Getkeys(key);
AES_lock(m);
init_m = init_m.append(ming[0]).append(ming[1]).append(ming[2]).append(ming[3]);
cout << "得到密文：\t" << init_m<<endl;
all = 0;
for (int i = 0; i <32 ; i++) {

    //要替换第几个字母
    //cout << "改变前的key[i]：" << key[i] << endl;
    
    //拿到第一个字母
    for (int j = 0; j < 4; j++) {
        string temp_key = key;
        cout << "改变第" << 4*i+j+1 << "位：\t" ;
        string temp1 = htob(key[i]);//拿到四个数字
        if (temp1[j] == '0') { temp1[j] = '1'; }
        else { temp1[j] = '0'; }
        temp_key[i] = btoh(temp1);

        cout  << temp_key ;

        Getkeys(temp_key);
        AES_lock(m);
        string later_m = "";
        later_m=later_m.append(ming[0]).append(ming[1]).append(ming[2]).append(ming[3]);
        cout << "\t得到密文：" << later_m;
        
        cout << "\t改变位数：" << changenum(init_m,later_m)<<endl;
        
    }
}
cout << "平均改变位数：\t" << float(all) / 128 << endl;

雪崩效应-改变明文

实现过程与改变密钥的过程大致相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
cout << "输入明文：\t";
cin >> m;
//存储原来明文
string mm = cin_check(m);
cout << "输入密钥：\t";
cin >> key;
key = cin_check(key);
Getkeys(key);
AES_lock(m);
init_m = "";
init_m = init_m.append(ming[0]).append(ming[1]).append(ming[2]).append(ming[3]);
cout << "得到密文：\t" << init_m << endl;
all = 0;
for (int i = 0; i < 32; i++) {
    //要替换第几个字母

    //拿到第一个字母
    for (int j = 0; j < 4; j++) {
        string temp_m = mm;
        cout << "改变第" << 4 * i + j + 1 << "位：\t";
        string temp1 = htob(mm[i]);//拿到四个数字
        if (temp1[j] == '0') { temp1[j] = '1'; }
        else { temp1[j] = '0'; }
        temp_m[i] = btoh(temp1);

        cout << temp_m;

        AES_lock(temp_m);
        string later_m = "";
        later_m = later_m.append(ming[0]).append(ming[1]).append(ming[2]).append(ming[3]);
        cout << "\t得到密文：" << later_m;

        cout << "\t改变位数：" << changenum(init_m, later_m) << endl;
    }
}
cout << "平均改变位数：\t" << float(all) / 128 << endl;

实验结果

密钥扩展

密钥扩展

AES加密

AES加密

AES解密

AES解密

雪崩效应-改变密钥

将密钥设置为128位0，这样可以能直观的看出翻转这128位的变化。

雪崩效应-改变密钥
雪崩效应-改变密钥

可以看到平均改变位为64.3125位

雪崩效应-改变明文

将明文设置为128位0，这样可以能直观的看出翻转这128位的变化。

雪崩效应-改变明文
雪崩效应-改变明文

可以看到平均改变位为63.6328位

*相关函数

输入检查

如果输入的密钥、明文、密文不足128位，会自动补0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//128bit检查
string cin_check(string a) {
    int len = a.length();
    //判断输入
    if (len > 32) { return 0; }
    if (len != 32) {
        for (int i = 0; i < 32 - len; i++) {
            a = "0" + a;
        }
    }
    for (int i = 0; i < 32; i++) {
        if (a[i] >= 97 && a[i] <= 122) {
            a[i] -= 32;
        }
    }
    //cout << "检查输入:\t" << a <<"位数：\t"<<a.length() << endl;
    return a;
}

进制转换

本实验中的进制转换基本都是通过map实现单字节的变换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//十六进制转二进制
string htob(char h) {
    string b;
    map<char, string>map_hb;
    map_hb['0'] = "0000";
    map_hb['1'] = "0001";
    map_hb['2'] = "0010";
    map_hb['3'] = "0011";
    map_hb['4'] = "0100";
    map_hb['5'] = "0101";
    map_hb['6'] = "0110";
    map_hb['7'] = "0111";
    map_hb['8'] = "1000";
    map_hb['9'] = "1001";
    map_hb['A'] = "1010";
    map_hb['B'] = "1011";
    map_hb['C'] = "1100";
    map_hb['D'] = "1101";
    map_hb['E'] = "1110";
    map_hb['F'] = "1111";
    b = map_hb[h];
    return b;
}

字符与整型转换

本实验中的字符与整型转换基本都是通过map实现单字节的变换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//十六进制转字符串 一字节
string htos(int a) {
    int b = a / 16;
    int c = a % 16;
    map<int, string>mp_ic;
    mp_ic[0] = "0";
    mp_ic[1] = "1";
    mp_ic[2] = "2";
    mp_ic[3] = "3";
    mp_ic[4] = "4";
    mp_ic[5] = "5";
    mp_ic[6] = "6";
    mp_ic[7] = "7";
    mp_ic[8] = "8";
    mp_ic[9] = "9";
    mp_ic[10] = "A";
    mp_ic[11] = "B";
    mp_ic[12] = "C";
    mp_ic[13] = "D";
    mp_ic[14] = "E";
    mp_ic[15] = "F";
    string s = "";
    s += mp_ic[b];
    s += mp_ic[c];
    return s;
}