对称密码算法初探

对称密码算法初探
CFCA

1.什么是对称密码算法
　　网络安全通信中要用到两类密码算法，一类是对称密码算法，另一类是非对称密码算法。对称密码算法有时又叫传统密码算法、秘密密钥算法或单密钥算法，非对称密码算法也叫公开密钥密码算法或双密钥算法。对称密码算法的加密密钥能够从解密密钥中推算出来，反过来也成立。在大多数对称算法中，加密解密密钥是相同的。它要求发送者和接收者在安全通信之前，商定一个密钥。对称算法的安全性依赖于密钥，泄漏密钥就意味着任何人都能对消息进行加密解密。只要通信需要保密，密钥就必须保密。

　　对称算法又可分为两类。一次只对明文中的单个位（有时对字节）运算的算法称为序列算法或序列密码。另一类算法是对明文的一组位进行运算，这些位组称为分组，相应的算法称为分组算法或分组密码。现代计算机密码算法的典型分组长度为64位――这个长度既考虑到分析破译密码的难度，又考虑到使用的方便性。后来，随着破译能力的发展，分组长度又提高到128位或更长。
常用的采用对称密码术的加密方案有5个组成部分（如图所示）

1)明文：原始信息。
2)加密算法：以密钥为参数，对明文进行多种置换和转换的规则和步骤，变换结果为密文。
3)密钥：加密与解密算法的参数，直接影响对明文进行变换的结果。
4)密文：对明文进行变换的结果。
5)解密算法：加密算法的逆变换，以密文为输入、密钥为参数，变换结果为明文。

2.对称密码常用的数学运算
　　对称密码当中有几种常用到的数学运算。这些运算的共同目的就是把被加密的明文数码尽可能深地打乱，从而加大破译的难度。

◆移位和循环移位
　　移位就是将一段数码按照规定的位数整体性地左移或右移。循环右移就是当右移时，把数码的最后的位移到数码的最前头，循环左移正相反。例如，对十进制数码12345678循环右移1位（十进制位）的结果为81234567，而循环左移1位的结果则为23456781。
◆置换
　　就是将数码中的某一位的值根据置换表的规定，用另一位代替。它不像移位操作那样整齐有序，看上去杂乱无章。这正是加密所需,被经常应用。
◆扩展
　　就是将一段数码扩展成比原来位数更长的数码。扩展方法有多种,例如,可以用置换的方法，以扩展置换表来规定扩展后的数码每一位的替代值。
◆压缩
　　就是将一段数码压缩成比原来位数更短的数码。压缩方法有多种，例如，也可以用置换的方法，以表来规定压缩后的数码每一位的替代值。
◆异或
　　这是一种二进制布尔代数运算。异或的数学符号为⊕ ，它的运算法则如下：
1⊕1 = 0 
0⊕0 = 0 
1⊕0 = 1 
0⊕1 = 1 
　　也可以简单地理解为，参与异或运算的两数位如相等，则结果为0，不等则为1。
◆迭代
　　迭代就是多次重复相同的运算，这在密码算法中经常使用，以使得形成的密文更加难以破解。

3.DES算法简介
　　下面我们将介绍一种流行的对称密码算法DES。

　　DES是Data Encryption Standard（数据加密标准）的缩写。它是由IBM公司研制的一种对称密码算法，美国国家标准局于1977年公布把它作为非机要部门使用的数据加密标准，三十年来，它一直活跃在国际保密通信的舞台上，扮演了十分重要的角色。

　　DES是一个分组加密算法，典型的DES以64位为分组对数据加密，加密和解密用的是同一个算法。它的密钥长度是56位（因为每个第8 位都用作奇偶校验），密钥可以是任意的56位的数，而且可以任意时候改变。其中有极少数被认为是易破解的弱密钥，但是很容易避开它们不用。所以保密性依赖于密钥。

DES加密的算法框架如下：
　　首先要生成一套加密密钥，从用户处取得一个64位长的密码口令，然后通过等分、移位、选取和迭代形成一套16个加密密钥，分别供每一轮运算中使用。

　　DES对64位(bit)的明文分组M进行操作，M经过一个初始置换IP，置换成m0。将m0明文分成左半部分和右半部分m0 = (L0，R0)，各32位长。然后进行16轮完全相同的运算（迭代），这些运算被称为函数f，在每一轮运算过程中数据与相应的密钥结合。

　　在每一轮中，密钥位移位，然后再从密钥的56位中选出48位。通过一个扩展置换将数据的右半部分扩展成48位，并通过一个异或操作替代成新的48位数据，再将其压缩置换成32位。这四步运算构成了函数f。然后，通过另一个异或运算，函数f的输出与左半部分结合，其结果成为新的右半部分，原来的右半部分成为新的左半部分。将该操作重复16次。

　　经过16轮迭代后，左，右半部分合在一起经过一个末置换（数据整理），这样就完成了加密过程。 
加密流程如图所示。


DES解密过程：
　　在了解了加密过程中所有的代替、置换、异或和循环迭代之后，读者也许会认为，解密算法应该是加密的逆运算，与加密算法完全不同。恰恰相反，经过密码学家精心设计选择的各种操作，DES获得了一个非常有用的性质：加密和解密使用相同的算法！

　　DES加密和解密唯一的不同是密钥的次序相反。如果各轮加密密钥分别是K1，K2，K3…K16，那么解密密钥就是K16，K15，K14…K1。这也就是DES被称为对称算法的理由吧。

　　至于对称密码为什么能对称? DES具体是如何操作的？本文附录中将做进一步介绍，有兴趣的读者不妨去读一读探个究竟。

4.DES算法的安全性和发展
　　DES的安全性首先取决于密钥的长度。密钥越长，破译者利用穷举法搜索密钥的难度就越大。目前，根据当今计算机的处理速度和能力，56位长度的密钥已经能够被破解，而128位的密钥则被认为是安全的，但随着时间的推移，这个数字也迟早会被突破。

　　另外，对DES算法进行某种变型和改进也是提高DES算法安全性的途径。

　　例如后来演变出的3-DES算法使用了3个独立密钥进行三重DES加密，这就比DES大大提高了安全性。如果56位DES用穷举搜索来破译需要2∧56次运算，而3-DES 则需要2∧112次。

　　又如，独立子密钥DES由于每轮都使用不同的子密钥，这意味着其密钥长度在56位的基础上扩大到768位。DES还有DESX、CRYPT、GDES、RDES等变型。这些变型和改进的目的都是为了加大破译难度以及提高密码运算的效率。
___________________________________________________
附录：DES的实际操作
A.密钥生成

第A-1步 取得密钥
　　从用户处取得一个64位(本文均指二进制位))长的密码口令key ，
　　去除64位密码中作为奇偶校验位的第8、16、24、32、40、48、56、64位，剩下的56位作为有效输入密钥。

第A-2步 等分密钥
表1：
输入密钥位序/ A位序对照表

注：表中每个单元格的数字是输入密钥位序，每个单元格的位置排序就是A位序，从左向右排，排完一行接着排下一行。

表2:
输入密钥位序/ B位序对照表

　　把在第A-1步中生成的56位输入密钥分成均等的A、B两部分，每部分为28位。不是简单地前后一分为二，而是参照表1和表2把输入密钥的位值填入相应的位置。 按照表1所示，A的第一位为输入的64位密钥的第57位，A的第2位为64位密钥的第49位，……，依此类推，A的最后一位第28位是64位密钥的第36位。这样，形成了A、B两部分：


第A-3步 密钥移位
表3：
每次迭代时密钥循环
左移的位数

　　DES算法的密钥是经过16次迭代（循环左移）得到一组密钥的，把在第A-1步中生成的A、B视为迭代的起始密钥，表3显示每一次迭代时密钥循环左移的位数。 比如在第1次迭代时密钥循环左移1位，第3次迭代时密钥循环左移2位。

　　第9次迭代时密钥循环左移1位，第14次迭代时密钥循环左移2位。

第一次迭代：
A(1) =(1) A
B(1) =(1) B
第i次迭代：
A(i) =(i) A(i-1)
B(i) =(i) B(i-1)
第A-4步 密钥的选取
在第A-3步中第i次迭代生成的两个28位长的密钥为



把合并，得：


表4：
56位密钥C的位序与加密密钥K的位序对照表

　　按照表4所示k的第一位为56位密钥的第14位，k的第2位为56位密钥的第17位，。。。，依此类推，k的最后一位第48位是56位密钥的第32位。 这样，就生成了一个48位使用密钥：

　　这个密钥在加密运算中将与进行第i次迭代加密的数据进行按位异或。

第A-5步 迭代
　　DES算法密钥生成需要进行16次迭代，在完成16次迭代前，循环执行第A-3步和第A-4步，最终形成16套加密密钥：key[0]，key[1]，key[2]，…。key[14]，key[15]。

B. 数据的加密操作

第B-1步 取得数据
　　把明文数据分成64位的数据块，不够64位的数据块以适当的方式补足。

第B-2步 初始换位置换
表5：初始置换表

注：表中每个单元格的位置排序是新数据的位序。下同。

　　按照表5所示把输入的64位数据的原第58位换到第一位，原第50位换到第二位，依此类推，。。。，原第7位换到第64位。最后的得到新的64位数据。

OldData newData 


第B-3步 数据扩展
表6： 数据扩展对照表（输入数据位序/生成新数据位序）

　　第一次迭代以第B-2步中生成的newRata作为输入数据，第i (i > 1)次迭代以第i-1次的64位输出数据为输入数据，把64位数据按位置等分成左右两部分： 

　　保持left不变，根据表6把right由32位扩展置换成48位。在数据扩展操作中，有些输入数据位（如第1、4、5、17、28、29、32……等数位）用了两次，因此数据得到了扩展。这样得到右半部分为：  把扩展后的48位right与第i次迭代生成的48位加密密钥进行按位异或操作形成一个新的48位的right。

第B-4步 数据压缩
表7.1：数据压缩置换表（蓝色栏内是置换前的十进制数字，白色栏内是置换后的16进制数字）

表7.2

表7.3 至表7.8与上表形式完全相同，仅数值不同，为节省篇幅从略不表。 

　　在B-3步中形成了48位的right值,

　　需要把48位的right值转换成32位的right值。置换的方法如下：
第一步，先把right视为由8个6位二进制块组成， 即

a，b…. h都是6位二进制数，转换成10进制整数的值应当都不大于64。

　　第二步，a，b…h转换成10进制整数后，在对应的表中根据转换后整数值取得对应位置的替代值。这些替代值都是一个16进制的个位数，因此，每个替代值只占有二进制数4位。

　　转换时各查各表：
　　a对应表7.1；b对应表7.2；c对应表7.3；d对应表7.4；e对应表7.5；f对应表7.6；g对应表7.7；h对应表7.8。
　　比如：
　　a = 32 ，则到表7.1中找到32的位置，把对应的替代值16进制的8赋给a ；
　　b = 53 ，则到表7.2中找到的位置，把对应的替代值16进制的c赋给b ；
　　g = 16， 则到表7.7中找到16的位置，把对应的替代值16进制的a赋给g ；
　　这样，每6位用一个4位替换，就完成了从48位向32位数据的压缩置换。

 

　　有些资料中介绍6位转4位的实现方法与本文所采用的不同，但殊途同归，最终的目的是相同的。

第B-5步 数据换位置换
表8


把第B-4步形成的32位right
 
根据表8进行转换：
　　数据的原第16位换到第一位，原第7位换到第二位，……，依此类推，最后得到新的32位数据。


第B-6步 交换数据
　　把right 和left按位异或后的值赋给right，然后将本轮输入的原始right值赋给left。

第B-7步 迭代
　　RES算法需要进行16次迭代，在完成16次迭代前，把第i-1次得到的的left和right的值作为第i次的输入数据，重复第B-3步到第B-6步的步骤。但是有一点要记住：在步骤第B-3中第i次迭代要选择第i次迭代生成的密钥与数据进行按位异或。

第B-8步 数据整理
表9

　　为保证加密和解密的对称性，RES算法的前15次迭代每完成一次迭代都要交换left和right的值，第16次迭代不交换两者的数值。

　　到此，把32位的left和right合并成64位的Data：

　　根据表9重新调整Data的位值，数据的原第40位换到第一位，原第8位换到第二位，。。。，依此类推，最后得到新的64位。 

　　好了，经过了这么多次的数学运算，我们最终得到的Data即为密文。

C 数据的解密操作
　　数据解密的算法与加密算法相同，区别在于第B-3步中和数据进行按位异或的密钥的使用顺序不同，在加密中是按照第i次迭代就采用第i次迭代生成的密钥进行异或，而解密时第i次迭代就采用第17-i次迭代生成的密钥和数据进行异或。