How DES or Data Encryption Standard works

On this "DES Visualized" I try to explain DES. I recommend reading through DES and block ciphers on wikipedia, but i will also explain it here. Please remind that i am not a crypto expert or got "deep" into DES, because i didn't. If you find any wrong information please leave a comment, and I will correct it as soon as possible. Cryptography Cryptography is the study of message secrecy. You want to give information to someone else and don't want a third party to be able to read it. Since computers were invented ways of encrypting information have become much quicker and easier, even for the public. Today you log in on secured websites without even knowing this, send encrypted passwords over the internet (although not very much used) and feel safe about checking your bank account on the internet. On the other side, by the use of computers cracking encrypted information have become much faster. That is way ever couple of years a encrypting is dropped and replaced by a (much) stronger one. Only problem that exists is companies not replacing those older encrypting techniques, and still relying on old, easy to hack, "security". So DES is still in use although AES replaced it in 2004, and DES shouldn't be used anymore. DES History DES stands for Data Encryption Standard and was invented in 73,74 by IBM for NSA and published in 1977 as FIPS PUB 46. In 1988 it was revised as FIPS-46-1 and 2 new variations were made public: FIPS-46-2 in 1993 and FIPS-46-3 (Better know as "Triple DES") in 1998. 64 Bits blocks DES takes a 64 bits key (16 hexadecimal numbers) to encrypt an even amount of clear text. So if you encrypt a message: 0123 4567 89AB CDEF with key: FEDC BA98 7654 3210 you get: ED39 D950 FA74 BCC4 If your clear text if bigger then 64 bits it get cut into 64 bits parts. So a message that is 284 bits long, get cut into 4 parts (64 bits) and you are left with 28 bits for part 5. Part 5 is then filled up until 64 bits with zero's. Part 5 could be something like: 0F42 A And is filled up: 0F42 A000 0000 0000 So you will have then 5 parts each 64 bits large. Those are then one by one encrypted and the output is put together with the other outputs. That is you encrypted text. 64 Or 56 bits key? DES takes a 64 bits key. BUT every 8th is not used! That means 8 bits (the 8th, 16th, 24th, 32th, 40th, 48th, 56th and 64th) are just dumped. As a result you will not have a 64 bit key, you will be left with a 56 bit key. DES encrypting key is thus not 64bits but 56 bits. XOR XOR stands for eXclusive OR. Your input will be 2 bits, and the output 1 bit. The output will be TRUE if only ONE of the 2 bits inputted is TRUE. Another way to describe it is: bit-by-bit addition modulo 2.

Bit1	Bit2	Output
0	0	0
0	1	1
1	0	1
1	1	0

The parts of DES DES exists of 3 parts: - Ciphering - Key schedule - Feistel (F) function In this image I put those together. Don't worry if you don't understand it right away, I will explain it step by step. The image gives a detailed, but cropped, view on DES. The INPUT is a 64 bits block and the KEY the 64 bits key. Logically if your message was longer then 64 bits the INPUT is first part1 everything is calculated, the OUTPUT is stored, then part2 is processed, then part3, etc. The KEY stays the same every round. Further to notice that every cipher and key schedule round have 16 rounds. I only drew the first 2 steps, an example step (n) and the last step. The rest of the steps are of course exactly the same, so i didn't drew them to save space (like the image isn't big enough now). The round with F in it, is detailed in the lower right corner (the blue part). The data flows from the top to the bottom and the directions of the arrows.

The Cipher The cipher is the part where your 64 bits block are encrypted into cipher text. I will try to explain the image here step by step.

INPUT is a 64 bits message. The 64 bits block is put into "Initial permutation" or IP. IP is a table which reorders the input. The IP for DES is:

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

That means the FIRST bit of the OUTPUT of IP is bit 58 of the INPUT. Bit 50 (from INPUT) is output bit 2, etc etc until the last bit is outputted (input bit 7).

The output from IP is split into two even halves. The first 32 bits from the output of IP is called L0. The second part (also 32 bits) is called R0.

Now 2 things happened. First the data from R0 is put into L1 (hence the L1 = R0). Second the data from R0 is put into F together with K1 (Key1), and the output from F is XOR'ed together with L0. That is stored as R1.

In other words: R1 = L0 XOR f(R0, K1) L1 = R0

Where K1 comes from and what F does will be explained later. Just look at the big picture and be sure you understand the above.

After the first step the process is repeated exactly the same for a total of 16 rounds. Every round L becomes R, and R becomes a calculated L and R.

Ln = L(n-1) Rn = L(n-1) XOR f(R(n-1), Kn)

After the 16 rounds you will have R16 and L16. Those are put together, first the 32 bits from R16, second the 32 bits from L16. The resulting 64 bits go through the "Inverse initial permutation" or IP-1.

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

OUTPUT bit 1 will be INPUT bit 40, OUTPUT bit 2 will be INPUT bit 8, etc etc, until the last OUPUT bit is INPUT bit 25.

The Key schedule The key schedule takes a 64 bits key and outputs 16 (56 bits) keys, which are used for the ciphering of the message. Output Key1 (K1) is used for cipher step 1, K2 for step 2 all the way until K16 for cipher step 16.

KEY is a 64 bits. First of all it is put into the "Permuted Choice 1" or PC-1. Like IP (and IP-1) this reorders the order of the KEY bits. Second thing PC-1 does is STRIP 8 bits from KEY. This is easily done by reordering just 56 bits, and never use the 8 other bits. Like after IP the first halve (28 bits) is put into (what is this time called) C0, the second (28 bits) part into D0.

PC-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	31	23	15
7	62	54	46	38	30	22
14	6	61	53	45	37	29
21	13	5	28	20	12	4

As you can see the numbers 8, 16, 24, 32, 40, 48, 56 and 64 do not appear in the table, since those are not used.

Then a "Left shift" is applied. A Left shift is a bitwise rotation to the left of the (in this case) 28 bits. For example a single left shift results in reordering the bits as:

2, 3, 4, 5 ..... 28, 1

2 Left shifts will get you:

3, 4, 5, 6 ..... 28, 1, 2

Not every symbol in the image for left shift means only 1 left shift, sometimes 2 are used. This table show how many left shifts are done.

Left shifts

Shift number	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Amount	1	1	2	2	2	2	2	2	1	2	2	2	2	2	2	1

That are a total of 28 left shits, so C16 and D16 are the same as C0 and D0.

The result of one left shift on C0 and D0 are C1 and D1. C10 and D10 are obtained from C9 and D10 with two left shifts.

C1 and C2 are put together and go trough "Permuted Choice 2" or PC-2, this becomes Key number 1 or K1. Notice here again we lose bits. 56 bits become 48 bits. Bits 9, 18, 22, 25 and 35, 38, 43, 54 are dropped.

PC-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

Now you know where K1 until K16 comes from.

The Feistel (F) function This is where it all comes together. Here the clear text is converted into cipher text. It is not as difficult as you might think. The image is even smaller and thus simpler.

As you remember R (R1, R2 ... R16 in the cipher image) is put into F. This R is 32 bits big. K (K1, K2 ... K16 in the key schedule image) is 48 bits long.

First R goes through E. E is function which takes 32 bits and yields a 48 bits output. It looks like IP by reordering, but it outputs some certain bits twice. Look for yourself.

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

Thus the OUTPUT bit 1 will be INPUT bit 32 all the way until the last OUTPUT bit is INPUT bit 1.

The resulting 48 bits are XOR'ed with the 48 bits KEY.

Now we get in the S1 ... S8 part. The encrypting! Finally! So many things around it for just this part. S1 ... S8 take 6 bits from the XOR

S1

Row / Column	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	14	4	13	1	2	15	11	8	3	10	6	12	5	9	0	7
1	0	15	7	4	14	2	13	1	10	6	12	11	9	5	3	8
2	4	1	14	8	13	6	2	11	15	12	9	7	3	10	5	0
3	15	12	8	2	4	9	1	7	5	11	3	14	10	0	6	13

This table has 16 (0..15) columns and 4 (0..3) rows. Remember we have 6 bits inputed. The first and the last bit are put together as a base 2 number thus 0..3. This number is called i and is the row number of the table. The middle 4 bits are also a base2 number (0..15), called j, and this represents the column number. For example say we have a S1 input:

011011

Now i will be the first and the last bit (in the example 0 and 1):

01

01 base2 means 1, so this is row 1. Next is j which are the 4 middle numbers:

1101

1101 base 2 means 13, so column 13. We can now do a lookup in the table with these numbers. Row 1 and column 13. That gives us 5. 5 is base10 which means as base2 it is 0101. The output is 0101, which is 4 bits. As you can see all the numbers in the table are only 4 bits numbers, so we replace the 6 bits number with a4 bits number.

S2 ... S8 are different lookup tables, and you can view the rest of the list here.

Only 1 tiny thing left P. P stands for Permutation. It inputs a 32 bits number and outputs a 32 bits number. It just reorders the bits.

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