henk-reints.nl

Pagina voor het laatst geupdated:
Deze pagina is ongeveer 100 KB en via een trage verbinding kan het dus even duren voordat hij is geladen...

basisbeginselen van
Data-encryptie

Ofwel: hoe houd ik een geheim geheim geheim?

De kernvraag van moderne encryptie is eigenlijk: Hoe kun je een vertrouwelijke, geheime boodschap naar iemand zenden via een niet-beveiligd communicatiekanaal?

Wel, in principe is dat vrij simpel: je moet de data zodaning "verminken" dat het onleesbaar wordt, maar wel zo, dat de legitieme ontvanger het weer kan terugvertalen naar het oorspronkelijke bericht. En verder niemand.


Inhoudsopgave


Letterverwisseling
Je kunt vele manieren bedenken om zo'n omkeerbare verminking voor elkaar te krijgen. Een aloude methode is bijvoorbeeld om in een tekst elke letter te vervangen door een andere letter. De vakterm hiervoor is: "monoalfabetische substitutie". Je moet daarbij natuurlijk zorgen dat de bijbehorende vertaaltabel uitsluitend bekend is bij jou en de legitieme ontvanger. Mocht iemand anders dan toch - ten onrechte - de vertaaltabel te pakken krijgen, dan maak je gewoon een nieuwe tabel en je kunt weer verder met het uitwisselen van je staatsgeheimen... Laten we daarvan maar eens een voorbeeldje bekijken. Stel dat het geheime bericht de volgende tekst is:

Even een afspraakje: in het Nederlands wordt de lange "ij" meestal als één letter beschouwd, maar in deze uiteenzetting behandel ik de "ij" als twee letters, de "i" en de "j". Gewoon omdat dat gemakkelijker is.

Stel vervolgens dat we met de legitieme ontvanger de volgende vertaaltabel hebben afgesproken. N.B. deze tabel moet je dus wel op een beveiligde manier uitwisselen met de beoogde ontvanger!

N.B. deze tabel is met JavaScript naar willekeur bepaald,
als je de pagina ververst krijg je een andere tabel!

Dan kunnen we de geheime boodschap als volgt vertalen:

Mensen die de vertaaltabel niet kennen weten hier dus geen raad mee!


Ontcijferen op basis van statistiek
Tenminste... dat had je gedacht! Iemand die kan veronderstellen dat de oorspronkelijke tekst in het Nederlands is geschreven kan dit waarschijnlijk heel eenvoudig terugvertalen. Een op deze manier gecodeerde boodschap voldoet namelijk nog steeds aan alle statistieken van de Nederlandse taal. We zouden dus bijvoorbeeld gebruik kunnen maken van letterfrequenties (= hoe vaak letters voorkomen in een taal, in het Nederlands is de "e" de meest voorkomende letter; hier is de lettertelling van deze pagina en het Genootschap Onze Taal heeft ook een overzicht - je ziet dat de lijsten al aardig overeenkomen!). De letter die in de gecodeerde boodschap het meest voorkomt zou wel eens een "e" kunnen zijn, daar heb je de oorspronkelijke tabel helemaal niet voor nodig! Van de oorspronkelijke boodschap is de letterfrequentie als volgt:

Wat betreft de "e" klopt dit dus al met het Nederlands! De letterfrequenties van de gecodeerde tekst zijn:

Zodat we dus al meteen kunnen veronderstellen dat we de kunnen terugvertalen naar de "e"! Voor een korte tekst als deze zullen niet alle letterfrequenties kloppen met de statistiek (in het Nederlands komt b.v. de "n" op de tweede plaats, terwijl dat in dit voorbeeld niet het geval is), maar voor een lange tekst kom je een heel eind. Zonder de oorspronkelijke vertaaltabel dus!

Behalve letterfrequenties zijn er natuurlijk ook statistieken omtrent woordlengtes, lettervolgordes binnen woorden, woordvolgordes binnen zinnen etc. Gewapend met die kennis is een op deze manier gecodeerde tekst simpel te kraken, ook zonder de vertaaltabel. Het gecodeerde bericht bevat doodgewoon nog veel te veel herkenbare informatie.
Bedenk ook, dat het meestal niet nodig is om een boodschap tot op de laatste letter helemaal foutloos terug te vertalen, eem teskt mte splefuoten kun jo imnerz meespal oyk nog geel hoed begirrpun...!

Aangezien aldus gecodeerde berichten te kraken zijn zonder de bijbehorende sleutel (de vertaaltabel) is voor deugdelijke geheimhouding de hele methode dus onbruikbaar! Zodra iemand (met name de vijand!) het trucje kent is de hele methode waardeloos.


Tekst omzetten naar getallen
Laten we dus eens kijken of het beter kan. Welnu, dat kan. Dankzij de wiskunde. We gaan rekenen. Maar om te rekenen hebben we getallen nodig, dus we moeten eerst een methode hebben om teksten om te zetten in getallen en weer terug. Laat zo'n methode nou al voor ons klaarstaan, dankzij de uitvinders van de computer...! Al sinds de jaren 60 is er de zogenoemde ASCII-tabel (ASCII = American Standard Code for Information Interchange). Daarin hebben alle letters en tekens uit het (Amerikaanse) alfabet een getalwaarde gekregen die in de computer wordt gebruikt. Deze tabel is als volgt:

Allereerst een serie zogenoemde stuurcodes, waarvan de meeste in onbruik zijn geraakt.
De belangrijkste die nog gebruikt worden zijn (wijs een blauwe aan voor meer info):
  9 10   13  
  TAB LF   CR  
Vervolgens de "echte" tekens:

Zoals je ziet zijn de cijfers en de letters er keurig op de juiste volgorde in opgenomen, zodat je b.v tekst kunt sorteren op basis van deze getalwaarden! Voor de getallen 128 t/m 255 (255 is het grootste getal dat in een byte past) waren vroeger geen tekens gedefinieerd, maar tegenwoordig staan daar met name de letters met diacritische tekens, zoals bv. á, é, ë, ö, etc.

Een en ander betekent, dat een tekst die in de computer is ingebracht altijd is te beschouwen als een gewone serie getallen, waarbij elk getal in het bereik van 0 t/m 255 valt. Onze geheime boodschap wordt derhalve in het geheugen van de computer opgeslagen als de volgende serie getallen:

Let wel dat deze omzetting naar getallen dus op zich zelf geen encryptie is, het is feitelijk net zo'n vertaalslag als de letterverwisseling die we zojuist ongeschikt hebben bevonden voor deugdelijke encryptie.


Willekeur inbouwen
Stel nu, dat we als codeersleutel een andere lange serie willekeurige getallen hebben, gemaakt met een soort dobbelsteen die van 0 t/m 255 gaat. Bijvoorbeeld:


N.B. deze lijst is met JavaScript naar willekeur bepaald,
als je de pagina ververst wordt het een andere serie.
Dan kunnen we deze lijst onder de getallenserie van de geheime boodschap zetten en dan telkens het zoveelste getal van de boodschap en het "evenveelste" getal van de sleutel bij elkaar optellen. Bij die optelling doen we echter wel iets speciaals: als we boven de 255 uitkomen trekken we er weer 256 vanaf. Daarmee gaat geen informatie verloren (zie onder, wanneer we gaan decoderen) en het resultaat blijft een serie getallen van 0 t/m 255. Als we dat niet zouden doen hebben we twee problemen:
1) we kunnen het resultaat niet meer in een byte opslaan;
2) we voegen informatie toe! Een afluisteraar weet dan immers dat voor die letter de getalwaarde plus de sleutel groter is dan 255, waarmee het aantal uit te proberen mogelijkheden voor hem wordt gehalveerd. En het laatste wat we willen is afluisteraars in de kaart spelen!
Omdat de serie getallen lang is, kunnen we er een tekst tot die lengte mee coderen. Dus, om een begin te maken voor het eerste stukje van onze geheime boodschap:

Zoals je ziet, wordt nu dezelfde letter (bijvoorbeeld de "e") telkens naar een andere waarde omgezet (nou ja, af en toe kan er natuurlijk best een keer hetzelfde uitkomen, oké). De afluisteraar kan dus met zijn statistische kennis van de Nederlandse taal niet veel meer beginnen!

Als we het aldus versleutelde bericht in zijn geheel volgens de ASCII-tabel terugvertalen naar gewone tekens wordt het:

Probeer daar nog maar eens een mooie smartlap van te maken...!

Om eerlijk te zijn: ik heb enkele codes moeten aanpassen omdat je browser er anders geen raad mee weet. Er zijn in de versleutelde boodschap immers getallen ontstaan die op willekeurige plekken in de ASCII-tabel staan, en die zogenoemde onprintbare codes heb ik allemaal vertaald naar het "" teken.

En hoe decodeer je dat? Wel, natuurlijk moet je dan per getal van de versleutelde boodschap het zoveelste getal van de sleutel er weer aftrekken. Kom je daarbij onder de nul, dan tel je er 256 bij op (dit compenseert dus het speciale wat we bij het optellen gedaan hebben).

In plaats van het optellen en aftrekken is er nog een andere bewerking mogelijk, die in de computer veel handiger is, omdat het zijn eigen 'inverse bewerking' is. Dat is de zogenoemde XOR operator, ofwel "exclusive OR". Deze XOR werkt op de afzonderlijke bitjes in een getal (de eentjes en de nulletjes zoals het feitelijk in de computer staat) en geeft aan of twee zulke bitjes wel of niet verschillend zijn. Het leuke is dat we de oorspronkelijke waarde terugkrijgen als we hem twee maal met hetzelfde XOR-en! Zie de volgende tabel, waarin a en b de betreffende bitjes zijn. Met c = a XOR b en d = c XOR b ofwel d = (a XOR b) XOR b zie je dat d weer gelijk is aan a.

ab c = a XOR b d = c XOR b
0000
0110
1011
1101

In de praktijk zullen we dan ook de XOR gebruiken, omdat dan het versleutelen en het ontsleutelen met precies dezelfde methode gedaan kan worden!

Die serie sleutelgetallen moeten we nu dus angstvallig geheimhouden! Alleen de legitieme ontvanger mag er een kopie van hebben. Als nu een afluisteraar de methode ontdekt: gefeliciteerd, maar zonder de serie sleutelgetallen heeft ie daar niets aan. Zonder de sleutelgetallen kan dit niet worden gekraakt, mits de serie sleutelgetallen goed is opgebouwd. De sleutelgetallen moeten zich gedragen als ruis, willekeurige getallen die door toeval zijn ontstaan, zonder dat er een patroon in te herkennen is. Dan is aan de versleutelde boodschap ook weinig tot niets te herkennen.


Schijnbaar willekeurige getallen genereren
Aan deze methode kleeft nog wel een praktisch nadeel: De serie is erg kort, je kunt er (in dit voorbeeld) maximaal tekens mee versleutelen. En tegelijkertijd is hij heel erg lang, dus moeilijk te onthouden (stel je voor dat je zo'n hele serie ergens als wachtwoord zou moeten invullen...). Je zou natuurlijk (de ASCII-waardes van) een gewone volzin als sleutelserie kunnen gebruiken, dat is wel gemakkelijk te onthouden, maar dan is de mate van willekeur in de sleutel ineens ver te zoeken! Voor deugdelijke encryptie is het absoluut nodig dat er geen herkenbaar patroon in zit. Alleen dan kan een afluisteraar er niets mee beginnen.

Wat we zouden willen, is een eenvoudige manier om een onbeperkte serie schijnbaar willekeurige getallen te produceren op basis van een korte geheime code (een wachtwoord). Schijnbaar willekeurig, omdat het namelijk wel degelijk zo in elkaar moet zitten dat je dezelfde serie kunt reproduceren, anders is de boodschap immers niet meer te ontsleutelen. In het Engels heet zo iets een Pseudo Random Number Generator, vaak afgekort als PRNG. Laten we maar eens kijken of we er eentje kunnen maken. Een digitale dobbelsteen.

We gaan een heel simpele PRNG maken, eentje die voortdurend getallen van 1 t/m 6 "uitspuugt", in een min of meer willekeurig patroon. Daarvoor beginnen we met wat we de interne status van de PRNG zullen noemen. Gewoon de getallen 1 t/m 6 in een willekeurige volgorde:

Ververs de pagina en je krijgt een andere status!

We gaan gebruik maken van het feit dat de getallen die in de status staan, ook kunnen worden gebruikt als een index naar een positie in diezelfde status! We gebruiken ook nog twee losse indices, die we i en j zullen noemen, alsmede een hulpindex k. De indices i en j initialiseren we op de waarde 1. Dan gaan we het volgende proces steeds herhalen:

  1. verhoog index i met 1, als het resultaat groter is dan 6 dan trekken we er 6 vanaf;
  2. lees op positie i het getal uit de status;
  3. tel dat op bij j, als het resultaat groter is dan 6 dan trekken we er 6 vanaf;
  4. verwissel in de status de getallen op de posities van de nieuwe i en j;
  5. maak index k gelijk aan de som van de getallen in de status op posities i en j, als het resultaat groter is dan 6 dan trekken we er 6 vanaf;
  6. kies uit de status het getal op positie k, en voeg dat toe aan de uitkomstserie.
Met name stap 4 is hierbij een belangrijke, die zorgt namelijk dat de status bij elke ronde verandert! Laten we dit dus maar eens proberen, en kijken wat er gebeurt. Bij de eerste paar rondes ontstaat de volgende tabel:

Als we met dat proces doorgaan totdat we er 100 hebben wordt dat de volgende serie:

't had zo van een echte dobbelsteen kunnen komen!

En nu kun je het wellicht al raden: die allereerste status is het enige wat we hoeven te onthouden om de hele serie te reproduceren! En een andere beginstatus levert een compleet andere serie op. Probeer dat maar eens, gewoon deze pagina verversen levert al een andere beginstatus en dus een andere serie. En als je die initiële status goed geheim houdt, blijft de hele serie geheim! Die initiële status is dus eigenlijk het wachtwoord!

En nu is dit, met slechts 6 getallen, natuurlijk niet de allerbeste PRNG die we kunnen maken, omdat er maar een beperkt aantal mogelijkheden zijn voor de status. Daardoor is een op basis hiervan versleutelde boodschap met een snelle computer toch in korte tijd te kraken. Gewoon alle mogelijkheden uitproberen zal waarschijnlijk in slechts één geval iets leesbaars opleveren en dat moet dan het oorspronkelijke bericht zijn.

Bovendien gaat deze serie al vrij snel een repeterend karakter krijgen. Op een gegeven moment kom je namelijk met de status en de indices i en j weer terug op de beginsituatie en dan begint de hele serie weer gewoon opnieuw. De getallen 1 t/m 6 kunnen op slechts 6 x 5 x 4 x 3 x 2 x 1 = 720 verschillende volgordes staan en samen met de 36 mogelijke combinaties van i en j betekent dit dat er een periodiciteit is te verwachten van 36 x 720 = stappen. Maar dus toch niet slecht voor zo'n heel erg simpele PRNG! In elk geval ruim voldoende voor een spelletje mens erger je.

Je kunt je ongetwijfeld wel voorstellen dat we een veel betere PRNG krijgen als we ditzelfde trucje uithalen met de getallen 0 t/m 255, en uiteraard heb ik de hierboven gebruikte voorbeeldserie daarmee gemaakt!


Praktisch onkraakbare versleuteling
Als we dan zo'n PRNG hebben op basis van de getallen 0 t/m 255 is die bovendien natuurlijk prima geschikt voor onze doelstelling: het versleutelen van ASCII-gecodeerde teksten. Daarbij hebben we immers ook byte-waardes in het bereik 0 t/m 255. En doordat de initiële status dan een lijst is van de getallen 0 t/m 255 in een willekeurige, voor de afluisteraar onbekende, volgorde, is het aantal mogelijkheden inmiddels zodanig gigantisch groot geworden dat het zelfs met een snelle computer geen optie meer is om simpelweg alle mogelijkheden uit te proberen. Het aantal mogelijke volgordes van 256 verschillende getallen is 256 x 255 x 254 x 253 x ... x 4 x 3 x 2 x 1 en dat is (schrik niet!):
Bijna tienmiljoen maal googol tot de vijfde!
Ter vergelijking: de ouderdom van het heelal, sinds de "big bang", wordt geschat op ongeveer 15 miljard = 15000000000 jaar. In 1 jaar zitten ongeveer 365,25 x 24 x 60 x 60 = seconden, dus de ouderdom van het heelal is ongeveer seconden. Een computer die 1 miljoen statussen (stati?) per seconde kan uitproberen zou dus in de hele leeftijd van het heelal nu ongeveer mogelijkheden hebben uitgeprobeerd. Een getal van slechts cijfers. Die computer is dus nog laaaaang niet klaar! En als we er een miljard van zulke computers tegelijk op hadden gezet, meteen al bij de big bang, dan was het aantal uitgeprobeerde mogelijkheden op dit moment nog steeds pas een getal van slechts cijfers! Om echt alle mogelijkheden uit te proberen met dat arsenaal aan computers is het aantal benodigde jaren een getal van cijfers!

Het op zichzelf heel simpele probleem van alle mogelijkheden uitproberen (een computerprogrammaatje van slechts pakweg 10 tot 20 regels code) is praktisch onoplosbaar vanwege dit gigantische aantal mogelijkheden. Ook onze afluisterende vijand zal dus onze versleutelde berichten niet zomaar even kunnen kraken. Een hele geruststelling.


Wachtwoord in plaats van tabel
Toch heb je wellicht al in de gaten dat we nu toch weer een praktisch probleem hebben. De initiële status is nu ineens een lijst van 256 verschillende getallen, in plaats van de 6 waar we het eerder over hadden. Dat is niet een gemakkelijk te onthouden wachtwoord! Zouden we iets kunnen verzinnen om op basis van een simpel wachtwoord een goede initiële status te produceren? Natuurlijk kunnen we dat!

We doen daarvoor iets soortgelijks als tijdens het produceren van de willekeurige getallen door de PRNG, alleen mengen we er nu de ASCII-waardes van een deugdelijk wachtwoord doorheen. En in plaats van een wachtwoord mag het natuurlijk ook best een wachtzin zijn, waarom zouden we spaties en leestekens verbieden?

We beginnen dan door de status gewoon 'op volgorde' te initialiseren, dus de getallen 0 t/m 255 achter elkaar. Dan gaan we minsten 256 rondes uitvoeren om die status door elkaar te gooien op basis van het wachtwoord. Zo nodig - als het een kort wachtwoord is - gaan we meerdere keren door het wachtwoord heen. En als het een heel lange wachtzin is van meer dan 256 tekens gebruiken we ze allemaal. Verder gebruiken we weer de indices i en j, en ook gebruiken we index k om tekens uit het wachtwoord te lezen. De posities starten op nul (dus b.v. de eerste letter van het wachtwoord staat op positie nul). We beginnen met i = 0, j = 0 en k = 0, en dan doen we de volgende stappen minimaal 256 keer, en vaker als het wachtwoord langer is:

  1. lees op positie i het getal uit de status;
  2. lees op positie k de ASCII-waarde uit het wachtwoord;
  3. tel deze alle twee op bij j, zolang het resultaat groter is dan 255 trek je er 256 vanaf;
  4. verwissel in de status de getallen op posities i en j;
  5. verhoog i met 1, als het meer wordt dan 255 dan 256 ervan aftrekken;
  6. verhoog k met 1, als het gelijk wordt aan de lengte van het wachtwoord dan die lengte ervan aftrekken.
Je ziet dat dit best veel lijkt op de PRNG die we al hadden. Eigenlijk doen we hetzelfde, alleen betrekken we er nu ook het wachtwoord bij. Laten we er maar eens wat mee gaan spelen. Tik hieronder een wachtwoord of -zin in naar keuze, en klik dan op de "Verhuzzelen" button voor de resulterende initiële status van de PRNG.

 

Resulterende status:

Nu zijn we klaar! We hebben alles wat we nodig hebben voor een deugdelijke, vrijwel onkraakbare encryptie met een gemakkelijk te onthouden wachtwoord. Want in tegenstelling tot wat ik boven heb vermeld omtrent het gebrek aan willekeur in een normale zin, geldt die beperking voor deze methode niet. Het wachtwoord geeft namelijk slechts de beginsituatie van een deugdelijke PRNG, terwijl het zelf niet per se een goede pseudowillekeurige serie hoeft te zijn. Overigens is het natuurlijk voor de geheimhouding wel beter als dat wachtwoord een grote mate van willekeur heeft, maar dan is het wel lastiger te onthouden.

zou een behoorlijk goede wachtzin zijn. Niet te raden door wie dan ook. Maar gewoon het koosnaampje van je geheime vriend(innet)je combineren met het telefoonnummer van je tante en nog een woord erbij dat je nooit hardop zou durven zeggen levert ook een heel bruikbare wachtzin op hoor!


Zend- en ontvangprocedure
De procedure voor het zenden en ontvangen van geheime berichten wordt nu als volgt:

Zender:

  1. verhuzzel het wachtwoord tot initiële PRNG-status;
  2. produceer met de PRNG vanuit die status een serie pseudowillekeurige getallen;
  3. XOR alle ASCII-waardes van de geheime boodschap met de overeenkomstige door de PRNG geproduceerde getallen;
  4. verstuur het versleutelde resultaat naar de legitieme ontvanger, afluisteraars zijn welkom!

Legitieme ontvanger:

  1. verhuzzel het juiste wachtwoord tot initiële PRNG-status;
  2. produceer met de PRNG vanuit die status dezelfde serie pseudowillekeurige getallen;
  3. XOR alle ASCII-waardes van de versleutelde boodschap met de overeenkomstige door de PRNG geproduceerde getallen;
  4. lees het resultaat, het is de ontcijferde geheime boodschap!

Afluisteraar:

  1. doe je best!
  2. doe beter je best!
  3. doe ng beter je best!
  4. geef het maar op, het wordt toch niks...


ARCFOUR algoritme
Deze encryptiemethode staat bekend onder de naam ARCFOUR. Dat is een onofficiële variant van de gepatenteerde RC4 algoritme van Ron Rivest ("RC4" = "Rivest Cypher 4" of "Ron's Code"). Die heb je, zonder dat je het hebt gemerkt, waarschijnlijk al vaak gebruikt, telkens wanneer je met je browser een beveiligde pagina hebt bezocht! En heb je een beveiligd draadloos netwerk? Grote kans dat daarin het WEP of het WPA protocol is geimplementeerd, en die gebruiken RC4!

Samengevat doet de ARCFOUR methode dus het volgende:

  • gebruik een wachtwoord om de interne status van een PRNG te initialiseren;
  • start de PRNG;
  • vermeng het te versleutelen bericht met de geproduceerde schijnbaar willekeurige getallen.

De kracht van de versleuteling zit hem in het vermengen van het bericht met schijnbaar willekeurige getallen. Daardoor wordt statistische informatie in het versleutelde resultaat vrijwel volledig gemaskeerd en een afluisteraar kan er dus niets mee beginnen, mits de willekeurige getallen in statistisch opzicht van voldoende kwaliteit zijn. Niet of nauwelijks van ruis te onderscheiden. De versleutelde boodschap gedraagt zich dan zelf ook als een serie willekeurige getallen. Zonder patroon. Zonder statistische kenmerken. Schijnbaar zonder informatie (maar de zender en de legitieme ontvanger weten natuurlijk wel beter...).

Er is trouwens in deze algoritme wel een zwakte ontdekt, het begin van de gegenereerde serie schijnbaar willekeurige getallen bevat namelijk nog wel degelijk traceerbare informatie over het wachtwoord, waardoor het onder bepaalde omstandigheden toch te kraken is. Dit is de zogeheten Fluhrer, Mantin and Shamir attack (zie ook RSA Security Response to Weaknesses in Key Scheduling Algorithm of RC4).
Dit probleem kan enigszins worden verholpen door de PRNG eerst een tijdje te laten "warmdraaien" zonder de gegenereerde getallen te gebruiken, en dan pas vanaf pakweg het 1000ste getal te starten met de eigenlijke versleuteling. Vanwege deze zwakte gebruiken moderne draadloze netwerken tegenwoordig het WPA2 protocol, dat geen RC4 gebruikt.
Overigens kan met deze "attack" niet zo maar een bericht worden gekraakt. Men moet enkele miljoenen met dezelfde sleutel ge-encrypte boodschappen afluisteren en statistisch analyseren om die sleutel te ontdekken. Door regelmatig het wachtwoord te wijzigen wordt dit risico al drastisch verminderd!
En deze pagina geeft slechts wat basisinzicht in encryptie, er zijn natuurlijk véél betere encryptiemethodes bekend en in gebruik.
Encryptie is altijd een wedstrijd tussen de bedenkers en de krakers, en naarmate de techniek vordert en computers steeds krachtiger worden kan men met behulp van zeer ingewikkelde wiskundige methodes steeds meer ontcijferen. Geen enkele encryptiemethode heeft eeuwigheidswaarde.


Vingerafdruk & automatische controle
Wat we nog graag zouden willen toevoegen is een mogelijkheid om automatisch te controleren of de ontvanger van het bericht wel het juiste wachtwoord heeft gebruikt. Anders krijgt hij immers een onleesbaar resultaat. Daarvoor moeten we behalve het bericht zelf, ook nog wat extra informatie in het versleutelde bericht opnemen. Een soort vingerafdruk van het originele bericht, die dan na decoderen uiteraard ongewijzigd moet blijven. Uiteraard zijn er verschillende methodes om zo'n vingerafdruk te maken, je eigen browser kent er een aantal en gebruikt ze regelmatig! In het Engels heet zo'n vingerafdruk een hash. De meest bekende en meest gebruikte zijn de MD5 (Message Digest versie 5) van Rivest, Shamir en Adleman (RSA, die kreet komen we straks nog vaker tegen, en ja, dezelfde Rivest als daarnet) en de SHA (Secure Hash Algorithm) van de Amerikaanse overheid. Maar ik zou natuurlijk Henk Reints niet zijn als ik niet met mijn eigen algoritme op de proppen zou komen...

Wat we gaan doen is het volgende. Precies net zoals we hierboven het wachtwoord "door de mangel" hebben gehaald om een initiële status voor de PRNG te krijgen, doen we dat nu met het bericht zelf. Alleen doen we die initialisatie nu twee keer, zodat ook een heel lang bericht altijd dubbel door de mangel gaat. We gaan dan de PRNG opstarten met deze beginstatus die dus is bepaald door de te versleutelen boodschap zelf. En dan nemen we laten we zeggen de eerste 20 getallen die door die PRNG worden geproduceerd. Dat kunnen we dan als vingerafdruk gebruiken. Overigens zou het vanwege de eerder genoemde zwakte in RC4 beter zijn om dan niet nummer 1 t/m 20 te nemen maar b.v. 1001 t/m 1020, maar om der wille van de eenvoud doe ik dat op deze pagina niet. En bedenk dat deze door mij voorgestelde vingerafdruk hoofdzakelijk is bedoeld als demonstratie, voor de "echtes" zijn er veel betere.

Zo'n vingerafdruk van 20 bytes met willekeurige waardes willen we nog graag wat leesbaarder maken, waarbij ik nog een beetje informatieverlies produceer, door van elke byte slechts de rest bij deling door 64 te nemen. Dan komt er een getal uit van 0 tot 63, in totaal dus 64 mogelijkheden. We gaan de volgende 64 tekens gebruiken voor de vingerafdruk:

Deze tekenset is in de internetwereld geen onbekende, het is de zogenoemde base 64 tekenset, die veel wordt gebruikt om bijlagen van e-mails te coderen, zoals bijvoorbeeld foto's.
De eerste plek in deze reeks noemen we positie nul, en van de 20 getallen van de vingerafdruk van ons bericht hadden we al de rest bij deling door 64 genomen, en dat wijst dus precies een van deze tekens aan. Daarmee krijgen we dan een serie van 20 leesbare tekens als vingerafdruk van ons bericht. De aldus gevormde vingerafdruk van onze smartlap ziet er zo uit:

Zo'n vingerafdruk zegt dus iets over het bericht, hij is er immers direct van afgeleid, maar toch zegt hij niets over de feitelijke inhoud van het bericht. Een ander bericht heeft een andere vingerafdruk. En het is niet zo dat twee berichten die veel op elkaar lijken ongeveer dezelfde vingerafdruk hebben. Je kunt met de vingerafdruk eigenlijk maar één ding vaststellen: het is wel of niet het goede bericht. Als twee onbekende berichten een verschillende vingerafdruk hebben zijn de berichten zeker verschillend, en als ze dezelfde vingerafdruk hebben zijn die berichten hoogstwaarschijnlijk gelijk. Hoogstwaarschijnlijk, want absolute zekerheid heb je niet, bij het bepalen van de vingerafdruk is namelijk per saldo gewoon een hoop informatie verloren gegaan. En dat willen we ook. Een vingerafdruk moet eenrichtingsverkeer zijn. Het moet onmogelijk zijn om vanuit de vingerafdruk het bericht weer terug te vinden, het was immers een geheim bericht! Maar de kans dat twee verschillende berichten dezelfde vingerafdruk hebben is wel hééééél erg klein. Verwaarloosbaar. Met een goede vingerafdruk kun je dus, zelfs als die vingerafdruk onversleuteld is, een bericht identificeren zonder daarvan de inhoud prijs te geven. Hieronder staan enkele voorbeelden van vingerafdrukken van telkens twee sterk op elkaar lijkende berichten:

We gaan nu als volgt versleutelen en ontsleutelen:

Zender:

  1. bepaal de vingerafdruk van het te verzenden bericht en zet die 20 tekens vóór het bericht;
  2. versleutel deze combinatie van vingerafdruk en bericht met het wachtwoord;
  3. verstuur dat naar de legitieme ontvanger.

Ontvanger:

  1. ontsleutel het ontvangen bericht met het wachtwoord;
  2. knip de eerste 20 tekens van het resultaat af, dat zou de vingerafdruk moeten zijn en het resterende deel zou de oorspronkelijke boodschap moeten zijn;
  3. bepaal zelf de vingerafdruk van die vermeende boodschap;
  4. vergelijk die zelf bepaalde vingerafdruk met de afgeknipte meegezonden vingerafdruk;
  5. is dat verschillend? dan was het wachtwoord zeker fout en de ontcijfering dus ook;
  6. is dat gelijk? dan mag je aannemen dat het wachtwoord goed was, je hebt het bericht correct ontcijferd!


JavaScript code
Aangezien we het hebben over encryptie met behulp van computers, moet deze procedure natuurlijk worden geprogrammeerd zodat de computer het ook daadwerkelijk voor je kan gaan doen. Hieronder zie je enkele stukjes JavaScript-code die je kunt gebruiken voor deugdelijke versleuteling van berichten.

function arcfour (bericht, sleutel)
{   // Copyright (c) 2006 Henk-Reints.nl
    // N.B. (c) geldt alleen voor deze js-implementatie, niet voor de algoritme.
    var c, t                                            // benodigde hulpvariabelen
    var resultaat = ""                                  // initialiseer het resultaat
    for (var s = [], i = 0; i < 256; s[i] = i++);       // vul status s met 0 t/m 255
    var i = 0, j = 0, k = 0                             // init indices etc.
    var n = Math.max (s.length, sleutel.length)
    for (var m = 0; m < n; m++)                         // statusinitialisatie
    {   j = (j + s[i] + sleutel.charCodeAt(k) ) % 256   // VERWERK DE SLEUTEL HIERIN
        t = s[i], s[i] = s[j], s[j] = t                 // verwissel s[i] en s[j]
        i = (i + 1) % s.length
        k = (k + 1) % sleutel.length
    }
    for (i = 0, j = 0, m = 0; m < bericht.length; m++)  // PRNG-rondes
    {   i = (i + 1   ) % s.length
        j = (j + s[i]) % s.length
        t = s[i], s[i] = s[j], s[j] = t                 // verwissel s[i] en s[j]
        k = (s[i] + s[j]) % s.length                    // s[k] is volgende PRN
        c = bericht.charCodeAt(m) ^ s[k]                // versleutel volgende letter
        resultaat += String.fromCharCode(c)             // plak die aan resultaat
    }
    return resultaat
}

function vingerafdruk (tekst)
{   // Copyright (c) 2006 Henk-Reints.nl
    // N.B. code is een variant van de arcfour algoritme.
    var c, t
    var resultaat = ""
    var b64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
    for (var s = [], i = 0; i < 256; s[i] = i++);
    var i = 0, j = 0, k = 0
    var n = 2 * Math.max (s.length, tekst.length)   // tekst gaat er 2 keer doorheen!
    for (var m = 0; m < n; m++)                     // statusinitialisatie
    {   j = (j + s[i] + tekst.charCodeAt(k) ) % 256
        t = s[i], s[i] = s[j], s[j] = t
        i = (i + 1) % s.length
        k = (k + 1) % tekst.length
    }
    for (i = 0, j = 0, m = 0; m < 20; m++)      // 20 PRNG-rondes
    {   i = (i + 1   ) % s.length
        j = (j + s[i]) % s.length
        t = s[i], s[i] = s[j], s[j] = t
        k = (s[i] + s[j]) % s.length
        c = s[k] % b64.length           // rest bij deling PRN door 64
        resultaat += b64.charAt(c)      // levert volgende letter
    }
    return resultaat
}

/*****************************************************************************
** Om deze methode te beschermen tegen de "Fluhrer, Mantin and Shamir attack"
** kun je in BEIDE bovenstaande functies n de statusinitialisatie en net vr
** het for-statement van de PRNG de volgende "warmdraaicode" tussenvoegen.
** Je krijgt dan natuurlijk wel ANDERE vingerafdrukken dan de op deze pagina
** getoonde voorbeelden.
    for (i = 0, j = 0, m = 0; m < 1024; m++)
    {   i = (i + 1   ) % s.length
        j = (j + s[i]) % s.length
        t = s[i], s[i] = s[j], s[j] = t
    }
*****************************************************************************/

Verder moet je er rekening mee houden dat in Windows een bericht ook heel speciale tekens kan bevatten, met codes groter dan 255 (Unicode heet dat). In JavaScript is een standaardfunctie beschikbaar om speciale tekens en niet printbare tekens om te zetten naar een gewone ASCII-codering. Dan wordt de interne code van een teken omgezet naar een tekstuele representatie van dat getal. Die functie heet 'escape'. En om dat weer ongedaan te maken gebruik je de 'unescape'. Het is een goede gewoonte om bij versleuteling van teksten die twee functies ook altijd te gebruiken. 'escape' bij het versleutelen en 'unescape' bij het ontsleutelen. Zowel voor het bericht zelf als voor de versleuteling. Dan krijg je de volgende code voor het ver- en ontsleutelen:

function versleutelen (bericht, sleutel)
{   // Copyright (c) 2006 Henk-Reints.nl
    var temp = vingerafdruk (bericht) + escape (bericht)
    var versleuteld = arcfour (temp, sleutel)
    return escape (versleuteld)
}

function ontsleutelen (bericht, sleutel)
{   // Copyright (c) 2006 Henk-Reints.nl
    var versleuteld = unescape (bericht)
    var temp        = arcfour (versleuteld, sleutel)
    var zenderhash  = temp.slice(0,20)
    var ontsleuteld = unescape (temp.slice(20) )
    var testhash    = vingerafdruk (ontsleuteld)
    return (testhash == zenderhash ? ontsleuteld : "### FOUT ###")
}

Het staat je vrij om deze code - mits ongewijzigd en MET bronvermelding - op je eigen website of waar dan ook te gebruiken!


Spelen met ARCFOUR
Hieronder kun je de bovenbenoemde JavaScript functies in werking zien. Tik een bericht in naar keuze, een wachtwoord of -zin voor het versleutelen, en vervolgens hetzelfde of een ander wachtwoord voor het ontsleutelen en kijk wat er gebeurt. N.B. De wachtwoorden worden gewoon getoond, het is immers een demo, maar voor de "echtes" moet je wachtwoorden natuurlijk altijd verborgen houden! Van de getallenseries worden telkens slechts de eerste 40 getoond.

bericht:
vingerafdruk:  
vingerafdruk in ASCII:  
escape(bericht):  
ASCII escape(bericht):  
wachtwoord:
initiële PRNG-status:  
door PRNG gegenereerde serie:  
ASCII te versleutelen:
(vingerafdruk+escape(bericht))
 
ASCII versleuteld:  
escape(versleuteld):
(dit is wat je verzendt!)
 
wachtwoord:
initiële PRNG-status:  
door PRNG gegenereerde serie:  
ASCII unescape(versleuteld):  
ASCII ontsleuteld:  
ASCII vingerafdruk ontsleuteld:  
ASCII escape(bericht):  
vingerafdruk van bericht:  
escape(bericht):  
bericht unescaped:  

Tot zo ver ARCFOUR. We gaan nu eens kijken of we met vingerafdrukken en willekeurige getallen nog meer leuke dingen kunnen doen.


Client/server wachtwoordcontrole
We kunnen deze methode, en wel met name de vingerafdruk, ook gebruiken voor z.g. client/server wachtwoordcontrole. Stel je hebt een server waarop je met gebruikersnaam en wachtwoord moet inloggen vanaf je eigen pc, terwijl er op het tussenliggende netwerk afluisteraars te verwachten zijn. Je wilt natuurlijk niet dat zo'n afluisteraar jouw naam+wachtwoord te pakken krijgt, dus het is géén optie om met name het wachtwoord "in z'n blootje" over het netwerk te verzenden! Je wilt dat versleutelen, maar nu moet de server wel kunnen controleren of je het juiste wachtwoord kent. En dat dus zonder dat het wachtwoord zelf over de lijn gaat! Dat kan bijvoorbeeld op de volgende manier. Uiteraard moet je wel eerst het wachtwoord op de server bekend maken op een versleutelde manier. Daarvoor gebruik je de z.g. asymmetrische encryptie, dat zal ik hieronder nog uitleggen. Dan is het wachtwoord op de server bekend en bij jou zelf, en verder bij niemand.

Op de server zijn dan dus gebruikersnaam+wachtwoord ergens in een bestand opgeslagen. Maar het liefst slaan we het wachtwoord natuurlijk niet leesbaar op! Als iemand het bestand te pakken zou krijgen weet hij dan immers alle wachtwoorden! Van iedereen!

Dat doen we dus anders. Wat we op de server opslaan is de gebruikersnaam plus de vingerafdruk van gebruikersnaam+wachtwoord. Waarom die combinatie? Wel, stel dat we de gebruikersnaam en de vingerafdruk van alleen het wachtwoord opslaan. En stel dat hacker Jan ontdekt dat de vingerafdruk van Piet's wachtwoord gelijk is aan de vingerafdruk van zijn eigen wachtwoord? Dan weet hij dat Piet hetzelfde wachtwoord heeft als hijzelf! Dat voorkom je door de vingerafdruk op te slaan van de combinatie van gebruikersnaam en wachtwoord. Die vingerafdruk is voor Jan en Piet immers verschillend.

Tegelijk is daarmee natuurlijk die vingerafdruk het eigenlijke wachtwoord geworden, dat is namelijk het enige wat de server nog kan controleren. Het blijft dus nog steeds uitermate belangrijk dat het wachtwoordenbestand op de server goed is afgeschermd, men mag het nog steeds niet zomaar kunnen lezen! Door zo'n vingerafdruk op te slaan i.p.v. het wachtwoord zelf wordt het dus alleen maar onmogelijk gemaakt om het oorspronkelijke wachtwoord te achterhalen, maar voor de feitelijke toegangsbeveiliging heeft het nog steeds geen toegevoegde waarde! En het is dus ook geen optie on die vingerafdruk "in z'n blootje" over het netwerk te gaan verzenden... Hoe kunnen we dan toch aan de server laten weten dat we het juiste wachtwoord kennen?

Daarvoor gebruiken we een zogeheten nonce. Dat is een uniek en willekeurig stukje tekst voor eenmalig gebruik. Die wordt ook maar één keer over het netwerk verzonden. Zo'n nonce bevat meestal de datum+tijd waarop hij is gegenereerd, waardoor het al uniek wordt, plus verder een volslagen willekeurig stukje tekst van een zekere lengte. Het liefst gemaakt met een echte Random Number Generator, gebaseerd op echte ruis, dus niet reproduceerbaar en absoluut onvoorspelbaar. Zo'n RNG moet dan niet volledig rekenkundig zijn bepaald, maar ook gegevens "van buitenaf" verwerken, zoals bijvoorbeeld tijdstippen van door gebruikers gedane toetsaanslagen of muisbewegingen. Ook het exacte "pad" dat een muis aflegt is zelfs voor een gebruiker met bijzonder vaste hand niet precies tot op de pixel en milliseconde reproduceerbaar en kan dus als basis dienen voor en goede RNG. Een nonce zou er bijvoorbeeld zo uit kunnen zien:

Die nonce wordt gegenereerd door de server en dan naar de client verzonden. Op de client moet jij dan je gebruikersnaam en wachtwoord intikken. Vervolgens doet jouw client-software het volgende:

  1. bepaal de vingerafdruk van ingevoerde gebruikersnaam+wachtwoord;
  2. plak daar de van de server ontvangen nonce achter;
  3. bepaal van die combinatie opnieuw de vingerafdruk
    (ja, je kunt ook een vingerafdruk maken van een vingerafdruk!);
  4. zend de gebruikersnaam plus die laatste vingerafdruk naar de server.

En de server doet het volgende:

  1. genereer een nonce en zend die naar de client;
  2. wacht op de door de client teruggestuurde gebruikersnaam+vingerafdruk;
  3. zoek bij de teruggezonden gebruikernaam in het "gebruikersbestand" de vingerafdruk van naam+wachtwoord zoals dat al op de server bekend is;
  4. plak daar de verzonden nonce achter;
  5. bepaal van die combinatie de vingerafdruk;
  6. klopt die met de door de client gestuurde vingerafdruk? Dan mag je aannemen dat de gebruiker het juiste wachtwoord kent. Hij is degene die hij zegt te zijn.
  7. klopt dat niet? Dan heeft de gebruiker op de client zeker een fout wachtwoord ingevoerd en hij is dus nog steeds een onbekend persoon.

De kracht van deze methode zit hem in het slechts één keer gebruiken (en met name verzenden) van die nonce, en in het combineren daarvan met de geheime informatie (de vingerafdruk van naam+wachtwoord). En daarvan dan weer de vingerafdruk. Die is onvoorspelbaar en onomkeerbaar. En omdat de nonce slechts één keer wordt gebruikt gaat die vingerafdruk ook maar 1 keer over het netwerk. En dan is het - gewoon door het gigantisch aantal mogelijkheden - niet te ontcijferen. Omdat er veeeel te weinig en veeeel te trage computers in het veeeel te jonge heelal zijn... Daarom moet het maken van een goede vingerafdruk dus éénrichtingsverkeer zijn, zoals al eerder gezegd. Dan kun je er de oorspronkelijke informatie mee geheim houden terwijl je wel kunt bewijzen dat je die informatie kent. Bovendien heeft een goede nonce een beperkte geldigheid, de server houdt bij op welk tijdstip de nonce is verzonden en accepteert alleen maar antwoorden die binnen een bepaalde tijd terugkomen. En alleen maar van dezelfde computer als waar de nonce heen is gestuurd.

Dit principe, waarbij je dus middels de nonce door de server wordt "uitgedaagd" om te bewijzen dat je het juiste wachtwoord kent, wordt meestal aangeduid met de term challenge/response.


Authenticatie & autorisatie
De termen authenticatie en autorisatie kom je veelvuldig tegen als het gaat om wachtwoordcontroles en het toelaten van gebruikers. Het lijkt me nuttig om even het verschill tussen die twee begrippen uit te leggen.

Authenticatie
(staat voor zo ver ik kan vinden overigens niet in Van Dale, dus beschouw het maar als een vakterm) is het vaststellen dat de gebruiker daadwerkelijk degene is die hij zegt te zijn. Niet meer dan dat. Ik kan wel zeggen dat ik Henk Reints ben, maar je mag best verlangen dat ik daar een deugdelijk bewijs van geef. Bijvoorbeeld door mij met een officieel document zoals paspoort of rijbewijs te legitimeren. Of, nadat ik me persoonlijk heb gelegitimeerd, op basis van een wachtwoord dat jij mij hebt gegeven en waarvan jij zelf zeker weet dat je het alleen maar aan mij hebt gegeven. Als ik daarna laat blijken dat ik dat wachtwoord ken heb jij het bewijs dat ik Henk Reints ben. Zolang jij er tenminste vertrouwen in hebt dat ik mijn wachtwoord zelf geheim houd. En dat vertrouwen krijg je door mij persoonlijk aansprakelijk te stellen voor alles wat er onder mijn gebruikersnaam wordt gedaan. Ik ben dan zuinig op mijn wachtwoord. Net zo zuinig als op mijn pincode.

Autorisatie
is volgens Van Dale het verlenen van bevoegdheid. Ofwel het toestaan om bepaalde handelingen te verrichten. En dat gebeurt pas nadat je weet aan wie je die bevoegdheid geeft. En het kan heel goed zijn dat iemand na authenticatie nergens voor ge-autoriseerd is. Als jij weet dat ik die beruchte bankrover ben, geef je me geen toegang tot de kluis.

De procedure is dus altijd een tweetrapsraket: eerst vaststellen wie je bent en daarna pas bepalen wat je mag. Authenticatie doe je op basis van gebruikersnaam plus wachtwoord, autorisatie doe je uitsluitend op basis van de gebruikersnaam, nadat authenticatie heeft plaatsgevonden. De hierboven uitgelegde client/server wachtwoordcontrole is authenticatie. Geen autorisatie.


(A)symmetrische encryptie
En dan nog dit. ARCFOUR is een symmetrische encryptiemethode, d.w.z. dat je voor het versleutelen en ontsleutelen dezelfde sleutel (wachtwoord) moet gebruiken.

Er bestaat ook asymmetrische encryptie, dan heb je daarvoor twee verschillende sleutels nodig. Dus een soort kluisje met een heel speciaal slot en twee verschillende sleutels. Als het open is kun je het met elk van die sleutels op slot doen, maar als het op slot is kan het alleen maar worden geopend met de andere sleutel. Ik heb één van die sleutels, jij de andere. Als ik dan het gesloten kluisje ontvang en het met mijn sleutel kan open maken weet ik absoluut zeker dat jij het met jouw sleutel op slot hebt gedaan. En omgekeerd. Maar de asymmetrie gaat nog een beetje verder. Stel dat ik zelf dat slot met die sleutels heb laten maken. De ene sleutel houd ik zelf en ik zorg dat niemand er aan kan komen. Mijn privésleutel. Om hem te herkennen kleur ik hem rood. Van de andere sleutel maak ik een heleboel kopieën en die kleur ik groen. Ik geef iedereen die met mij wil communiceren zo'n kopie. De publieke sleutel dus.

Nu is niet alleen de encryptie asymmetrisch, maar ook de communicatie die we op die basis gaan verrichten. De communicatie van mij naar jou houdt alleen maar in dat ik mijzelf kan identificeren. Ik ben immers de enige met de rode sleutel, dus als jij van mij zo'n kluisje krijgt en je kunt het met jouw groene sleutel openen, dan weet je zeker dat het van mij komt. Zeker als er dan een briefje in zit met mijn handtekening. Je communiceert dus echt met mij en niet met iemand anders die net doet alsof hij mij is.

De communicatie van jou naar mij is nu uitermate geschikt om vertrouwelijke informatie naar mij te versturen. Je hebt bijvoorbeeld iets bij mij gekocht wat je moet betalen en daarvoor schrijf je je creditcardnummer op een briefje met ook je handtekening. Dat doe je in het kluisje en je doet het op slot met de groene sleutel. Vanaf dat moment kan niemand het nog openmaken, behalve ik. Zelfs jijzelf kunt het niet meer openen! Al die andere mensen met een groene sleutel hebben daar niets aan, want het kluisje is door jou met de groene sleutel op slot gedaan, dus het kan alleen nog maar open met mijn rode privésleutel. Je weet dan zeker dat je je creditcardnummer alleen maar naar mij stuurt en niet naar een of andere oplichter.

Hoe krijg je dat nu voor elkaar in een digitale vorm? Wel, daar is echt hogere wiskunde voor nodig. Getallentheorie in ultima forma. Ik zal daar niet tot in alle details op ingaan, en het wiskundige bewijs waarom het werkt laat ik ook achterwege. Alleen het principe ga ik uitleggen.


Grote priemgetallen
De methode werkt op basis van heel erg grote priemgetallen. Getallen van tenminste honderd vijftig cijfers. Voor wie het nog niet wist: priemgetallen zijn getallen die je nergens door kunt delen, behalve door 1 en door zichzelf. En oh ja, met "kunnen delen" bedoel ik natuurlijk delen zonder dat er een "rest" overblijft. En priemgetallen zijn altijd gehele getallen groter dan 1. En het getal 1 wordt nadrukkelijk niet tot de priemgetallen gerekend. Het kleinste priemgetal is dus 2, dat kun je immers alleen maar delen door 1 of door 2. En, als je even een beetje zelf nadenkt kun je er gemakkelijk nog meer vinden. En het moge duidelijk zijn dat 2 het enige even priemgetal is, alle andere zijn oneven.

"All prime numbers are odd, except two, which is even.
That makes two the oddest prime of all..."

De eerste 100 priemgetallen zijn:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541

Nu is het zo, dat het vinden van priemgetallen op zich gemakkelijk is, maar naarmate ze groter worden wordt het wel steeds bewerkelijker. Er is namelijk geen methode bekend om priemgetallen via een of andere formule te produceren. Als je een serie priemgetallen hebt, kun je niet van daaruit snel uitrekenen wat het volgende priemgetal is. En zoals je in bovenstaand lijstje al kunt zien komen er bij priemgetallen af en toe "tweelingen" voor, priemgetallen die twee opeenvolgende oneven getallen zijn. Met een verschil van twee dus. En zulke tweelingen blijven voorkomen in de lijst van priemgetallen, ook bij de heel erg grote. Dit betekent kortgezegd dat de enige manier om de volledige serie van grote priemgetallen te vinden is om letterlijk alle oneven getallen te testen op deelbaarheid!

Priemgetallen die we gemakkelijk als opeenvolgende serie kunnen vinden noemen we kleine priemgetallen. Maar vergis je niet, klein is hier een betrekkelijk begrip. We praten wel degelijk over heel grote getallen. Maar vanaf een zekere waarde is de lijst niet meer compleet. De "priemgetallenjagers" blijven echter wel op zoek en de lijst van bekende kleine priemgetallen wordt dus steeds langer. Maar feit is dat er op een gegeven moment dus gaten in de lijst vallen.

Testen of één groot getal wel of niet priem is kan overigens best in een redelijk korte tijd. Daar hebben wiskundigen slimme methodes voor kunnen bedenken. Overigens wel voer voor een computer, met de hand hoef je daar echt niet aan te beginnen. Vergelijk het met de (bekende?) deelbaarheidsregeltjes zoals bijvoorbeeld: een getal is deelbaar door 5 als het eindigt op 0 of 5 en het is deelbaar door 9 als de som der cijfers deelbaar is door 9. Je hoeft de eigenlijke deling niet uit te proberen om te kijken of het lukt. Op zo'n soort manier werkt ook de "priemcontrole", maar dan natuurlijk toch wel iets ingewikkelder. Voor heel grote getallen moet je dan denken aan een computer-rekentijd van pakweg een tiende seconde of zo. Per test. Als je dus bijvoorbeeld alle priemgetallen van 50 cijfers zou willen vinden, moet je alle oneven getallen van 50 cijfers testen. Dat zijn dus alle oneven getallen

van: 10000000000000000000000000000000000000000000000001
t/m: 99999999999999999999999999999999999999999999999997
(snap je waarom het onderste getal op "7" eindigt en niet op "9"?).

Het aantal tests dat je moet doen is dan ook een getal van 50 cijfers. Laten we een supercomputer bedenken die 1 miljoen zulke tests per seconde kan doen. En dat we 1 miljard van zulke computers aan het werk kunnen zetten. Dus 1 miljard maal 1 miljoen = 1000000000000000 tests per seconde, een getal van 16 cijfers. Dan is, om de lijst compleet te maken, de totale benodigde rekentijd in seconden dus een getal van 50 - 16 = 34 cijfers. Met de pakweg 30 miljoen seconden die er in een jaar zitten dus een aantal jaren van 26 cijfers. Hadden we hierboven al niet een beetje gerekend met de leeftijd van het heelal? Het is dus doodgewoon praktisch onmogelijk om de lijst van grote priemgetallen "helemaal vol" te krijgen! De lijst van bekende priemgetallen van zeg 150 cijfers is dus vrijwel helemaal leeg! (Kijk ook eens hier als je daar nog wat meer inzicht in wilt krijgen.)

Maar als we een willekeurig getal van 150 cijfers willen testen op deelbaarheid zijn we toch in pakweg een tiende seconde klaar. En er zijn veel priemgetallen, dus na niet al te veel (willekeurige) pogingen vind je er gewoon een. Het is dus niet zo moeilijk om twee verschillende priemgetallen te vinden van elk 150 cijfers. En als je die dan met elkaar vermenigvuldigt krijg je een getal van 300 cijfers.

Stel nu dat je zo'n getal van 300 cijfers krijgt, wetend dat het een product is van twee grote priemgetallen, maar je weet niet welke priemgetallen dat zijn. Kun je die dan gemakkelijk terugvinden uit dat getal van 300 cijfers? Forget it! (Mits die priemgetallen verschillend waren, want worteltrekken is ook bij 300 cijfers een fluitje van een cent.) Dat getal van 300 cijfers is immers alleen maar deelbaar door die twee priemgetallen en verder helemaal nergens door. Als je die twee priemgetallen niet weet vind je ze ook niet. Want dan zou je dat getal van 300 cijfers moeten proberen te delen door alle priemgetallen tot dat je de kleinste van die twee tegenkomt. Zodra het delen zou lukken heb je natuurlijk het andere priemgetal ook, maar omdat het vinden van het eerste priemgetal dus onmogelijk is kom je er niet uit. Je zoekt niet een speld in een hooiberg, nee, zelfs niet 1 atoom in het hele heelal! Astronomen schatten het totaal aantal atomen in het hele heelal (voor zover we het kennen) op een getal van 81 cijfers, dus dat kan niet tippen aan onze priemgetallen van 150 cijfers!

Nog even dit: elk natuurlijk getal is ofwel een priemgetal dan wel te schrijven als een product van priemgetallen, waarbij hetzelfde priemgetal best meer dan 1 keer mag voorkomen. Bijvoorbeeld:

2 = priem,
3 = priem,
4 = 2 x 2,
5 = priem,
6 = 2 x 3,
7 = priem,
8 = 2 x 2 x 2,
9 = 3 x 3,
10 = 2 x 5,
11 = priem,
12 = 2 x 2 x 3,
33 = 3 x 11,
35 = 5 x 7.

Het proces om van een getal die samenstellende priemgetallen te vinden heet "ontbinden in priemfactoren". En nog een begrip dat nodig is: "copriem". Simpel gezegd: één getal is priem als er geen enkel getal is waar je het door kan delen, twee getallen zijn copriem als er geen enkel getal is waar je ze allebei door kunt delen. Of, in een betere wiskundige formulering: twee getallen zijn copriem als de grootste gemene deler 1 is. In het lijstje hierboven zie je dat bijvoorbeeld 33 en 35 copriem zijn. Geen gemeenschappelijke priemfactoren.


RSA-methode
Drie Amerikaanse wiskundigen/cryptologen, Rivest, Shamir en Adleman, hebben op basis van zulke grote priemgetallen de naar hen genoemde RSA-methode ontwikkeld. De onkraakbaarheid zit hem in de zo juist beschreven onmogelijkheid om uit zo'n getal van 300 cijfers de oorspronkelijke twee priemgetallen terug te vinden. En verder nog een leuk stukje wiskunde.

Overigens, voor alle duidelijkheid: er bestaat géén wiskundig bewijs dat ontbinden in priemfactoren de enige manier zou zijn om de RSA-methode te kraken, en er bestaat ook géén wiskundig bewijs dat ontbinden in priemfactoren niet heel snel zou kunnen. Alleen weet men geen enkele snelle methode voor het ontbinden in priemfactoren en we weten geen andere methode om RSA te kraken. En de heren wiskundigen zijn er wel degelijk heel sterk van overtuigd dat die twee dingen niet kunnen. Maar er is dus geen bewijs voor. Zodra iemand wel een snelle methode zou vinden is het hele principe volslagen waardeloos, en dan heeft de hele wereld ineens een heel groot probleem als het bijvoorbeeld gaat om electronisch betalingsverkeer!

Verder definiëren we nog de z.g. mod operator ('mod' staat voor 'modulo'). Met die operator bepaal je de rest bij deling, dus b.v. 12 mod 7 = 5. Je kunt je afvragen: wat heeft dat voor nut, alleen maar de rest bij deling en het quotient weggooien? Nou denk eens aan de klok. Die is modulo 12. We zijn vaak alleen geïnteresseerd in het tijdstip op de dag, niet in het aantal dagen dat sinds een of andere datum is verstreken. En soms zijn we wel geïnteresseerd in de dag, en dat doen we dus modulo 7. En de maanden doen we modulo 12. Dus zo raar is die 'mod' operator niet...

De RSA methode gaat nu als volgt.
Allereerst het genereren van een sleutelpaar:

  1. vind twee verschillende priemgetallen, P en Q;
  2. bereken N = P x Q;
  3. bereken R = (P-1) x (Q-1);
  4. vind een (niet al te groot) getal E dat copriem is met R;
  5. vind het getal D zodanig dat (D x E) mod R = 1;
  6. publiceer de getallen E en N als de publieke sleutel;
  7. bewaar de getallen D en N als de privésleutel.
Het getal D moet je angstvallig geheim houden! Dat is onderdeel van de privésleutel. En de waarde van D is alleen maar te vinden als je E en R kent. Dus je moet R ook geheimhouden! en dus ook P en Q, want daaruit is R bepaald. In de praktijk worden P, Q en R weggegooid. Niet bewaren die getallen! Dan zijn P en Q dus weer onbekend en uit N kun je ze niet terugvinden. Mits P en Q groot genoeg waren. 150 cijfers of daaromtrent. Dan kan een kraker nooit vinden wat D is. En dat hoort ook zo, het is jouw eigen geheime privésleutel!

Nu we zo'n sleutelpaar hebben gaat de encryptie en decryptie als volgt, en dat is het wiskundige "foefje" waardoor de encryptie asymmetrisch is. Je gaat met de publieke sleutel [E,N] een boodschap versleutelen en naar een server zenden die over de privésleutel [D,N] beschikt:

  1. stel het te verzenden geheim is het getal M, waarbij M kleiner moet zijn dan N;
  2. de zender berekent C = M E mod N;
  3. de zender stuurt C naar de server; 
  4. de server berekent M = C D mod N;
  5. daarmee is de boodschap ontsleuteld! 
Het leuke is dat hier dus toch weer een bepaalde symmetrie inzit:

  C = ME mod N
en M = CD mod N

Je zou nu wellicht kunnen denken dat je uit deze laatse symmetrie gemakkelijk D kunt bepalen als je M en C kent, terwijl N uiteraard ook bekend is. Nou, niet dus. Ook hier is het aantal uit te proberen mogelijkheden namelijk weer te groot voor het heelal.

En zoals je aan die symmetrie ook kunt zien maakt het dus eigenlijk niet uit wat je als de boodschap beschouwt, M of C. Maar er is dus wel een ander soort asymmetrie aanwezig: wat de server versleutelt met [D,N] kan worden ontsleuteld door iedereen die de publieke sleutel [E,N] heeft. Dus niet geschikt voor geheimhouding. En wat met [E,N] is versleuteld kan uitsluitend door de server met [D,N] weer worden ontsleuteld. Dus wel geschikt voor geheimhouding.

Op Paj's Home vind je een goede wiskundige verhandeling over de RSA-methode, en op de site van Leemon Baird kun je leuk met RSA spelen (maar dan wel met kleinere priemgetallen, het is een demopagina).


Digitale handtekening
Als ik een privésleutel [D,N] heb en jij de bijbehorende publieke sleutel [E,N], dan kan ik het volgende doen. Ik heb een bericht voor jou dat op zich niet geheim is. Ik bereken van dat bericht de vingerafdruk. Die vingerafdruk versleutel ik met [D,N]. Dat is mijn digitale handtekening. Ik stuur het - niet versleutelde - bericht naar jou, samen met de digitale handtekening, dus de versleutelde vingerafdruk van dat bericht. Jij ontvangt het bericht en ontsleutelt de door mij meegezonden vingerafdruk met de publieke sleutel [E,N]. Je berekent zelf ook de vingerafdruk van het bericht en die vergelijk je met de ontsleutelde door mij meegezonden vingerafdruk. Als die gelijk zijn weet je zeker dat het bericht van mij afkomt en van niemand anders. Bovendien weet je zeker dat het bericht identiek is aan wat ik heb verzonden. Niemand heeft het onderweg gewijzigd. Maar het bericht zelf was dus niet versleuteld! Het was openbare informatie.


Symmetrisch en asymmetrisch gecombineerd
Zoals je wellicht al hebt gezien is er een beperking in de RSA-methode ten aanzien van de grootte van het bericht. Dat moet een getal M zijn, kleiner dan N. Een tekst naar één groot getal omzetten is niet zo moeilijk, bij wijze van spreken kun je gewoon de hele serie ASCII-codes achter elkaar zetten en dat als 1 getal beschouwen. Maar N is 300 cijfers of daaromtrent, dus dat stelt een maximum aan de te coderen tekst. Je kunt natuurlijk de tekst "in mootjes" hakken en elk gedeelte afzonderlijk versleutelen, maar dan loop je tegen de volgende beperking aan: het rekenwerk met zulke grote getallen is zelfs voor een computer geen sinecure. Het is dus een nogal trage methode.

Hoe gaan we dan in de praktijk te werk? Nou gewoon zo: Jij maakt contact met mijn server, ik stuur jou een op zichzelf onbelangrijk bericht met mijn digitale handtekening. Dan kun jij verifiëren dat je daadwerkelijk met mij verbinding hebt en met niemand anders. Vervolgens genereer jij op jouw eigen pc met een PRNG een volslagen willekeurig stukje tekst, dat op dat moment dus niemand kent behalve jij. Dat stukje tekst versleutel je met de publieke sleutel en je stuurt dat naar mij. Niemand kan het ontsleutelen, behalve ikke! Dan zijn wij met z'n tweetjes de enigen die dat door jou gegenereerde stukje tekst kennen. En verder helemaal niemand. Maar dan kunnen we dat stukje tekst toch gewoon gebruiken als sleutel voor symmetrische encryptie? Dat gaat wel snel!


Certificaten
Geheime informatie noemen we ook wel vertrouwelijk. Dat is de kern van de zaak: vertrouwen. Als jij mij persoonlijk kent (en vertrouwt) en je krijgt van mij een cd'tje met daarop mijn publieke sleutel, dan mag je er behoorlijk zeker van zijn dat mijn digitale handtekening ook inderdaad mijn digitale handtekening is en dat je veilig geheime, vertrouwelijke informatie naar mij kunt sturen. Maar als je mij niet kent en ik stuur jou zomaar een berichtje met de mededeling: "Alsjeblieft, hier heb je een publieke sleutel en mijn digitale handtekening!", ben ik dan te vertrouwen? Iedereen kan wel een RSA-sleutelpaar genereren en jou de publieke sleutel sturen en vertellen dat ze iemand zijn. En dan je creditcardnummer bemachtigen! Hoe weet je nu dat de andere partij echt degene is die hij zegt te zijn, als je niet in staat bent om dat persoonlijk te controleren? Als je via internet iets koopt doe je dat om nu juist niet zelf naar die winkel te hoeven gaan. En je kunt daardoor ook "ver over de grens" iets kopen vanuit je huiskamer. En je wilt natuurlijk wel dat je met een betrouwbare verkoopsite te maken hebt.

Welnu, stel dat een andere instantie voor jou wel betrouwbaar is, bijvoorbeeld een notaris die in een officieel document verklaart dat ik mij bij hem persoonlijk heb gelegitimeerd en dat mijn digitale handtekening legitiem is, dan kun je mij wel vertrouwen, nietwaar? En een dergelijke procedure wordt dus gevolgd. Instanties die betrouwbaar willen en moeten zijn, zullen niet zomaar zelf een sleutelpaar genereren. Zij gaan daarvoor naar een zogeheten Certifying Authority, dat is een instelling vergelijkbaar met een notariskantoor. Verisign en Thawte zijn bijvoorbeeld bekende C.A.'s, de kans is groot dat je die namen al eens op je beeldscherm hebt gehad in een pop-up venster om te bevestigen of je een of andere website wilt vertrouwen.

Die C.A. genereert dan voor jou een sleutelpaar, nadat jij je persoonlijk bij hen hebt gelegitimeerd. Met een officieel document. Paspoort of rijbewijs of zo. En als je daar namens een bedrijf komt moet je ook een inschrijvingsbewijs van de Kamer van Koophandel overleggen. Vervolgens krijg jij dat sleutelpaar plus een digitaal certificaat, waarin de C.A. verklaart dat ze jouw identiteit persoonlijk hebben vastgesteld via deugdelijke legitimatie en dat jij de enige houder bent van dat sleutelpaar. Jij hebt dan natuurlijk de verplichting om jouw privésleutel goed geheim te houden! En, net zoals de notaris zijn documenten ondertekent met zijn eigen handtekening, is dat certificaat voorzien van de digitale handtekening van de C.A. zelf.

In het vorige hoofdstukje had ik geschreven: "Ik stuur jou een op zichzelf onbelangrijk bericht met mijn digitale handtekening". Nou, zo onbelangrijk is dat bericht helemaal niet, ik stuur namelijk een kopie van mijn certificaat! Daarmee krijg je mijn publieke sleutel toegestuurd en het bevat de identificatie plus digitale handtekening van de Certifying Authority. Vergelijk het met een door mij gesigneerde kopie van de notarisverklaring. Als je het certificaat niet vertrouwt kun je zelf naar de website van de genoemde C.A. gaan en daar nog een kopie van dat certificaat opvragen. Die moet dan identiek zijn aan wat ik heb meegestuurd en dan weet je dat het certificaat echt van die C.A. afkomt en dat die sleutel dus echt door hen aan mij is uitgereikt. En als jij het dan vertrouwt, kun je met je creditcardnummer iets bij mij kopen. Veilig.

En als je de C.A. niet vertrouwt? Wel, dan kun je ter verificatie een certificaat ophalen van een overkoepelende organisatie, die met weer een eigen digitale handtekening verklaart dat die C.A. wel degelijk betrouwbaar is. Vergelijk dat met een verklaring van de bond van notarissen waarin staat dat de betreffende notaris betrouwbaar is. Met handtekening van de voorzitter van de bond van notarissen. Dan wordt dus door een betrouwbare notaris verklaard dat mijn website betrouwbaar is. Nou, dan kun je mij echt wel vertrouwen hoor! Of toch niet? Wie zegt dat de bond van notarissen betrouwbaar is? Afijn, dit spelletje kunnen we eindeloos herhalen, met certificaat op certificaat op certificaat etc. Ergens kom je op het punt dat jij zelf de knoop moet doorhakken en kiezen: "ik vertrouw de ander wel of niet." En als dat "niet" is moet je van die site wegsurfen en er niets kopen met je creditcard. Alleen jijzelf maakt uiteindelijk uit hoe betrouwbaar jij een andere partij vindt.

Verder: ik kan wel zeggen en bewijzen dat ik Henk Reints ben en jij kunt er volledig van overtuigd zijn dat ik inderdaad Henk Reints ben, maar dat betekent nog steeds niet dat ik betrouwbaar ben... Met handtekening en certificatie bewijs je uiteindelijk alleen maar dat je bent wie je zegt te zijn, niet meer dan dat.


Vertrouwen
Ongetwijfeld heb je weleens gesurft naar een beveiligde site. Zo'n internetadres begint dan met "https://" in plaats van "http://". De "s" van "secure" is toegevoegd. Ook krijg je rechtsonder (althans bij Microsoft Internet Explorer) een "hangslotje" te zien dat aangeeft dat je op dat moment via een beveiligde, dus versleutelde verbinding werkt. En dat werkt precies op de manier zoals boven omschreven. Je browser regelt het allemaal. De controle van de certificaten, het genereren van een tijdelijke symmetrische sleutel, het ontsleutelen van ontvangen berichten en versleutelen van de verzonden informatie. Je hoeft je er niet druk om te maken.

Overigens moet je ook de software die je gebruikt kunnen vertrouwen. Ik kan jou best een programmaatje sturen en erbij zeggen dat het een deugdelijke versleuteling doet en dat je daarmee dus beveiligde websites kunt bezoeken, maar wat als ik er stiekem iets heb ingebouwd dat jouw creditcardgegevens toch onbeschermd in mijn eigen database opslaat? Zodat ik daarna op jouw kosten kan gaan feestbeesten? Zou Internet Explorer wel betrouwbaar zijn? En Netscape? Of Opera, of ...? Wel als ze digitaal zijn ondertekend met een certificaat van een betrouwbare C.A.

En op jouw pc staat ergens een lijst van betrouwbare Certifying Authorities, d.w.z. dat jij de certificaten van die instanties vertrouwt, zodat je niet bij elk bezoek aan een site met zo'n certificaat telkens opnieuw op "OK" hoeft te klikken om te vertellen dat jij die site vertrouwt. Soms bezoek je een site met een certificaat van een C.A. die niet in die lijst staat, en dan krijg je wel een venstertje om te vertellen of je wel of niet verder durft te gaan. Als je het niet vertrouwt moet je dan niet op "OK" klikken!

Wellicht kun je je niet herinneren dat je ooit die lijst van betrouwbare C.A.'s hebt ingevoerd. Dat heb je ook niet. Je weet die lijst waarschijnlijk niet eens te vinden! (klik hier voor een voorbeeld). Microsoft heeft die lijst bij de installatie van Windows alvast voor je klaargezet. Vertrouw jij Microsoft?

Cirkels zijn rond... Het hele verhaal begint en eindigt met vertrouwen. Als je iemand niet vertrouwt moet je hem nooit een geheim vertellen. Zelfs niet zeggen dat je een geheim hebt.

Alleen een geheim geheim is geheim.


Steganografie
En om die laatste zin waar te maken moet je dus niemand laten zien dat je een geheime boodschap hebt.

Behalve dat je informatie kunt versleutelen, waarmee je de boodschap voor outsiders onleesbaar maakt, is het ook nog mogelijk een boodschap zodanig te verbergen dat het zo goed als onherkenbaar wordt dat je überhaupt een geheime boodschap verstuurt. Want zeg nou zelf, als een afluisteraar ziet dat ik jou een serie tekens stuur waar op geen enkele manier iets zinnigs van te maken is, dan kan hij gemakkelijk veronderstellen dat het een versleutelde boodschap is. En de C.I.A. zal het toch wel heel erg verdacht vinden als ik kennelijk versleutelde boodschappen aan het versturen ben.

Maar als ik jou nou eens een leuke zelfgemaakte vakantiefoto stuur met een begeleidende tekst die ook over mijn vakantie gaat, dan heeft de afluisteraar waarschijnlijk niets in de gaten. En in die foto kan dan een geheime boodschap verborgen zitten. Want de precieze waarden van de kleuren en helderheden van elk beeldpunt in de foto komen niet zo heel erg nauw voor het menselijk oog, toch? Heel kleine nuanceverschillen zien we doodgewoon niet. Dat betekent dat we best een paar bitjes van een foto kunnen "stelen" om er een geheime boodschap in te zetten.

Zo iets heet steganografie. Het verbergen van informatie. Het beste is het natuurlijk als je de informatie zowel versleutelt als verstopt. Dan wordt de kans dat men je boodschap vindt wel heel erg klein. Overigens zijn er natuurlijk wel weer heel erg geavanceerde statistische analysemethodes om te proberen te achterhalen of een foto geheime informatie bevat. Maar je kunt het de tegenstander wel heel erg moeilijk maken, zo niet onmogelijk, om met zekerheid vast te stellen dat je een boodschap hebt en wat dan die boodschap is.

Van mijn javascriptpagina kun je enkele kant en klare scripts downloaden om bestanden te versleutelen of steganografisch in foto's te verstoppen. Overigens is die pagina in het Engels. En let wel, het zijn en blijven slechts voorbeeldscripts, de gebruikte algoritmes zijn niet goed genoeg voor militaire toepassingen.


Links naar andere websites
Uiteraard kun je op internet nog veel meer informatie over encryptie vinden.
De onderstaande heb ik alvast voor je op een rijtje gezet.




 

N.B.
Ik heb een reactie gekregen op deze pagina met de opmerking dat er "geen woord Chinees" in stond.
Dat wil ik bij deze graag corrigeren: Babi Pangang!