# 9.5A Het DES-algoritme

Inhoud van de DES-pagina:
D.1 De techniek van het DES-algoritme
D.2 Wat doet de functie f met Ri en Ki?
D.3 Hoe ziet de deelsleutel Ki eruit?

D.1 - De techniek van het DES-algoritme

De behoefte aan een standaard cijferschrift om bedrijven in staat te stellen met elkaar versleutelde berichten uit te wisselen, groeide. In de beginjaren zeventig ontwikkelde Horst Feistel een geducht algoritme en noemde het Lucifer. Lucifer was gebaseerd op een 12-bits sleutel.
Het DES-algoritme (Data Encryption Standard) is door IBM ontwikkeld en in 1977 verheven tot federale standaard van de Verenigde Staten. Het vercijfert data-blokken van 64 bits en gebruikt daarbij een 64-bits sleutel, waarvan 8 controlebits, die niet meedoen met de vercijfering. Een opvolger van DES is AES (Advanced Encryption Standard), welke gebruik maakt van een grotere sleutel van 128, 192 of 256 bits.
Ook IDEA (International Data Encryption Algorithm), een algoritme uit 1990, gebruikt een 128-bits sleutel om data-blokken van 64 bits te vercijferen. Een toepassing van dit algoritme is het e-mail pakket Pretty Good Privacy (PGP), wat later nog ter sprake komt.

De genoemde algoritmes geven een symmetrische versleuteling, met andere woorden, de verzender en de ontvanger moeten beschikken over dezelfde sleutel. Ze zijn echter zeer gecompliceerd en zonder computer niet te gebruiken. We geven in deze paragraaf een toelichting van DES op hoofdlijnen. De vercijfering bestaat uit een reeks van permutaties en substituties. Onder een permutatie wordt verstaan een verwisseling en onder een substitutie een vervanging.

De klare tekst wordt in binaire vorm aangeboden en bestaat dus uit nullen en enen. Deze tekst wordt opgedeeld in blokjes van 64 bits. (In les 9 werd het binaire syteem uitgelegd). In de eerste stap worden de bits volgens een schema door elkaar geschud. Dit noemen we de Initiële permutatie (IP). De 64 bits worden vervolgens gescheiden in twee helften van 32 bits, de linkerhelft L0 en de Rechterhelft R0 (zie de afbeelding hiernaast). Dan volgen er 16 rondes waarbij steeds een deelsleutel Ki (met i=1,2,...16) wordt gebruikt voor een versleuteling van de rechterhelft. De cijfertekst wordt op een speciale manier opgeteld bij de linkerhelft en vormt de nieuwe rechterhelft. De oude rechterhelft wordt daarbij de nieuwe linkerhelft. Na de eerste iteratie is L0 opgeteld bij de cijfertekst en niet meer herkenbaar. In de tweede iteratie wordt R1 opnieuw vercijferd en is R0, na een eerste verwisseling, opgeteld bij deze tweede vercijfering. Daarmee is R0 ook niet meer herkenbaar. Ieder deel van de klare tekst wordt op deze manier 8 maal versleuteld.

Na 16 iteraties worden links en rechts niet verwisseld om aan te sluiten op de ontcijfering.

Na de 16e iteratie vindt er opnieuw een permutatie plaats die de inverse is van de initiële permutatie aan het begin. Dit geeft de output van het eerste vercijferde blok van 64 bits.

Een paar vragen blijven over na dit eerste overzicht:

- hoe ziet de deelsleutel Ki eruit

- wat doet de functie f met Ri en Ki

- hoe werkt de vreemde optelling van f met L

De laatste vraag is het simpelst te beantwoorden. De optelling is een modulo 2 optelling, ook bekend als de exclusieve OR. De 32 bits van Li en de 32 bits van f(Ri,Ki+1) worden onder elkaar gezet en paarsgewijs opgeteld. Daarbij is

0+0 mod(2) = 0
0+1 mod(2) = 1
1+0 mod(2) = 1
1+1 mod(2) = 0

Op de eerste twee vragen gaan we nog wat uitgebreider in.

Reflectie

Tel de volgende twee rijen bij elkaar op met gebruik van de mod(2) optelling. Wat is het resultaat?

0 0 0 1 1 0 1 1 1 0 0 1 1 0 0 1
0 0 1 1 0 0 0 0 0 1 1 1 0 1 1 1

klik hier

Ontcijfering gebeurt in tegengestelde richting, waarbij de deelsleutels ook in omgekeerde volgorde worden gebruikt. Het begint met de initiële permutatie. De twee helften zijn nu L16 en R16. Er geldt

R15=L16 en L15=R16 + f(L16,K16) mod(2)
De output L16 is dus de eerste input voor de functie f op de weg terug.

Samengevat geldt op de heenweg Li=Ri-1 en Ri=Li-1 + f(Ri-1,Ki) mod(2)
en op de weg terug geldt dan Ri-1=Li en Li-1=Ri + f(Li,Ki) mod(2)

Opgave 1

Als je de weg terug neemt lijkt het logischer om R16 terug te zetten op de plek van R15. Daar komt deze immers vandaan.
Dat zou inhouden dat L16 via de functie f teruggeleid zou moeten worden naar L15. Waarom is dit niet mogelijk?

D.2 - Wat doet de functie f met Ri en Ki?

De tweede vraag die we willen beantwoorden is wat de functie f met Ri en Ki doet:
Allereerst wordt de 32 bits rechterhelft in een tabel met 4 kolommen van 8 rijen gezet en uitgebreid tot een 48-bits tabel. Daarbij worden de entries in de eerste en laatste kolom gekopieerd naar de 5een 0e kolom:

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

Je ziet hiernaast de 1e tot en met de 32e bit ingevuld in de middelste 4 kolommen. Verder zijn de bits van de eerste kolom
scheef gekopieerd naar de 5e kolom en de bits van de 4e kolom scheef gekopieerd naar de 0e kolom. De getallen stellen dus
de nummers van de bits voor en niet de bits zelf.

De rechterhelft bestaat dus nu uit 48 bits en wordt modulo 2 opgeteld bij een 48 bits deelsleutel. Deze deelsleutel is op een speciale manier afgeleid van de 64 bits sleutel. We zullen straks zien hoe dat gedaan wordt.

Het resultaat is een tabel van 8 rijen en 6 kolommen.

Stel dat het resultaat van de bewerking op R0 met deelsleutel K1 er als volgt uitziet:

1 | 1 | 1 | 0 | 0 | 1
0 | 1 | 1 | 0 | 0 | 0
1 | 1 | 0 | 1 | 0 | 0
0 | 1 | 1 | 0 | 1 | 1
0 | 0 | 0 | 1 | 1 | 0
1 | 1 | 0 | 0 | 0 | 0
1 | 1 | 0 | 1 | 0 | 1
1 | 1 | 0 | 0 | 1 | 1

Dit levert 8 rijen met 6 bits. De eerste rij bestaat uit 1 1 1 0 0 1, de tweede uit 0 1 1 0 0 0, en zo verder.
Neem de eerste rij als voorbeeld: 1 1 1 0 0 1. De buitenste 2 bits vormen het binaire getal 11, wat gelijk is aan het decimale getal 3.
De binnenste 4 bits vormen het binaire getal 1100, wat gelijk is aan het decimale getal 12.

Doen we hetzelfde met de tweede rij, dan vinden we 0 1 1 0 0 0. De buitenste 2 bits vormen het binaire getal 00, wat hetzelfde is
als het decimale getal 0. De binnenste vier bits vormen het binaire getal 1100, wat opnieuw gelijk is aan het decimale getal 12.

Opgave 2

Doe hetzelfde voor de derde t/m de achtste rij en zet de resultaten in een tabel.

Met het resultaat van opgave 2 wordt nu de substitutietabel geraadpleegd, die hieronder is afgebeeld.

Deze tabel bestaat uit 8 deeltabellen S1t/m S8. De eerste rij leverde ons de getallen 3 en 12. In deeltabel S1vinden we in de derde rij en de twaalfde kolom het binaire getal 10.
De eerste rij wordt nu vervangen door de binaire representatie van het decimale getal 10,
dus door 1 0 1 0.

De tweede rij leverde ons de getallen 0 en 12. In deeltabel S2vinden we in de 0e rij, in de 12ekolom het decimale getal 12.
De tweede rij wordt nu vervangen door de binaire representatie van het decimale getal 12,
dus door 1 1 0 0.

Zo gaan we rij voor rij langs en vervangen iedere rij door een binair getal van 4 cijfers.
Het resultaat is een 32 bits getal. We noemen dit f(R0,K1).

Opgave 3

Stel met behulp van het resultaat van opgave 2 de 32-bits tabel samen van f(R0,K1).

Uit opgave 3 volgt dat f(R0,K1) nu het 32-bits getal
10101100001010100001011100001100 is.
Dit getal wordt modulo 2 opgeteld bij de 32-bits van L0.
Het resultaat van deze bewerking is R1.

D.3 - Hoe ziet de deelsleutel Ki eruit?

De laatste vraag die nu nog beantwoord moet worden is de vraag waaruit de 16 deelsleutels K1 t/m K16 bestaan en hoe die gevonden worden. In feite is het een eenvoudige bewerking in een spreadsheet. Uitgangspunt is een 64-bits sleuteltabel van 8 rijen en 8 kolommen.
Van deze tabel worden volgens een schema 56 bits geselecteerd.
De 56 bits worden gesplitst in 2 rijtjes van 28 bits.
De volgorde binnen deze 28-bits rijtjes draait bij iedere iteratie 1 of 2 plaatsen door. Dit wordenSHIFTs genoemd.
Hierbij worden de eerste bit of eerste 2 bits de laatste en de andere komen 1 of 2 plaatsen naar voren. De twee helften worden teruggezet in een tabel en vervolgens worden er volgens een vast schema 48 bits uitgekozen. Bij iedere iteratie zijn de bits van plaats gewisseld bij het doordraaien, zodat iedere deelsleutel anders zal zijn. De schema's om 56 bits te selecteren en bij iedere iteratie 48 bits te selecteren staan vast. Het aantal SHIFTs staat ook per ronde vast.

Hieronder een rekenvoorbeeld waarin dit wordt toegelicht.

We kiezen een 64-bits sleutel, bijvoorbeeld:

1 | 1 | 0 | 1 | 0 | 0 | 1 | 0
1 | 1 | 0 | 1 | 1 | 1 | 1 | 0
1 | 1 | 0 | 0 | 1 | 0 | 1 | 0
1 | 0 | 1 | 0 | 1 | 0 | 0 | 1
0 | 1 | 0 | 1 | 0 | 0 | 1 | 1
1 | 1 | 0 | 0 | 0 | 1 | 0 | 0
1 | 0 | 1 | 0 | 1 | 0 | 0 | 1
0 | 0 | 1 | 0 | 0 | 1 | 0 | 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

Vervolgens wordt er een keuze gemaakt volgens het rechterschema. Hierin is te zien dat eerst de 57e bit wordt geselecteerd (linksonder kleur oranje), vervolgens de 49e (recht daarboven kleur geel) etcetera. Zetten we deze op volgorde in 2 rijen van 28 bits dan krijgen we het volgende resultaat:
0 1 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 0 1 0 0 0 0 0 0 1

0 0 1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 1

Zoals je kunt zien bestaat de laatste kolom uit niet-gebruikte bits. Dit worden controlebits of pariteitsbits genoemd.

We kijken nu naar het aanal SHIFTs. In onderstaand schema is dit vastgelegd

Ronde | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16
SHIFTs | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 1

Voor de eerste ronde schuiven alle bits 1 plaats op en de eerste gaan naar de laatste plaats:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
1 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 0 1 0 0 0 0 0 0 1 0

29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
0 1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 1 0

Vervolgens worden er 48 bits gekozen volgens het linkerschema:

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

1 | 1 | 1 | 0 | 1 | 1
0 | 0 | 1 | 1 | 0 | 1
0 | 0 | 0 | 1 | 0 | 0
1 | 1 | 1 | 1 | 1 | 1
0 | 0 | 1 | 1 | 0 | 1
1 | 1 | 1 | 0 | 1 | 0
0 | 0 | 0 | 0 | 0 | 1
1 | 1 | 0 | 1 | 0 | 0

Het resultaat levert de rechtertabel voor K1:

In de tweede iteratie verandert de volgorde binnen de rijen als gevolg van de SHIFT waardoor de matrix K2 verschilt van de matrix K1. Hetzelfde geldt voor de hieropvolgende deelsleutels.

Opgave 4

Bereken K2 .

De manier om het DES-algoritme te kraken is met behulp van een Brute-Force-Attack, oftwel een brute aanval. Het komt er op neer dat je gewoon alle 56-bits sleutels moet uitproberen en los moet laten op het algoritme. Dat lijkt simpel, maar er zijn 256 mogelijke sleutels, oftewel 72.057.594.037.900.000. Met een snelle computer zou je wellicht 1 miljoen mogelijkheden per seconde uit kunnen proberen. Daarmee kun je de computer gemiddeld ruim 1000 jaar bezighouden.
In 1997 is het een groep wetenschappers onder leiding van Rocke Verser gelukt het DES-algoritme te kraken in een challenge die uitgeschreven was door het bedrijf RSA Data Security. Het bedrijf stelde een beloning van $10.000.= in het vooruitzicht voor degene die het algoritme als eerste zou weten te kraken. Daarvoor gebruikten zij niet 1 computer maar een hele serie computers. Daarmee duurde het 4 maanden om het algoritme te kraken. Op dat moment was pas 25% van alle sleutels uitgeprobeerd. De ontcijferde tekst luidde "Strong cryptography makes the world a safer place".

Opgave 5

Maak een schatting van het aantal computers dat de groep gebruikt heeft.

Opgave 6

Bereken hoeveel jaar het algoritme met een 128 bits sleutel stand zou hebben gehouden tegen een Brute Force Attack onder identieke voorwaarden als in bovenstaand voorbeeld.