5 DES

DES was developed in 1975 by IBM. Successing Lucifer, it is the most widely spread cryptosystem.

DES encrypts a plaintext bitstring x of length 64 with a key of length 56. The gained ciphertext is 64 bits long.
The calculation of the 16 single keys for point (2) is very tedious and is described in 5.1 DES Key.

The algorithm has three steps:

1. Given a plaintext x, a bitstring x₀ is constructed by reordering the bits of x according to a fixed initial permutation IP. We write x₀ = IP(x) = L₀ R₀ , where L₀ contains the first 32 Bits of x₀, and R₀ the last ones.
2. Now, 16 repetitions of a certain function are executed. We determine L_iR_i, i = 1,...,16, after the following rule:
   • L_i = R_i-1
   • R_i = L_i-1 [+] f(R_i-1 , K_i) ,
   where [+] stands for the exklusive OR of two bitstrings. f is described further below, and K₁, K₂ , ... , K₁₆ are bitstrings of length 48, which are determined as a function of the key K.
3. Apply the inverse permutation IP^-1 on the bitstring R₁₆ L₁₆; this yields the ciphertext y, that is y = IP^-1(R₁₆ L₁₆). (Regard the inverse order of L₁₆ and R₁₆).

The function f takes as input the first argument A (bitstring of length 32) and as the second J (bitstring of length 48), and returns a bitstring of length 32:

1. The first argument A is expanded to a bitstring of length 48 by a fixed expansion function E. E(A) consisting of 32 bits from A, permuted in a certain way, where 16 of the bits occur twice.
2. Determine E(A) [+] J and write the result as a concatenation of eight strings of six bit each,
   B = B₁B₂ B₃ B₄ B₅ B₆ B₇ B₈.
3. Each B_i is now permuted in the so-called S-boxes S_j into C_j, i.e. C_j = S_j (B_j ), j = 1,...,8.
   The S-boxes are 4x16-matrices with entries between 0 and 15. Let B_j = b₁b₂ b₃ b₄ b₅ b₆. Then the wto bits b₁b₆ correspond with the binary representation of a row r from S_j (0 <= r <= 3), and the four bits b₂ b₃ b₄ b₅ determine the number of the column c from S_j (0 <= c <= 15).
   Then S_j (B_j) is the entry S_j (r,c), written as bitstring of length 4.
4. The bitstring C = C₁C₂ C₃ C₄ C₅ C₆ C₇ C₈ of length 32 is now reordered according to the fixed permutation P. The gained bitstring P(C) is f(A,J).

Start applet in new window


Initial Permutation IP:

58	50	42	31	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	25	7

Final Permutation 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

Bit Table  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

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

5.1 DES key