DES算法中S盒的重组方法
2015年5月20日 17:20 作者:陈侨川 李红灵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 ={a1, a2, …, am}是一个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 序数法
序数法是组合数学中全排列的一种算法，对于给定的一个序列（a1，a2，a3…an），可以找出对应的全排列。
首先了解一种数的表达形式：
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=an-1(n-1)!+an-2(n-2)!+…+a11!
m与序列(an-1, an-2,…, a1)一一对应。n个元素的全排列与(an-1, an-2,…, a1)一一对应[8][9]。下面给出求m对应序列的方法。
M1=m
M2=m/2=b1 余数a1
M3=b1/3=b2 余数a2
M4=b2/4=b3 余数a3
……
m除以2的余数为a1，商为b1，b1除以3的余数为a2，商为b2，b2除以4的余数为a3，商为b3……bn-2除以n的余数为an-1，这样便可以求出m对应的序列 (an-1, an-2,…, a1)，根据ai表示i+1所在位置右边比i+1小的数的个数，可求出序列(an-1, an-2,…, a1)的全排列，比如（a3，a2，a1）=（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位，穷举法破解需要256次，前缀码译码引起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.
发给朋友
分享到朋友圈
回顶部