基于DES加密算法的改进研究

张 旭，洪家平

(湖北师范大学 计算机与信息工程学院，湖北 黄石 435002)

1 密码学概述

密码学自古以来就一直在被人研究着，如今的加密算法都以Shannon的混淆和扩散两个思想为基础，混淆以达到模糊明文、密文及其之间的关系，而扩散则是将明文和密钥的影响尽可能地反映在密文之中。密码学不仅仅是用于保护消息的机密性，还可以保护消息的完整性和真实性，除此之外在鉴别、认证、签名等方面都有长足的应用。

现今网络的使用已经十分普遍，规模也在不断增大，随之也带来了相关的安全性问题，譬如说隐私的泄漏，商业机密的窃听，甚至是消息的篡改等。因此，对在网络环境下数据通信及数据加密技术进行全面的分析具有普遍的现实意义[1]。同时，随着电子技术不断更迭，集成电路规模不断发展，相较于传统的电路，高集成度的嵌入式系统在越来越多的设备上得到应用。在嵌入式系统中，同样也需要对一些机密数据进行加密，以防止数据在通信过程中被窃取[2]。因此密码学无论在嵌入式设备还是在网络空间的领域中都有着非常广泛的应用，对于保护嵌入式设备的正常工作，建立安全可靠的通信环境都有着举足轻重的作用。同样对云端文件的防护，安全地网上购物等也需要安全可靠的保护手段，如在电子商务中应用 ssl、set等安全协议、数字证书、数字签名等多项数据加密技术，都能够实现对交易双方信息的有效保护[3]。

现在的加密技术可以简单分为两种类型[4]，一种是分组加密算法，这种算法将消息分成若干个分组，并对其每个分组进行加密运算，最后将每组的密文拼凑在一起作为整个消息的密文。另一种是序列密码，使用伪随机发生器产生与明文等长的密钥加密明文得到密文。在分组加密算法之中，还细分为对称加密算法和公钥加密算法。对称加密算法的加密和解密都使用同一个密钥，而公钥加密算法使用公开的密钥对消息进行加密，用私密的密钥进行解密。

2 DES加密算法介绍

对于分组加密算法而言，数据加密标准DES(Data Encryption Standard)是这种算法的典型代表[5]。DES加密算法其明文分组为64位，密钥64位，经过16轮的运算后输出密文[6]。DES加密算法的密钥共有64位，每个字节的最后一位为奇偶校验位。首先将密钥中的奇偶校验位去除[7]，形成56位的初始密钥K1.之后每轮都将初始密钥K1拆分为两部分，对左半部分和右半部分分别进行移位，将移位后的左半部分和右半部分结合在一起形成新一轮的初始密钥K2，将新一轮的初始密钥K2进行压缩置换后得到该轮的子密钥k1，依次不断迭代16轮产生16个子密钥k.由于DES的对称性，解密的算法和加密算法共同使用同一个算法，唯一需要改变的地方是子密钥k的使用顺序与加密算法中使用子密钥k的顺序相反。

很多年的实际应用证明了DES加密算法非常优秀，但却或多或少依然存在着不足。众多专家学者都对其进行了不懈的研究，包括对DES中密钥的探索，对S盒的改进等，并以此为基础产生了许多改进的DES加密算法。例如GDES加密算法拓展了DES中采用的Feistel结构，snDES加密算法对DES所使用的S盒进行了探索。同时也进一步研究了对DES及其相关加密算法的攻击方式，产生了如差分攻击、线性攻击、中间相遇攻击等其他攻击方法。随着计算机性能不断提升，对于DES加密算法，主要的问题还是密钥长度不足，实际使用中只有56位密钥的DES加密算法已经禁不起穷举法的攻击。

为了克服传统DES加密算法的缺点，Wang Yihan和Li Yongzhen所提出的《Improved Design of DES Algorithm Based on Symmetric Encryption Algorithm》一文[8]，在该文中，将密钥与明文分组长度拓展到128位。该算法每轮将Lli-1与Lri-1加密后得到的Lli与Lri交换，分别作为下一轮的Lri-1与Lli-1，重复16轮相同的操作后将所得的各个部分合并为一个密文分组，具体流程如图1所示。该算法扩展了DES的密钥位数使得穷举攻击变得更加困难，增强了算法的安全性，但与DES相比却失去了对合性。

图1 Improved Design of DES Algorithm算法流程图

3 优化改进的DES加密算法

3.1 DES加密算法一般改进方案

上面介绍的Wang Yihan和Li Yongzhen所提出的改进算法，不足之处在于其不是对合运算，解密的算法需要重新编写。为了解决上述问题，做出了如下改进，主要是对最后一轮的算法进行了改动，如图2所示。

图2 一般改进方案中最后一轮算法流程图

交换运算定义为交换L’li与R’li，则包含最后一轮在内的每一轮迭代则是在传统的Feistel结构上加上了所定义的交换运算。记上图中的Ll16为Rr16，Lr16为Rl16，Rl16为Lr16，Rr16为Ll16，则可以得到该方案加密算法结构的一般形式如下：

Lli= Rri-1

Lri= Lli-1⊕f( Lri-1, kli)

Rli= Lri-1

Rri= Rli-1⊕f( Rri-1, kri)

其中i=1，2，…，16.

该方案更具一般性，只需在原有的代码上稍加改动即可，实现也更加便捷，同时也继承了对合性，编写解密算法时只需要交换左右加密子密钥以及更改使用子密钥的顺序即可，无需更改整体算法结构。

3.2 DES加密算法优化改进方案DESTH分析

上述所介绍的改进方案只适用于具有Feistel结构的加密算法，不适用于有独特的f函数的DES加密算法。为了能够扩展DES加密算法的密钥长度并进一步加强相关的安全性，对上述的改进方案进行更进一步的优化，提出了新的优化改进方案，将该算法命名为DESTH.DESTH加密算法在每轮加密时，左半部分使用Kl产生的子密钥kli，右半部分使用Kr产生的子密钥kri.

DESTH算法的1-8轮流程如图3所示。

图3 DESTH加密算法结构1～8轮原理图

在第1轮至第7轮加密中，每一轮均在DES加密算法迭代结束前交换L’li与R’li，在第8轮加密时延用DES加密算法最后一轮的加密方法。

记图3中第8轮的Ll8为Lr8，Lr8为Rl8，Rl8为Rr8，Rr8为Ll8，则可以得到DESTH加密算法结构第1 - 8轮的一般形式如下：

Lli= Rri-1

Lri= Lli-1⊕f( Lri-1, kli)

Rli= Lri-1

Rri= Rli-1⊕f( Rri-1, kri)

其中i=1，2，…，8.

DESTH算法的9～16轮流程如图4所示。

图4 DESTH加密算法结构9～16轮原理图

在第9轮至第15轮加密中，每一轮则在DES加密算法迭代结束前交换L’ri与R’ri，在最后一轮加密时使用与DES加密算法相同的方案。

记图4中最后一轮的Ll16为Rr16，Lr16为Ll16，Rl16为Lr16，Rr16为Rl16，则可以得到DESTH加密算法结构第9～16轮的一般形式如下：

Lli= Lri-1

Lri= Rli-1⊕f( Rri-1, kri)

Rli= Rri-1

Rri= Lli-1⊕f( Lri-1, kli)

其中i=9，10，…，16.

则初始的明文数据Ll0和Rl0在1，3，5，7，10，12，14以及16轮进行总计8次的加密操作，初始明文数据Lr0与Rr0在2，4，6，8，9，11，13和15轮进行总计8次的加密操作。

上述的改进算法依然为对合算法，解密算法中的子密钥使用序列与方案一中一致，仅需逆序使用加密算法中的子密钥顺序即可，不必交换左半部分和右半部分加密的子密钥。

3.3 DESTH加密算法的实现

DESTH加密算法的实现代码所使用的部分函数如下所示。

void DESTHEN ( char M[], char K1[], char K2[], int C[]) // DESTH加密主体函数，M为需要加密的明文数据，K1为用于左半部分加密的密钥，K2为用于右半部分加密的密钥，C为以二进制形式输出的加密数据。

{

void PRE ( char string[], char K1[], char K2[], int MLL[], int MLR[], int MRL[], int MRR[],int KL[], int KR[]) ; //准备函数，将输入的字符串分

为LL0，LR0，RL0和RR0四部分，同时将输入的密钥转换为二进制。密钥每个字节的二进制表示由低位到高位占据1～7位，并在第8位添加偶校验码。

void KREP ( int KD[]) ; //密钥置换

void KMOVL1 ( int K[]) ; //密钥向左移动1位，用于产生加密子密钥

void KMOVL2 ( int K[]) ; //密钥向左移动2位，用于产生加密子密钥

void DESTHST1 ( int MLL[], int MLR[], int MRL[], int MRR[], int KL[], int KR[] ) ; // GESTH第1～7轮加密函数

void DESTHST2 ( int MLL[], int MLR[], int MRL[], int MRR[], int KL[], int KR[] ) ; // GESTH第9～15轮加密函数

void DESLAST ( int MLL[] , int MLR[] , int MRL[], int MRR[], int KL[], int KR[] ) ; // DES最后一轮的加密函数，在DESTH算法中用于第8轮与第16轮

}

准备函数中使用void SDOU ( char instr[],int outstr[])函数将temp[i]中的明文转为二进制存放在对应分组中。

3.4 DES加密算法的对比分析

以下使用DES加密算法与本文所提出的DESTH加密算法对相同的明文进行加密与解密的对比操作，DES的密钥则取自DESTH密钥的前半部分。通过分析这两个不同的加密算法在加密与解密操作中所用时间的长短来比较这两种加密与解密算法的运行效率。

对明文“It is a program.”使用密钥“security”通过DES加密的情况如图5所示。

图5 DES加密截图

将上图5中所得到的密文通过DES解密的情况如图6所示。

图6 DES解密截图

对明文“It is a program.”使用密钥“security”和“solution”通过DESTH加密的情况如图7所示。

图7 改进的DESTH加密截图

将上图中所得到的密文通过DESTH解密的情况如图8所示。

图8 改进的DESTH解密截图

由于程序运行时间包括输入参数的时间，因此没有实际的参考价值和意义。所以在程序中加入“time.h”头文件，引入函数clock_t clock(void)测试加密和解密过程所花的实际时间。从上图中可以得到两种加密算法的加密耗时均比解密耗时长，这是由于在加密时需要将明文转换为二进制数进行操作得到密文，而密文以二进制的字符串输入转换为二进制速度更快造成的。

通过以上2组运行截图的对比，由此可以看出，尽管DESTH密钥由64位扩展到了128位，改进了DES算法上的不足，但是DESTH在加密和解密所花的时间上与DES算法却并没有太大的变化。

4 结语

本文在分析DES加密算法和研究Wang Yihan和Li Yongzhen所提出的基础上，提出了DESTH加密算法，与原有的DES加密算法相比，DESTH加密算法通过扩展加密明文的分组以及加密的密钥，将64位的密钥扩展到了128位，同时通过左半部分和右半部分的交互通信进一步加强了算法的安全性，提高了抵抗穷举攻击目的的能力。与2DES相比，实现了抵抗中间相遇攻击的目标。也克服了Wang Yihan和Li Yongzhen提出的不足，该算法还具有对合性，使得解密算法的实现仅需在加密算法的基础上稍加改动即可，节省了需要存储解密代码的空间，也节约了需要实现解密算法电路的空间及其设计实现的过程。