数据加密标准研究之DES加密原理剖析

唐琳

（赤峰学院 计算机与信息工程学院，内蒙古 赤峰 024000）

数据加密标准研究之DES加密原理剖析

唐琳

（赤峰学院 计算机与信息工程学院，内蒙古 赤峰 024000）

DES的原始设计思想类似于恩尼格玛密码机，都是用了扩散的循环移位思想，本文在阐述了恩尼格玛机构造原理的基础上，针对DES的归属关系从迭代分组密码的Feistel结构出发对DES的分组位数、密钥及基本原理进行论述.

DES；加密；原理

1 引言

笔者在《数据加密标准研究之DES设计思想及体制分析》一文中，论述了传统密码加密的核心思想大多来源于古代的循环移位思想，在此思想基础上再进行模糊扩散，便构成了由德国发明家亚瑟·谢尔比乌斯（ArthurScherbius）和理查德·李特（RichardRitter）发明的恩尼格玛密码机的基本原理.DES的原始思想与恩尼格玛机的基本思想大致相同，都是在代换过程中进行模糊运算以增加密码（算法）分析的难度.这里所说的模糊扩散，就是在模糊信息处理中加上一种有效的过滤信息的方法——信息扩散法，这是一个蘸方法，是从原始数据信息中直接抽象构建出模型，这样做的好处是减少了数学上的外加约束，避免了原始数据结构的破坏.在这一理论指导下，形成了模糊扩散下的循环移位，这才为恩尼格玛机的诞生奠定了理论基础.

2 恩尼格玛机的构造原理

图1 恩尼格玛密码机

图2 恩尼格玛机基本构造

如图1所示，恩尼格玛机由键盘、显示器和转子三个部件构成，键盘共有26个英文字母键，显示器则是简单的对应26个按键的小灯泡，实现的只是最原始的“指示灯”作用，当在键盘上按下某一字母键时，与这个字母加密后得到的密文字母所对应的指示灯就会点亮.其实最能体现恩尼格玛机关键加密技术的核心部件是转子（如图3所示），转子的作用是在输入一个明文字母后，其相应密文字母的指示灯会闪烁，转子则自动转动到下一个字母.也就是说位于明文不同位置的同一个字母，依靠转子的转动可以被不同的字母替换，相反的，位于密文中不同位置的同一个字母可以用来表示（对应）明文中的不同字母，这种方法在密码学中又被称为“复式替换密码”.应用复式替换加密的密码并不是简单的字母代换，传统的字母频率分析法对此密码的破解没有任何作用.

图3 恩尼格玛机中的转子

在恩尼格玛机中，转子的数目越多，编码的重复性就越小，常使用三个转子的情况较多，此时编码重复的概率为1/(26×26×26)，即在编码输入17576个字母之后才会出现重复.转子的初始方向则是整个恩尼格玛机加密技术的关键，也是通信双方约定的密钥，在通信前，发信人首先要初始化设定好三个转子的旋转方向，然后输入明文，并依次记录指示灯闪亮字母的顺序，最后把这些字母顺序（即密文）发送给收信方.收信方收到密文通信数据后，按照密钥约定调整转子初始化方向，依次键入密文字母，此时闪亮的指示灯标示的就是明文.由此可见，在恩尼格玛机中，加密和解密过程都是用相同的步骤来完成，关键之处就在于密钥——转子的初始化方向上.为了进一步增加破解难度，恩尼格玛机除了约定转子的初始化方向外，还要选择三个转子的六种排列方式，同时又用连接板将键盘和第一个转子连接起来，让明文字母在进入转子之前就会转变为另一个字母.这样一来，由转子方向、排列顺序及连接板简单替换密码系统共同构筑的三道防线组成了一套完整的恩尼格玛机，通信双方只要事先约定好这三项内容，就可以很容易地实现通信，这也被称为恩尼格玛机的三重密钥，也是恩尼格玛机的保密原理.

3 基于Feistel技术的DES分组及密钥

DES加密过程虽然在原理上和恩尼格玛机的工作原理有很大差别，但是它们二者的核心思想都是模糊扩散后的循环移位思想，这也就让DES在算法设计时从明文到密文的转变过程中首先要对明文字母进行循环移位，并尽可能将模糊扩散做到最优，扩散的优劣是直接影响密码安全的主要因素.通过扩散使得明文中的单个字符可以影响密文中的多个字符，从而在密文中消除明文的统计特征，相当于扩散掉明文的统计结构.我们可以通过下面这个例子来直观看到这种扩散效果：

例 构造一个数学模型，使得明文中的1个数字可以影响密文中的k个数字.

在上面的例子中我们可以感受到扩散后的循环效果，实际分组中，DES密码又是基于Feistel结构的迭代分组密码，这里所谓的迭代，就是在加密过程中增加循环的次数.之所以DES要选择Feistel密码结构，可以使得DES密码中当明文变化一位时会有至少一半以上的密文发生变化，尽可能实现雪崩效应这种加密算法中的理想属性，极大的增加了加密安全性.

3.1 Feistel结构

Feistel结构是分组密码加密方案的一种通用规则，在这一方案中，明文由若干个长度为2l的分组构成，密钥设定为K=(k1,k2,…,kn)，其中ki为每一轮加密的子密钥，i=1,2,…,n，表示第i轮加密过程.

此结构在加密前首先将输入的明文分组分成长度都为l的左右两部分，记为L和R，实现加密过程的第一步是对L和R进行n轮迭代，在迭代完成后再将新得到的L和R合并到一起以产生密文分组.

新的左半部分和右半部分产生规则为：

其中，ki是派生自密钥K并遵循特定密钥调度算法的第i轮加密的子密钥，F是以旧的右半部分Ri－1和子密钥ki作为输入参数的轮函数.一般来说，各轮加密中的子密钥ki之间各不相同，即k1≠k2≠k3≠…≠kn，这样就能保证轮函数F的值也各不相同.

经过n轮加密后，得到的密文C则是最后一轮加密结果的输出：C=(Ln，Rn)

由公式1可知，每一轮迭代后得到的新的左半部分Li就是旧的右半部分Ri-1；

由公式2可知，每一轮迭代后得到的新的右半部分Ri是旧的左半部分Li-1与轮函数F的输出值进行异或运算的结果.

这里需要说明的是，在每轮代换过程完成后，还要经过一个置换过程，即将代换后得到的新的左右两个部分Li和Ri进行交换，如图4所示.

总结前文，可以得出基于Feistel结构的通信网络其安全性能与明文分组大小、密钥大小、密钥调度（子密钥产生算法）、轮数及轮函数等几个参数有关，但是这些参数最后都会归结为密钥调度和轮函数这两个问题，而密钥调度中产生子密钥的算法越复杂，密码分析就越困难，而这种调度中本身就包含了Feistel结构的加密算法，无需保密，所以密码调度问题不会成为影响安全性的主要问题，因此从Feistel结构上来说，绝大多数密码分析往往都会集中于轮函数F的问题上，而轮函数的数学描述越复杂，分析起来就越困难，这样就要求轮函数的结构复杂性要高，并随着子密钥ki的取值变化其函数值也各不相同.

图4 Feistel加密结构图

3.2 DES分组位数

在引文[1]中，我们知道DES既是一种对称密码标准，同时又是一种分组密码，之所以将DES划归到分组密码体系中是因为DES在进行循环移位时需要事先将明文分成若干等数位的序列组，如同当前许多分组密码通用规则一样，DES对数据加密时的分组也是以64位作为标准分组长度.通信时将输入端输入的明文分成64位一组的明文块，逐块加密后在输出端以64位一组的密文块输出.

3.3 DES密钥及其长度

作为一种对称算法，DES加密和解密使用的是同一个算法（私有密钥），其密钥长度为56位，再加上8位奇偶校验位，所以经常能看到DES密钥是一个64位的分组数列，其中56位密钥数字是实际上的密钥长度，可以随时任意改变，同时DES所拥有的子密钥长度为48位.

4 DES的基本原理

4.1 DES加密原理

众所周知，DES的前身Lucifer密码是一种基于Feistel结构的密码，DES在Lucifer的基础上将密钥长度从128位压缩到64位，并修改了替换盒S-box（substitutionboxes，又称S盒），虽然密钥缩短了，但经过多次密码分析后，对DES攻击的成本比用穷举式密钥检索方法遍试255个密钥的成本只略微小了一点，对S-box的修改进一步增强了DES算法的复杂性，所以实际仅拥有56位密钥长度的DES算法与拥有更长密钥的Lucifer密码的安全性相差并不大，DES完全能够对抗多年以后出现的若干新的密码分析技术，也造就了DES算法多年来在加密领域中一直处于牢不可破的领军地位的辉煌.

由于这种血统上的遗传特性，DES亦是基于Feistel结构的迭代分组密码，这样DES的加密计算也势必要遵循前文中的公式1和公式2.

以一轮DES加密为例，其数学模型的构建与Feistel结构相同，也是由下面的公式构成DES加密的数学表达.

公式3说明，DES明文分组在一轮加密后新得到的左半部分就是原来的右半部分Ri－1；

公式4说明，DES明文分组在一轮加密后新得到的右半部分Ri就是原来的左半部分Li－1与轮函数F的异或.

DES的一轮加密运算结构如图5所示.

5DES加密算法结构图

在这一方案中，构成DES结构的轮函数F由排列扩展、子密钥、S-box和P-box等几个部分组成，其中关于扩展、子密钥产生算法、S-box和P-box的详细内容将在关于DES算法解析一文中详细论述.DES轮函数结构如图6所示，它的数学表达式为：

F(Ri-1,ki)=P-box{S-box[Expand(Ri-1)⊕ki]} 公式5

在公式5中，Expand函数的作用是对32位的右半部分排列扩展至48位，扩展后的结果再与子密钥ki进行异或运算.运算后的值仍为48位，通过S-box压缩为32位后作为输入参数赋给P-box.P-box运算后得出的结果就是DES轮函数F的值.

在DES加密过程中，加密轮数并不是无穷尽的，共计有16轮加密过程，即i的最大值n=16，每一轮都重复着如图5所示的加密过程.

4.2 DES解密原理

图6 DES轮函数F结构图

而在DES解密过程中，其本质原理与加密过程一样，密文作为输入端数据，子密钥产生规则发生变化，以相反次序使用子密钥.解密与加密过程都使用同一个算法，将加密结构图中的输入改为密文分组，解密过程仍然遵循公式3、4、5的数学规则，例如用C来代表密文，密文仍然分为左右各32位的分组，则解密规则数学表达式为：

其中Li是密文分组的左半部分，Ri是密文分组的右半部分，其余公式的说明可以参照加密规则，公式及算法完全一致.

5 总述

随着数据加密技术的不断发展，密码分析手段也在不断推陈出新，各种破解技术及工具层出不穷，为了进一步增加DES的加密安全性，目前使用的DES较数年前进化了许多，最常用的就是DES的变体——三重DES（3DES或称TripleDES）.这一变体对资料数据（明文）重复三次DES加密过程，解密时也需要重复三次DES解密过程，这种重复并不只是对过程的三次累计，而是使用三组每组56位有效数字的密钥产生一个168位的复杂密钥来对数据进行三次DES加密，这种加密机制通常可为我们提供极为强大的安全保障.在三重DES加密时，存在着一种极端情况，即算法选择的三组56位密钥的子密钥都相同时，三重DES在实施时对数据安全性的增值幅度并不大，这就需要向后继续兼容新的DES加密过程来调度出三组不同的密钥完成3DES过程.

其实对传统的DES来说，截止目前也只有一种方法能对其进行破解，那就是穷举法，既使密钥仅有56位有效数再加上8位校验数，用它来加密一段256位空间的明文，如果使用一台百万次/秒计算级的PC机对其密文进行穷举，大概需要花费2285年的时间，所以相对来说DES目前还是具有一定安全性的.

然而DES随着时间的推移也并非绝对安全，其本身还存在着致命的缺陷，56位密钥强度会随时间的流逝而日益减弱，这种缺陷尽管被三重DES在一定程度上有所解决，但面临着层出不穷的新的密码分析手段最终在安全性上会马失前蹄，所以风靡一时的DES也将被新的加密标准所取代.这也正如日月盈仄一般向我们揭示着事物发展演化的客观规律，在密码安全领域也存在着新生与消亡.

TP309

A

1673-260X（2014）12-0021-03