DES算法实现

发表于 | 更新于: |
字数统计: 1.8k 字

本文阐述DES算法的基本原理及其C++实现方法，并给出源代码

算法概述

DES 是一种典型的块加密方法：它以64位为分组长度，64位一组的明文作为算法的输入，通过一系列复杂的操作，输出同样64位长度的密文。
DES 采用64位密钥，但由于每8位中的最后1位用于奇偶校验，实际有效密钥长度为56位。密钥可以是任意的56位的数，且可随时改变。其中极少量的数被认为是弱密钥，但能容易地避开它们。所有的保密性依赖于密钥。虽然56位的密钥对于现在来说加密强度不够，但是可以通过多次DES加密来加强加密强度。
DES 算法的基本过程是换位和置换。

总体结构

DES算法的总体结构如图所示：

加密和解密过程都适用于上图，唯一的差别在于子密钥的调度顺序不同：

输入64位明文 M 时，子密钥按 (K1K2… K16)次序调度，是加密过程。
输入64位密文 C 时，子密钥按 (K16K15 … K1)次序调度，是解密过程

下面以加密为例，阐述DES算法的具体过程：

分解明文

按照8个字节(64位)一组来将明文分组，原始明文消息按PKCS#5 (RFC 8018) 规范进行字节填充，即：

  • 最后一组长度不够8个字节时，在末尾以字节填满，填入的字节取值相同，都是填充的字节数目

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

接下来的每一组作为DES算法的输入M，开始加密

接下来的下标除了S盒之外，都是从1开始，而不是从0开始

初始置换IP

通过固定的初始置换表来重排M中的二进制位，以下表为例：

置换的过程即是把M[58]的值赋给M[1]，M[50]的值赋给M[2]。

要注意的是下标不是从0开始

之后的所有置换都类似于这种情况

置换后得到64位二进制串M0 = L0R0，L0、R0分别为前32位和后32位

16轮迭代T

这是算法最复杂的部分，迭代过程如图所示：

上一步得到的L0、R0作为这一步骤的初始输入，开始迭代。

  • 这一轮的右32位Ri-1直接作为下一轮的左32位Li
  • 这一轮的左32位Li-1与输出为32位的Feistel 函数进行异或运算之后得到下一轮的右32位Ri-1

这个过程要持续16次，即得到L16、R16

Feistel函数

从迭代过程的图可以看到，Feistel的输入输出为：

  • 输入1：上一轮迭代结果的右32位Ri-1
  • 输入2：长度为48位的子密钥Ki
  • 输出：32位的结果

此函数的具体工作过程为：

  1. 将长度为32位的串Ri-1进行 E-扩展，成为48位的串 E(Ri-1)，E-扩展的原理类似于IP置换，通过借助E-扩展规则 (比特-选择表) 来实现
  2. 将 E(Ri-1) 和长度为48位的子密钥 Ki 作异或运算，Ki 由密钥 K 生成(稍后解释生成子密钥过程)
  3. 将 (2) 得到的结果分成8个分组，每个分组长度6位(可以直接按照下标顺序来分组)。各个分组分别经过8个不同的 S-盒进行 6-4 转换，得到8个长度分别为4位的分组(S-盒操作也稍后解释)
  4. 将 (3) 得到的分组结果顺序连接得到长度为32位的串
  5. 将 (4) 的结果经过 P-置换，得到的结果作为Feistel函数的最终32位输出

生成子密钥

根据给定的64位密钥K，生成16个48位的子密钥 K1-K16

原理为：

  1. 对64位密钥K进行PC-1置换，得到去掉了8位检验位的56位串，C0和D0分别为前28位和后28位结果，令i = 1
  2. 分别对Ci和Di进行循环左移，如果i=1,2,9,16，则循环左移一位，否则循环左移两位，得到Ci+1和Di+1
  3. 对56位的CiDi进行PC-2置换压缩，得到48位的子密钥Ki，i = i + 1，返回第二步，直到生成第16个子密钥Ki

生成过程图解：

S-盒

前面已经介绍，S-盒用于把6位二进制串转换成4位二进制串，Feistel函数中有8个6位的分组，因此用到了8个不同的S-盒

S-盒原理为：

每一个S-盒是一个4行(编号 0-3)、16列(编号 0-15) 的表，表中元素值是10进制的值

假设 Si 的6位输入为b1b2b3b4b5b6，则由 n = (b1b6)10 确定行号，由 m = (b2b3b4b5)10 确定列号，[ Si ]n,m元素的值的二进制形式即为所要的 Si 的输出

在这里要注意，行号和列号都是从0开始的，这一点与其他地方不同

用一个例子来说明：

S1盒的表如图所示：

设S1 的6位输入b1b2b3b4b5b6 = 101100，则：

  • n = (b1b6)10 = (10)10 = 2
  • m = (b2b3b4b5)10 = (0110)10 = 6
  • [ S1 ]2,6可通过上表得知是2
  • 2 = (0010)2即为输出

交换置换W

将第十六轮迭代生成的串L16R16交换位置，输出R16L16

逆置换IP-1

操作类似于IP置换，只是换了置换表为IP逆置换表

模块分解

根据DES算法特点，我将算法分解为以下几个模块：

  1. 进制转换convert：用于8位的字符串和64位的二进制01字符串互相转换

  2. DES总体结构des：实现DES算法的总体结构，利用到了辅助模块：

    • 循环左移leftshift
    • 生成子密钥createkey

    同时在des中会按需调用其他模块，用以算法实现

  3. 全局变量globalVar：存放DES算法中需要用到的各种表(如IP置换表)

  4. T迭代iteration：描述16轮迭代过程，其中用到了辅助模块：

    • 轮函数feistel

  5. 置换transform：进行各种置换：IP置换、IP逆置换、PC-1置换、PC-2置换、E-扩展置换、P-置换

  6. 测试main：进行算法的测试，查看算法是否正确

数据结构

C++中有bitset这个类库来管理一系列的bit位，但本实验中为了输入输出转换方便，我使用了char来存放一个bit位，用到的其他数据结构只有string

输入的明文是string，经过convert模块转换后成为了每组64位的二进制字符串，字符串用char数组表示，因此最后得到的密文也是每组64位的二进制字符串

密文经过convert模块转换后成为string

算法中还需要自己定义一些数据结构，即各种表，都是二维/三维的char数组

源代码

源代码地址：https://github.com/chenf99/DES/tree/master/C%2B%2B

编译运行结果

1
2
3
4
5
PS C:\Users\11638\Desktop\DES\C++> g++ .\main.cpp -o des
PS C:\Users\11638\Desktop\DES\C++> ./des
plain:TAKERS Championship
encrypt:▊噴。償挒皷煗硵柊
decrypt:TAKERS Championship

-------------本文结束感谢您的阅读-------------