DES算法程序设计及实现

加密算法
博客

算法概述

DES算法共有两种功能：加密和解密。其中加密需要输入16位十六进制数的明文和密钥，解密需要输入密文和密钥。DES算法的要求输入是64位二进制数，为了方便起见，我将其改为输入16位十六进制数，转换在程序中实现。

加密过程：C=IP-1∙W∙T16∙T15∙…∙T1∙IP(M)，其中C为结果密文，M为输入明文，根据输入密钥Key进行中间的十六轮T迭代变换。

解密过程：M=IP-1∙W∙T1∙T2∙…∙T16∙IP(C)，其中M为结果明文，C为输入密文，根据输入密钥Key进行解密，需要注意的是，十六轮T迭代变换的次序与加密过程相反。

以加密为例，具体步骤如下：

  1. 在算法开始，先要根据输入密钥，计算出16个子密钥。将输入密钥除去第8，16……64等奇偶校验位，进行PC-1置换，结果分为两部分，得到C0和D0两个28位数组。然后再将这两个数组进行16轮左移操作，依据LS位数表进行左移，得到结果。将每一轮的CiDi进行PC-2置换，得到第i个子密钥。

  2. 将输入明文M进行IP置换，根据IP置换表，将旧数据重新排列，然后将结果分为前后两部分L0和R0，各为32位，用作后续输入。

  3. 进入十六轮迭代。将L0和R0作为输入，进行如下变换：

    Li= Ri-1; Ri= Li-1⊕f(Ri-1,Ki)，其中f为Feistel函数，Ki为第i个子密钥，需要注意的是，若在解密过程中，Ki则应为17-i个子密钥(i=1,……,17)。

  4. Feistel轮函数，步骤如下：

    • 首先将输入的Ri-1根据E扩展表进行扩展，变为48位。
    • 将第一步得到的结果与Ki做48位二进制按位异或运算。
    • 将上一步结果分为8组，每组为6位，所以要循环8次。在每一轮循环中，分组第一位与第六位按二进制转为十进制，作为行数目；第二三四五位按二进制转为十进制数，作为列数目。然后在第i个S盒中找到对应的行列数，取出相应数字，然后将其转为四位二进制数，保存起来。
    • 将上一步每次循环得到的结果拼接，得到一个32位的串。
    • 将该串进行P置换，结果即为Feistel函数的最终结果。

  5. 前面我们进行了十六轮迭代，得到了L16和R16，将R16作为一个64位串的前半段，L16作为后半段，即为W置换。

  6. 将上一步得到的64位串根据IP-1置换表进行置换，得到的结果即是我们要求的密文。
    在本算法中，我将64位二进制密文结果转化为16位十六进制数输出。

总体结构

Feistel结构：

Feistel

模块分解

  1. 初始置换IP：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
     void IP_Permutation(bool *l, bool *r, bool *m){
        bool temp[64];//store the result after permutating
        for(int i = 0;i < 64;i++){
            temp[i] = m[IP_Table[i]-1];
        }
        for(int i = 0;i < 64;i++){
            if(i<32){
                l[i] = temp[i];//store the left part
            }
            else{
                r[i-32] = temp[i];//store the right part
            }
        }
    }

  2. 16轮迭代T：

    1
    2
    void Iteration_En(bool *l, bool *r, bool *out)//encrypt
    void Iteration_De(bool *l, bool *r, bool *out)//decrypt

其中16轮循环，每次进行Feistel和异或运算，以函数方式调用：

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
void Feistel(bool *r, bool *k, bool *o){//feistel function
    bool out[48];
    E_Permutation(r, out);//expand to 48 bits
    for(int i = 0;i < 48;i++){
        out[i] ^= k[i];//XOR operation
    }
    bool s[32] = {0};
    
    for(int i = 0;i < 8;i++){
        int h = (out[i*6]<<1)+out[i*6+5];
        int l = (out[i*6+1]<<3)+(out[i*6+2]<<2)+(out[i*6+3]<<1)+out[i*6+4];
        int data = S_Box[i][h-1][l-1];//select the S Box data
        s[i*8] = (data&8)>>3;//convert decimal number to binary number
        s[i*8+1] = (data&4)>>2;
        s[i*8+2] = (data&2)>>1;
        s[i*8+3] = data&1;
    }
    
    P_Permutation(s, o);//put the result in o
}

void XOR(bool *r, bool *l, bool *f){//XOR operation
    for(int i = 0;i < 32;i++){
        r[i] = l[i]^f[i];//put the result in r
    }
}

  1. 交换置换W：

此部分我放在迭代运算的最后：

1
2
3
4
5
6
7
8
9
//out = R16L16
for(int i = 0;i < 64;i++){
    if(i < 32){
        out[i] = r[i];
    }
    else{
        out[i] = l[i-32];
    }
}

  1. 逆置换IP：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void IP_Inverse(bool *in){//IP inverse permutation
        bool temp[64];
        for(int i = 0; i < 64;i++){
            temp[i] = in[IPR_Table[i]-1];
        }
        for(int i = 0;i < 64;i++){
            in[i] = temp[i];//update the data
        }
    }

  2. 输出64位，我将其转换为16位十六进制数进行输出：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void Output(bool *s){//convert the binary number to hexadecimal number
        for(int i = 0;i < 16;i++){
            int data = s[i*4];
            data = data*2+s[i*4+1];
            data = data*2+s[i*4+2];
            data = data*2+s[i*4+3];
            printf("%X",data);
        }
    }

  3. 密钥调度：

    1
    void setSubkey(bool *key)

首先将64位输入密钥转换为56位，然后进行PC-1置换，之后在循环中进行移位与PC-2置换操作：

1
2
3
4
5
6
PC1_Permutation(k,c,d);//get C0 and R0
for(int i = 0;i < 16;i++){
    LS(c, LS_Table[i-1]);//C(i) = LS(i)(C(i-1))
    LS(d, LS_Table[i-1]);
    PC2_Permutation(c, d, i);//set the subKey
}

LS为根据输入次数，进行左移，以下展示PC-2置换函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void PC2_Permutation(bool *c, bool *d, int times){
    bool temp[56];
    for(int i = 0;i < 56;i++){
        if(i < 28){
            temp[i] = c[i];
        }
        else{
            temp[i] = d[i-28];
        }
    }
    
    for(int i = 0;i < 48;i++){
        subKey[times][i] = temp[PC2_Table[i]-1];//put the subKey in the array
    }
}

数据结构

算法并没有需要特别的数据结构，我主要是采用了Bool数组：

1
2
3
4
5
bool M[64];//ciphertext or plaintext
bool L[32];//Left part of M
bool R[32];//Right part of M
bool K[64];//Key
bool subKey[16][48];//subKey

此外，还有几个Int数组用来存各种转换表，不做赘述。

运行结果

Test1:

明文：A38B77FD99ECF823

密钥：37BACAE0D8BF0254

加密后密文为：6D0959FE56DCF42E

encrypt

解密：结果为A38B77FD99ECF823，符合要求。

decrypt

Test2

明文：2018103120181101

密钥：7FA8920C8ABEDD87

加密后密文为：27AC0F3220E42230

encrypt

解密：结果为2018103120181101，符合要求。

decrypt

代码戳传送门哟，有任何问题也欢迎与我交流。

分享到 评论