DES算法实现及C++实现

算法原理概述

  DES（Data Encryption Standard），是一种使用密钥加密的块密码，也就是常说的分组加密算法。从密码体系上看，DES属于对称密码体系。DES的特征是，以64位分组对数据加密，加密和解密用的是同一个算法。对数据加密的过程基本是循环移位和矩阵置换。

  DES有以下几大特点：

1. DES是一种典型的块加密方法：它以64位为分组长度，64位一组的明文作为算法的输入，通过一系列复杂的操作，输出同样64位长度的密文。
2. DES使用加密密钥定义变换过程，因此算法认为只有持有加密所用的密钥的用户才能解密密文。
3. DES采用64位密钥，其中每8位含有一个校验位。因此密钥的有效程度是56位。

  DES算法过程概要：

1. 加密过程

     $C = E_k(M) = IP^{-1}\cdot T_{16}\cdot T_{15}\cdot \dots \cdot T{1} \cdot IP(M)$

   其中，$IP$为初始置换，$IP^{-1}$是$IP$的逆置换，$T_1,T2,\cdots,T_{16}$是一系列的迭代变换。

2. 解密过程

   $ M = D_k(M) = IP^{-1}\cdot T_{1}\cdot T_{2}\cdot \dots \cdot T{16} \cdot IP(C)$

---

总体结构

  DES算法的总体结构——Feistel结构

---

模块分解

  根据DES的总体步骤有C++特性，我将DES算法分成下面几个模块。

① 循环左移模块。

在生成子密钥的过程中，需要对上下两部分进行循环左移的操作，位移可能是1，也可能是2，根据位数来判断。因为这一部分需要重复使用，所以把这个封装成一个模块。

② 子密钥生成模块。

算法需要根据输入的一个64位密钥K，来生成16个长度为48位的子密钥，用于轮函数。过程如下：

1. 对K的56个非校验位实行置换PC-1，得到$C_0D_0$，其中$C_0$和$D_0$分别由PC-1置换后的前28位和后28位组成。$i=1$。

2. 计算$C_i=LS_i(C_{i-1})$和$D_i = LS{i}(D_{i-1})$，当$i=1,2,9,16$时，$LS_i(A)$表示将二进制串A循环左移一个位置；对于其他的$i$，循环左移两个位置。

3. 对56位的$C_iD_i$实行PC-2压缩置换，得到48位的$K_i$。$i = i + 1$。

4. 如果已经得到$K_{16}$，密钥调度过程结束；否则转2。

③ Feistel轮函数$f(R_{i-1},K_i)$

过程如下：

1. 将长度为32位的串$R_{i-1}$作E-扩展，成为48位的串$E(R_{i-1})$；

2. 将$E(R_{i-1})$和长度为48位的子密钥$K_i$作48位二进制串按位异或运算$K_i$又密钥K生成；

3. 将2得到得到的结果平均分成8个分组（每个分组长度6位），各个分组分别经过8个不同的S-盒进行6-4转换，得到8个长度分别为4位的分组；

4. 将3得到的分组结果顺序连接，得到长度为32位的串；

5. 将4的结果经过P-置换，得到的结果作为轮函数$f(R_{i-1},K_i)$的最终32位输出。

  这里重点解释一下S-盒。S-盒是一类选择函数，用于二进制的6-4转换。Feistel轮函数使用8个S-盒$S_1,\cdots，S_8$，每个S-盒是一个4行（编号0-3），16列（编号0-15）的表，表中的每个元素是一个十进制数，取值在0-15之间，用于表示一个4位的二进制数。

  假设$S_i$的6位输入为$b_1b_2b_3b_4b_5b_6$，则由$n=(b_1b_6){10}$确定行号，由$m=(b_2b_3b_4b_5){10}$确定列号，$[s_i]_{n,m}$元素的值的二进制形式即为所要的$S_i$的输出。

④ 加密模块

  加密模块是综合上述几个模块的一个大模块。先对输入的64位数据进行初始置换IP，然后进行16轮迭代T，对迭代结果进行逆置换，最后输出结果。

⑤ 解密模块

  解密模块的步骤与加密模块一致，唯一不同的地方在于16轮迭代T的调用顺序与加密过程相反。

⑥ 格式转换模块

   为了方便数据处理，在加密过程中使用的是STL提供给的bitset数据结构，因此需要在输入时将用户输入的数据和密钥转化为bitset，在输出时需要将bitset转化为字符串。转换的规则为：每八位对应一个字符，使用ASCII来转换。

C++实现及代码

这里就直接给出代码了

/*
  DES Algorithum
  Author: LiangYucheng
*/

#include <iostream>
#include <bitset>
#include <string>

using namespace std;

bitset<64> key; // 一个64位的密钥
bitset<48> subKey[16]; // 16个子密钥

/* 置换矩阵定义 */
// 初始IP置换
int 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};

// IP逆置换
int 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};

// E-扩展规则
int E[] = {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};

// 8个S-盒
int S[8][4][16] = {
                    { {14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7},
                      {0, 15, 7, 4, 15, 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}},

                    { {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}},

                    { {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}},

                    { {7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15},
                      {12, 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}},

                    { {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}},

                    { {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}},

                    { {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}},

                    { {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}}};

// P-置换
int 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};

// PC-1置换
int 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};

// PC-2压缩置换
int 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 loop[] = { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};


// 左移操作
bitset<28> LS(bitset<28>A, int shift) {
  bitset<28> output = A;
  if (shift == 1) {
    for (int i = 0; i < 27; i++) {
      if (i - shift < 0)
        output[i - shift + 28] = A[i];
      else
        output[i] = A[i + shift];
    }
  }
  if (shift == 2) {
    for (int i = 0; i < 26; i++) {
      if (i - shift < 0)
        output[i - shift + 28] = A[i];
      else
        output[i] = A[i + shift];
    }
  }
  return output;
}

// 子密钥生成
void generateSubKey() {
  bitset<56> reducedKey;
  bitset<28> Ci;
  bitset<28> Di;
  bitset<48> Ki;

  // (1)对K的56个非校验位实行置换PC-1，得到C0D0，其中C0和D0分别由PC-1置换后的前28位和后28位组成。
  for (int i = 0; i < 56; i++) {
    reducedKey[i] = key[PC1[i] - 1];
  }

  // (2)计算Ci = LSi(Ci-1)和Di = LSi(Di-1)，即左移
  // (3)对56位的CiDi实行PC-2压缩置换，得到48位的Ki。
  // (4)如果已经得到K16，密钥调度过程结束。
  for (int times = 0; times < 16; times++) {
    // 上下分开
    for (int i = 0; i < 28; i++) {
      Ci[i] = reducedKey[i];
    }
    for (int i = 28; i < 56; i++) {
      Di[i-28] = reducedKey[i];
    }
    Ci = LS(Ci, loop[times]);
    Di = LS(Di, loop[times]);
    
    // 上下合并
    for (int i = 0; i < 56; i++) {
      if (i < 28) {
        reducedKey[i] = Ci[i];
      }
      else {
        reducedKey[i] = Di[i - 28];
      }
    }

    // PC-2置换，得到48位的subKey
    for (int i = 0; i < 48; i++) {
      Ki[i] = reducedKey[PC2[i] - 1];
    }

    // 添加到子密钥集合中
    subKey[times] = Ki;
  }
}


// 轮函数
bitset<32> f(bitset<32>R, bitset<48> K) {
  bitset<48> Ei;
  bitset<32> result;
  
  // (1)将长度为32位的R作E-扩展，成为48为的串
  for (int i = 0; i < 48; i++) {
    Ei[i] = R[E[i] - 1];
  }

  // (2)将Ei和长度为48位的子密钥K作48位二进制串按位异或运算。
  for (int i = 0; i < 48; i++) {
    Ei[i] = Ei[i] ^ K[i];
  }

  // (3)将(2)得到的结果平均分成8个分组（每个分组长度为6），各个分组分别经过8个不同的S-盒进行6-4转换，得到8个长度分别为4位的分组。
  int j = 0; // result的下标
  for (int i = 0; i < 48; i+=6) {
    // input: b1b2b3b4b5b6
    // n = (b1b6) 行号
    // m = (b2b3b4b5) 列号
    int n = Ei[i] * 2 + Ei[i + 5];
    int m = Ei[i+1] * 8 + Ei[i+2] * 4 + Ei[i+3] * 2 + Ei[i+4];
    int value = S[i / 6][n][m];

    // (4)将(3)得到的分组结果顺序连接得到长度为32位的串
    bitset<4> newValue(value); // int to binary
    result[j] = newValue[3];
    result[j+1] = newValue[2];
    result[j+2] = newValue[1];
    result[j+3] = newValue[0];
    j += 4;
  }

  bitset<32> output = result;
  // (5)将(4)的结果经过P-置换，得到的结果作为论函数f的最终32位输出。
  for (int i = 0; i < 32; i++) {
    output[i] = result[P[i] - 1];
  }

  return output;
}

// 加密
bitset<64> encrypt(bitset<64> plain) {
  bitset<64> M0;
  bitset<32> Li;
  bitset<32> Ri;
  bitset<32> temp;
  bitset<64> cipher;

  // 初始置换IP
  for (int i = 0; i < 64; i++) {
    M0[i] = plain[IP[i] - 1];
  }

  for (int i = 0; i< 32; i++) {
    Li[i] = M0[i];
  }
  for (int i = 32; i < 64; i++) {
    Ri[i - 32] = M0[i];
  }

  // 16轮迭代T
  for (int times = 0; times < 16; times++) {
    temp = Ri;
    Ri = Li^f(Ri, subKey[times]);
    Li = temp;
  }
  
  // 逆置换IP^-1
  for (int i = 0; i < 32; i++) {
    cipher[i] = Ri[i];
  }
  for (int i = 32; i < 64; i++) {
    cipher[i] = Li[i - 32];
  }

  M0 = cipher; // 使用中间变量存储cipher，非常关键！
  for (int i = 0; i < 64; i++) {
    cipher[i] = M0[IP_[i] - 1];
  }

  return cipher;
}

// 解密
bitset<64> decrypt(bitset<64> cipher) {
  bitset<64> M0;
  bitset<32> Li;
  bitset<32> Ri;
  bitset<32> temp;
  bitset<64> plain;

  // 初始置换IP
  for (int i = 0; i < 64; i++) {
    M0[i] = cipher[IP[i] - 1];
  }

  for (int i = 0; i< 32; i++) {
    Li[i] = M0[i];
  }
  for (int i = 32; i < 64; i++) {
    Ri[i - 32] = M0[i];
  }

  // 16轮迭代T(逆序)
  for (int times = 15; times >= 0; times--) {
    temp = Ri;
    Ri = Li^f(Ri, subKey[times]);
    Li = temp;
  }

  // 逆置换IP^-1
  for (int i = 0; i < 32; i++) {
    plain[i] = Ri[i];
  }
  for (int i = 32; i < 64; i++) {
    plain[i] = Li[i - 32];
  }

  M0 = plain;
  for (int i = 0; i < 64; i++) {
    plain[i] = M0[IP_[i] - 1];
  }

  return plain;
}

/*输入输出转换函数*/
// string转bitset
bitset<64> stringToBitset(const char str[8]) {
  bitset<64> output;
  for (int i = 0; i < 8; i++) {
    for (int j = 0; j < 8; j++) {
      output[i * 8 + 7 - j] = (str[i] >> j) & 1;
    }
  }
  return output;
}

// bitset转string
string bitsetToString(bitset<64> s) {
  string output;
  for (int i = 0; i < 8; i++) {
    char c = '\0';
    for (int j = 0; j < 8; j++) {
      if (s[i*8 + j] == 1) {
        c = (c << 1) | 1;
      }
      else {
        c = c << 1;
      }
    }
    output += (unsigned char)c;
  }
  return output;
}

int main() {
  string str;
  cout << "Please input plain(length <= 8): ";
  cin >> str;
  string k;
  cout << "Plese input the key(length = 8): ";
  cin >> k;
  bitset<64> plain = stringToBitset(str.c_str());
  key = stringToBitset(k.c_str());

  generateSubKey();

  // 加密
  bitset<64> cipher = encrypt(plain);
  // 解密
  bitset<64> result = decrypt(cipher);
  /*
  cout << endl << endl;
  for (int i = 0; i < 8; i++) {
    for (int j = 0; j < 8; j++) {
      cout << result[i*8 + j] << " ";
    }
    cout << endl;
  }
  */
  string output = bitsetToString(result);
  cout << output << endl;
  return 0;
}

测试时，先加密再解密，如果最终解密结果与输入结果一致，则说明正确。

运行结果：

总结

  DES的安全性至今仍是可靠的，通常是使用3-DES来实现数据加密。在实现过程中，注意在置换前先保存一份副本，不然置换就会错误。这里实现的DES仅支持8个字符（64位）的输入。对于多于8个字符的输入，只需要将他们分割成多个长度为8的分组，然后分组加密即可。DES的算法设计与实现分享就到这里，感谢您的支持！