DES算法

1. DES算法简介

DES算法¹由子密钥的生成、加密、解密3部分组成。

1.1 子密钥的生成

该部分的目的是由64位的密钥K生成16个48位的子密钥。

首先，64比特的密钥K，经过PC-1后，扔掉了8位奇偶校验位，生成56比特的串。该比特串分为长度相等的比特串C0和D0。然后C0和D0分别循环左移1位，得到C1和D1。C1和D1合并起来生成C1D1。C1D1经过PC-2变换后即生成48比特的K1。C1、D1分别循环左移Ls2位，再合并，经过PC-2，生成子密钥K2……依次类推直至生成子密钥K16。 其中每次循环左移的位数Lsi (i =1,2,….16)基于查密钥循环移位表得出。

1.2 DES单组加密过程

此过程中，输入的数据为64位，首先经过初始置换IP后把其左半部分1至32位记为L0，右半部分33至64位记为R0，即生成了置换后的输入。

然后把R0与密钥发生器产生的密钥K1进行f运算，结果记为f(R0，K1)，再与L0进行异或运算得L0⊕f(R0，K1)。把R0记为L1放在左边，而把L0⊕f(R0，K1)记为R1放在右边，从而完成了第一次迭代运算。

在此基础上，重复上述的迭代过程，一直迭代至第16次，所得的第16次迭代结果左右不进行交换，即L15⊕f(R15，K16)记为R16放在左边，R15记为L16放在右边，成为预输出，最后经过初始置换的逆变换IP\^-1运算后即得密文。

1.3 DES单组解密过程

DES的解密过程和DES的加密过程完全类似，只不过将16圈的子密钥序列K1，K2……K16的顺序倒过来。即第一圈用第16个子密钥K16，第二圈用K15，其余类推。

1.4 CBC模式的加密过程

首先将数据按照8个字节一组进行分组得到D1D2......Dn（若数据不是8的整数倍，用指定的PADDING数据补位）。

第一组数据D1与初始化向量I异或后的结果进行DES加密得到第一组密文C1；第二组数据D2与第一组的加密结果C1异或以后的结果进行DES加密，得到第二组密文C2；之后的数据以此类推，得到Cn。按顺序连为C1C2C3......Cn即为加密结果。

1.5 CBC模式的解密过程

首先将数据按照8个字节一组进行分组得到C1C2C3......Cn。

将第一组数据进行解密后与初始化向量I进行异或得到第一组明文D1；将第二组数据C2进行解密后与第一组密文数据进行异或得到第二组数据D2；之后依此类推，得到Dn。

按顺序连为D1D2D3......Dn即为解密结果。

2. 概要设计

1. 用户由键盘输入密钥和初始化向量，待加密的明文存放于1.txt文件中。

2. 不足8字节一组的明文，在该组末尾填充'\0'，最后一个字符保存包括最后一个字符在内的所填充的字符数量。

3. 程序运行完毕后，1.txt的加密结果保存在2.txt中，2.txt的解密结果保存在3.txt中。

4. 对比1.txt的内容和3.txt的内容，可验证加解密是否正确。

参考代码

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int IP_Table[64] = {  //IP初始换位表 
    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 };

int IPR_Table[64] = {  //逆IP换位表 
    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 };

int E_Table[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 };

int P_Table[32] = {  //P盒换位表 
    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 };

int PC1_Table[56] = {  //PC1换位表 
    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 };

int PC2_Table[48] = {  //PC2换位表 
    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 };

int S_Box[8][4][16] = {  //8个S盒   三维数组
    // 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 };

int move_times[16] = {1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};

//1个字节转换成8位二进制串 
void charToBit(char ch, char bit[8]) {
    int i;
    for (i = 0; i < 8; i++){
        *(bit + 7 - i) = (ch >> i) & 1;
    }
}

//8位二进制串转换成1个字节 
void bitToChar(char bit[8], char *ch) {
    int i;
    for (i = 0; i < 8; i++){
        *ch |= *(bit + 7 - i) << i;
    }
}

//8个字节转换成64位二进制串 
void char_8ToBit_64(char ch[8], char bit[64]) {
    int i;
    for (i = 0; i < 8; i++){
        charToBit(*(ch + i), bit + (i << 3));
    }
} 

//64位二进制串转换成8个字节 
void bit_64ToChar_8(char bit[64], char ch[8]) {
    int i;
    memset(ch, 0, 8);
    for (i = 0; i < 8; i++){
        bitToChar(bit + (i << 3), ch + i);
    }
}

//PC1置换 
void pc1_Transform(char key[64], char temp[56]) {
    int i;
    for (i = 0; i < 56; i++){
        temp[i] = key[PC1_Table[i] - 1];
    }
}

//PC2置换 
void pc2_Transform(char key[56], char temp[48]) {
    int i;
    for (i = 0; i < 48; i++){
        temp[i] = key[PC2_Table[i] - 1];
    }
}

//循环左移 
void loop_Left(char key[56], int n) {
    char temp[56];                          //用temp储存密钥前28位和后28位循环左移移出的位
    memcpy(temp, key, n);                   //将前28位密钥的前n位拷贝到temp的第0位到第n-1位
    memcpy(temp + n, key + 28, n);          //将后28位密钥的前n位拷贝到temp的第n位到第2n-1位

    memcpy(key, key + n, 28 - n);           //将前28位密钥的后28-n位拷贝到key的第0位到28-n位
    memcpy(key + 28 - n, temp, n);          //将前28位密钥的循环左移出的n位移动到前28位末尾

    memcpy(key + 28, key + 28 + n, 28 - n); //将后28位密钥的后28-n位拷贝到key的第28位到56-n位
    memcpy(key + 56 - n, temp + n, n);      //将后28位密钥的循环左移出的n位移动到后28位末尾
} 

//生成子密钥 
void getSubKeys(char key[64], char subKeys[16][48]) {
    char temp[56];
    pc1_Transform(key, temp);
    int i;
    for (i = 0; i < 16; i++){
        loop_Left(temp, move_times[i]);
        pc2_Transform(temp, subKeys[i]); 
    }
} 

//IP置换 
void ip_Transform(char input[64]) {
    int i;
    char temp[64];
    for (i = 0; i < 64; i++){
        temp[i] = input[IP_Table[i] - 1];
    }
    memcpy(input, temp, 64);
}

//逆IP置换 
void ip1_Transform(char input[64]) {
    int i;
    char temp[64];
    for (i = 0; i < 64; i++){
        temp[i] = input[IPR_Table[i] - 1];
    }
    memcpy(input, temp, 64);
}

//E扩展
void e_Transform(char input[48]) {
    int i;
    char temp[48];
    for (i = 0; i < 48; i++){
        temp[i] = input[E_Table[i] - 1];
    }
    memcpy(input, temp, 48);
}

//P置换
void p_Transform(char input[32]) {
    int i;
    char temp[32];
    for (i = 0; i < 32; i++){
        temp[i] = input[P_Table[i] - 1];
    }
    memcpy(input, temp, 32);
} 

//异或
void xOr(char R[48], char L[48], int n) {
    int i;
    for (i = 0; i < n; i++){
        R[i] ^= L[i];
    }
}

//S盒 
void s_Transform(char input[48]) {
    int i;
    int row, col;
    int temp_output;
    int pos1, pos2;
    for (i = 0; i < 8; i++){
        pos1 = i * 6;  //每6 bit 输入分为一组 
        pos2 = i << 2; //每4 bit 输出分为一组 

        //每组输入首尾2个比特作为行条件 
        row = (input[pos1] << 1) + input[pos1 + 5];
        //每组输入中间4个比特作为列条件 
        col = (input[pos1 + 1] << 3) + (input[pos1 + 2] << 2) 
            + (input[pos1 + 3] << 1) + input[pos1 + 4];
        temp_output = S_Box[i][row][col];

        input[pos2] = (temp_output & 0x08) >> 3;
        input[pos2 + 1] = (temp_output & 0x04) >> 2;
        input[pos2 + 2] = (temp_output & 0x02) >> 1;
        input[pos2 + 3] = temp_output & 0x01;   
    }   
}

//交换左右32 bit 
void swap(char left[32], char right[32]) {
    char temp[32];
    memcpy(temp, left, 32);
    memcpy(left, right, 32);
    memcpy(right, temp, 32);
} 

//加密单个分组  
void encryptBlock(char plainBits[64], char subKeys[16][48], char cipherBlock[8]) {  
    char copyRight[48];  
    int i;  

    //初始IP置换  
    ip_Transform(plainBits);  

    //16轮迭代  
    for (i = 0; i < 16; i++) {         
        memcpy(copyRight, plainBits + 32, 32);  
        //将右半部分进行扩展置换，从32位扩展到48位  
        e_Transform(copyRight);  
        //将右半部分与子密钥进行异或操作  
        xOr(copyRight, subKeys[i], 48);   
        //异或结果进入S盒，输出32位结果  
        s_Transform(copyRight);  
        //P置换  
        p_Transform(copyRight);  
        //将明文左半部分与右半部分进行异或  
        xOr(plainBits, copyRight, 32);  
        if (i != 15) {  
            //最终完成左右部的交换  
            swap(plainBits, plainBits + 32);  
        }  
    }  
    //逆初始置换（IP^1置换）  
    ip1_Transform(plainBits);  
    bit_64ToChar_8(plainBits, cipherBlock);  
}  

//解密单个分组  
void decryptBlock(char cipherBits[64], char subKeys[16][48], char plainBlock[8]) {   
    char copyRight[48];  
    int i;  

    //初始IP置换  
    ip_Transform(cipherBits);  

    //16轮迭代  
    for (i = 15; i >= 0; i--) {        
        memcpy(copyRight, cipherBits + 32, 32);  
        //将右半部分进行扩展置换，从32位扩展到48位  
        e_Transform(copyRight);  
        //将右半部分与子密钥进行异或操作  
        xOr(copyRight, subKeys[i], 48);       
        //异或结果进入S盒，输出32位结果  
        s_Transform(copyRight);  
        //P置换  
        p_Transform(copyRight);       
        //将明文左半部分与右半部分进行异或  
        xOr(cipherBits, copyRight, 32);  
        if (i != 0) {  
            //最终完成左右部的交换  
            swap(cipherBits, cipherBits + 32);  
        }  
    }  
    //逆初始置换（IP^1置换）  
    ip1_Transform(cipherBits);  
    bit_64ToChar_8(cipherBits, plainBlock);   
}  

//加密文件  
int encrypt(char *plainFile, char *cipherFile, char keyBlock[8], char init[8]) {  
    FILE *plain,*cipher;  
    int count;  
    char plainBlock[8], cipherBlock[8];  
    char plainBits[64], cipherBits[64];
    char initBits[64]; 
    char_8ToBit_64(init, initBits);
    char bKey[64];  
    char subKeys[16][48];  
    int i;
    if ((plain = fopen(plainFile,"rb")) == NULL) {  
        return -1;  
    }     
    if ((cipher = fopen(cipherFile,"wb")) == NULL) {  
        return -1;  
    }  
    //将密钥转换为二进制流  
    char_8ToBit_64(keyBlock, bKey);  
    //生成子密钥  
    getSubKeys(bKey, subKeys);  

    while (!feof(plain)) {  
        //每次读8个字节，并返回成功读取的字节数  
        if ((count = fread(plainBlock, sizeof(char), 8, plain)) == 8) { 
            char_8ToBit_64(plainBlock, plainBits);
            for (i = 0; i < 64; i++) {
                plainBits[i] = plainBits[i] ^ initBits[i];
            } 
            encryptBlock(plainBits, subKeys, cipherBlock);  
            char_8ToBit_64(cipherBlock, cipherBits);
            memcpy(initBits, cipherBits, 64);
            fwrite(cipherBlock, sizeof(char), 8, cipher);    
        } 
    }  
    if (count) {  
        //填充  
        memset(plainBlock + count, '\0', 7 - count);  
        //最后一个字符保存包括最后一个字符在内的所填充的字符数量  
        plainBlock[7] = 8 - count;  
        char_8ToBit_64(plainBlock, plainBits);
        for (i = 0; i < 64; i++) {
            plainBits[i] = plainBits[i] ^ initBits[i];
        } 
        encryptBlock(plainBits, subKeys, cipherBlock); 
        fwrite(cipherBlock, sizeof(char), 8, cipher);  
    }  
    fclose(plain);  
    fclose(cipher);  
    return 0;  
}  

//解密文件  
int decrypt(char *cipherFile, char *plainFile, char keyBlock[8], char init[8]) {  
    FILE *plain, *cipher;  
    int count, times = 0;  
    long fileLen;  
    char plainBlock[8], cipherBlock[8];   
    char initBits[64];
    char_8ToBit_64(init, initBits);
    char cipherBits[64], plainBits[64];
    char copycipher[64];
    char bKey[64];  
    char subKeys[16][48];  
    int i;
    if((cipher = fopen(cipherFile,"rb")) == NULL){  
        return -1;  
    }  
    if((plain = fopen(plainFile,"wb")) == NULL){  
        return -1;  
    }  
    //将密钥转换为二进制流  
    char_8ToBit_64(keyBlock, bKey);  
    //生成子密钥  
    getSubKeys(bKey, subKeys);  

    //取文件长度   
    fseek(cipher, 0, SEEK_END);   //将文件指针置尾  
    fileLen = ftell(cipher);    //取文件指针当前位置  
    rewind(cipher);             //将文件指针重指向文件头  
    while (1) {  
        //密文的字节数一定是8的整数倍  
        fread(cipherBlock, sizeof(char), 8, cipher); 
        char_8ToBit_64(cipherBlock, cipherBits);
        //将读入的64位密文通过DES 
        memcpy(copycipher, cipherBits, 64);
        decryptBlock(cipherBits, subKeys, plainBlock); 
        //将得到的8字节明文转换64位 
        char_8ToBit_64(plainBlock, plainBits); 
        for (i = 0; i < 64; i++) {
            plainBits[i] = initBits[i] ^ plainBits[i];
            initBits[i] = copycipher[i];
        }  
        bit_64ToChar_8(plainBits, plainBlock);                      
        times += 8;  
        if (times < fileLen) {  
            fwrite(plainBlock, sizeof(char), 8, plain);  
        }  
        else {  
            break;  
        }  
    }  
    //判断末尾是否被填充  
    if (plainBlock[7] < 8) {  
        for (count = 8 - plainBlock[7]; count < 7; count++) {  
            if (plainBlock[count] != '\0') {  
                break;  
            }  
        }  
    }     
    if (count == 7) {//有填充  
        fwrite(plainBlock, sizeof(char), 8 - plainBlock[7], plain);  
    }  
    else {//无填充   
        fwrite(plainBlock, sizeof(char), 8, plain);  
    }  

    fclose(plain);  
    fclose(cipher);  
    return 0;
}  

int main() {
    char key[100];
    printf("Please enter your 8-character key:\n");
    gets(key);
    char init[100];
    printf("Please enter your 8-character initial vector:\n");
    gets(init);
    encrypt("1.txt", "2.txt", key, init);
    printf("1.txt has been encrypted into 2.txt\n");
    decrypt("2.txt", "3.txt", key, init);
    printf("2.txt has been encrypted into 3.txt\n");
    return 0;
}

3. 加解密示例

1.短文本加密解密：

2.长文本加解密：

---

1. J. Orlin Grabbe. 2016. The DES Algorithm Illustrated. ↩