第2 2 卷专刊 2 0 0 5 年8 月河北省科学院学报J o u r a a lo ft h eH e b e iA c a d e m yo fS c i e n c e sV 0 1 2 2S u pA u g2 0 0 5对D E S 算法实现的改进方法刘晓星1 ，胡畅霞2 ，刘展威1( 1 石家庄铁道学院计算机系0 5 0 0 4 3 ；2 石家庄铁道学院信息工程系0 5 0 0 4 3 )摘要：通过对分组密码D E S 算法I P 变换、I P 逆变换、S 一盒换位袭的分析，拽出了他们的换位规则，根据这种规则提出了一种对D E S 算法软件实现的改进方法。关词：D E S ；I P 变换；I P 叫麦换；S 一盒T h ei m p r o v e m e n tm e t h o do fD E Sa l g o r i t h m Sr e a l i z a t i o nL i uX i a o - x i n 9 1 。H Uc h a n g - x i a 2 L I UZ h a n - w e i l( 1S h i f i a z h 眦n gr a i l 瑚y i n s t i t u t e C o m p u t e rs c i e n c e d e p a r t m e n t0 5 0 0 4 3 ；2S h i l t a z h u a n gr a i l 咖yi n s t i t u t e ，I n f o r m a t i o ne n g i n e e r i n gd e p a r t m 删t0 5 0 0 4 3 )A b s t r a c t ：T h r o u g ht h ea n a l y s i so fD E Sa l g o r i t h m ，I Pc o m m u t a t i o n ，I P - 。c o m m u t a t i o n ，S b o x ，f i n do u tt h e i rr e p l a c e m e n tr u l ea n dp u tf o r w a r dak i n do fi m p r o v e m e n tm e t h o do fD E Sa l g o r i t h m ss o f t w a r er e a l i z a t i o na c c o r d i n gt ot h i sk i n do fr u l eK e y w o r d s ：D E S I Pc o m m u t a t i o n ，I P c o m m u t a t i o n ，Sb o x1 引言D E S 全称为D a t aE n c r y p t i o nS t a n d a r d 即数据加密算法，它是一种分组密码体制，1 9 7 7 年由美国国家标准局颁布为数据加密标准。D E S 算法公开了其加密流程及具体实现步骤，但没有公开算法设计的原理和所有技术细节，算法具有极高安全性，到目前为止，除了用穷举搜索法对D E S 算法进行攻击外，还没有发现更有效的办法。D E S 算法在P O S 、A T M 、磁卡及智慧卡( I C 卡) 、加油站、高速公路收费站等领域被广泛应用，以此来实现关键数据的保密，如信用卡持卡人的P I N 的加密传输，I c 卡与P O S 问的双向认证、金融交易数据包的M A C 校验等，均用到了D E S 算法。2D E S 算法实现过程D E S 算法的人口参数有三个：K e y 、D a t a 、M o d e 。其中K e y 为8 个字节共6 4 位，有效位为5 6 位，是D E S 算法的工作密钥；D a t a 也为8 个字节6 4 位是要被加密或被解密的数据；M o d e 为D E S 的工作方式，有两种：加密或解密。D E S 算法是这样工作的：如M o d e 为加密，则用K e y去把明文数据D a t a 进行加密生成D a t a 的密文( 6 4 位) f i e为D E S 的输出结果；如M o d e 为解密则用K c y 去把密文D a t a 解密，还原为D a t a 的明文( 6 4 位) 作为D E S 的输出结果。通信双方约定一致的K e y ，在通信的源点用K e y 对明文数据进行D E S 加密，然后以密文形式在公共通信网中传输到通信网路的终点，数据到达目的地后，用同样的K e y 对密文数据进行解密，便再现了明文的数据。这样，便保证了数据在公共通信网中传输的安全性和可靠性。D E S 算法加密过程如下：1 ) 对给定的6 4 比特的明文x ，通过一个初始置换函数I P 来排列x ，从而构造出长为6 4 比特的串x 0 ：X o = I P( x ) = L o R o ，L o 表示】【0 的前3 2 比特，R 0 表示x 0 的后3 2比特。2 ) 计算1 6 次迭代，设前i1 次迭代结果为x 。=L 一I R 一l ，则第i 次迭代运算为：k = R 一1 ；R = L i o f ( R - k ，) = 1 ，2 ，1 6 。其中L 一l 表示写一l 的前3 2 比特一Rl 表示x 一，的后3 2 比特，0 表示两比特申的“异或”运算，f 主要是由一个称为S 盒的置换构成。k 是一些由初始的5 6比特经过密钥编排函数产生的4 8 比特长的块。3 ) 对比特串R 1 6L 1 6 作逆置换I P _ 1 得密文y 。Y = I P _ 1( R t 6 L 。6 ) 。置换I P _ 1 是I P 的逆置换。下面分别说明初始置换I P ，I P ，函数f ，S 盒及由密钥产生的k ，。1 ) 置换I P ，I P 一：置换I P 和逆置换I P 叫如表l 。从收翦日期：2 0 0 5 0 6 2 0作者简介：刘晓星( 1 9 8 0 一) ，男，河北石家庄 。助教。硕士，主要研究矗向：网络与信息安全专刊刘晓星等：对D E S 算法实现的改进方法表中可以看出函数I P 和I P 叫的输入和输出比特的对应时即将明文的第m 位移到I P 置换后的i * 8 + i 位。I P关系。假如把此矩阵看成一维形式当I P ( i * 8 + j ) = 1 1 1 1 -满足I P I P - 1 = I P 叫I p = I 。襄1 置换I P 和逆置换l P 叫数据对应裹2 ) 函数F ( R 一1 ，k ) “= 1 ，2 ，1 6 ) ：位选择表E 从R 一l 的3 2 位中选取某些位，构成4 8 位，共8 组，每组6位。即E 将3 2 位扩展置换为4 8 位。k 是由密钥产生的4 8 位比特串。将E 的选位结果与k 按位作模加法，得E ( R 一1 ) o k ，这是一个4 8 位的输出。分为8 组。每组6 位，作为8 个S 盒的输入。每个S 盒输出4 位，共3 2 位。S 盘的输出卫作为P 的输入，P 的功能是对输入进行位置换。3 ) 子密钥k ，i = 1 ，2 ，1 6 的构造；设密钥串为K =K l K 2 K 6 4 ，共6 4 位，但是，其中第8 、1 6 、2 4 、3 2 、4 0 、4 8 、6 4用作奇偶校验位，密钥实际上只有5 6 位。k ，i = 1 2 ，1 6 的构造分1 6 轮。首先，对于给定的密钥K ，应用P C 1进行进位，选定后，设其前2 8 位为岛，后2 8 位为。第 一轮：对c 0 作左移崎得c l ，对作左移嗡得D l ，对q D l 应用P C 一2 进行选位，得k L 。第二轮：对c I ，D L 作左移L S 得岛和马进一步对呸跳应用P C 一2 进行选位，得k 2 。如此继续分别可得k 3 ，k 4 ，k 1 6 。4 ) S 盒的工作原理：S 盒以6 位作为输人，而以4 位作为输出，现以S l 为例说明其运行过程。设输人为A =a I a 2 a 3 a 4 a 5a 6 ，则由8 2 8 3a 4 a 5 所代表的二进钳数是0 到1 5 间的一个数，记为k = a 2 a 3 a 4 a 5 ；由a la 6 所代表的二进制数是0 到3 问的一个数，记为h = a la 6 。则在S l 的h 行，k 列查得一数B 0 B 1 5 ，它可用4 位二进制数表示，设为B =b l b 2 b ) ，这就是s I 的输出。D E S 解密算法和加密算法完全一样，只须在第一次迭代时使用k m 第二次迭代时使用k m 最后一次迭代时使用k 。3 改进方法3 1J P 变换表分析爰实觏方法的改进通过对表1 分析可以看出，先输人6 4 比特的一组明文M ( 6 4 ) ，编号次序为0 ，1 2 ，3 ，6 3 ，把M ( 6 4 ) 的第2 ，4 ，6 ，8 ，1 ，3 ，5 ，7 列变成第1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 行后再首尾翻转1 8 0 。就得到明文M ( 6 4 ) 的初始换位表I P ( 6 4 ) 。l P 。1 换位表是将6 4 比特的字符串R 。6L 1 6 的第1 2 ，3 ，4 ，5 ，6 7 8行变成2 4 ，6 8 。1 3 ，5 7 列后再首尾翻转1 8 0 得到的。找到这个规律有助于程序实现的改进并能够提高计算速度。软件设计上。可以用一个表实现两个表的操作，减少程序的大小；也可以直接用算式代替I p 及l P 叫变换表，由计算代替查表，可以大大提高计算的速度。3 2S 盒实现方 击的改进在进行S 盒运算时，设6 位输人为A = a 。a 2a 3 a 4 a 5 a 6 ，记h = 8 l a 6 ，k = 8 2 8 3 钆a 5 ，则在S ( _ _ 1 ，2 。，8 ) 表中第h 行k列所对应的值即为输出值。由于8 la 6 8 2 a 3 a 4 a 5 = a l a 6 1 6 +a 2 a 仙a ，所以在具体软件实现时，可以将S 盘的= 维表化为一维表来操作将在4 行，1 6 列的一个二维表中查找对应的值S ( a la 6 ，a 2 a 3 山幻) 变成逐行接续的一维表，直接查找一维表中a l a 6 a 2 a 3 a 4 a 5 所对应的值，这样可以大大提高程序运行速度。进一步将E 表第6 列变到第2 列，P C 一2表第6 列变到第2 剜，在查找S ( i = 1 ，2 ，8 ) 表时，只须去查找a 1 8 2 行，a 3 丑4 码列所对应的值，变成一维表后，直接查找表中a l a 2 a 弛a 5a 6 所对应的值即可。4 结束语本文介绍了分组密码体制D E S 算j 击的加解密过程，并通过对I P ，I P 一1 变换表，S 盒及整个算法实现过程的分析，提出了在算法设计上的优化方法，经过在软件开发中的应用，能提高算法的运行效率，此种优化方法是可行的。参考文献： 1 肖军模刘军，周海刚网络信息安全 M 北京：机械工业出四川大学学报( 自然科学版) 2 0 0 1 州3 8 ( 3 ) 3 5 0 3 5 1版社。2 0 0 3 4 王立胜，王磊，顾洲穰数据加密标准d 髓分析及其攻击研【2 】冯登国网络安全原理与技术【M 北京| 辛 学出版杜，2 0 0 3究，计算机工程2 0 0 3v o l2 9 ( 1 3 ) 1 3 0 1 3 1 3 陶理，周澈流分组密码d e s 的换位规刚与信息加密的吏现，