In my description of LUCIFER, I numbered bits from 0 to 127 or from 0 to 63; here, bits will be numbered from 1 to 64 or from 1 to 32. In both cases, the lowest-numbered bit is the MSB of the first character, and the highest-numbered bit is the LSB of the last character; that is, big-endian (68000-like and not 8086-like) conventions are observed throughout.
First, for no particularly good reason (except, just possibly, to group together the most and least significant bits of uncompressed text characters) the bits of the block are transposed according to the following 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
As in the section on LUCIFER, all bit permutations are to be interpreted as follows: if the permutation begins 58 50 42..., that means that the first bit of the output came from bit 58 of the input, the second bit of the output came from bit 50 of the input, and so on.
For 16 rounds, the left half, or the first 32 bits, is modified by being XORed with a 32 bit result calculated from the right half of the block in its current state and the subkey for that round. After each of the first 15 rounds, the halves are then swapped.
This calculation, known as the f-function, proceeds as follows:
The 32-bit right half of the block is expanded to 48 bits by means of this, the 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 eight groups of four bits in the right half are each made the middle four bits of a group of six bits in the result, and they are joined, on each side, by the bits that were adjacent to them originally. Those two outer bits are, in a way, supplementary to the four bits in the middle, since the S-box tables contain four encodings of the middle bits, in which every different value has a different result, selected by the two outer bits.
(One could even implement DES with a permutation starting
32 5 1 2 3 4 4 9 5 6 7 8
to allow the S-boxes to be laid out more simply, provided that one generated and stored the subkeys with the same change in the order of their bits.)
After the right half of the block has been expanded to 48 bits, it is XORed with the current round's 48-bit subkey. The result is then used as the input to eight lookup tables, with a six bit input and a four bit output.
Bit |Bits 2, 3, 4, and 5 form: 1 6 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |----------------------------------------------- 0 0 |14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 1 | 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 1 0 | 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 1 1 |15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 Bit |Bits 8, 9, 10, and 11 form: 7 12 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |----------------------------------------------- 0 0 |15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 0 1 | 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 1 0 | 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 1 1 |13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 Bit |Bits 14, 15, 16, and 17 form: 13 18 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |----------------------------------------------- 0 0 |10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 0 1 |13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 1 0 |13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 1 1 | 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12 Bit |Bits 20, 21, 22, and 23 form: 19 24 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |----------------------------------------------- 0 0 | 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15 0 1 |13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 1 0 |10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 1 1 | 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14 Bit |Bits 26, 27, 28, and 29 form: 25 30 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |----------------------------------------------- 0 0 | 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 0 1 |14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 1 0 | 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14 1 1 |11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3 Bit |Bits 32, 33, 34, and 35 form: 31 36 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |----------------------------------------------- 0 0 |12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11 0 1 |10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 1 0 | 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 1 1 | 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13 Bit |Bits 38, 39, 40, and 41 form: 37 42 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |----------------------------------------------- 0 0 | 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 0 1 |13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 1 0 | 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 1 1 | 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12 Bit |Bits 44, 45, 46, and 47 form: 43 48 | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |----------------------------------------------- 0 0 |13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 0 1 | 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 1 0 | 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 1 1 | 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11
Then, the 32 bit result formed by the output of the eight S-boxes above in turn is subjected to the following 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
One round of DES, with the f-function shown in detail, is illustrated by the following diagram, accompanied by another diagram giving an overview of the whole block cipher:
Round:
Overview:
Since bit transposition is slow in software, software implementations of DES will normally use, for the S-boxes, a table with 32-bit entries showing each four-bit output as it looks after going through permutation P.
After the sixteen rounds of DES are complete, the left and right halves of the block together, not swapped in the last round, are then subjected to the inverse of the initial permutation, which takes the bits from 1 to 64 of the block, and puts them in the final result in this order:
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
The 56-bit key used by DES is, when in standard format, stored in eight bytes, in which the least significant bit of each byte is used for parity! Thus, the permutation, called Permuted Choice 1, which divides the 56-bit key into two 28-bit halves, acts on bits 1 through 7, 9 through 15, 17 through 23, and so on.
Permuted choice 1 is the following:
First half:
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
Second half:
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
Like the initial permutation and inverse initial permutation, permuted choice 1 is irrelevant to the strength of DES, except insofar as it makes things awkward for general-purpose computers. On the other hand, the permutation P is vitally necessary to the cryptographic strength of DES.
The two 28-bit quantities are then subjected to successive circular left shifts of different sizes before the subkey for each round is determined from them. These circular left shifts, one of which is applied before the first subkey is taken, are in order of the following sizes:
1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1
Note also that to decrypt, the only alteration in the DES algorithm is that the subkeys are used in reverse order.
The 48-bit subkey for each round is extracted from the two 28-bit quantities, the first consisting of bits 1 to 28, and the second of bits 29 to 56, by the following permutation, Permuted Choice 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
Note that, since only 48 bits are produced, some numbers from 1 through 56 are absent. This permutation is important to the strength of DES. (Also, if the implementation is modified to simplify the arrangement of the S-boxes, as noted in the preceding parenthetical note, then this permutation is the one that must be changed correspondingly, to 14 5 17 11 24 1, 3 10 28 15 6 21, and so on. Also, likely the subkeys would be stored in 8-byte spaces, with each byte containing only six bits of the subkey.)
Next
Chapter Start
Skip to Next Section
Table of Contents
Main Page
Home Page