信息安全与技术作业一：DES算法

1.1算法原理概述

1.1.1介绍

Data Encryption Standard (DES) 是一种典型的对称密钥算法，采用块加密方法，运行速度较慢，但较安全。DES 是一种典型的块加密方法：它以64位为分组长度，64位一组的明文作为算法的输入，通过一系列复杂的操作，输出同样 64位长度的密文。DES 使用加密密钥定义变换过程，因此算法认为只有持有加密 所用的密钥的用户才能解密密文。DES 采用64位密钥，但由于每8位中的最后1位用于奇偶校验，实际有效密钥长度为56位。密钥可以是任意的56位的数，且可 随时改变。其中极少量的数被认为是弱密钥，但能容易地避开它们。所有的保密性依赖于密钥。DES 算法的基本过程是换位和置换。

1.1.2 信息空间

DES的信息空间由 {0, 1} 组成的字符串构成，原始明文消息和经过 DES 加密的密文信息是8个字节 (64位) 的分组，密钥也是64位。 ²

  • 原始明文消息按 PKCS#5 (RFC 8018) 规范进行字节填充：

  • 原始明文消息最后的分组不够8个字节 (64位) 时，在末尾以字节填满，填入的字节取值相同，都是填充的字节数目；

  • 原始明文消息刚好分组完全时，在末尾填充8个字节 (即增 加一个完整分组)，每个字节取值都是08。 ²

  • 明文分组结构：M = m1m2 … m64 , mi Î{0, 1}, i = 1 .. 64. ² 密文分组结构：C = c1c2 … c64 , ci Î{0, 1}, i = 1 .. 64. ²

  • 密钥结构：K = k1k2 … k64 , ki Î{0, 1}, i = 1 .. 64.

  • 除去 k8, k16, …, k64 共8位奇偶校验位，起作用的仅56位。

  • 算法过程用到的16个密钥记为 K1, K2, …, K16。

1.1.3 算法过程

DES加密过程：

C = Ek(M) = IP-1 · W · T16 · T15 ·… · T1 · IP(M).

  • M 为算法输入的64位明文块；

  • Ek 描述以 K 为密钥的加密函数，由连续的过程复合构成；

  • IP 为64位初始置换；

  • T1, T2 , …, T16 是一系列的迭代变换；

  • W 为64位置换，将输入的高32位和低32位交换后输出；

  • IP-1 是 IP 的逆置换；

  • C 为算法输出的64位密文块。

DES的解密过程与加密完全相同，只不过从后向前使用子密钥列表。

M = Dk(C) = IP-1 · W · T1 · T2 · … · T16 · IP (C).

1.2 总体结构

image-20191220151904677

1.3 模块分解

1.3.1 IP初始置换

根据初始置换表对输入明文进行置换，置换过程就是把输入数据的第58位放到第1位，50位放到第2位，42位放到第3位，以此类推，初始置换以后得到的是一个64位的输出。

//ip初始置换表  
int DES::ip[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 };  
  
//ip置换    
bitset<64> DES::IP(const bitset<64> & plain) {    
    bitset<64> M;    
    for (int i = 0; i < 64; i++) {          
            M[i] = plain[ip[i] - 1];    
    }    
    return M;    
}

1.3.2 生成子密钥

用户将初始密钥输入到子密钥生成器中，首先经过PC_1置换选择去掉8位奇偶校验位，留下真正的56bit有效密钥。

for (int i = 0; i < 56; i++) {  
    real_key[i] = key[PC_1[i] - 1];  
}

接着，分成两部分left和right，每部分28bit，左右两部分分别循环左移，每部分循环左移，每轮次根据轮次移位表左移位数不同，然后再连接成56bit。

//轮次位移表  
int shiftBits[] = { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 };

再使用PC_2重排并压缩为48bit，即得到一个子密钥。

for (int round = 0; round < 16; round++) {  
    left_shift(left, shiftBits[round]);  
    left_shift(right, shiftBits[round]);  
    //合并左右部分  
    for (int i = 0; i < 28; ++i) {  
        real_key[i] = right[i];  
        real_key[i + 28] = left[i];  
    }  
    //使用PC_2重排并压缩为48位  
    for (int j = 0; j < 48; j++) {  
        subkeys[round][47 - j] = real_key[56 - PC_2[j]];  
    }  
}

进行16轮得到16个子密钥。

PC_1和PC_2如下：

//置换选择PC_1  
//64bit密钥转为56bit  
int DES::PC_1[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 };  
  
//置换选择PC_2  
//56bit密钥转为48bit  
int DES::PC_2[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 };

1.3.3 Feistel轮函数

F接受两个参数：32位的data和48位的subkey。

E盒拓展，使用E置换表将data从32位扩展为48位。输出的每一位为

//E盒扩展  
bitset<48> expand;  
for (int i = 0; i < 48; i++) {  
    expand[i] = data[E[i] - 1];  
}

密钥异或，将得到的48bit输出作为输入与对应的48bit子密钥进行异或运算。

//异或  
expand = expand ^ subkey;

S盒压缩，将异或之后得到48bit作为S盒输入，分成8组，每组6bit，分别进入8个S盒进行压缩，最终输入48bit变为输出32bit。DES共有8个S盒，每个S盒有4行16列，每个元素4bit但一般用十进制表示。S盒接收到6bit的输入，6bit中的第一个bit和最后一个bit构成2位二进制数为行号，6bit中间的4bit二进制为列号，然后根据行号和列号查该S盒得到对应的值，该值的二进制就是S盒变换的输出。S盒压缩是DES算法唯一的非线性变换，提高了DES算法的安全性。

//S盒压缩  
bitset<32> output;  
for (int i = 0; i < 8; i++) {  
    int pos = 47 - i * 6;   
    int row = expand[pos] * 2 + expand[pos - 5];  
    int col = expand[pos - 1] * 8 + expand[pos - 2] * 4 + expand[pos - 3] * 2 + expand[pos - 4];  
    bitset<4> result(S_BOX[i][row][col]);  
    for (int j = 0; j < 4; j++) {  
        output[31 - i * 4 - j] = result[3 - j];  
    }  
}

最后进行P盒置换，P置换类似于IP初始置换。

E置换表和P置换表：

//E盒扩展置换表  
//将32bit扩展为48bit  
int DES::E[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 };  
//P盒置换表  
int DES::P[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 };

1.3.4 IP逆置换

过程与IP初始置换完全相同，只不过使用的置换表不同。

//IP逆置换  
bitset<64> DES::IP_1(const bitset<64> & input) {  
    bitset<64> output;  
    int ip_1[64];  
    for (int i = 0; i < 64; i++) {  
        ip_1[ip[i] - 1] = i + 1;  
    }  
    for (int i = 0; i < 64; i++) {  
        output[i] = input[ip_1[i] - 1];  
    }  
    return output;  
}

IP逆置换表。

//IP逆置换表  
int DES::IP_1[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  
};

1.4 数据结构

除S置换表之外的置换表都使用一维数组表示。

S置换表使用三维数组表示，每一个S盒为二维数组。

密钥，数据等使用bitset表示，方便进行位操作。

子密钥列表使用bitset的一维数组表示。

1.5 源代码

见Github

1.6 运行结果

可以处理任意类型的文件

image-20191220160546730

image-20191220160554962

image-20191220160600729