DES算法描述与示例
amoon原创 2006年01月
前些天想写一段DES加密的程序，到网上搜了半天，看到很多中文的贴子都是相互转的，有些描述的也不太详尽，自己照着描述编了一段代码，输出的结果自己也不知是否正确，因为没有示例对照，只能反过来解密，看是否与原来数据一致，看到结果不一致时就不知该怎么办了。后来搜到一个英文的贴子，对照后发现有个地方说明的有问题，修改后程序就能工作了。现在把算法的详细描述附上示例写出来，供您参考。
DES算法是一个按位(bit)操作的算法。在计算机中数据一般都按字节(byte)存储。因此在理解算法时要把字节转换成二进制位来看，才能比较清楚，如字符'a'，用一个字节表示，十六进制为0x61，转换成二进制为01100001。DES算法是对称加密算法，加密和解密都是通过相同的算法和密钥进行的。DES 算法的输入分为数据(data)、密钥(key)和模式(mode)，模式指示算法进行加密还是解密操作，输出为加密或解密后的数据。DES算法是通过一系列的位置换和异或操作来完成的，分为密钥(key)处理和数据 (data)处理两部分，下面分别描述。
约定
为方便阅读，我们约定位是从1开始编号的，比如字节0x53，二进制为01010011，那么第一位是0，第二位是1，第三位是0，最后一位是第八位，是1。如果是两个字节，如0x5392，二进制为 01010011 10010010，第二个字节的第一位是第九位，是1，最后一位是第十六位，是0。
密钥(key)处理
DES密钥是64位数据，即8个字节。其中8、16、24、32、40、48、56、64位是校验位，舍弃不用，剩下的56位参与运算。DES算法要进行16轮的数据置换和异或操作，所以需要从原始的密钥产生出 16组子密钥待用。下面我们看一下这16组子密钥是怎么生成的。
原始的密钥K(64 bits)经过下表的置换(permutation)生成两组28位的密钥，分别叫做KA和KB。
PC-1
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
KA的第一位是K的57位，KA的第二位是K的49位... KA的最后一位是K的36位。
KB的第一位是K的63位，KB的第二位是K的55位... KB的最后一位是K的第4位。
KA=K57K49K41 ... K44K36， KB=K63K55K47 ... K12K4，各为28位。
KA和KB分别进行循环左移，产生KA'和KB'，把KA'和KB'合并成56位，然后通过下面的选择表选出48位来作为子密钥。
PC-2
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组密钥，所以要进行16次循环操作。在循环前我们已经得到了KA和KB，第一次循环把KA和KB分别进行循环左移一次，得到KA1和KB1，然后把KA1和KB1合并，得到KS1，然后把KS1通过PC-2置换后就得到了子密钥sub-key1。接下来进行第二次循环，把KA1和KB1分别进行循环左移一次，得到KA2和KB2，然后把 KA2和KB2合并，得到KS2，把KS2通过PC-2置换后就得到了子密钥 sub-key2。然后进行第三次循环，注意这次循环KA2和KB2要循环左移两次，为什么呢？因为每次循环KA和KB 左移的次数遵循下面的规则。
循环轮次 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16
左移次数 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
完成16轮循环操作，我们得到了16组子密钥(SKEY1SKEY2 ... SKEY16)，至此密钥处理完成。
数据(data)处理
DES输入的数据也是64位的，8个字节。数据首先进行一个初始置换(Initial Permutation)，
置换表如下。
IP
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
如果原始数据为D，那么经过初始置换后得到D'=D58D50D42 ... D15D7。把D'分成左右两组，叫做L和R，
各为32位，4个字节。然后进行16次循环操作。左半部分数据不动，把右半部分数据的32位先扩展成48位
与48位的子密钥进行异或(XOR)操作，然后再通过一个变换表把48位数据变换成32位数据，再进行一次置
换，然后把左半部分数据和右半部分数据交换，进行下一次循环。先列出变换用到的表，再进行详细解释。
扩展表(expansion table)
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 box)
SBOX-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
SBOX-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
SBOX-3
10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 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, 11, 5, 2, 12
SBOX-4
7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 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
SBOX-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
SBOX-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
SBOX-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
SBOX-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
置换表(P box)
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
下面详细解释。数据处理也要经过16次循环，在循环开始前我们得到左半部分数据L和右半部分数据R，
L和R作为循环的初始数据L0和R0。进入第一次循环，我们看R1是怎么产生的。R0先通过扩展表扩展成48
位，设为RE，然后RE与SKEY1进行按位异或(XOR)操作，结果存在RE中。现在RE是48位，需要通过S盒
变换回到32位，我们来看一下S盒的结构，每个S盒由4行16列组成，行从0到3，列从0到15，S盒中的每
个数都是0和15之间的值，正好构成半个字节(4位)，这样从8个S盒中各取4位就变换成原来的32位数据。
下面我们看一下怎样从S盒中取数。我们的RE有48位，如果除以S盒的个数8，得到的数值是6，所以每
6位代表一个S盒中的4位数据，我们用二进制表示这个6位的数为D1D2D3D4D5D6，我们取D1D6的值作为
S盒的行号，D2D3D4D5的值作为S盒的列号，这样就能在一个S盒中唯一的取到一个4位数。
假设RE开始的6位是101010，那么行号是r=10，是十进制的2，列号是c=0101，是十进制的5，因为开始
的六位代表从第一个S盒取数，所有我们在SBOX-1中的第2行，第5列取到6(记住行和列从0开始计数)。
RE有48位，第1到第6位从SBOX-1中取数，第7到第12位从SBOX-2中取数，第13到18位从SBOX-3中取数 ...
第43到第48位从SBOX-8中取数。我们把RE经过S盒选取的32位数据设为RS，RS再经过P盒置换，生成的
数据仍然是32位，设为RP。然后RP与L0进行按位异或(XOR)操作，结果保存在R1中，至此R1生成了，
此时L1等于L0。然后把左半部分数据和右半部分数据互换，即L1R1，进入下一次循环。
完成16次循环后，把左右两部分数据合并到一起，注意一定要右半部分数据在前，左半部分数据在后，
即DS=R16L16。然后经过最后一次置换，就生成了最终数据。
最终置换表IP-1
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
解密操作是加密的逆操作，其他保持不变，只是在数据处理循环时不同，第一次循环，加密操
作与SKEY1异或，而解密操作与SKEY16异或，后续循环加密操作的SKEY递增，解密操作的SKEY递减。
下面举例说明，为方便编程时对照，以下都用十六进制码表示，各位可自己翻译成二进制。
假设我们进行加密操作，待加密数据为字符串"testdata"，加密密钥为"mydeskey"。用十六进制表示
为D=74 65 73 74 64 61 74 61，K=6D 79 64 65 73 6B 65 79。下面先看密钥的生成。
密钥经过64选56的置换，生成KA和KB两组各28位，用十六进制表示为KA=00 FF FF 90，KB=30 4D A3 20，
最后的半个字节没用，设为0。下面进入16轮循环，对应的KA和KB值如下：
KA[ 1]=01 FF FF 20 KB[ 1]=60 9B 46 40
KA[ 2]=03 FF FE 40 KB[ 2]=C1 36 8C 80
KA[ 3]=0F FF F9 00 KB[ 3]=04 DA 32 30
KA[ 4]=3F FF E4 00 KB[ 4]=13 68 C8 C0
KA[ 5]=FF FF 90 00 KB[ 5]=4D A3 23 00
KA[ 6]=FF FE 40 30 KB[ 6]=36 8C 8C 10
KA[ 7]=FF F9 00 F0 KB[ 7]=DA 32 30 40
KA[ 8]=FF E4 03 F0 KB[ 8]=68 C8 C1 30
KA[ 9]=FF C8 07 F0 KB[ 9]=D1 91 82 60
KA[10]=FF 20 1F F0 KB[10]=46 46 09 B0
KA[11]=FC 80 7F F0 KB[11]=19 18 26 D0
KA[12]=F2 01 FF F0 KB[12]=64 60 9B 40
KA[13]=C8 07 FF F0 KB[13]=91 82 6D 10
KA[14]=20 1F FF F0 KB[14]=46 09 B4 60
KA[15]=80 7F FF C0 KB[15]=18 26 D1 90
KA[16]=00 FF FF 90 KB[16]=30 4D A3 20
生成的16组密钥如下：
sub-key[ 1]=F0 BE 6E B3 88 28
sub-key[ 2]=E0 BE F6 03 46 5E
sub-key[ 3]=F4 F6 76 9D 91 80
sub-key[ 4]=E6 D7 72 80 46 65
sub-key[ 5]=EE D3 77 5A AA 84
sub-key[ 6]=AF D3 5B B0 45 99
sub-key[ 7]=2F 53 FB 0B 32 03
sub-key[ 8]=BF 59 D9 F6 61 20
sub-key[ 9]=1F 59 DB 17 C8 07
sub-key[10]=3F 69 DD 46 05 D0
sub-key[11]=1F 6D 8D 89 A1 4D
sub-key[12]=5B 2D BD 62 D6 80
sub-key[13]=DD AC AD 58 05 2F
sub-key[14]=D3 AE AE 8E 58 88
sub-key[15]=F8 BE A6 40 73 71
sub-key[16]=F1 BE 26 EC C8 11
下面是数据的处理。先进行初始置换，得到D'=FF 4D 5B A6 00 FF 00 04，分成左右两组，得到初始值
L[0]=FF 4D 5B A6 和 R[0]=00 FF 00 04，下面进入16轮循环，右半部分的数据经过扩展，数据如下：
R'[ 1]=00 17 FE 80 00 08
R'[ 2]=0F 02 0F DA 40 08
R'[ 3]=15 97 F0 2A AB A0
R'[ 4]=C5 01 F9 7F 3D F7
R'[ 5]=E0 94 02 B5 7D 53
R'[ 6]=AA 95 56 90 D5 5A
R'[ 7]=D5 15 0E A0 40 0B
R'[ 8]=5A 7C FA AA 7C A1
R'[ 9]=3F 2A 0C 0F 3E A8
R'[10]=EF 7C FA 95 97 5B
R'[11]=1F 15 02 A0 16 FC
R'[12]=80 03 FD 60 C2 F2
R'[13]=DF 97 F7 EA EB A3
R'[14]=95 56 00 3F BC F2
R'[15]=25 82 59 75 3D A8
R'[16]=85 E9 0B E5 56 FA
R'与sub-key异或操作后，经过S盒选择，生成数据如下：
RS[ 1]=5B 91 B1 17
RS[ 2]=05 FC 50 2E
RS[ 3]=3D E3 2E C7
RS[ 4]=2E 4F 37 E9
RS[ 5]=F7 F5 48 6B
RS[ 6]=02 B0 77 0F
RS[ 7]=07 B5 D7 F6
RS[ 8]=A7 CF AA 81
RS[ 9]=27 AC 15 AD
RS[10]=93 C6 C6 03
RS[11]=E7 63 AB 1F
RS[12]=78 B7 24 E6
RS[13]=E8 8C 73 5B
RS[14]=A2 6D 7B E3
RS[15]=E0 FE D3 20
RS[16]=34 2D C0 2A
RS通过P盒置换，生成数据如下：
RP[ 1]=E7 0A E9 A2
RP[ 2]=2C 07 55 74
RP[ 3]=90 7B 4B BF
RP[ 4]=E8 79 3E D9
RP[ 5]=DC 97 DF 16
RP[ 6]=6C 26 29 AC
RP[ 7]=E7 36 75 3D
RP[ 8]=D1 E1 5B D1
RP[ 9]=68 00 7F 7D
RP[10]=41 E7 59 0A
RP[11]=DB E3 EA B4
RP[12]=84 5A 97 AF
RP[13]=2A BE BB C0
RP[14]=F0 B7 3E C5
RP[15]=25 E5 B7 44
RP[16]=89 06 16 56
每次循环，左右两部分数据分别为：
L[ 1]=00 FF 00 04 R[ 1]=18 47 B2 04
L[ 2]=18 47 B2 04 R[ 2]=2C F8 55 70
L[ 3]=2C F8 55 70 R[ 3]=88 3C F9 BB
L[ 4]=88 3C F9 BB R[ 4]=C4 81 6B A9
L[ 5]=C4 81 6B A9 R[ 5]=54 AB 26 AD
L[ 6]=54 AB 26 AD R[ 6]=A8 A7 42 05
L[ 7]=A8 A7 42 05 R[ 7]=B3 9D 53 90
L[ 8]=B3 9D 53 90 R[ 8]=79 46 19 D4
L[ 9]=79 46 19 D4 R[ 9]=DB 9D 2C ED
L[10]=DB 9D 2C ED R[10]=38 A1 40 DE
L[11]=38 A1 40 DE R[11]=00 7E C6 59
L[12]=00 7E C6 59 R[12]=BC FB D7 71
L[13]=BC FB D7 71 R[13]=2A C0 7D 99
L[14]=2A C0 7D 99 R[14]=4C 4C E9 B4
L[15]=4C 4C E9 B4 R[15]=0F 25 CA DD
L[16]=0F 25 CA DD R[16]=C5 4A FF E2
最后一次置换前的数据D-1=C5 4A FF E2 0F 25 CA DD，置换后生成最终数据为
DE=E6 9D E6 9E 06 25 5F 4F。
本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/4864/showart_391168.html |
免费注册
发表于 2007-09-27 14:06