DES原理与实现
一 DES综述
DES是对称密码的一种，它使用56位秘钥对64位长分组进行加密。DES对每个分组的内容都会进行16轮迭代，每轮的操作相同但是对应不同的子秘钥。所有的子秘钥都是由主密钥推导而来。
64位明文加密过程如下：
1. 按位置换（IP）
2. 明文被分成L0和R0两部分。
3. L1=R0 R1=L0⊕f(R0，k1)
4. 重复步骤3 16次
5. 按位置换（IP^-1）
二 细节分析
其中的重点在于：1. 如何实现函数f 2. 如何生成子秘钥k
1. 函数f 输入与输出的数据为32位。
E: 将输入的数据分成8个4位的分组。这个过程在E盒中进行。E盒是一种特殊的置换。32位输入中有16位输入位在输出中出现了两次。分别为第1 4 5 8 9 12 ... 32位。E盒的输入数据为32位，输出为48位，仅有置换操作。
S: 将拓展得到的48位结果与密钥ki进行XOR操作，将8个6位长的分组送入8个不同的替换盒S中，将6位输出裁剪成4位。S盒的输入数据为48位，输出为32位，有和密钥的XOR操作，也有置换。
P: 按位置换，以实现扩散。P盒的输入和输出均为32位，仅有置换操作。
2. 密钥生成函数GetKey的输入为64位密钥，输出为16个48位子密钥。
密钥的实际有效位数为56位，其余8位为奇校验位。PC-1处理得到的56位密钥分为C和D两部分。首先将C和D按照轮数移动一位或者两位。然后将C和D合起来，用PC-2将56位密钥置换成48位密钥。
PC-1：置换的意义是去掉校验位。
PC-2：意义是将56位置换成48位。
三 几个小问题
1. 从总体上来说，DES是什么？
前面杂七杂八的扯了那么多细节问题，不免让人头昏脑涨。用最简单的话讲，DES是什么？一种加密方法。它将8位密钥处理得到16组子密钥。它还将待加密数据分成许多个分组，每个分组有8个字符组成。然后每组待加密数据，做16轮加密处理，每轮加密处理都用不同的密钥，即最初得到的16组子密钥。
举例说明：
密钥：12345678
待加密数据:i am a good student
子密钥：
Array (
[1] => 010100000010110010101100010101110010101011000010
[2] => 010100001010110010100100010100001010001101000111
[3] => 110100001010110000100110111101101000010010001100
[4] => 111000001010011000100110010010000011011111001011
[5] => 111000001001011000100110001111101111000000101001
[6] => 111000001001001001110010011000100101110101100010
[7] => 101001001101001001110010100011001010100100111010
[8] => 101001100101001101010010111001010101111001010000
[9] => 001001100101001101010011110010111001101001000000
[10] => 001011110101000101010001110100001100011100111100
[11] => 000011110100000111011001000110010001111010001100
[12] => 000111110100000110011001110110000111000010110001
[13] => 000111110000100110001001001000110110101000101101
[14] => 000110110010100010001101101100100011100110010010
[15] => 000110010010110010001100101001010000001100110111
[16] => 010100010010110010001100101001110100001111000000 )
待加密数据：
i am a g => 281EBCF251148911 (16进制)
ood stud =>ECFB5BFD44D714EF (16进制)
ent00004 =>BFBE729B56B9B540(16进制)#最后一组待加密数据位数不足8位，用0补齐，最后一位表示补0的个数
2. 怎么实现置换？
置换在代码中的实现尤为简单，具体见最下方的代码 function move()。
3. 函数过程中数据应该是以二进制流动的，二进制如何与字母数字转化？
被加密字符采用了ASCII码到二进制的转换。密钥每一位都被当做10进制数字处理。
被加密的字符首先被转化成两位16进制表示的ASCII码，然后每个字符转换成8位2进制,即为二进制原始待加密数据。
4. 密钥的格式是什么：字母或者是数字？多少位？
在整个加密过程中，共生成16组子密钥，分别用于16轮加密。每个生成的子密钥的实际均为48位的二进制数组。具体格式如上所示。具体转换的方法是：用户提供的密钥中的每一位数字，都由1位十进制转化成8位二进制，不足8位的在最前方补0。即得出64位二进制原始密钥。
四 贴代码（php）
$S = array(
1 => array(
array(14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7),
array(0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8),
array(4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0),
array(15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13),
),
2 => array(
array(15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10),
array(3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5),
array(0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15),
array(13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9),
),
3 =>array(
array(10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8),
array(13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1),
array(13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7),
array(1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12),
),
4 => array(
array(7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15),
array(13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9),
array(10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4),
array(3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14),
),
5 => array(
array(2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9),
array(14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6),
array(4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14),
array(11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3),
),
6 => array(
array(12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11),
array(10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8),
array(9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6),
array(4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13),
),
7 => array(
array(4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1),
array(13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6),
array(1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2),
array(6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12),
),
8 => array(
array(13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7),
array(1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2),
array(7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8),
array(2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11),
),
);
$E = array(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);
$P = array(
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,
);
$PC1 = array(
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);
$PC2 = array(
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,
);
$IP = array(
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,
);
$IP1 = array(
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,
);
$r = array(1=>1,2=>1,3=>2,4=>2,5=>2,6=>2,7=>2,8=>2,9=>1,10=>2,11=>2,12=>2,13=>2,14=>2,15=>2,16=>1,);
1 $k = array();
2
3 function index($data,$key,$type=1){
4 global $k;
5 $k=GetKey($key);
6 if($type==1){
7 $str=BitByte($data);
8 return DES($str);
9 }
10 else{
11 $str=DecodeTrans($data);
12 return ToASCII(DES($str,2));
13 }
14 }
15
16 function shiftleft($data,$num) { //循环左移一位
17 return substr($data, $num, (strlen($data) - $num)) . substr($data, 0, $num);
18 }
19
20 function move($array, $data) { //置换
21 $rs = '';
22 foreach($array as $index) {
23 $rs .= $data[$index-1];
24 }
25
26 return $rs;
27 }
28
29 function dataXOR($data1, $data2) {
30 if(strlen($data1) != strlen($data2)) {
31 exit('xor err');
32 }
33
34 $rs = '';
35 for($i=0; $i<strlen($data1); $i++){
36 $rs .= ($data1[$i] == $data2[$i])?0:1;
37 }
38
39 return $rs;
40 }
41
42 function S($EL) {
43 global $S;
44
45 $B = array();
46 for($i=1;$i<=8;$i++){
47 $B[$i] = substr($EL, 6*($i-1),6);
48 }
49
50 $BI = array();
51 foreach($B as $id => $row) {
52 $a = base_convert($row[0] . $row[5], 2, 10);
53 $b = base_convert(substr($row, 1, 4), 2, 10);
54 $BICurrent = base_convert($S[$id][$a][$b], 10, 2);
55
56 while(strlen($BICurrent) < 4) {
57 $BICurrent = 0 . $BICurrent;
58 }
59
60 $BI[$id] = $BICurrent;
61 }
62
63 return implode('', $BI);
64 }
65
66 function BitByte($data){
67 $str='';
68 for($i=0;$i<strlen($data); $i++){
69 $temp=base_convert(ord($data[$i]), 10, 2);
70 while(strlen($temp) < 8) {
71 $temp = 0 . $temp;
72 }
73
74 $str .= $temp;
75 }
76
77 return $str;
78 }
79
80 function DecodeTrans($data){ //16进制转换为二进制
81 $result = '';
82 for($start = 0; $start < strlen($data); $start += 2) {
83 $bin = substr($data, $start, 2);
84 $temp= strtoupper(base_convert($bin, 16, 2));
85 while(strlen($temp) < 8) {
86 $temp = 0 . $temp;
87 }
88
89 $result .=$temp;
90 }
91
92 return $result;
93 }
94
95 function GetKey($key){
96 global $PC1,$PC2;
97
98 if(strlen($key)!=8){
99 exit('密钥长度错误！');
100 }
101
102 $binKey=BitByte($key); //key转成二进制
103 $keyPC1 = move($PC1,$binKey); //对key（binkey）进行pc-1处理
104 $C[0] = substr($keyPC1, 0, 28);
105 $D[0] = substr($keyPC1, 28, 28);
106 $C=GetMove($C);
107 $D=GetMove($D);
108
109 for($i=1; $i<=16; $i++) {
110 $concat = $C[$i] . $D[$i];
111 $k[$i]=move($PC2,$concat);
112 }
113
114 return $k;
115 }
116
117 function GetMove($data) //获取左移之后的密钥
118 {
119 global $r;
120
121 for($i=1; $i<=16; $i++) {
122 $shift = $data[$i-1];
123 $data[$i] = shiftleft($shift,$r[$i]);
124 }
125
126 return $data;
127 }
128
129
130 function DES($data,$type=1){
131 global $IP,$IP1,$E,$k,$P;
132 $temp=move($IP,$data);
133
134 $L = $R = array();
135 $L[0] = substr($temp, 0, 32);
136 $R[0] = substr($temp, 32, 32);
137
138
139 for($i=1; $i<=16; $i++) {
140 $L[$i] = $R[$i-1];
141 $EL = move($E, $L[$i]);
142
143 $EL = ($type==1)?dataXOR($EL, $k[$i]): dataXOR($EL, $k[17-$i]);
144 $s = S($EL);
145 $f = move($P, $s);
146 $R[$i] = dataXOR($L[$i-1], $f);
147 }
148
149 $concat = $R[16] . $L[16];
150
151 $encoded = move($IP1, $concat);
152 $result = '';
153 for($start = 0; $start < strlen($encoded); $start += 4) {
154 $bin = substr($encoded, $start, 4);
155 $result .= strtoupper(base_convert($bin, 2, 16));
156 }
157
158 return $result;
159 }
160
161 function ToASCII($data){
162 $str='';
163 for($start = 0; $start < strlen($data); $start += 2) {
164 $bin = substr($data, $start, 2);
165 $str .= chr(base_convert($bin, 16, 10));
166 }
167
168 return $str;
169 }