📝 Code | DES算法设计与实现

上个星期的的 Web 安全技术课上讲了 DES 算法的具体算法，本文来说明一下 DES 算法的具体流程，以及使用 C 语言和 Go 语言实现 DES 算法。🎉

🚀 代码: Github

算法原理概述

DES 是一种对称加密算法，加密和解密使用同样的密钥。

DES 使用 64 位的密钥对明文进行块加密，将明文划分为 64 位一个块，通过换位和置换，对其进行加密混淆，输出同样的 64 位长度的密文，但是由于采用了 ECB 模式，在块与块之间没有扩散，同样的明文块会被加密成相同的密文块，因此并不能很好地隐藏数据模式。

64 位密钥除去 8 位奇偶验证位，实际上起作用的只有 56 位，但是我们可以通过多次 DES 加密来加强加密强度，延长密钥长度。

总体结构

DES 的加密和解密的过程除了引用子密钥的顺序相反，其他的过程都是一样的。

总体结构如图所示：

其具体的过程如下：

（注意：下面所有下标都是从 1 开始而不是从 0 开始）

首先，对原始明文消息按 PKCS#5 规范进行字节填充：

• 原始明文消息最后的分组不够 8 个字节(64 位) 时，在末尾以 字节填满，填入的字节取值相同，都是填充的字节数目
• 原始明文消息刚好分组完全时，在末尾填充 8 个字节(即增 加一个完整分组)，字节取值都是 08。

举个例子：

如果原文为 xxxxxxxx xxx，末尾需要填充 5 位，因此填充xxxxxxxx xxx,05,05,05,05,05

如果原文为 xxxxxxxx， 末尾就需要填充 8 个08，这样解密出来就可以识别出那些是填充的。

然后对其的每 64 位进行如下处理：

• 初始置换$IP$

  • 根据IP置换表（各种表的数据在下文的代码中可以查看）将 64 位明文进行初始置换得到$L_0R_0$

• 16 轮迭代$T$

  • 将$L_0R_0$按照下述规则进行 16 次迭代：

    

  • 其中$K_i$为第i个子密钥， f 是 Feistel 轮函数：

    • 输入：32 位串$R_{i-1}$、48 位的子密钥（子密钥的生成方式稍后再说明）
    • 将 32 位串$R_{i-1}$根据扩展置换表进行E扩展，得到 48 位串$E(R_{i-1})$
    • 将 48 位串$E(R_{i-1})$和 48 位子密钥$K_i$进行异或操作
    • 将 48 位串分成 8 个分组，每个分组 6 位，分别经过 8 个 S 盒的6-4转换，得到 8*4=32 位的串
      • S-盒转换输入 6 位$b_1b_2b_3b_4b_5b_6$串
      • 取$b_1b_6$作为行、$b_2b_3b_4b_5$作为列，从 4 行 16 列的 S 盒中取出 4 位结果输出
    • 最后将结果进行P置换，得到 Feistel 轮函数的 32 位输出

  • 将 Feistel 轮函数的结果与上一轮的左边 32 位串进行异或操作，作为这一轮的右边 32 位串

  • 将上一轮的右边 32 位串作为这一轮的左边 32 位串

• 交换置换$W$

  • 将第十六轮迭代生成的串$L_{16}R_{16}$交换，输出$R_{16}L_{16}$

• 逆置换$IP^{-1}$

  • 根据IP逆置换表将 64 位串置换得到结果

然后就得到 64 位的密文块。

最后把所有密文块合在一起就是密文。

其中16 个子密钥的生成过程如下：

• 首先对 64 位密钥串进行PC-1置换，得到 56 位串（去掉了 8 位检验位），分为前 28 位和后 28 位$C_0D_0$
• 然后分别对$C_i$和$D_i$进行循环左移，如果$i = 1,2,9,16$，则循环左移一位，否则循环左移两位，得到$C_{i+1}$和$D_{i+1}$
• 对 56 位的$C_iD_i$进行PC-2置换压缩，得到 48 位的子密钥$K_i$
• 返回第二步，直到生成第 16 个子密钥$K_i$

其中子密钥的生成过程可以和 T 迭代置换同时进行，也可以一开始先生成所有的子密钥，只是安全性不高。密钥停留在内存中事件越久就越危险，尤其是没有内核保护的情况下。在Linux下，加密算法可以将密钥生成在内核的保护区域内以确保安全。

而解密过程和加密过程大致相同，在迭代变换过程中则从 T16-T1 反过来进行迭代，最后就可以得到明文，最后记得根据最后一位的内容删除掉之前根据PKCS#5填充的内容。

模块分解

由于 DES 的加密和解密只有 T 迭代的顺序有所不同，因此可以共用一个主体模块 DES。

而 DES 的算法的主体模块DES又可以分解为以下的模块：

• 生成子密钥 ：makeKey
  • 根据 64 位密钥生成 16 个 48 位的子密钥，用于 16 轮 T 迭代变换
• T 迭代：tIteration
  • 按照一定规则，使用子密钥对 IP 置换后的信息执行迭代变换 16 轮，最后进行一次 W 置换

其中需要到一些辅助模块：

• PKCS5 填充：PKCS5Padding

  • 对明文信息补全，使明文可以划分为一定数量的 64 位块

• 置换：transform

  • 进行各种置换：IP 置换、IP 逆置换、PC1 置换、PC2 置换、E 扩展置换、P 置换

• Feistel：feistel

  • T 迭代中比较重要的函数，将 32 位输入和 48 位子密钥进行 PC 置换和 S-BOX 置换，得到 32 位输出

• S-Box 置换：sBoxTransform

  • Feistel 轮函数中的一个重要步骤，将 6 位输入根据S-Box生成 4 位输出

• 循环左移：leftShift

  • 生成子密钥时每次迭代时对于CD的处理

数据结构

这里使用了unsigned char作为主要的数据存储单位，虽然一个unsigned char为 1 个字节，即 8 位，但是为了运算的方便起见，某些数据结构还是使用 1 个字节来存储 1 位数据。

为了运算速度，需要预先存储一些置换运算将会使用到的表：

• PC1-Table：生成密钥时对原密钥的 PC1 置换
• PC2-Table：生成密钥时生成子密钥的 PC2 置换
• IP-Table：IP 置换
• IPInverse-Table：IP 逆置换
• sBox(1-8)：feistel 轮函数中的 S 盒选择函数
• P-Table：feistel 轮函数中的 P 置换
• E-Table：feistel 轮函数中的 E 扩展

为了节省空间，以上表都使用unsigned char数组存储

对于明文数据和密文数据，同样是使用unsigned char数组存储。

源代码

根据上面的过程，分别使用 C 语言的 Go 语言实现了 DES 算法，对于同一明文使用同一密钥加密的结果都是一样的。

下面是 Github 地址：

C 语言源代码

Go 语言源代码

由于 Go 语言的版本划分了多个文件，这里不便贴出来，因此只把 C 语言的版本展示出来，详情可以点击上面的连接查看：

C 语言版本：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define true 1
#define false 0

typedef char bool;
typedef unsigned char byte;

byte pc1Table[] = {0,  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};

byte pc2Table[] = {0,  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};

byte ipTable[] = {0,  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};

byte ipInverseTable[] = {0,  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};

byte sBox[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},
    },
};

byte pTable[] = {0,  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};

byte eTable[] = {0,  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};

// to64 src: [0-7]8 to dst: [1-64]64
void to64(byte *src, byte *dst) {
  for (int i = 0; i < 8; i++) {
    byte cur = src[i];
    for (int j = 0; j < 8; j++) {
      dst[(8 - j) + i * 8] = cur % 2;
      cur >>= 1;
    }
  }
}

// to8 src: [1-64]64 to dst: [0-7]8
void to8(byte *src, byte *dst) {
  for (int i = 1; i <= 8; i++) {
    byte b;
    for (int j = 1; j <= 8; j++) {
      b <<= 1;
      if (src[(i - 1) * 8 + j] == 1) b |= 1;
    }
    dst[i - 1] = b;
  }
}

// 置换
void transform(byte *src, int sSize, int dSize, byte *table) {
  byte copy[sSize + 1];
  memcpy(copy, src, (sSize + 1) * sizeof(byte));
  memset(src, 0, dSize * sizeof(byte));
  for (int i = 1; i <= dSize; i++) {
    src[i] = copy[table[i]];
  }
}

// leftShift 循环左移
void leftShift(byte *src) {
  byte hc = src[1], hd = src[29];
  for (int j = 1; j < 28; j++) {
    src[j] = src[j + 1];
    src[j + 28] = src[j + 29];
  }
  src[28] = hc;
  src[56] = hd;
}

// makeKey 生成密钥
void makeKey(byte *key, byte keys[17][49]) {
  transform(key, 64, 56, pc1Table);
  for (int i = 1; i <= 16; i++) {
    if (i != 1 && i != 2 && i != 9 && i != 16) leftShift(key);
    leftShift(key);
    byte copy[65];
    memcpy(copy, key, 65 * sizeof(byte));
    transform(key, 64, 48, pc2Table);
    for (int j = 1; j <= 48; j++) keys[i][j] = key[j];
    memcpy(key, copy, 65 * sizeof(byte));
  }
}

// 补全
void PKCS5Padding(byte *src, byte *dst) {
  int len = strlen(src);
  int count = 8 - len % 8;
  memcpy(dst, src, len * sizeof(byte));
  for (int i = 0; i < count; i++) {
    dst[len + i] = count;
  }
}

// S盒转换
void sBoxTransform(byte *dst, byte *src, int i) {
  int begin = 6 * i - 5, n = src[begin] * 2 + src[begin + 5],
      m = src[begin + 1] * 8 + src[begin + 2] * 4 + src[begin + 3] * 2 +
          src[begin + 4],
      s = sBox[i - 1][n][m];
  for (int j = 0; j < 4; j++) {
    dst[4 - j + (i - 1) * 4] = s % 2;
    s >>= 1;
  }
}

// feistel轮函数
void feistel(byte *dst, byte *src, byte key[49]) {
  // E - 扩展 Test OK
  memcpy(dst, src, 33 * sizeof(byte));
  transform(dst, 48, 48, eTable);
  // 异或
  for (int i = 1; i <= 48; i++) {
    dst[i] ^= key[i];
  }
  byte copy[49];
  memcpy(copy, dst, 49 * sizeof(byte));
  // s-Box
  for (int i = 1; i <= 8; i++) {
    sBoxTransform(dst, copy, i);
  }
  // P - 置换
  transform(dst, 32, 32, pTable);
}

// T - 迭代
void tIteration(byte *src, byte keys[17][49], bool isEncrypt) {
  for (int i = 1; i <= 16; i++) {
    byte newRaw[65], right[33], f[33];
    for (int j = 1; j <= 32; j++) {
      newRaw[j] = src[32 + j];
      right[j] = src[j];
    }
    if (isEncrypt) {
      feistel(f, newRaw, keys[17 - i]);
    } else {
      feistel(f, newRaw, keys[i]);
    }
    for (int j = 1; j <= 32; j++) {
      right[j] ^= f[j];
    }
    for (int j = 1; j <= 32; j++) newRaw[32 + j] = right[j];
    memcpy(src, newRaw, 65 * sizeof(byte));
  }
  // W-置换
  byte copy[65];
  memcpy(copy, src, 65 * sizeof(byte));
  for (int j = 1; j <= 32; j++) {
    src[j] = copy[j + 32];
    src[j + 32] = copy[j];
  }
}

// DES算法主函数
byte *DES(byte *src, byte *key, bool isEncrypt, int *len) {
  if (strlen(key) != 8) {
    printf("Error key length");
    return src;
  }
  if (isEncrypt) {
    *len = strlen(src) + 8 - strlen(src) % 8;
  } else {
    *len = strlen(src);
  }
  byte *dst = malloc(*len * sizeof(byte));
  memset(dst, 0, *len * sizeof(byte));
  // 生成16个子密钥
  byte keys[17][49];
  byte keyBit[65];
  to64(key, keyBit);
  makeKey(keyBit, keys);
  // 补全
  if (isEncrypt)
    PKCS5Padding(src, dst);
  else
    memcpy(dst, src, *len * sizeof(byte));
  int times = strlen(dst) / 8;
  for (int i = 0; i < times; i++) {
    // 分割64位
    byte raw[8];
    for (int j = 0; j < 8; j++) raw[j] = dst[i * 8 + j];
    byte bit[65];
    to64(raw, bit);
    // IP 变换
    transform(bit, 64, 64, ipTable);
    // T-迭代 && W-置换
    tIteration(bit, keys, !isEncrypt);
    // IP逆置换
    transform(bit, 64, 64, ipInverseTable);
    to8(bit, raw);
    for (int j = 0; j < 8; j++) dst[i * 8 + j] = raw[j];
  }
  return dst;
}

// 加密
byte *encrypt(byte *plain, byte *key, int *len) {
  return DES(plain, key, true, len);
}

// 解密
byte *decrypt(byte *cipher, byte *key, int len) {
  int t = 0;
  byte *plain = DES(cipher, key, false, &t);
  // 删除PKCS5填充
  plain[len - plain[len - 1]] = '\0';
  return plain;
}

// 测试
int main() {
  byte key[10] = "megashow",
       plain[100] = "hello,world!";
  int len = 0;
  byte *cipher = encrypt(plain, key, &len);
  byte *mPlain = decrypt(cipher, key, len);
  printf("plain: %s\n", plain);
  printf("cipher: ");
  for (int i = 0; i < len; i++) {
    printf("%x", cipher[i]);
  }
  printf("\n");
  printf("mPlain: %s\n", mPlain);
  free(cipher);
  free(mPlain);
  return 0;
}

编译运行结果

测试对于一个字符串使用密钥对其加密，然后对密文用同一密钥进行解密，如果解密出来的明文和原来的一样，那么这个加密算法就算成功了。

使用gcc对上面的代码进行编译并运行，得到下面的结果：

$ gcc ./DES.c
$ .\a.exe
plain: hello,world!
cipher: 9f596cc78ad84141dc97b440193dcaf
mPlain: hello,world!

可以看到，解密出来的结果和之前输入的明文是一样的，因此这个算法是成功的。