实验目的

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

实验原理

DES算法将明文分成64位大小的众多数据块，即分组长度为64位。同时用56位密钥对64位明文信息加密，最终形成64位的密文。如果明文长度不足64位，即将其扩展为64位（如补零等方法）。具体加密过程首先是将输入的数据进行初始置换（IP），即将明文M中数据的排列顺序按一定的规则重新排列，生成新的数据序列，以打乱原来的次序。然后将变换后的数据平分成左右两部分，左边记为\(L_{0}\)，右边记为\(R_{0}\)，然后对\(R_{0}\)实行在子密钥（由加密密钥产生）控制下的变换f，结果记为f（\(R_{0}\)，\(K_{1}\)），再与\(L_{0}\)做逐位异或运算，其结果记为\(R_{1}\)，\(R_{0}\)则作为下一轮的\(L_{1}\)。如此循环16轮，最后得到\(L_{16}\)、\(R_{16}\)，再对\(L_{16}\)、\(R_{16}\)实行逆初始置换\(IP^{-1}\)，即可得到加密数据。解密过程与此类似，不同之处仅在于子密钥的使用顺序正好相反。

DES加密总流程图

实验过程

本实验用string类型记录明文、密钥、密文等信息，用全局变量keys[16]记录所有密钥。

DES加密

程序流程图

程序流程图

相关函数

输入检查

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

1
2
3
4
5
6
7
8
9
10
11
12
13
//输入64bit数据检查
string cin_check(string a) {
    int len = a.length();
    //判断输入
    if (len > 16) { return 0; }
    if (len != 16) {
        for (int i = 0; i < 16 - len; i++) {
            a = "0" + a;
        }
    }
    //cout << "检查输入:\t" << a << endl;
    return a;
}

二进制转十六进制

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 btoh(string h) {
    string b="";
    map<string, char>map_hb;
    map_hb["0000"] = '0';
    map_hb["0001"] = '1';
    map_hb["0010"] = '2';
    map_hb["0011"] = '3';
    map_hb["0100"] = '4';
    map_hb["0101"] = '5';
    map_hb["0110"] = '6';
    map_hb["0111"] = '7';
    map_hb["1000"] = '8';
    map_hb["1001"] = '9';
    map_hb["1010"] = 'A';
    map_hb["1011"] = 'B';
    map_hb["1100"] = 'C';
    map_hb["1101"] = 'D';
    map_hb["1110"] = 'E';
    map_hb["1111"] = 'F';
    for (int i = 0; i < 16; i++) {
        string t = h.substr(4 * i, 4);
        b += map_hb[t];
    }
    return b;
}

十六进制转二进制

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 htob(string 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";
    for (int i = 0; i < h.length(); i++) {
        if (h[i] >= 97 && h[i] <= 122) { h[i] -= 32; }
        b += map_hb[h[i]];
    }
    return b;
}

密钥生成

子密钥生成流程 
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
void Getkeys(string key) {
    //密钥64->56
    key = pc_1(key);
    //cout << "pc1置换后：\t" << key << "   位数为" << key.length() << endl;

    //key分成左和右
    string key_l = key.substr(0, 28);
    string key_r = key.substr(28, 28);
    //cout << "左密钥：\t" << key_l << "   位数为" << key_l.length() << endl;
    //cout << "右密钥：\t" << key_r << "   位数为" << key_r.length() << endl;
    for (int num = 0; num < 16; num++) {
       // cout << "第" << num+1 << "次\t\t：" << endl;

        //移位
        key_l = leftmove(key_l, num);
        key_r = leftmove(key_r, num);
        key = key_l + key_r;
       // cout << "key_56：\t" << key << "   位数为" << key.length() << endl;

        //密钥56->48
        string key_48 = "";
        key_48 += key_l;
        key_48 += key_r;

        //子密钥k1
        key_48 = pc_2(key_48);
        keys[num] = key_48;
        //cout << "密钥key："<<num+1<<"\t" << key_48 << "   位数为" << key_48.length() << endl;
    }
}

行pc-1置换

输入的初始密钥值为64位，但DES算法规定，其中第8、16、...、64位为奇偶校验位，不参予DES的运算。所以，实际可用位数只有56位，经过缩小选择即密钥置换PC-1的变换后，初始密钥的位数由64位变成了56位，将其平分位两部分\(C_{0}\)，\(D_{0}\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//密钥选择置换1 64->56
string pc_1(string key) {
    //压缩置换
    int pc1[56] = {
    57,49,41,33,25,17,9,1,58,50,42,34,26,18,
    10,2,59,51,43,35,27,19,11,3,60,52,44,36,
    63,55,47,39,31,23,15,7,62,54,46,38,30,22,
    14,6,61,53,45,37,29,21,13,5,28,20,12,4
    };
 
    char k[56];
    for (int i = 0; i < 56; i++) {
        k[i] = key[pc1[i]-1];
    }
    string key_1 = "";
    for (int i = 0; i < 56; i++) {
        key_1 += k[i];
    }
    return key_1;
}

左循环移位

得到\(C_{0}\)，\(D_{0}\)之后分别进行第一次循环左移，得到\(C_{1}\)，\(D_{1}\)，将\(C_{1}\)（28位）、\(D_{1}\)（28位）合并后得到56位的输出结果.

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
//左移位数
const int leftarr[16] ={
    1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1
};
//密钥左移
string leftmove(string key,int b) {  
    //key为密钥 b为密钥数组下标
    string a="";
    if (leftarr[b] == 1) {
        
        for (int i = 1; i < key.length(); i++) {
            a += key[i];
        }
        a += key[0];
    }
    else if (leftarr[b] == 2) {
        
        for (int i = 2; i < key.length(); i++) {
            a += key[i];
        }
        a += key[0];
        a += key[1];
    }
    //cout << "左移" << leftarr[b] << "位后：\t" << a << endl;
    return a;
}

pc-2置换

得到的56位的输出结果，再经过压缩置换PC-2，从而得到了密钥\(K_{1}\)（48位）。依次类推，便可得到\(K_{2}\)、...、\(K_{16}\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//密钥选择置换2 56->48
string pc_2(string key) {
    //压缩置换2
    int pc2[48] = {
    14,17,11,24,1,5,3,28,15,6,21,10,
    23,19,12,4,26,8,16,7,27,20,13,2,
    41,52,31,37,47,55,30,40,51,45,33,48,
    44,49,39,56,34,53,46,42,50,36,29,32
    };
    char k[48];
    for (int i = 0; i < 48; i++) {
        k[i] = key[pc2[i]-1];
    }
    string key_1 = "";
    for (int i = 0; i < 48; i++) {
        key_1 += k[i];
    }
    return key_1;
}

明文加密

明文加密流程 
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 DES_lock(string c, string a) {
    //c 密钥  a明文
    //加密
    //得到了十六轮密钥
    string key = htob(c);
    Getkeys(key);
    //IP置换
    string ming = IP(htob(a));
    //cout << "ip置换后：\t" << ming << "   位数为" << ming.length() << endl;
    //左明文 右明文
    string ming_l = ming.substr(0, 32);
    string ming_r = ming.substr(32, 32);
    string temp_ming_r = ming_r;

    //16轮轮函数
    for (int i = 0; i < 16; i++) {
        ming_r = Xor(F(ming_r, i), ming_l);
        ming_l = temp_ming_r;
        temp_ming_r = ming_r;
    }
    //密文合并
    ming = ming_r;
    ming += ming_l;
    //逆置换
    ming = IPR(ming);

    cout << "获得密文：\t" << btoh(ming) ;

    return btoh(ming);
}

初始置换IP

它的作用是把输入的64位数据块的排列顺序打乱，每位数据按照下面的置 换规则重新排列，即将第58位换到第一位，第50位换打第2位，...，依次类推。置换后的64位输出分为\(L_{0}\) 、\(R_{0}\)（左、右）两部分，每部分分别为32位。
58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//初始置换IP
string IP(string ming) {
    //初始置换IP表
    const int iptable[64] = {
        58,50,42,34,26,18,10,2,60,52,44,36,28,20,12,4,
        62,54,46,38,30,22,14,6,64,56,48,40,32,24,16,8,
        57,49,41,33,25,17,9,1,59,51,43,35,27,19,11,3,
        61,53,45,37,29,21,13,5,63,55,47,39,31,23,15,7
    };

    char k[64];
    for (int i = 0; i < 64; i++) {
        k[i] = ming[iptable[i] - 1];
    }
    string key_1 = "";
    for (int i = 0; i < 64; i++) {
        key_1 += k[i];
    }
    return key_1;
}

\(R_{0}\)和\(K_{1}\)经过f（\(R_{0}\)，\(K_{1}\)）变换后的输出结果，再和\(L_{0}\)进行异或运算，输出结果位\(R_{1}\)，\(R_{0}\)则赋给\(L_{1}\)。\(L_{1}\)和\(R_{1}\)同样再做类似运算生成\(L_{2}\)和\(R_{2}\)，...，经过16次运算后生成\(L_{16}\)和\(R_{16}\)。

f函数

f 函数是多个置换函数和替代函数的组合函数，它将32位比特的输入变换为32位的输出，原理图如下图：

f函数

\(R_{i}\)经过扩展运算E变换后扩展为48位的E（\(R_{i}\)），与 进行异或运算后输出的结果分成8组，每组6比特。每一组再经过一个S盒（共8个S盒）运算转换为4位，8个4位合并为32位后再经过P变换输出为32位的 。其中，扩展运算E与置换P主要作用是增加算法的扩散效果。

1
2
3
4
5
6
7
8
9
10
11
string F(string ming_r,int i) {
    //右边进入轮函数
    ming_r = E(ming_r);
    //与当前轮密钥异或
    ming_r = Xor(ming_r, keys[i]);
    //S盒压缩
    ming_r = S(ming_r);
    //P置换
    ming_r = P(ming_r);
    return ming_r;
}
E扩展运算

将\(R_{i-1}\)（即输入A）扩展从32位扩展为48位，32位->48位 通过扩展置换E，数据的右半部分\(R_{i-1}\)从32位扩展到48位。扩展置换改变了位的次序，重复了某些位。

作用：产生与秘钥相同长度的数据以进行异或运算，\(R_{0}\)是32位，子秘钥是48位，所以\(R_{0}\)要先进行扩展置换之后与子秘钥进行异或运算；提供更长的结果，使得在替代运算时能够进行压缩。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//E盒扩展
string E(string ming) {
    const int etable[48] =
    {
        32,1,2,3,4,5,4,5,6,7,8,9,
        8,9,10,11,12,13,12,13,14,15,16,17,
        16,17,18,19,20,21,20,21,22,23,24,25,
        24,25,26,27,28,29,28,29,30,31,32,1
    };
    char k[48];
    for (int i = 0; i < 48; i++) {
        k[i] = ming[etable[i] - 1];
    }
    
    string key_1 = "";
    for (int i = 0; i < 48; i++) {
        key_1 += k[i];
    }
    
    return key_1;
}
异或运算

48位中间结果与48位子密钥按位异或,引入密钥.

1
2
3
4
5
6
7
8
9
//异或
string Xor (string ming,string key) {
    string res = "";
    for (int i = 0; i < ming.length(); i++) {
        if (((int(ming[i] - 48))^(int(key[i] - 48)) )== 1) { res += "1"; }
        else { res += "0"; }
    }
    return res;
}
S盒选择

8个S盒，每个6位输入，4位输出，混淆作用，48位->32位.

\(R_{n}\)扩展置换之后与子秘钥Kn异或以后的结果作为输入块，功能是把48位数据压缩为32位数据，由8个不同的代替盒(S盒)完成。每个S盒有6位输入，4位输出。48位的输入块被分成8个6位的分组，每一个分组对应一个S盒代替操作。经过S盒代替，得到8个4位分组结果---32位。

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
51
52
53
54
55
56
57
58
59
60
61
62
//S盒
string S(string ming) {
    int stable[8][4][16] = {
        //S1
        {{14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7},
        {0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8},
        {4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0},
        {15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13}},
        //S2
        {{15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10},
        {3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5},
        {0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15},
        {13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9}},
        //S3
        {{10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8},
        {13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1},
        {13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7},
        {1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12}},
        //S4
        {{7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15},
        {13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9},
        {10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4},
        {3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14}},
        //S5
        { {2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9},
        {14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6},
        {4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14},
        {11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3}},
        //S6
        { {12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11},
        {10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8},
        {9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6},
        {4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13}},
        //S7
        {{4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1},
        {13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6},
        {1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2},
        {6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12}},
        //S8
        {{13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7},
        {1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2},
        {7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8},
        {2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11}}
    };
    string m[8];
    string res="";
    map<string, int>mp_si;
   
    for (int i = 0; i < 8; i++) {
        string x = "";
        string y = "";
        m[i]= ming.substr(6*i, 6);
        x.append(1,m[i][0]).append(1,m[i][5]);
        y.append(1, m[i][1]).append(1, m[i][2]).append(1, m[i][3]).append(1, m[i][4]);
       // cout <<endl<< x << endl << y ;
        //在S盒中找到的xxxx
        int s = stable[i][bstod(x)][bstod(y)];
        res += dtobs(s);
    }
    //cout <<"S盒" << res << "位数" << res.length() << endl;
    return res;
}
P置换

将S盒输出的32位数据打乱重排，扩散作用，32位->32位；结果为一轮f函数输出.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//P置换
string P(string ming) {
    int ptable[32] =
    {
        16,7,20,21,29,12,28,17,1,15,23,26,5,18,31,10,
        2,8,24,14,32,27,3,9,19,13,30,6,22,11,4,25
    };
    char k[32];
    for (int i = 0; i < 32; i++) {
        k[i] = ming[ptable[i] - 1];
    }
    string key_1 = "";
    for (int i = 0; i < 32; i++) {
        key_1 += k[i];
    }
    return key_1;
}

逆初始置换\(IP^{－1}\)

它将\(L_{16}\)和\(R_{16}\)作为输入，进行逆初始置换得到密文输出。逆初始置换是初始置换的逆运算：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//逆置换
string IPR(string ming) {
    //逆初始置换IPR表
    const int iprtable[64] = {
        40,8,48,16,56,24,64,32,39,7,47,15,55,23,63,31,
        38,6,46,14,54,22,62,30,37,5,45,13,53,21,61,29,
        36,4,44,12,52,20,60,28,35,3,43,11,51,19,59,27,
        34,2,42,10,50,18,58,26,33,1,41,9,49,17,57,25
    };
    char k[64];
    for (int i = 0; i < 64; i++) {
        k[i] = ming[iprtable[i] - 1];
    }
    string key_1 = "";
    for (int i = 0; i < 64; i++) {
        key_1 += k[i];
    }
    return key_1;
}

实验结果

PS:第一次输入的明文虽然只有0，但是程序会用0补齐至明文为64位。

DES加密测试结果

DES解密

实验流程

DES加密和解密使用相同的算法，唯一的不同是密钥的次序相反。如果各轮加密密钥分别是\(K_{1}\)，\(K_{2}\)，\(K_{3}\)...\(K_{16}\)，那么解密密钥就是\(K_{16}\)，\(K_{15}\)，\(K_{14}\)...\(K_{1}\)。

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
//解密
    cout << "---------------------------DES解密---------------------------" << endl;
    //输入密钥
    cout << "输入密钥：\t";9
    cin >> c;
    c = cin_check(c);
    //得到了十六轮密钥
    string key = htob(c);
    Getkeys(key);

    //输入密文
    cout << "输入密文：\t";
    cin >> a;
    a = cin_check(a);
    //IP置换
    string ming = IP(htob(a));
    //cout << "ip置换后：\t" << ming << "   位数为" << ming.length() << endl;
    //左明文 右明文
    string ming_l = ming.substr(0, 32);
    string ming_r = ming.substr(32, 32);
    string temp_ming_r = ming_r;

    //16轮轮函数
    for (int i = 15; i >= 0; i--) {
        ming_r = Xor(F(ming_r, i), ming_l);
        ming_l = temp_ming_r;
        temp_ming_r = ming_r;
    }
    //密文合并
    ming = ming_r;
    ming += ming_l;
    //逆置换
    ming = IPR(ming);
    cout << "获得明文：\t" << btoh(ming) << endl;

实验结果

DES解密测试结果

雪崩效应

对DES的密文进行雪崩效应检验。即固定密钥， 仅改变明文中的一位，统计密文改变的位数；固定明文，仅改变密钥中的一位，统计密文改变的位数。

实验流程

固定密钥，改变明文一位

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
cout << "---------------------------雪崩效应-改变明文---------------------------" << endl;
//输入密钥
cout << "固定密钥：\t";
cin >> c;
string d = cin_check(c);
//输入明文
cout << "输入明文：\t";
cin >> a;
string b = cin_check(a);
//原本得到的密文sta
string sta= DES_lock(d, b);
cout << endl;
sta = htob(sta);
int diff[64] = {0};
double sum = 0;
for (int i = 0; i < 64; i++) {
    cout << "改变第" << i+1 << "位\t" ;
    //翻转
    d = cin_check(c);
    b = htob(cin_check(a));
    //cout << "翻转前:" << b << endl;
    if (b[i] == '0') { b[i] = '1'; }
    else { b[i] = '0'; }
    //cout << "翻转后:" << b << endl;

    b = btoh(b);
    string sta2=htob(DES_lock(d, b));
    for (int j = 0; j < 64; j++) {
        if (sta2[j] != sta[j]) { diff[i]++; }
    }
    sum += diff[i];
    cout << "\t改变数量：" << diff[i] << endl;
}

cout << "平均改变位数：\t" << sum / 64 << 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
cout << "---------------------------雪崩效应-改变密钥---------------------------" << endl;
    //输入密钥
    cout << "输入密钥：\t";
    cin >> c;
    string d = cin_check(c);
    //输入明文
    cout << "固定明文：\t";
    cin >> a;
    string b = cin_check(a);
    //原本得到的密文sta
    string sta = DES_lock(d, b);
    cout << endl;
    sta = htob(sta);
    int diff[64] = { 0 };
    double sum = 0;
    for (int i = 0; i < 64; i++) {
        cout << "改变第" << i + 1 << "位\t";
        //翻转
        d = htob(cin_check(c));
        b = cin_check(a);
        //cout << "翻转前:" << b << endl;
        if (d[i] == '0') { d[i] = '1'; }
        else { d[i] = '0'; }
        //cout << "翻转后:" << b << endl;

        d = btoh(d);
        string sta2 = htob(DES_lock(d, b));
        for (int j = 0; j < 64; j++) {
            if (sta2[j] != sta[j]) { diff[i]++; }
        }
        sum += diff[i];
        cout << "\t改变数量：" << diff[i] << endl;
    }

    cout << "平均改变位数：\t" << sum / 64 << endl;

实验结果

固定密钥，改变明文一位:

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

可以看到平均改变位数为32.1719位。

固定明文，改变密钥一位：

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

可以看到平均改变位数为 28.9844位，并且，改变奇偶校验位不会对最后结果产生影响。