如何實(shí)現(xiàn) DES 算法（全）

發(fā)布時(shí)間：2008-07-09 閱讀數(shù)：次來源：網(wǎng)樂原科技

這是摘自清華BBS的一篇文章，洋文的，小弟把它翻成中文請(qǐng)各位高手指點(diǎn)。
分號(hào)（；）后的話是小弟的翻譯，井號(hào)（#）后的是小弟的一點(diǎn)感想。

How to implement the
Data Encryption Standard (DES)

A step by step tutorial
Version 1.2

The Data Encryption Standard (DES) algorithm, adopted by the U.S.
government in 1977, is a block cipher that transforms 64-bit data blocks
under a 56-bit secret key, by means of permutation and substitution. It
is officially described in FIPS PUB 46. The DES algorithm is used for
many applications within the government and in the private sector.

This is a tutorial designed to be clear and compact, and to provide a
newcomer to the DES with all the necessary information to implement it
himself, without having to track down printed works or wade through C
source code. I welcome any comments.
Matthew Fischer <mfischer@heinous.isca.uiowa.edu>

；上面是介紹，我就不翻了。 ;)

Here's how to do it, step by step:

1 Process the key.
；生成密鑰

1.1 Get a 64-bit key from the user. (Every 8th bit is considered a
parity bit. For a key to have correct parity, each byte should contain
an odd number of "1" bits.)
；從用戶處得到一個(gè)64位的密鑰。（每8位一組，每組的第8位是校驗(yàn)位。如果校驗(yàn)
正確，每個(gè)字節(jié)應(yīng)該有一個(gè)為1的

1.2 Calculate the key schedule.
；計(jì)算密鑰表

1.2.1 Perform the following permutation on the 64-bit key. (The parity
bits are discarded, reducing the key to 56 bits. Bit 1 of the permuted
block is bit 57 of the original key, bit 2 is bit 49, and so on with bit
56 being bit 4 of the original key.)
；對(duì)64位的密鑰進(jìn)行如下的置換。（去掉校驗(yàn)位，密鑰的實(shí)際長(zhǎng)度是56位。置換后的
；第一位是原密鑰的第57位，第二位是原第49位，第五十六位就是原來密鑰的第4位。）
# 古怪的置換，哪位大哥能寫出算式？
# 好象是分成兩部
# for(j=57;j<64;j++)
# {
# for(i=j;i<0;i-=8)
# {
# if(k=28)
# break;
# c[k]=i;
# k++;
# }
# 這是前28位，不知道對(duì)不對(duì)？請(qǐng)指正。

Permuted Choice 1 (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

1.2.2 Split the permuted key into two halves. The first 28 bits are
called C[0] and the last 28 bits are called D[0].
；把置換后的密鑰分為C[0] 和D[0]兩部分，各28位。

1.2.3 Calculate the 16 subkeys. Start with i = 1.
；計(jì)算16個(gè)子密鑰，從i=1開始。

1.2.3.1 Perform one or two circular left shifts on both C[i-1] and
D[i-1] to get C[i] and D[i], respectively. The number of shifts per
iteration are given in the table below.
；分別對(duì)C[i-1]和D[i-1]進(jìn)行左移一到兩位的位移操作，得到C[i]和D[i]。每次
；位移數(shù)目如下：
# 共16次

Iteration # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Left Shifts 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1

1.2.3.2 Permute the concatenation C[i]D[i] as indicated below. This
will yield K[i], which is 48 bits long.
；如下表，改變C[i]和D[i]的排列，得到48位長(zhǎng)的k[i]。
# 不懂 :(
# 是不是丟掉了某些位？

Permuted Choice 2 (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

1.2.3.3 Loop back to 1.2.3.1 until K[16] has been calculated.
；重復(fù) 1.2.3.1 開始的過程，算出16個(gè)字密鑰。

2 Process a 64-bit data block.
；處理一個(gè)64位的數(shù)據(jù)塊。

2.1 Get a 64-bit data block. If the block is shorter than 64 bits, it
should be padded as appropriate for the application.
；獲取一個(gè)64位的數(shù)據(jù)塊。如果數(shù)據(jù)塊不到64位，就補(bǔ)足64位。
# 可能是用0補(bǔ)吧。

2.2 Perform the following permutation on the data block.
；對(duì)數(shù)據(jù)塊進(jìn)行如下置換。
# 又是分成兩部分進(jìn)行，先是偶數(shù)位。
# 比較簡(jiǎn)單，算式就不寫了。

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

2.3 Split the block into two halves. The first 32 bits are called L[0],
and the last 32 bits are called R[0].
；將數(shù)據(jù)塊平分為L(zhǎng)[0]和R[0]兩部分。

2.4 Apply the 16 subkeys to the data block. Start with i = 1.
；從i=1開始，用16個(gè)子密鑰對(duì)數(shù)據(jù)塊進(jìn)行加密。

2.4.1 Expand the 32-bit R[i-1] into 48 bits according to the
bit-selection function below.
；將數(shù)據(jù)塊的后32位R[i-1]以下面規(guī)則進(jìn)行擴(kuò)展。
# 不會(huì)寫算式。:(
Expansion (E)

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

2.4.2 Exclusive-or E(R[i-1]) with K[i].
；用K[i]對(duì)E(R[i-1])進(jìn)行異或操作。

2.4.3 Break E(R[i-1]) xor K[i] into eight 6-bit blocks. Bits 1-6 are
B[1], bits 7-12 are B[2], and so on with bits 43-48 being B[8].
；將上一步的操作結(jié)果分成8塊，每塊6位，命名為B[1]到B[8]。

2.4.4 Substitute the values found in the S-boxes for all B[j]. Start
with j = 1. All values in the S-boxes should be considered 4 bits wide.
；把所有的B[j]在S框中進(jìn)行置換，S框中所有的值的寬（長(zhǎng)）度應(yīng)是4位。
# 不懂?。?！ :(

2.4.4.1 Take the 1st and 6th bits of B[j] together as a 2-bit value
(call it m) indicating the row in S[j] to look in for the substitution.
；把B[j]中的第一位和第六位命名為m，表示S[j]在置換時(shí)的行。

2.4.4.2 Take the 2nd through 5th bits of B[j] together as a 4-bit
value (call it n) indicating the column in S[j] to find the substitution.
；把B[j]二到五位命名為n，表示S[j]在置換時(shí)的列。

2.4.4.3 Replace B[j] with S[j][m][n].
；用S[j][m][n]置換B[j]。

Substitution Box 1 (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 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

S[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

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

2.4.4.4 Loop back to 2.4.4.1 until all 8 blocks have been replaced.
；重復(fù)2.4.4.1開始的步驟，直至8個(gè)數(shù)據(jù)塊都被置換。

2.4.5 Permute the concatenation of B[1] through B[8] as indicated below.
；以下面的方法改變B[1]到B[8]的順序。

Permutation 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

2.4.6 Exclusive-or the resulting value with L[i-1]. Thus, all together,
your R[i] = L[i-1] xor P(S[1](B[1])...S[8](B[8])), where B[j] is a 6-bit
block of E(R[i-1]) xor K[i]. (The function for R[i] is written as, R[i] =
L[i-1] xor f(R[i-1], K[i]).)
；用L[i-1]對(duì)上一步的結(jié)果進(jìn)行異或操作。如此就有以下結(jié)果：R[i] = L[i-1] xor ；

P(S[1](B[1])...S[8](B[8]))。這里，B[j]是六位的數(shù)據(jù)塊，它是E(R[i-1]) xor
；K[i]的結(jié)果。（R[i]的函數(shù)可以寫成R[i] = L[i-1] xor f(R[i-1], K[i])。）

2.4.7 L[i] = R[i-1].
；L[i] = R[i-1].

2.4.8 Loop back to 2.4.1 until K[16] has been applied.
；重復(fù)2.4.1開始的步驟，直至所有的子密鑰都被使用過。
# 就是再重復(fù)15次，每次使用不同的子密鑰。

2.5 Perform the following permutation on the block R[16]L[16].
；對(duì)R[16]L[16]進(jìn)行如下的置換。

Final Permutation (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

This has been a description of how to use the DES algorithm to encrypt
one 64-bit block. To decrypt, use the same process, but just use the keys
K[i] in reverse order. That is, instead of applying K[1] for the first
iteration, apply K[16], and then K[15] for the second, on down to K[1].
；以上就是怎樣用DES算法對(duì)一個(gè)64位的數(shù)據(jù)塊進(jìn)行加密的過程。至于解密，只需要
；在以上過程中把子密鑰的順序倒過來用就可以了。也就是說，在加密時(shí)用子密鑰
；K[1]，在解密過程中就用K[16]；在加密時(shí)用子密鑰K[2]，在解密過程中就用K[12]。

Summaries:
；摘要
# 以下是生成子密鑰，加密和解密的公式化敘述。

Key schedule:
C[0]D[0] = PC1(key)
for 1 <= i <= 16
C[i] = LS[i](C[i-1])
D[i] = LS[i](D[i-1])
K[i] = PC2(C[i]D[i])

Encipherment:
L[0]R[0] = IP(plain block)
for 1 <= i <= 16
L[i] = R[i-1]
R[i] = L[i-1] xor f(R[i-1], K[i])
cipher block = FP(R[16]L[16])

Decipherment:
R[16]L[16] = IP(cipher block)
for 1 <= i <= 16
R[i-1] = L[i]
L[i-1] = R[i] xor f(L[i], K[i])
plain block = FP(L[0]R[0])

To encrypt or decrypt more than 64 bits there are four official modes
(defined in FIPS PUB 81). One is to go through the above-described
process for each block in succession. This is called Electronic Codebook
(ECB) mode. A stronger method is to exclusive-or each plaintext block
with the preceding ciphertext block prior to encryption. (The first
block is exclusive-or'ed with a secret 64-bit initialization vector
(IV).) This is called Cipher Block Chaining (CBC) mode. The other two
modes are Output Feedback (OFB) and Cipher Feedback (CFB).
；對(duì)超過64位的加密和解密，(美國(guó))聯(lián)邦信息處理標(biāo)準(zhǔn) PUB 81 中定有四種方法。
；一種是連續(xù)的對(duì)每個(gè)數(shù)據(jù)塊進(jìn)行上述操作。這種方法被稱 ECB mode。另一種更
；高強(qiáng)度的方法是在加密前，用前述的密文塊對(duì)明文塊進(jìn)行異或操作。
# 括號(hào)里那句話不懂 :(
；這種方法被稱為 CBC mode。還有兩種方法是 OFB mode 和 CFB mode。

When it comes to padding the data block, there are several options. One
is to simply append zeros. Two suggested by FIPS PUB 81 are, if the data
is binary data, fill up the block with bits that are the opposite of the
last bit of data, or, if the data is ASCII data, fill up the block with
random bytes and put the ASCII character for the number of pad bytes in
the last byte of the block. Another technique is to pad the block with
random bytes and in the last 3 bits store the original number of data bytes.
；在填充數(shù)據(jù)塊時(shí)（還記不記得，當(dāng)數(shù)據(jù)塊不足64位時(shí)要進(jìn)行填充），有以下幾種
；選擇：一種就是填0。第二種是被(美國(guó))聯(lián)邦信息處理標(biāo)準(zhǔn) PUB 81所建議的，如
；果數(shù)據(jù)是二進(jìn)制的，就填入和數(shù)據(jù)位最后一位相反的數(shù)；如果數(shù)據(jù)塊是ASCII碼，
；就填入隨機(jī)字節(jié)，并且將填充數(shù)目寫入最后一個(gè)字節(jié)。另一種技術(shù)就是填入隨機(jī)
；字節(jié)，并且將最后原數(shù)據(jù)字節(jié)數(shù)寫入最后的三位。（注意：是位，bit）