DES AND SDES

MATH 195

First, some notation: 𝔽_{2} = ℤ/2ℤ. In general, 𝔽_{q} denotes a finite field with q elements: So 𝔽_{p} = ℤ/pℤ if p is prime; in general, q needs to be of the form q = p^{n}, with p prime and n ≥ 1. Note: 𝔽_{p^{n}} ≠ ℤ/p^{n}ℤ.

In SDES and DES, we have P = C = 𝔽_{2}^{2k=8 or 64}, k = 4 or 32, K = 𝔽_{2}^{10 or 56}, S = 𝔽_{2}^{8 or 48} (the subkey space), t = 2 or 16 (the number of rounds). In order to define

E : P × K → P
(z, K) ↦ E_{K}(z)

and similarly D_{K}, we need three ingredients:

• A map K → S^{t} = \underbrace{S × ⋯ × S}_{t}, K ↦ (K_{1}, …, K_{t});

• A round function F : 𝔽_{2}^{k} × S → 𝔽_{2}^{k};

• An initial permutation ι (of P). Given these three ingredients, E and D are defined as follows:

E_{K}(z) = (ι^{−1} ∘ G_{t} ∘ s ∘ ⋯ ∘ s ∘ G_{2} ∘ s ∘ G_{1} ∘ ι)(z),

where s(x, y) = (y, x) and G_{i}(x, y) = (x + F (y, K_{i}), y) and therefore

D_{K}(z) = (ι^{−1} ∘ G_{1} ∘ s ∘ ⋯ ∘ s ∘ G_{t−1} ∘ s ∘ G_{t} ∘ ι)(z).

The initial permutation ι : 𝔽_{2}^{2k} → 𝔽_{2}^{2k} permutes the 2k coordinates according to the following formula [see p. 53 in the text]: in SDES: ι(z_{1}, …, z_{8}) = ι(z_{2}, z_{6}, z_{3}, z_{1}, z_{4}, z_{8}, z_{5}, z_{7}), and in DES [see Table 3.2(a), p. 68],

ι(z_{1}, …, z_{64}) = (z_{58}, z_{50}, …, z_{15}, z_{7}).

As a check, we include “parity bits” in our key. We let

K = {(k_{1}, …, k_{64}) ∈ 𝔽_{2}^{64} : ∑_{i=8j+1}^{8(j+1)} k_{i} = 0, j = 0, 1, …, 7}

i.e. k_{1} + k_{2} + ⋯ + k_{8} = 0, k_{9} + k_{10} + ⋯ + k_{16} = 0, …, k_{57} + ⋯ + k_{64} = 0. We let the least significant bit in each byte be treated as extraneous information, so we have only 56 meaningful bits.

Now the subkey generation is a map K ↦ (K_{1}, …, K_{t}) (for DES) where K ∈ 𝔽_{2}^{64}, K_{i} ∈ 𝔽_{2}^{48}:

K_{i} = (τ ∘ λ^{n_{i}} ∘ σ)(K) :

where [Table 3.4(a), p. 72]

σ(k_{1}, …, k_{56}, …, k_{64}) = (k_{57}, k_{49}, k_{41}, …, k_{12}, k_{4})

This is some of the material covered February 19–21, in Math 195: Cryptography, taught by Hendrik Lenstra, prepared by John Voight jvoight@math.berkeley.edu.

(recall we write the 56 bits as 64 bits, using the bits k_{8}, …, k_{64} as parity bits), [Table 3.4(b), p. 72]

τ(k_{1}, …, k_{56}) = (k_{14}, k_{17}, …, k_{29}, k_{32}) ∈ 𝔽_{2}^{48},

and

λ(k_{1}, …, k_{28}, k_{29}, …, k_{56}) = (k_{2}, k_{3}, …, k_{28}, k_{1}, k_{30}, k_{31}, …, k_{56}, k_{29})

and [Table 3.4(c), p. 72] n_{1} = 1, n_{2} = 2, n_{3} = 4, …, n_{16} = 28 = 0.

The round function F : 𝔽_{2}^{32} × 𝔽_{2}^{48} → 𝔽_{2}^{32} is equally explicit. To compute F (x, k), expand

x = ( x_{1} x_{2} x_{3} x_{4} ; x_{5} x_{6} x_{7} x_{8} ; ⋮ ; x_{29} x_{30} x_{31} x_{32})

to

ϵ(x) = (x_{32} x_{1} x_{2} x_{3} x_{4} x_{5} ; x_{4} x_{5} x_{6} x_{7} x_{8} x_{9} ; ⋮ ; x_{2}8 x_{29} x_{30} x_{31} x_{32} x_{1});

write k also as an 8 × 6-matrix

k = ( k_{1} k_{2} … k_{6} ; ⋮ ; k_{43} k_{44} … k_{48})

and then add them:

k + ϵ(x) = ( k_{1} + x_{32} … x_{5} + k_{6} ; ⋮ ; k_{43} + x_{28} … x_{1} + k_{48}) .

Then apply the ith S-box S_{i} to the ith row of that matrix, i = 1, …, 8 [p. 71]. This compresses the bits on the basis of a table-lookup. Finally, follow it by the permutation of the 32 positions [Table 3.2(d), p. 68]. That results in an 8 × 4 matrix, which read as a vector gives F (x, k) ∈ 𝔽_{2}^{32}.

For a word about design criteria—diffusion and confusion, resistance against differential cryptanalysis and linear cryptanalysis, ease of use and analysis—see the text [e.g. p. 60/61].