Cryptography Reference
In-Depth Information
3.3.3 Key Schedule
The
key schedule
derives 16 round keys
k
i
, each consisting of 48 bits, from the
original 56-bit key. Another term for round key is subkey. First, note that the DES
input key is often stated as 64-bit, where every eighth bit is used as an odd parity
bit over the preceding seven bits. It is not quite clear why DES was specified that
way. In any case, the eight parity bits are
not
actual key bits and do not increase the
security. DES is a 56-bit cipher, not a 64-bit one.
As shown in Fig. 3.13, the 64-bit key is first reduced to 56 bits by ignoring every
eighth bit, i.e., the parity bits are stripped in the initial
PC
1 permutation. Again,
the parity bits certainly do not increase the key space! The name
PC
−
1 stands for
“permuted choice one”. The exact bit connections that are realized by
PC
−
−
1are
given in Table 3.11.
LSB
MSB
64
7
1
7
1
P
. . .
P
P = parity bit
Fig. 3.13
Location of the eight parity bits for a 64-bit input key
Table 3.11
Initial key permutation
PC
−
1
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
312315 7 62544638
302214 6 61534537
29 21 13
PC
−
5
28 20 12
4
The resulting 56-bit key is split into two halves
C
0
and
D
0
, and the actual key
schedule starts as shown in Fig. 3.14. The two 28-bit halves are cyclically shifted,
i.e., rotated, left by one or two bit positions depending on the round
i
according to
the following rules:
In rounds
i
= 1
,
2
,
9
,
16, the two halves are rotated left by one bit.
In the other rounds where
i
= 1
,
2
,
9
,
16, the two halves are rotated left by two
bits.
Note that the rotations only take place within either the left or the right half. The
total number of rotation positions is 4
2 = 28. This leads to the interesting
property that
C
0
=
C
16
and
D
0
=
D
16
. This is very useful for the decryption key
·
1 + 12
·
