DES 加密算法的改进方案*

黄 伟

（广州科技职业技术大学，广东 广州 510550）

0 引 言

数据加密算法是由IBM 公司于20 世纪70年代早期开发的一种分组加密法，由于其具有数学上可证明的安全强度[1]（以扩散模糊和扰乱模糊为特征），易于硬件实现的特点[2]，已逐渐由理论走向实践应用，被广泛应用于通信行业和金融行业，并在1977 年成为美国政府正式认可的数据加密标准（Data Encryption Standard，DES）[3]。然而，DES 算法仍未解决所有对称加密算法共有的缺陷：对称密钥的分发要占用额外的安全信道。同时，随着计算机计算速度的提升，DES 算法对于穷举法攻击的抵抗能力被逐渐削弱。到了互联网加密流量爆发式增长的20 世纪90 年代，网络通信中的主流数据加密算法是以RSA 为代表的非对称加密体系。这种非对称加密算法具有密钥易于分配（不占用额外信道）的特点以及强大的抵抗穷举法攻击的能力。非对称加密体系的广泛应用，是技术进步和对信息安全需求提高所带来的必然结果。

如今，对称加密算法仍然应用于通信、经济等众多领域，并没有因为科技的发展而被淘汰。究其原因，是对称加密和非对称加密并不是两种互相对立、互相排斥的密码体系，它们各有优点和缺点，清晰地认识到它们的互补性，是构造相对完善的密码体系的关键。公钥密码体系虽具有易于分配密钥和难于被暴力攻击的优点，但这些优点是以牺牲效率为代价的。与对称算法相比，非对称算法在加密和解密时需要花费更多的时间[4]。这使得非对称算法在一些需要即时响应的应用场景中，如边缘计算，变得不再适用。这说明，要获得更高的安全强度，同时使算法效率不至于大幅降低，必须把两种密码体系有机结合。

本文选取了在现代密码算法中具有里程碑意义的对称加密算法DES 作为研究对象，引入非对称密码体系的思想对其进行改进。本文提出的改进算法，除了保留DES 算法原有优点，还具备非对称算法的所有优点，是一种适应现代网络通信的数据安全保护的密码算法。

1 DES 算法

DES 算法是一种分组密码，明文每64 比特为一组，密钥为64 比特，除去8 比特奇偶校验位，实际密钥为56 比特，因此密钥组合数量为 256个。加密时，用同一密钥依次对每组明文进行加密，得到的每组密文也是64 比特，因此最后得到的密文长度和明文长度一致。对每组等长明文加密时，密钥不变，算法也不变，因此DES 十分适合以嵌入式硬件实现[5]。DES 加密前先把明文用一个置换函数IP 映射为初始密文。DES 加密算法由16 轮迭代加密构成，每次迭代加密所用密钥由原始密钥循环左移得到，称为子密钥K[6]。每轮迭代前，把上一轮迭代得到的密文（如果是第一轮迭代，加密对象是初始密文）分为左半L（第1~32 位）和右半R（第33~64 位）。R被当前子密钥加密为f(R,K)，f为加密函数。f(R,K)和L异或运算后得到下一轮迭代的右半R'。下一轮迭代的左半L'由R赋值，和R完全一致。16 轮迭代完成后得到的密文，经过一个置换函数IP−1映射后得到最终密文。解密算法和加密算法一致，密钥也一致，但每轮迭代所使用的子密钥的顺序和加密时相反。

经过16 轮迭代的DES 算法已被证明具有充分的对抗统计分析和线性分析的能力。因此，破解16 轮迭代的DES 密文的唯一途径是暴力破解，即用穷举法尝试所有的 256个可能的密钥[7]，这在DES 算法刚提出时被认为是不可能完成的任务。但随着计算机运算速度的提高和并行计算技术的成熟，DES 的安全度被大大弱化。

2 DES 算法的改进方案

对DES 算法的改进原则是使用RSA 保护DES 密钥，同时在加密前，对明文增加乱序和干扰处理。

2.1 改进方案的总体设计

DES 算法的密钥是对称密钥，必须通过秘密信道传送。为了使其也能通过互联网等公开信道传送，必须使用公钥密码体系对其进行保护。最常用的公钥密码算法是RSA，因此，我们可以把DES 密钥“封装”在一个RSA 加密的“头部”（Header）里，然后把这个头部附加在DES 密文前，成为一个密文包（Encrypted Data Packet），再把这个密文包发送给接收方。“封装”主要是指用接收方的公钥加密DES 密钥。接收方收到密文包后，先以自己的私钥解密包头，取出DES 密钥后，再用其解密密文包的数据部分（即DES 密文），得到明文。

如果头部封装的信息仅仅是DES 密钥，抗攻击意义并不大，仅解决了密钥通过公共信道分发的问题，攻击者仍然可以用穷举法对密文包的数据部分实施暴力破解。为了增加暴力破解的难度，密文包头部字段中必须包含一些有助于提高暴力破解难度的信息，并且不能显著影响密文包头的RSA 解密效率。主要可以采取以下两个策略：（1）对明文预先进行乱序处理，扰乱（Confuse）明文的原来顺序；（2）在DES加密前插入无效信息，攻击者只有在剔除这些无效信息后，才能得到有效的密文分组，并对此分组尝试暴力破解。

2.2 改进算法详述

改进算法包括密文包的结构、明文的预处理和加密流程，以及密文包的头部结构。

2.2.1 密文包的整体结构

密文包由头部和密文两个部分组成。由于头部是用RSA 加密的密文，因此本文以“RSA 头”这一名称指代头部。明文通过RSA 头中的密钥集加密后，生成密文部分。由于无效信息的插入，使密文部分和明文部分的长度不相等，大大增加了破解的难度。“密钥集”不仅是DES 密钥，还包含了加密或解密流程中各阶段所使用的密钥，而DES 加密或解密仅仅是其中一个阶段。为方便接收方把头部分离出来，RSA 头的长度是固定的，只能用接收方的私钥解密。

2.2.2 对原始明文的预处理

加密前需要对原始明文P进行预处理，详细流程如下文所述。

（1）分组。分组长度和DES 加密的分组长度一致（64 位），最后一组不足64 位的以0 补足。

（2）分段。段是比组更高一级的单位，每段包含64个分组，最后一段不足64组的以0补足。

对预处理后的明文用P0表示，得出P0==S0,S1, …,S63，其中Si为P0的第i个分段，S i==Gi0,Gi1,…,Gi63（Gij为Si段的第j个分组），Gi j=bi j0,bij1,…,bij63（bijk为Gij分组中的第k位）。

整个加密过程需经过3 次加密，分别以U，J，D表示，每次加密后的密文分别以A，B，C表示。图1 说明了3 次加密之间的输入/输出关系。

2.2.3 密文包的头部结构

RSA 头包括3 个关键字段和一些辅助字段（如图2 所示）。关键字段分别存放3 个密钥，对应加密流程的U，J，C 这3 个阶段。辅助字段主要存放控制和校验信息。这些字段的名称、长度和作用如下文所述。

（1）乱序密钥（Confusing Key，CK）。乱序密钥的作用是对每段明文进行重排（Reshuffle）。其长度为64 个字节，每个字节最高位恒为0，最低位为校验位，中间6 位转化为10 进制数后表示一个加密参数Ki(i=0, 1, …,63 )，i为字节的序号。乱序加密算法为U(Gi)=b(0,K i),b(1,Ki),…,

b(63,Ki)，表明第i组的密文由明文各组的第Ki比特排列而成。其中，b(m,n)是第m组的第n位，满足0≤m≤63。

（2）干扰密钥（Jamming Key，JK）。干扰密钥的作用是在密文A的每个分组中插入无效信息，以增加破解难度。其长度为8 位，前6 位表示在分组中插值的位置J( 0≤J≤63) ，后两位是需要插入的值。如干扰密钥是01011010,(01011010)2=(010110)2(10)2=(19)10(10)2，可以看出，干扰密钥前6 位的10 进制数值为19，故J= 19，二进制10 会被插入到目标分组的第19个比特前。干扰密钥只应用在密文A的第1 个分组中，此后，它会发生动态变化。应用在密文A的第2 个分组的干扰密钥将从第1 个分组的明文中产生。方法是把一个8 位的空字节（窗口）放置在明文第1 个分组的起始位置（即0号位），窗口的最高位对应分组的0 号位，窗口显示的字节即为第2 个分组的干扰密钥。同样地，把8 位窗口放置在第2 个分组的1 号位，得到第3 个分组的干扰密钥。以此类推，每次把窗口右移一位，即可得到下一分组的干扰密钥。如果窗口越过分组的右边界，则把越过的比特循环对应分组开始时的几个比特。这种插值法有一个缺陷，密文分组的长度固定是66 位（因为插值固定是2 位），使攻击者可以轻松地从密文中分离出有效分组，再对有效分组实施破解。为了使插值后的分组长度不固定，需要改变插值的长度，具体操作是从第2 个分组开始，使算法中干扰密钥末两位的含义发生变化，由原来的“插值的内容”变化为“插值的位数”。插值的内容从窗口后截取，截取的长度就是末两位所指出的插值的位数。同样地，截取插值时把背景分组看成首尾相接的环。这样一来，插值长度可能是0，1，2，3 其中之一。

（3）DES 密 钥（DES Key，DK）。DES 密钥的作用、形式、应用方法和经典DES 加密密钥一致，在RSA 头占64 位，它作用于干扰加密的结果B，产生密文C。

（4）标志位（Flags）。标志位占2 位，分别指出在加密过程中是否使用了干扰加密和乱序加密。

（5）摘要算法（Hash Algorithm，HA）。摘要算法占6 位，对RSA 头中特定部分应用本算法，得出摘要（Hash）字段的值。特定部分是指RSA头中从起始到标志位（包括标志位）的部分，本文称为“上段”。这一字段最多可表示62 =64 种摘要算法，包括常用的MD5 信息摘要算法（MD5 Message-Digest Algorithm，MD5）、安全散列算法（Secure Hash Algorithm，SHA）等算法。

（6）保留位（Reserved Bits）。未使用位，留待优化算法时使用。

（7）摘要（Hash）。摘要是对RSA 头上段应用“摘要算法”字段指定的散列算法而得到的哈希值，长128 位。

（8）校验值（Checksum）。校验值是密文部分的校验值，所用散列算法由“摘要算法”字段指定，长128 位。

2.2.4 加密和解密流程

加密流程如下文所述。

（1）把原始明文P预处理为P0 。

（2）随机产生3 个密钥，即CK，JK，DK。

（3）对P0 应用CK，得到A。

（4）对A应用JK，得到B。

（5）对B应用DK，得到C。

（6）填写RSA 头各字段。

（7）计算并填写摘要（Hash）和校验值（Checksum）字段。

（8）用接收方的公钥加密RSA 头的明文，得到密文包的头部。

（9）把密文包头部和密文C连接，整合成一个完整的密文包。

解密流程与加密流程各步骤的顺序相反，要注意以下几点。

（1）容易分离出密文包头部，因为它的长度是固定的896 位。

（2）在解密密文包头部时，须使用接收方的私钥。

（3）对B应用JK时（清除无效信息），是从第1 个分组开始，而不是相反地从最后一个分组开始。即先用JK恢复第1 个分组，再用8 位窗口循环右移的方法得到第2 个分组的干扰密钥，从而恢复第2 个分组，以此类推。

（4）对于加密前的预处理，没有逆算法，因而解密时不需要执行逆算法。

3 改进DES 算法的抗攻击能力分析

本文提出的改进DES 算法的密钥不再是单一的对称密钥，而是由3个互相独立的密钥CK，JK，DK组成的密钥集，并受RSA 密码的保护。即使通过穷举法暴力破解密钥集CK，JK，DK，其面临的可能密钥组合数量为：64！×28×256=64！×264，这个组合数量已经具备足够的强度来抵抗当前计算技术下可以实现的暴力破解攻击。

对于统计分析攻击的防御，DES 加密所实现的扩散模糊有效地抵御了基于统计的攻击。这是经典DES 算法的优点之一[8]，本文的算法完整保留了这一优点。

对于差分分析[9]、线性分析等数学分析方法的防御，因为多重密钥必然会带来分析参数数量的暴增，使得数学分析难度加大[10]，同时，分阶段的加密流程使本算法难以使用单一的数学分析方法破解。表明对称密码和非对称密码体系在应用中可以混合使用，取长补短，互为加固。

4 结 语

本文在经典的DES 加密算法的基础上，提出了一种改进算法。其设计思想是用非对称密码算法保护DES 密钥，产生“密钥外壳”，使加壳密钥和密文组成了防御破解的共同体；同时在DES 加密的基础上，增加了乱序加密和干扰加密，其密钥同样受到密钥外壳的保护，使攻击者无法在不攻破密钥外壳的情况下，单独对密文实施暴力破解。然而，这种算法的软硬件实现方式和性能仍有待进一步评估和测试，这关系到它在何种范围、何种场景中才能得到实际的应用。