Data Encryption Standard (DES)
The Data Encryption Standard (DES), known as the Data Encryption Algorithm
(DEA) by ANSI and the DEA-1 by the ISO, has been most widely used
block cipher in world, especially in financial industry. It encrypts 64-bit
data, and uses 56-bit key with 16 48-bit sub-keys.
6.1 DES (Data Encryption Standard) history
In the early 1970s, there are no cryptagraphic equipment available on
the market. Although several small companies made and sold cryptographic
equipment. The equipment was all different and couldn't interoperate.
No one really knew if any of it was secure; there was no independent body
to certify the security.
In 1972, the National Bureau of Standards (NBS), now the National Institute
of Standards and Technology (NIST), initiated a program to protect computer
and communications data. As part of that program, they wanted to develop
a single, standard cryptographic algorithm. A single algorithm could be
tested and certified, and different cryptographic equipment using it could
interoperate. It would also be cheaper to implement and readily available.
In the May, 1973 and again in August, 1974, the NBS issued a public request
for proposals for a standard cryptographic algorithm. They specified a
series of design criteria:
The algorithm must be:
- security
- completely specified
- easy to understand
- public
- available to all users
- efficient to use
- able to be validated
- exportable
Public response indicated
that there was considerable interest in a cryptographic standard, but
little public expertise in the field. Most of the submissions are reworked
classical or machine cipher; none of the submissions came close to meeting
the requirements.
However, IBM submitted an algorithm based on one developed by IBM during
the early 1970s, called Lucifer. The algorithm, although complicated,
was straightforward. It used only simple logical operations on small
groups of bits and could be implemented fairly efficiently in hardware.
The proposed standard was adopted as a federal standard in November,
1976 and authorized for use on all unclassified government communications.
ANSI approved DES as a private-sector standard in 1980.
6.2 Description of DES
DES is a block cipher; it encrypts data in 64-bit blocks. A 64-bit block
of plaintext
goes in one end of the algorithm and a 64-bit block of ciphertext comes
out
the other end. DES is a symmetric algorithm: The same algorithm and
key are used for both encryption and decryption (except for minor differences
in the key
schedule).
The key length is 56 bits. (The key is usually expressed as a 64-bit
number, but
every eighth bit is used for parity checking and is ignored. These parity
bits are
the least- significant bits of the key bytes.) The key can be any 56-bit
number and can be changed at any time. All security rests within the
key.
At its simplest level, the algorithm is nothing more than a combination
of the two
basic techniques of encryption: confusion and diffusion. The fundamental
building block of DES is a single combination of these techniques (a
substitution followed by a permutation) on the text, based on the key.
This is known as a round. DES has 16 rounds; it applies the same combination
of techniques on the plaintext block 16 times (see Figure 6.1).
Figure
6.1 DES
Outline of the Algorithm
The basic process in enciphering a 64-bit data block using the DES
consists of:
- an initial permutation
(IP)
- 16 rounds of a complex
key dependent calculation f
- final permutation,
being the inverse of IP
In each round (see
Figure 6.2), the key bits are shifted, and then 48 bits are selected
from the 56 bits of the key. The right half of the data is expanded
to 48 bits via an expansion permutation, combined with 48 bits of a
shifted and permuted key via an XOR, sent through 8 S-boxes producing
32 new bits, and permuted again. These four operations make up Function
f. The output of Function f is then combined with the left half via
another XOR. The result of these operations becomes the new right half;
the old right half becomes the new left half.
If Bi is the result of the ith iteration, Li and Ri are the left and
right halves of Bi, Ki is the 48-bit key for round i, and f is the function
that does all the substituting and permuting and XORing with the key,
then a round looks like:
Li = R j-1
Ri = L i-1 Xor f (Ri-1,
Ki)
Figure 6.2 One
round of DES
The Initial Permutation
The initial permutation occurs
before round 1; it transposes the input block as described in Table
6.1. This table, like all the other tables in this lecture, should be
read left to right, top to bottom. For example, the initial permutation
moves bit 58 of the plaintext to bit position 1, bit 50 to bit position
2, bit 42 to bit position 3, and so forth.
The initial permutation and the corresponding final permutation do not
improve DES's security, just
make DES more complex.
Example:
IP(675a6967 5e5a6b5a) = (ffb2194d 004df6fb)
Note that all numbers are written in hexadecimal as a "short-form" version
of the binary actually used, since 1 Hex digit = 4 Binary bits. The
digit mapping is:
0=0000 1=0001 2=0010 3=0011 4=0100 5=0101 6=0110 7=0111
8=1000 9=1001 a=1010 b=1011 c=1100 d=1101 e=1110 f=1111
The Key Transformation
Initially, the 64-bit DES
key is reduced to a 56-bit key by ignoring every eighth bit. Let us
call this
operation PC1. This is described in Table 6.2.
PC2 is the operation which reduces the 56-bits key to a 48-bits subkey
for each of the 16 rounds of DES. These subkeys, Ki, are determined in the
following manner.
PC1 splits the key bits into 2 halves
(C and D), each 28-bits. The halves C and D are circularly shifted
left by either one or two bits, depending on the round. This shift is
given in Table 6.3.
After being shifted,
48 out of the 56 bits are selected. This is done by an operation called
compression permutation, it permutes the order of the bits
as well as selects a subsets of
bits. Table 6.4 defines the compression permutation.
Example:
keyinit(5b5a5767, 6a56676e)
PC1(Key) C=00ffd820, D=ffec9370
KeyRnd01 C1=01ffb040, D1=ffd926f0,
PC2(C,D)=(38 09 1b 26 2f 3a 27 0f)
KeyRnd02 C2=03ff6080, D2=ffb24df0,
PC2(C,D)=(28 09 19 32 1d 32 1f 2f)
KeyRnd03 C3=0ffd8200, D3=fec937f0,
PC2(C,D)=(39 05 29 32 3f 2b 27 0b)
KeyRnd04 C4=3ff60800, D4=fb24dff0,
PC2(C,D)=(29 2f 0d 10 19 2f 1d 3f)
KeyRnd05 C5=ffd82000, D5=ec937ff0,
PC2(C,D)=(03 25 1d 13 1f 3b 37 2a)
KeyRnd06 C6=ff608030, D6=b24dfff0,
PC2(C,D)=(1b 35 05 19 3b 0d 35 3b)
KeyRnd07 C7=fd8200f0, D7=c937ffe0,
PC2(C,D)=(03 3c 07 09 13 3f 39 3e)
KeyRnd08 C8=f60803f0, D8=24dfffb0,
PC2(C,D)=(06 34 26 1b 3f 1d 37 38)
KeyRnd09 C9=ec1007f0, D9=49bfff60, PC2(C,D)=(07
34 2a 09 37 3f 38 3c)
KeyRnd10 C10=b0401ff0, D10=26fffd90, PC2(C,D)=(06
33 26 0c 3e 15 3f 38)
KeyRnd11 C11=c1007fe0, D11=9bfff640, PC2(C,D)=(06
02 33 0d 26 1f 28 3f)
KeyRnd12 C12=0401ffb0, D12=6fffd920, PC2(C,D)=(14
16 30 2c 3d 37 3a 34)
KeyRnd13 C13=1007fec0, D13=bfff6490, PC2(C,D)=(30
0a 36 24 2e 12 2f 3f)
KeyRnd14 C14=401ffb00, D14=fffd9260, PC2(C,D)=(34
0a 38 27 2d 3f 2a 17)
KeyRnd15 C15=007fec10, D15=fff649b0, PC2(C,D)=(38
1b 18 22 1d 32 1f 37)
KeyRnd16 C16=00ffd820, D16=ffec9370, PC2(C,D)=(38
0b 08 2e 3d 2f 0e 17)
Table 6.1
Initial Permutation
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.
Table 6.2
Key Permutation
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.
Table 6.3
Number of Key Bits Shifted per Round
Round 1 2 3 4 5 6 7
8 9 10 11 12 13 14 15
16
Number 1 1 2 2 2 2 2 2
1 2 2 2
2 2 2 1
Table 6.4
Compression Permutation
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.
The Expansion Permutation
This operation expands the
right half of the data, Ri, from 32 bits to 48 bits. Because
this operation changes the order of the bits as well as repeating certain
bits, it is known as an expansion permutation. This operation has two
purposes: It makes the right half the same size as the key for the XOR
operation and it provides a longer result that can be compressed during
the substitution operation. However, neither of those is its main cryptographic
purpose.
For each 4-bit input block, the first and fourth bits each represent
two bits of the output block, while the second and third bits each represent
one bit of the output block. Table 6.5 shows which output positions
correspond to which input positions. For example, the bit in position
3 of the input block moves to position 4 of the lutput block, and the
bit in position 21 of the input block moves to positions 30 and 32 of
the output block.
Table 6.5
Expansion Permutation
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
The S-Box Substitution
After the compressed key is XORed with the expanded block, the 48-bit
result moves to a substitution operation. The substitutions are performed
by eight substitution boxes, or S-boxes.
Each S-box has a 6-bit input and a 4-bit output, and there are eight
different S-boxes. The 48 bits are divided into eight 6-bit sub-blocks.
Each separate block is operated on by a separate S-box: The first block
is operated on by S-box 1, the second block is operated on by S-box
2, and so on.
Each S-box is a table of 4 rows and 16 columns. Each entry in the box
is a 4-bit number. The 6 input bits of the S-box specify under which
row and column number to look for the output. Table 6.6 shows all eight
S-boxes.
The input bits specify an entry in the S-box in a very particular manner.
Consider an S-box input of 6 bits, labeled bi, b2, b3, b, b, and b6.
Bits b, and b6are combined to form a 2-bit number, from 0 to 3, which
corresponds to a row in the table. The middle 4 bits, b2 through b5,
are combined to form a 4-bit number, from 0 to 15, which corresponds
to a column in the table.
For example, assume that the input to the sixth S-box (i.e., bits 31
through 36 of the XOR function) is 110011. The first and last bits combine
to form 11, which corrspends to row 3 of the sixth S-box. The middle
4 bits combine to form 1001, which corresponds to the column 9 of the
same S-box. The entry under row 3, column 9 of S-box 6 is 14. (Remember
to count rows and columns from 0 and not from 1.) The value 1110 is
substituted for 110011.
The S-box substitution is the critical step in DES. The algorithm's
other operanons are linear and easy to analyze. The S-boxes are nonlinear
and, more than any.hing else, give DES its security.
The result of this substitution phase is eight 4-bit blocks which are
recombined into a single 32-bit block. This block moves to the next
step: the P-box permutation.
Table 6.6
S-Boxes
S-box 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-box 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-box 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-box 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-box 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,
41, 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-box 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-box 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-box 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
Example:
S(18 09 12 3d 11 17 38 39) = 5fd25e03
The P-Box Permutation
The 32-bit output of the S-box substitution is permuted according to
a P-box. This permutation maps each input bit to an output position;
no bits are used twice and no bits are ignored. Table 12.7 shows
the position to which each bit moves. For example, bit 21 moves to bit
4. while bit 4 moves to bit 3 1.
Table 6.7
P-Box Permutation
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
Finally, the result of the P-box permutation is XORed with the left
half of the initial 64-bit block. Then the left and right halves are
switched and another round begins.
The Final Permutation
The final permutation is the inverse of the initial permutation and
is described in Table 6.8. Note that the left and right halves are not
exchanged after the last round of DES; instead the concatenated block
R16L16 is used as the input to the final permutation.
There's nothing going on here; exchanging the halves and shifting around
the permutation would yield exactly the same result. This is so that
the algorithm can be used to both encrypt and decrypt.
Table 6.8
Final Permutation
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.
Decrypting DES
After all the substitutions, permutations, XORs, and shifting around,
you might think that the decryption algorithm is completely different
and just as confusing as the encryption algorithm. On the contrary,
the various operations were chosen to produce a very useful property:
The same algorithm works for both encryption and decryption.
With DES it is possible to use the same function to encrypt or decrypt
a block. The only difference is that the keys must be used in the reverse
order. That is, if the encryption keys for each round are K1, K2, K3,
. . . , K16, then the decryption keys are K16, K15, K14, . . . , K1,.
The algorithm that generates the key used for each round is circular
as well. The key shift is a right shift and the number of positions
shifted is 0, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1.
|
