DES算法中S盒的重组方法

 

 

DES算法中S盒的重组方法

陈侨川 李红灵

（云南大学信息学院，昆明 650091）

摘要：DES算法是1972年美国IBM公司研制的对称密码体制加密算法，采用56位密钥长度，经过一系列的变换实现加密解密。但是自算法提出以来，面临着来自各方面的安全威胁，如穷举攻击，选择明文攻击等。本文分析DES算法的原理和特性，对原始算法提出有效的改进措施，在不影响算法加密效率的前提下，对提高DES的安全性和后续研究具有一定作用^[1][2]。

关键字：DES，S盒，前缀码，序数法。

 

1引言

DES算法是对称密码的一种，又被称为美国数据加密标准，在各方面有着广泛的运用。它包含了64位明文，64位密钥，而实际上参与计算的只有56位数据，其中有8位用于奇偶校验，明文和密钥进行一系列的置换等运算后，最终加密数据^[3][4]。

 

2 DES算法的特点和缺陷

（1）DES算法的密钥长度只有56位，相对较短，因此算法的保密对DES的安全性影响较低，密钥的保密是关键。

（2）DES算法对选择明文攻击抵抗性不足，攻击者可以有针对性的选择一些明文，让算法对选定的明文进行加密从而得到密文，而攻击者再通过明文和密文之间的联系得到算法的一些信息，找出规律，方便后面破解算法。如果在加密过程中对密钥或者相关步骤做出一些处理和改进，算法的安全性将增强。

（3）该算法的实现主要依靠S盒替代函数，S盒在DES算法中是非线性的，至今为止尚未公布S盒的由来，一旦S盒的安全性得不到保障，整个算法都将面临严峻的考验，它是分组密码的关键^[5]。

由此看来，DES虽然被广泛运用，但是对于穷举攻击和选择明文攻击存在安全隐患，因此本文对于DES的算法的核心部分S盒提出改进。

 

3 DES算法的原理

DES算法的加密由四部分完成，分别为：初始置换，获取子密钥，F函数，末置换，从而完成加密算法^[6]。

加密算法流程如图3-1,3-2

         3-1 DES加密过程                         3-2 轮迭代过程

其中，F函数是算法的核心部分，其实现的原理是将输入的右32位数据先通过扩充函数的扩充扩展，其结果与子密钥进行异或，并把结果送入S盒，把S盒的输出进行P置换得到结果。如图3-3所示

3-3 DES中的S盒

S盒可以看成一个4×6的矩阵，将本来输入的6位数据变成4位数据。S盒共有8个，数据的首位和末位组成的二进制数为S盒的行，中间4位组成的二进制数为S盒的列，这样便可以得到一个矩阵的坐标，完成数据压缩输出。

 

4 DES算法的改进

4.1 前缀码

设Q ={a₁, a₂, …, a_m}是一个0-1序列集合。如果Q中没有一个序列是另一个序列的前缀，则称Q为前缀码。例如，{0,10,110}就是一个前缀码，而{0,10,101}就不是前缀码。

前缀码与二叉树是一一对应的，任何一个前缀码都对应一个二叉树。给定一个前缀码，h表示前缀码中最长序列的长度，对于一个高度为h的完全二叉树，给每一分支的边标上0（左）和1（右），这样每个结点可以表示一个二进制序列，它由树根到各点通路上各边标记所确定，因此，对长度不超过h的每个二进制序列必定对应一个结点。对于一个完全二叉树，标记上是前缀码的结点，并将标记结点的所有子节点删除，这样得到一颗二叉树，再删除其中未标记的边，得到的二叉树就是前缀码对应的二叉树。因此可以知道，如果前缀码对应的二叉树是完全二叉树，则此前缀码可以译码。比如已知一个前缀码为{000,001,01,10,11}，如图4-1，4-2所示。

         4-1 完全二叉树                    4-2 前缀码对应的二叉树

根据前缀码与二叉树的关系，设有二进制序列10011101100100100010，译码为10,01,11,001,001,000,10，不能译的补0或1直到能译为止^[7]。

 

4.2 序数法

序数法是组合数学中全排列的一种算法，对于给定的一个序列（a₁，a₂，a₃…a_n），可以找出对应的全排列。

首先了解一种数的表达形式：

n!=(n-1)(n-1)!+(n-1)!，(n-1)!=(n-2)(n-2)!+(n-2)!…3!=2*2!+2!

所以n!=(n-1)(n-1)!+(n-2)(n-2)!+(n-3)(n-3)!+…+2*2!+2。

0到n!-1之间的任一整数m可唯一表示成m=a_n-1(n-1)!+a_n-2(n-2)!+…+a₁1!

m与序列(a_n-1, a_n-2,…, a₁)一一对应。n个元素的全排列与(a_n-1, a_n-2,…, a₁)一一对应^[8][9]。下面给出求m对应序列的方法。

M1=m

M2=m/2=b1   余数a1

M3=b1/3=b2  余数a2

M4=b2/4=b3  余数a3

……

m除以2的余数为a₁，商为b₁，b₁除以3的余数为a₂，商为b₂，b₂除以4的余数为a₃，商为b₃……b_n-2除以n的余数为a_n-1，这样便可以求出m对应的序列 (a_n-1, a_n-2,…, a₁)，根据a_i表示i+1所在位置右边比i+1小的数的个数，可求出序列(a_n-1, a_n-2,…, a₁)的全排列，比如（a₃，a₂，a₁）=（0，1，1），则对应的排列为2314。

4.3 S盒重组

S盒是分组加密算法的唯一的非线性部件，其密码强度决定整个算法的安全性，是DES的核心部分。目前使用的S盒是美国国家安全局设计的8 S盒，对于S盒可能存在的弱点，采用前缀码可以译码和组合数学中求全排列的思想，提出一种S盒的重组方法。即用分组加密算法过程的每一轮的子密钥来控制S盒的使用顺序。从而使一组明文在加密的过程中进行每一轮迭代时使用的S盒的顺序都不同，达到一次一密的效果。

假设密钥为000100000010001101000011101010100001100000101010，选取前缀码{000,001,01,10,11}。

译码：000,10,000,001,000,11,01,000,01,11,01,01,01,000,01,10,000，01,01,01,000。将译码结果等分为两组（奇数个则去掉最后一个），（000,10,000,001,000,11,01,000，01，11），（01,01,01,000,01,10，000,01,01,01）。转换为十进制数，L1=（02010301013），L2=（1110120111）。按位进行加法运算得M=1311151124。

求M对应的序列

M1=1311151124

M2=M1/2=655575562……0

M3=M2/3=218525187……1

M4=M3/4=54631296……3

M5=M4/5=10926259……1

M6=M5/6=1821043……1

M7=M6/7=260149……0

M8=M7/8=32518……5

总共有8个S盒，求解7步即可得到M对应的序列为（5011310），此时对应的全排列为48135627，求得S盒的使用顺序。

 

4.4 安全性分析

（1）对字密钥的处理采用了前缀码译码的方法，由于前缀码是不固定的，译码结果也不相同，实现了对密钥的加密。

（2）用子密钥的顺序来控制S盒的使用顺序，每一轮迭代子密钥不同，译码不同，对于S盒的顺序也不同，达到了一次一密的效果。

（3）DES初始密钥长度为56位，穷举法破解需要2⁵⁶次，前缀码译码引起S盒的使用顺序不同，大概还需要20！次穷举。8个S盒有8！种全排列，最坏情况则需要20！*8！次穷举才能破解。

 

5 结束语

DES算法自推出以来被广泛运用，同时也面临着各方面的威胁。本文提出的重组S盒的方法，通过子密钥来控制S盒的顺序，有效提高了算法的安全性，增强了抗穷举攻击的能力，也能更好的保护数据。

 

参考文献

[1]刘晓星，胡畅霞，刘明生.安全加密算法DES的分析与改进[J].微计算机信息(管控一体)，2006，22（4-3）：32-33.

[2]胡美燕，刘然慧.DES算法安全性的分析与研究[J].内蒙古大学学报（自然科学版），2005,36（6）：693-697.

[3]陈良.一种优化DES算法硼[J].计算机工程与应用，2004，40(6)：74-76．

[4]普运伟，耿植林，楼静.从 DES算法论分组密码的设计的原则[J].微机发展，2005,15（5）：57-59.

[5]张周圆，董芳，陈一鸣，刘星，王文丰.DES加密算法的迭代改进[J].科技经济市场，2012,10：24-26.

[6]解双建，原亮，谢方方.DES算法原理及其FPGA实现[J].计算机技术与发展，2011，21（7）：158-164.

[7]谢志强，高鹏飞，杨静.基于前缀码的DES算法改进研究[J].计算机工程与应用，2009，45（9）：92-119.

[8]Richard A.Brualdi.组合数学（第四版）[M].北京.机械工业出版社，2005:59-61.

[9]张巨萍，张利军.序数法求解全排列[J].内蒙古科技与经济，2007,141（11）：281-282.