Informaticasite van het Lauwers College te Buitenpost © R.J. van der Beek

[terug naar H17]

DES, onderdeel van Hoofdstuk 17

1. De eerste husseling

DES versleutelt data in blokken van 64 bits, en gebruikt daarbij een 64-bits sleutel (hoewel de effectieve lengte van de sleutel maar 56 bits is). Het neemt een blok van 64 bits als input en de output is ook weer een blok van 64 bits.

DES heeft 16 ronden, dat betekent dat het algorithme 16 keer herhaald wordt. Het is gebleken dat de tijd die nodig is om de sleutel te vinden door een brute-force attack exponentieel toeneemt als het aantal ronden lineair toeneemt.
Hoewel de sleutel voor DES 64 bits lang is , is de effectieve lengte van de sleutel maar 56 bits.
Het meest rechtse bit in elke byte is a pariteits bit, en wordt zo gewijzigd dat er altijd een oneven aantal enen in elke byte zit. Deze pariteitsbits worden verder niet gebruikt in het algoritme, dus er worden eigenlijk maar 56 bits gebruikt.

De eerste stap is dat de 56 bits op een bepaalde manier door elkaar gehusseld worden. Hoe dat gebeurt zie je in onderstaande tabel.

Husseling nr. 1

Bit	0	1	2	3	4	5	6
1	57	49	41	33	25	17	9
8	1	58	50	42	34	26	18
15	10	2	59	51	43	35	27
22	19	11	3	60	52	44	36
29	63	55	47	39	31	23	15
36	7	62	54	46	38	30	22
43	14	6	61	53	45	37	29
50	21	13	5	28	20	12	4

In de tabel zie je bijvoorbeeld dat bit nr. 30 van de sleutel na husseling op plaats nr 41 komt.
Want 30 staat in de kolom waar 5 boven staat, en in de rij waar 36 voor staat, dus het wordt bit 36 + 5 = 41 van de nieuwe 56-bits sleutel. Zie je dat de bits 8, 16, 24, 32, 40, 48, 56 en 64 niet in de tabel staan? Dat zijn de ongebruikte pariteits-bits.

2. De subsleutels

Nu we de nieuwe 56-bits sleutel hebben is de volgende stap het maken van 16 48-bit subsleutels, die we K[1] t/m K[16] noemen. Die worden gebruikt in de 16 ronden van de DES-encryptie. Dit gaat als volgt

Zet het ronde-nummer R op 1.
Splits de huidige 56-bit sleutel K op in twee blokken van 28-bits, L (de linker helft) en R (de rechter helft).
Roteer L een aantal bits naar links en wel zovaak als in onderstaande tabel is aangegeven, en roteer R naar links over hetzelfde aantal bits.
Voeg L en R samen, dan heb je de nieuwe K.
Pas husseling nr. 2 toe op K en dan heb je de subsleutel K[R], waarin R het ronde-nummer is.
Verhoog R met 1 en herhaal de procedure totdat we alle 16 subsleutels K[1] t/m K[16] hebben.

Hier vind je de tabellen die nodig zijn voor bovenstaande bewerkingen:

**Subsleutel Rotatie Tabel**
ronde-nummer	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
aantal bits om over te roteren	1	1	2	2	2	2	2	2	1	2	2	2	2	2	2	1

**Husseling nr. 2**
Bit	0	1	2	3	4	5
1	14	17	11	24	1	5
7	3	28	15	6	21	10
13	23	19	12	4	26	8
19	16	7	27	20	13	2
25	41	52	31	37	47	55
31	30	40	51	45	33	48
37	44	49	39	56	34	53
43	46	42	50	36	29	32

3. Initiële Permutatie

De volgende stap is de te coderen tekst door elkaar te husselen, dit wordt de Initiële Permutatie genoemd, afgekort tot IP.
Deze husseling heeft ook een inverse, dat wordt wel de Inverse Initiële Permutatie genoemd, afgekort tot IP^-1.
Soms wordt IP^-1 ook wel de Finale Permutatie genoemd.
Beide tabellen zie je hier onder.

**IP: Initiële Permutatie**
Bit	0	1	2	3	4	5	6	7
1	58	50	42	34	26	18	10	2
9	60	52	44	36	28	20	12	4
17	62	54	46	38	30	22	14	6
25	64	56	48	40	32	24	16	8
33	57	49	41	33	25	17	9	1
41	59	51	43	35	27	19	11	3
49	61	53	45	37	29	21	13	5
57	63	55	47	39	31	23	15	7

**IP^-1: Inverse Initiële Permutatie**
Bit	0	1	2	3	4	5	6	7
1	40	8	48	16	56	24	64	32
9	39	7	47	15	55	23	63	31
17	38	6	46	14	54	22	62	30
25	37	5	45	13	53	21	61	29
33	36	4	44	12	52	20	60	28
41	35	3	43	11	51	19	59	27
49	34	2	42	10	50	18	58	26
57	33	1	41	9	49	17	57	25

Deze tabellen worden net zo gebruikt als die voor de husseling van de sleutel-bits. Als je naar de tabel kijkt wordt snel duidelijk waarom de ene permutatie de inverse van de andere genoemd wordt. Kijk bijvoorbeeld maar eens hoe bit 32 wordt verplaatst bij IP. In de tabel zie je dat bit 32 in de kolom met 4 als kop en de rij behorend bij 25 zit, dus dit bit wordt bit 29 na de permutatie.
In de tabel van IP^-1 zie je dat bit 29 in de kolom met 7 als kop en de rij behorend bij 25 zit, dus dit bit wordt bit 32 na de permutatie.
IP^-1 doet dus precies het omgekeerde van IP.
Als je een blok van 64 bits door IP laat veranderen, en op het resultaat laat je IP^-1 los, dan krijg je het oorspronkelijke blok met bits terug.

4. Het DES-algoritme

Nu vindt de eigenlijke encryptie of decryptie plaats door het DES algoritme. Het 64-bits blok met input data wordt eerst gesplitst in twee helften, L en R. L bestaat uit de meest linkse 32 bits, en R uit de meest rechtse 32 bits.
Het volgende proces wordt 16 keer herhaald, in de 16 ronden van het DES-algoritme.
We noemen de 16 linker-helften, die zo ontstaan, L[0]-L[15] en de 16 rechter-helften noemen we R[0]-R[15].
Daarbij is L[0] gelijk aan L, dus de linker helft van het input blok. En R[0] is gelijk aan R, dus de rechter helft van het input blok.

We nemen R[I-1], waarbij I het ronde-nummer is en bij de start geldt I = 1. Dus we starten met R[0], en dat is gelijk aan R, dus de rechter helft van het input blok.
Het blok R[I-1] van 32 bits wordt gewijzigd in een 48 bits blok, dat gebeurt door de E-Bit SelectieTabel, die als een bit-husseling werkt, maar zo dat sommige bits meer dan één keer worden gebruikt.
Het 48-bits blok R[I-1] wordt geXORed met K[I] (dus de i-de deelsleutel) en wordt opgeslagen in een buffer-geheugen zodat R[I-1] niet veranderd wordt.
Het resultaat van de vorige stap wordt nu gesplitst in acht stukken van 6 bits elk. De meest linkse 6 bits worden aangegeven met B[1], en de meest rechtse 6 bits met B[8].

Stel we hebben de volgende 48-bits:
011101000101110101000111101000011100101101011101

Deze 48 bits worden gesplitst in acht 6-bits blokken:
B[1]=011101 B[2]=000101 B[3]=110101 B[4]=000111 B[5]=101000 B[6]=011100 B[7]=101101 en B[8]=011101

Deze blokken worden in de volgende stap gebruikt; met behulp van de S-boxen worden er 32 nieuwe bits gevormd.
De Substitutie boxen, die S-boxen genoemd worden, zijn een set van 8 twee-dimensionale rijen, elk met 4 rijen en 16 kolommen.
De getallen in de boxen zijn altijd 4 bits lang, dus de waarde zit tussen 0 en 15. De S-boxen zijn genummerd S[1] tot en met S[8].
Nu wordt van elk 6-bits blok het eerste en het zesde (dus laatste) bit genomen en achter elkaar geplaatst zodat je een getal van twee bits hebt (decimaal kan dat 0, 1, 2 en 3 zijn). Dat getal bepaalt welke rij van de S-box je moet hebben.
De middelste vier bits vormen een getal van vier bits (decimaal kan dat 0 t/m 15 zijn). Dat getal bepaalt welke kolom van de S-box je moet hebben.
Het getal dat in de S-box op de betreffende rij en in de betreffende kolom staat is een getal tussen 0 en 15, binair bestaat dat uit vier bits. Je begint met B[1] en S[1], dat levert het eerste 4-bits getal. Dit wordt herhaald met B[2] en S[2], , dat levert het volgende 4-bits getal Vervolgens B[3] en S[3], en de anderen, tot en met B[8] en S[8]. Als je zover bent heb je acht 4-bits getallen, die worden samengevoegd tot een 32-bit resultaat.

We gaan verder met het voorbeeld van de vorige stap: B[1]=011101
Het eerste en het zesde bit zijn 0 en 1, samen wordt dat 01. Dat is decimaal 1, dus we moeten rij 1 hebben van S-box S[1].
De middelste vier bits zijn 1110. Dat is decimaal 14, dus we moeten kolom 14 hebben van S-box S[1].
Dan zoeken we S-box S[1] hieronder op, en daar zien we dat op die plaats 3 staat. Dat is binair 0011, en daar hebben we de eerste vier bits, die ontstaan zijn uit B[1] en S[1]

Het eerste resultaat noteren we als volgt: S[1](01, 1110) = S[1][1][14] = 3 = 0011
De andere resultaten ontstaan op dezelfde manier:
Uit B[2]: S[2](01, 0010) = S[2][1][2 ] = 4 = 0100
Uit B[3]: S[3](11, 1010) = S[3][3][10] = 14 = 1110
Uit B[4]: S[4](01, 0011) = S[4][1][3 ] = 5 = 0101
Uit B[5]: S[5](10, 0100) = S[5][2][4 ] = 10 = 1010
Uit B[6]: S[6](00, 1110) = S[6][0][14] = 5 = 0101
Uit B[7]: S[7](11, 0110) = S[7][3][6 ] = 10 = 1010
Uit B[8]: S[8](01, 1110) = S[8][1][14] = 9 = 1001

De resultaten worden nu samengevoegd tot een 32-bits getal, dat dient als de invoer van stap 5 van het
DES-algoritme (de P permutatie): 00110100111001011010010110101001
Het resultaat van de vorige stap wordt nu gewijzigd zoals in de P-permutatie tabel is aangegeven.
Dit resultaat wordt geXORed met L[I-1], en het wordt opgeslagen in R[I]. R[I-1] wordt opgeslagen in L[I].
Nu hebben we een nieuwe L[I] en R[I]. Nu verhogen we I met 1 en herhalen het algoritme. Net zo lang tot er 16 ronden zijn geweest en de sleutels K[1] tot en met K[16] allemaal zijn gebruikt.

Als L[16] en R[16] klaar zijn dan worden ze samengevoegd op dezelfde manier als waarop ze gesplitst zijn (L[16] is de linker helft, R[16] is de rechter helft), de twee helften worden verwisseld, R[16] wordt de meest linkse 32 bits en L[16] wordt de meest rechtse 32 bits van het output blok en het resultaat van 64-bits wordt wel de pre-output genoemd.

5. Tabellen die gebruikt worden bij het DES-algoritme

**E-Bit SelectieTabel**
Bit	0	1	2	3	4	5
1	32	1	2	3	4	5
7	4	5	6	7	8	9
13	8	9	10	11	12	13
19	12	13	14	15	16	17
25	16	17	18	19	20	21
31	20	21	22	23	24	25
37	24	25	26	27	28	29
43	28	29	30	31	32	1

**P permutatie**
Bit	0	1	2	3
1	16	7	20	21
5	29	12	28	17
9	1	15	23	26
13	5	18	31	10
17	2	8	24	14
21	32	27	3	9
25	19	13	30	6
29	22	11	4	25

**S-Box 1: Substitutie Box 1**
rij / kolom	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

**S-Box 2: Substitutie Box 2**
rij / kolom	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	15	1	8	14	6	11	3	4	9	7	2	13	12	0	5	10
1	3	13	4	7	15	2	8	14	12	0	1	10	6	9	11	5
2	0	14	7	11	10	4	13	1	5	8	12	6	9	3	2	15
3	13	8	10	1	3	15	4	2	11	6	7	12	0	5	14	9

**S-Box 3: Substitutie Box 3**
rij / kolom	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	10	0	9	14	6	3	15	5	1	13	12	7	11	4	2	8
1	13	7	0	9	3	4	6	10	2	8	5	14	12	11	15	1
2	13	6	4	9	8	15	3	0	11	1	2	12	5	10	14	7
3	1	10	13	0	6	9	8	7	4	15	14	3	11	5	2	12

**S-Box 4: Substitutie Box 4**
rij / kolom	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	7	13	14	3	0	6	9	10	1	2	8	5	11	12	4	15
1	13	8	11	5	6	15	0	3	4	7	2	12	1	10	14	9
2	10	6	9	0	12	11	7	13	15	1	3	14	5	2	8	4
3	3	15	0	6	10	1	13	8	9	4	5	11	12	7	2	14

**S-Box 5: Substitutie Box 5**
rij / kolom	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	2	12	4	1	7	10	11	6	8	5	3	15	13	0	14	9
1	14	11	2	12	4	7	13	1	5	0	15	10	3	9	8	6
2	4	2	1	11	10	13	7	8	15	9	12	5	6	3	0	14
3	11	8	12	7	1	14	2	13	6	15	0	9	10	4	5	3

**S-Box 6: Substitutie Box 6**
rij / kolom	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	12	1	10	15	9	2	6	8	0	13	3	4	14	7	5	11
1	10	15	4	2	7	12	9	5	6	1	13	14	0	11	3	8
2	9	14	15	5	2	8	12	3	7	0	4	10	1	13	11	6
3	4	3	2	12	9	5	15	10	11	14	1	7	6	0	8	13

**S-Box 7: Substitutie Box 7**
rij / kolom	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	4	11	2	14	15	0	8	13	3	12	9	7	5	10	6	1
1	13	0	11	7	4	9	1	10	14	3	5	12	2	15	8	6
2	1	4	11	13	12	3	7	14	10	15	6	8	0	5	9	2
3	6	11	13	8	1	4	10	7	9	5	0	15	14	2	3	12

**S-Box 8: Substitutie Box 8**
rij / kolom	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	13	2	8	4	6	15	11	1	10	9	3	14	5	0	12	7
1	1	15	13	8	10	3	7	4	12	5	6	11	0	14	9	2
2	7	11	4	1	9	12	14	2	0	6	10	13	15	3	5	8
3	2	1	14	7	4	10	8	13	15	12	9	0	3	5	6	11

6. De output en decryptie; zelf uittesten

De laatste stap: pas de permutatie IP^-1 toe op de pre-output. Het resultaat is de versleutelde tekst.

Voor encryptie en decryptie kan het zelfde algoritme worden gebruikt. De methode, die hierboven beschreven is, zal een tekst versleutelen.
Als je de versleutelde tekst weer wilt decoderen kun je de procedure hierboven gewoon herhalen, maar de subsleutels worden nu in omgekeerde volgorde toegepast, dus van K[16] tot en met K[1].
Dat betekent dus dat bij stap 2 van het DES-algoritme niet R[I-1] geXORed wordt met K[I] maar R[I-1] wordt geXORed met K[17-I]. Verder gaat het decoderen precies als het coderen.
Je kunt het hieronder uitproberen.