Informaticasite van het Lauwers College te Buitenpost                 © R.J. van der Beek
 
[1 Eerste husseling]  [2 De subsleutels]  [3 Initiële Permutatie]  [4 Het DES-algoritme]  [5 Tabellen bij DES-algoritme] 
[6 De output en decryptie; zelf uittesten]  [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 0123456
15749413325179
81585042342618
151025951433527
221911360524436
2963554739312315
367625446383022
431466153453729
50211352820124

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
  1. Zet het ronde-nummer R op 1.
  2. Splits de huidige 56-bit sleutel K op in twee blokken van 28-bits, L (de linker helft) en R (de rechter helft).
  3. 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.
  4. Voeg L en R samen, dan heb je de nieuwe K.
  5. Pas husseling nr. 2 toe op K en dan heb je de subsleutel K[R], waarin R het ronde-nummer is.
  6. 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 1234 5678 9101112 13141516
aantal bits om over te roteren 11222222 12222221

Husseling nr. 2
Bit012345
11417112415
73281562110
132319124268
191672720132
25415231374755
31304051453348
37444939563453
43464250362932

  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 01234567
1585042342618102
9605244362820124
17625446383022146
25645648403224168
3357494133251791
41595143352719113
49615345372921135
57635547393123157


IP-1: Inverse Initiële Permutatie
Bit 01234567
1408481656246432
9397471555236331
17386461454226230
25375451353216129
33364441252206028
41353431151195927
49342421050185826
5733141949175725

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.
  1. 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.
  2. 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.
  3. 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].
  4. 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
  5. Het resultaat van de vorige stap wordt nu gewijzigd zoals in de P-permutatie tabel is aangegeven.
  6. Dit resultaat wordt geXORed met L[I-1], en het wordt opgeslagen in R[I]. R[I-1] wordt opgeslagen in L[I].
  7. 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
Bit012 345
13212345
7456789
138910111213
19121314151617
25161718192021
31202122232425
37242526272829
4328293031321

P permutatie
Bit01 23
11672021
529122817
91152326
135183110
17282414
21322739
251913306
292211425

S-Box 1: Substitutie Box 1
rij / kolom01 234 567 8910 111213 1415
0144131215 1183106125907
101574142 13110612119538
2411481362 1115129731050
315128249 17511314100613

S-Box 2: Substitutie Box 2
rij / kolom01 234 567 8910 111213 1415
01518146113 497213120510
1313471528 1412011069115
201471110413 15812693215
3138101315 4211671205149

S-Box 3: Substitutie Box 3
rij / kolom01 234 567 8910 111213 1415
01009146315 511312711428
113709346 10285141211151
2136498153 0111212510147
3110130698 7415143115212

S-Box 4: Substitutie Box 4
rij / kolom01 234 567 8910 111213 1415
0713143069 1012851112415
11381156150 347212110149
21069012117 131513145284
33150610113 894511127214

S-Box 5: Substitutie Box 5
rij / kolom01 234 567 8910 111213 1415
021241710116 85315130149
1141121247131 5015103986
242111101378 15912563014
3118127114213 6150910453

S-Box 6: Substitutie Box 6
rij / kolom01 234 567 8910 111213 1415
01211015926 801334147511
11015427129 561131401138
29141552812 370410113116
3432129515 1011141760813

S-Box 7: Substitutie Box 7
rij / kolom01 234 567 8910 111213 1415
04112141508 133129751061
1130117491 1014351221586
21411131237 141015680592
36111381410 795015142312

S-Box 8: Substitutie Box 8
rij / kolom01 234 567 8910 111213 1415
01328461511 110931450127
11151381037 412561101492
27114191214 206101315358
3211474108 1315129035611

  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.


Boodschap   
DES sleutel
Versleutelde boodschap   
Berekening: