 DES algorithm

DES is a Feistel cipher which processes plaintext blocks of n = 64 bits, producing 64-bit ciphertext blocks (Figure 7.8). The effective size of the secret key К is к = 56 bits; more precisely, the input key К is specified as a 64-bit key, 8 bits of which (bits 8,16,... , 64) may be used as parity bits. The 2°6 keys implement (at most) 2°6 of the 204! possible bijec- tions on 64-bit blocks. A widely held belief is that the parity bits were introduced to reduce the effective key size from 64 to 56 bits, to intentionally reduce the cost of exhaustive key search by a factor of 256. Figure 7.8: DES input-output.

Full details of DES are given in Algorithm 7.82 and Figures 7.9 and 7.10. An overview follows. Encryption proceeds in 16 stages or rounds. From the input key K, sixteen 48-bit subkeys Ki are generated, one for each round. Within each round, 8 fixed, carefully selected 6-to-4 bit substitution mappings {S-boxes) Si, collectively denoted S, are used. The 64-bit plaintext is divided into 32-bit halves L0 and R0. Each round is functionally equivalent, taking 32-bit inputs L, t and R,-i from the previous round and producing 32-bit outputs Li and R, for 1 < г < 16, as follows: Here E is a fixed expansion permutation mapping R,-i from 32 to 48 bits (all bits are used once; some are used twice). P is another fixed permutation on 32 bits. An initial bit permutation (DP) precedes the first round; following the last round, the left and right halves are exchanged and, finally, the resulting string is bit-permuted by the inverse of IP. Decryption involves the same key and algorithm, but with subkeys applied to the internal rounds in the reverse order (Note 7.84).

A simplified view is that the right half of each round (after expanding the 32-bit input to 8 characters of 6 bits each) carries out a key-dependent substitution on each of 8 characters, then uses a fixed bit transposition to redistribute the bits of the resulting characters to produce 32 output bits.

Algorithm 7.83 specifies how to compute the DES round keys Ki, each of which contains 48 bits of К. These operations make use of tables PCI and PC2 of Table 7.4, which are called permuted choice 1 and permuted choice 2. To begin, 8 bits (fcg, кщ,... , kG4) of К are discarded (by PCI). The remaining 56 bits are permuted and assigned to two 28-bit variables C and D and then for 16 iterations, both C and D are rotated either 1 or 2 bits, and 48 bits (Ki) are selected from the concatenated result.

7.82 Algorithm Data Encryption Standard (DES)

INPUT: plaintext mi... m6 4; 64-bit key К = k... кщ (includes 8 parity bits).

OUTPUT: 64-bit ciphertext block C = c... C04. (For decryption, see Note 7.84.)

• 1. (key schedule) Compute sixteen 48-bit round keys AT, from A' using Algorithm 7.83.
• 2. (L0. R0) IP(mim2 ... m64). (Use IP from Table 7.2 to permute bits; split the

result into left and right 32-bit halves Lq = morris0 ... mg, Ro = ... m-;.)

• 3. (16 rounds) for i from 1 to 16, compute L, and R, using Equations (7.4) and (7.5) above,computing f(Ri-1, A',) = P(S(E(Rj^i) ® A',)) as follows:
• (a) Expand 1 = гхг2 ... Г32 from 32 to 48 bits using E per Table 7.3:

T <- E(Ri-i). (Thus Г = Г32ПГ2 .. .r32ri.)

• (b) T' <- TkBK,. Represent T' as eight 6-bit character strings: (Bi,... , B\$) = V.
• (c) T" <- (S1(B1),S2(B2),...S8(B8)). (Here \$(В4) maps Bt = M2...b6 to the 4-bit entry in row r and column c of 5, in Table 7.8, page 260 where r = 2 • 61 + b6, and 626364As is the radix-2 representation of 0 < c < 15. Thus 5i (011011) yields r = 1, c = 13, and output 5, i.e., binary 0101.)
• (d) T"' <- P(T"). (Use P per Table 7.3 to pennute the 32 bits of T" = t 2 .. .f32, yieldmgfi6<7..-<25)
• 4. b2 ... Ьв4 <- (Ri6- Ею). (Exchange final blocks Li6, Rie-)
• 5. C «- IP-1 (bib2 ■ ■ ■ bfn). (Transpose using IP-1 from Table 7.2; C = bi0b& ... b25.)
 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
 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

Table 7.2: DES initial permutation and inverse (IP and IP x).

 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

Table 7.3: DES per-round functions: expansion E and permutation P.

 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 Figure 7.9: DES computation path. Figure 7.10: DES inner function f.

7.83 Algorithm DES key schedule

INPUT: 64-bit key К = ki... k6i (including 8 odd-parity bits).

OUTPUT: sixteen 48-bit keys К,, 1 < i < 16.

• 1. Define ь, 1 < i < 16 as follows: Vi = 1 for i € {1,2,9.16}; v, = 2 otherwise. (These are left-shift values for 28-bit circular rotations below.)
• 2. T <- PCI (A'); represent T as 28-bit halves (Co, D0). (Use PCI in Table 7.4 to select

bits from A: Co = ... кзв, Do = квзкы ... Aj.)

3. For i from 1 to 16, compute AT, as follows: C-, <- (C<_i vf), D, <- (С,_1 Vi), Ki <- PC2(Ci,Di). (Use PC2 in Table 7.4 to select 48 bits from the concatenation 61&2 ■ • ■ br,a of Cj and D,: A', = 614617 ... 632. denotes left circular shift.)

If decryption is designed as a simple variation of the encryption function, savings result in hardware or software code size. DES achieves this as outlined in Note 7.84.

7.84 Note (DES decryption) DES decryption consists of the encryption algorithm with the same key but reversed key schedule, using in order AT16, A'i5, ... , Ki (see Note 7.85). This works as follows (refer to Figure 7.9). The effect of IP-1 is cancelled by IP in decryption, leaving (Вщ, бщ); consider applying round 1 to this input. The operation on the left half yields, rather than L0®/(Ao, ATi), now АюФДАю, А'ю) which, since Li6 = Arr> and Лю = А15ФДЯ15, A'le), is equal to L15®f(R15. K16) = A15. Thus

round 1 decryption yields (A15, L15), i.e., inverting round 16. Note that the cancellation

 PCI PC2 57 49 41 33 25 17 9 14 17 11 24 1 5 1 58 50 42 34 26 18 3 28 15 6 21 10 10 2 59 51 43 35 27 23 19 12 4 26 8 19 11 3 60 52 44 36 16 7 27 20 13 2 above for C,; below for Di 41 52 31 37 47 55 63 55 47 39 31 23 15 30 40 51 45 33 48 7 62 54 46 38 30 22 44 49 39 56 34 53 14 6 61 53 45 37 29 46 42 50 36 29 32 21 13 5 28 20 12 4

Table 7.4: DES key schedule bit selections (PCI and PC2).

of each round is independent of the definition of f and the specific value of Kf, the swapping of halves combined with the XOR process is inverted by the second application. The remaining 15 rounds are likewise cancelled one by one in reverse order of application, due to the reversed key schedule.

• 7.85 Note (DES decryption key schedule) Subkeys К i,... , К is may be generated by Algorithm 7.83 and used in reverse order, or generated in reverse order directly as follows. Note that after Кщ is generated, the original values of the 28-bit registers C and I) are restored (each has rotated 28 bits). Consequently, and due to the choice of shift-values, modifying Algorithm 7.83 as follows generates subkeys in order Кю,... ,K replace the left-shifts by right-shift rotates; change the shift value v to 0.
• 7.86 Example (DES test vectors) The plaintext “Now is the time for all ”, represented as a string of 8-bit hex characters (7-bit ASCII characters plus leading 0-bit), and encrypted using the DES key specified by the hex string К = 01234 5678 9ABCDEF results in the folio whig plaintext/ciphertext:

P =4E6F772069732074 68652074696D6520 666F7220616C6C20 C = 3FA40E8A984D4815 6A271787AB8883F9 893D51EC4B563B53. □