DES算法 (转)[@more@]

**DES算法**

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 <Mailto:mfischer@heinous.isca.uiowa.edu">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.)

1.2 Calculate the key schedule.

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.)

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].

1.2.3 Calculate the 16 subkeys. Start with 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.

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.

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.

2 Process a 64-bit data block.

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.

2.2 Perform the following permutation on the data block.

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].

2.4 Apply the 16 subkeys to the data block. Start with i = 1.

2.4.1 Expand the 32-bit R[i-1] into 48 bits according to the

bit-selection function below.

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].

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].

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.

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.

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.

2.4.4.3 Replace B[j] with S[j][m][n].

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.

2.4.5 Permute the concatenation of B[1] through B[8] as indicated below.

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]).)

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

2.4.8 Loop back to 2.4.1 until K[16] has been applied.

2.5 Perform the following permutation on the block R[16]L[16].

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].

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).

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.

The DES algorithm can also be used to calculate checksums up to 64 bits

long (see FIPS PUB 113). If the number of data bits to be checksummed is

not a multiple of 64, the last data block should be padded with zeros. If

the data is ASCII data, the first bit of each byte should be set to 0.

The data is then encrypted in CBC mode with IV = 0. The leftmost n bits

(where 16 <= n <= 64, and n is a multiple of 8) of the final ciphertext

block are an n-bit checksum

中华技术网整理发布 http://www.asfocus.com .NETqu.com">http://www.netqu.com

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 <Mailto:mfischer@heinous.isca.uiowa.edu">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.)

1.2 Calculate the key schedule.

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.)

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].

1.2.3 Calculate the 16 subkeys. Start with 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.

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.

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.

2 Process a 64-bit data block.

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.

2.2 Perform the following permutation on the data block.

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].

2.4 Apply the 16 subkeys to the data block. Start with i = 1.

2.4.1 Expand the 32-bit R[i-1] into 48 bits according to the

bit-selection function below.

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].

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].

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.

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.

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.

2.4.4.3 Replace B[j] with S[j][m][n].

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.

2.4.5 Permute the concatenation of B[1] through B[8] as indicated below.

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]).)

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

2.4.8 Loop back to 2.4.1 until K[16] has been applied.

2.5 Perform the following permutation on the block R[16]L[16].

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].

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).

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.

The DES algorithm can also be used to calculate checksums up to 64 bits

long (see FIPS PUB 113). If the number of data bits to be checksummed is

not a multiple of 64, the last data block should be padded with zeros. If

the data is ASCII data, the first bit of each byte should be set to 0.

The data is then encrypted in CBC mode with IV = 0. The leftmost n bits

(where 16 <= n <= 64, and n is a multiple of 8) of the final ciphertext

block are an n-bit checksum

中华技术网整理发布 http://www.asfocus.com .NETqu.com">http://www.netqu.com

来自 “ ITPUB博客 ” ，链接：http://blog.itpub.net/10752043/viewspace-988635/，如需转载，请注明出处，否则将追究法律责任。

上一篇：
怎样让超星图书浏览器不会过期 (转)

下一篇：
DES算法,头文件 (转)

请登录后发表评论
登录

全部评论

- 可怕的 C# (转)
- Unify the Role-Based Security Models for Enterprise and Application Domains with .NET (转)
- Building Secure ASP.NET Applications: Authentication, Authorization, and Secure Communication (转)
- [Sample] Playing with music file (转)
- 中文web-app_2_3.dtd (转)
- 使用ASP.NET加密口令 (转)
- C++ Builder 高手进阶 （五）用BCB编写多线程应用程序 (转)
- 24点游戏探秘系列6：用概率统计的眼光看24点游戏 (转)
- Schema-oriented message destination (转)
- J2EE vs. Microsoft.NET (转)