详解DES算法

〖Encrypt〗
 
上一篇|下一篇|回文章  分类讨论区   全部讨论区   本讨论区  
 
  发信人: Hitachi (鱼肠剑?断肠毒), 信区: Encrypt
标  题: 详解DES算法
发信站: 武汉白云黄鹤站 (2002年05月28日15:25:13 星期二), 转信

DES算法介绍
　　随着电脑的普及，很多以前在纸上的东西慢慢的转变为了电脑里面的文件了，而在
这其中又有很多重要的资料，还有就是隐私都不想被别人轻易看到，这时就有必要对文
件进行加密了。由此产生了本文。
DES算法：
　　DES是一个分组加密算法，他以64位为分组对数据加密。同时DES也是一个对称算法
：加密和解密用的是同一个算法。
　　它的密匙长度是56位（因为每个第8位都用作奇偶校验），密匙可以是任意的56位的
数，而且可以任意时候改变。其中有极少量的数被认为是弱密匙，但是很容易避开他们
。所以保密性依赖于密匙。
算法概要：
　　DES对64位的明文分组进行操作，通过一个初始置换，将明文份组成左半部分和右半
部分，各32位长。然后进行16轮完全相同的运算，这些运算被称为函数f，在运算过程中
数据于密匙结合。经过16轮候，左，右半部分合在一起经过一个末置换，这样就完成了
。
　　在每一轮中，密匙位移位，然后再从密匙的56位中选出48位。通过一个扩展置换将
数据的右半部分扩展成48位，并通过一个异或操作替代成新的32位数据，在将其置换换
一次。这四步运算构成了函数f。然后，通过另一个异或运算，函数f的输出与左半部分
结合，其结果成为新的右半部分，原来的右半部分成为新的左半部分。将该操作重复16
次，就实现了。具体如下图。
　　
……………………………………………………………..
初始置换：
　　初始置换在第一轮运算之前执行，对输入分组实施如表1-2所示的变换。
表1-2 初始置换
--------------------------------------------------------------
58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4,
62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8,
57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3,
61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7,
--------------------------------------------------------------
　　初始置换和对应的末置换并不影响DES的安全性。所以很多软件实现方式删去了初始
置换和末置换。尽管这种新的算法的安全性不比DES差，但他没有遵循DES标准，所以不
叫DES。
密匙置换：
　　由于不考虑每个字节的第8位，DES的密匙由64位减至56位，每个字节第8位作为奇偶
校验确保密匙不发生错误。在DES每一轮中，从56位密匙产生出不同的48位子密匙，这些
子密匙Ki由下面的方式确定。
表1-3密匙置换
--------------------------------------------------------------
57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18,
10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36,
63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22,
14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4,
--------------------------------------------------------------
　　首先，56位密匙本分成了两个部分，每部分28位。然后，根据论数，这两部分分别
循环左移1位或者2位。表1-4给出了每轮移动的位数。
表1-4 每轮移动的轮数
--------------------------------------------------------------
轮 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
位数 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1
--------------------------------------------------------------
　　移动后，就从56位中选出48位。因为这个运算不仅置换了每位的顺序，同时也选择
了子密匙，因而被称作压缩置换。这个运算提供了一组48位的集。表1-5定义了压缩置换
。
表1-5 压缩置换
--------------------------------------------------------------
14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10,
23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2,
41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32,
--------------------------------------------------------------
　　因为由移动运算，在每一个子密匙中使用了不同的密匙子集的位。虽然不是所有的
位在子密匙中使用的次数都相同，但在16个子密匙中，每一位大约使用了其中14个子密
匙。
扩展置换：
　　这个运算将数据的右半部分Ri从32位扩展到了48位。由于这个运算改变了位的次序
，重复了某些位，故被称为扩展置换。这个操作有两个方面的目的：它产生了与密匙通
长度的数据以进行异或运算；它提供了更长的结果，使得在替代运算时能进行压缩。由
于输入的一位将影响两个替换，所以输出对输入的依赖性将传播的更快，这叫雪崩效应
。
　　图1-6显示了扩展置换，有时他也叫E-盒。对每个4位输入分组，第1和第4位分别表
示输出分组中的两位，而第2和第3位分别表示输出分组中的一位。表1-7给出了那一位输
出对应于那一位输入。
　
表1-7 扩建置换二
--------------------------------------------------------------
32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9,
8, 9, 10, 11, 12, 13, 12, 13, 14, 15, 16, 17,
16, 17, 18, 19, 20, 21, 20, 21, 22, 23, 24, 25,
24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32, 1,
--------------------------------------------------------------
　　尽管输出分组大于输入分组，但每一个输入分组产生唯一的输出分组。
S盒代替:
　　压缩后的密匙与扩展分组异或以后，将48位的结果送入，进行代替运算。替代由8个
代替盒，或S盒完成。每一个S盒都有6位输入，4位输出，且这8个S盒是不同的。48位的
输入悲愤位8个6位分组，每一分组对应一个S盒代替操作：分组1由S盒1操作，分组2由S
盒2操作,如此进行。
表1-8
　　每个S盒是一个4行，16列的表。盒中的每一项都是一个4位数。S和的6个位输入确定
了其对应的输出在那一行那一列。表1-9列出了所有8个盒。
表1-9 S盒
--------------------------------------------------------------
S盒1：
14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13,
S盒2：
15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9,
S盒3：
10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 1, 4, 2, 8,
13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 1, 5, 2, 12,
S盒4：
7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 5, 15,
13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14,
S盒 5：
2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3,
S盒6：
12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13,
S盒7：
4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12,
S盒8：
13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11,
--------------------------------------------------------------
　　输入位以一种非常特殊的方式确定了S和盒的项。假定将S盒的6位的输入标记为
a1,a2,a3,a4,a5,a6。则a1和a2组合构成了一个2位的数，从0到3，他对应着表中的一行
。从a2,到a5构成一个4位数，从0到15，对应着表中的一列。
　　例如，假设第6 个S盒的输入为110011（二进制）。第1位盒最后以位组合形成了11
，他对应着第6个S盒的第三行。中间的4位组合在一起形成了1001，他对应着同一个S盒
的第9列。S盒6的第3行第9列的数是14（注意：行、列的记数从0开始），则值1110就代
替了110011。
P盒置换：
　　　S盒大体运算后的32位输出依照P盒进行置换。给置换把每输入位映射到输出位,任
一位不能被映射量此。也不能被略去，这个置换叫做直接置换。表1-10给出了每位移至
位置。
表1-10 P和置换
--------------------------------------------------------------
16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10,
2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25,
--------------------------------------------------------------
　　最后，将P盒置换的结果与最初的64位分组的左半部分异或，然后左、右半部分交换
，接着开始另一轮。
末置换：
　　末置换是初始置换的逆过程，表1-11列出了该置换。应该注意的是DES在最后一轮后
，左半部分和右半部分并未交换，而是将R16与L16并在一起形成一个分组作为末置换的
输入。其实交换左、右两部分并循环移动，仍将获得完全相同的结果；但这样左，就使
该算法既能作加密又能解密。
表1-11 末置换
--------------------------------------------------------------
40, 8, 48, 16, 56, 24, 64, 32, 39, 7, 47, 15, 55, 23, 63, 31,
38, 6, 46, 14, 54, 22, 62, 30, 37, 5, 45, 13, 53, 21, 61, 29,
36, 4, 44, 12, 52, 20, 60, 28, 35, 3, 43, 11, 51, 19, 59, 27,
34, 2, 42, 10, 50, 18, 58, 26, 33, 1, 41, 9, 49, 17, 57, 25,
--------------------------------------------------------------
DES解密：
　　　　在经过所有的代替、置换、异或盒循环之后，你也许认为解密算法与加密算法
完全不同。恰恰相反，经过精心选择的各种操作，获得了一个非常有用的性质：加密和
解密使用相同的算法。
　　DES加密和解密唯一的不同是密匙的次序相反。如果各轮加密密匙分别是K1,K2,K3…
.K16那么解密密匙就是K16,K15,K14…K1。为各轮产生的密是的算法也是循环的。米匙想
右移动，每次移动的个数为：0，1，2，2，2，2，2，2，1，2，2，2，2，2，2，1。
参考文献：Bruce Schneier. Applied Cryptography Protocols,algorithms,and sour
ce code in C 1996

--
   ___ ___  .___ ___________ _____   _________    ___ ___