Voor een middagje shoppen hoef je eigenlijk de voordeur niet meer uit. Ga naar de website van je favoriete winkels, klik aan wat je wilt hebben, en de volgende dag gaat de deurbel: het is de postbode met je bestelling. Betalen hoeft niet aan de deur, dat heb je al gedaan door je creditcardgegevens op de website in te vullen. We vertrouwen erop dat dit betaalverkeer veilig gebeurt, daarvoor bestaat immers cryptografie.
Publieke cryptografie
Om informatie over het internet te versturen gebruiken we asymmetrische, of publieke, cryptografie. Dit werkt heel simpel: laat het publiek weten hoe ze een bericht gericht aan jou moeten coderen, en gebruik je geheime sleutel om het bericht te ontcijferen. Mailprogramma’s als Outlook maken bijvoorbeeld gebruik van publieke cryptografie. Outlook heeft van elke mailbox een zogeheten publieke sleutel die ze bekend maken op hun server. De publieke sleutel vertelt precies hoe je een bericht bestemd voor die ene mailbox moet versleutelen.
Wil Bob bijvoorbeeld een beveiligd mailtje sturen naar Alice, dan zoekt de Outlook van Bob op wat de publieke sleutel van Alice is. Het encryptie-algoritme doet de rest, en een paar tellen later heeft Alice een versleuteld mailtje in haar inbox. Om dit te ontsleutelen gebruikt Alice haar privésleutel. Deze is wiskundig verbonden aan de publieke sleutel, en bevat de ontbrekende schakel om het mailtje te ontcijferen. Door haar publieke sleutel openbaar te maken, maar haar privésleutel voor haarzelf te houden, weet Alice zeker dat niemand mailtjes kan lezen die alleen voor haar ogen bestemd zijn.
Publieke encryptie werkt als volgt: wil Bob een bericht voor Alice versleutelen, dan doet hij dit met Alice haar publieke sleutel. Deze is voor iedereen zichtbaar. Als Alice het versleutelde bericht wil ontcijferen gebruikt ze haar privésleutel. Niemand anders heeft deze sleutel, dus kan niemand anders haar berichten ontcijferen. Bron: Wikipedia
RSA encryptie
De populairste manier van publieke cryptografie is de RSA encryptie, genoemd naar haar bedenkers Rivest, Shamir en Adleman. Het is een wiskundige methode en die werkt als volgt:
1. Vertaal je boodschap in een rijtje getallen. Dit doe je door bijvoorbeeld elke letter een nummer mee te geven. A is dan 01, B is 02 enzovoort, met 00 als spatie. Het woord CODE wordt dan 03150405.
2. Kies twee geheime priemgetallen. Deze kies je niet zomaar, want ze moeten minstens 150 cijfers lang zijn in verband met veiligheid. Deze getallen zet je vervolgens om in binaire code, zodat je twee getallen overhoudt van 512 nullen en enen lang.
3. Vermenigvuldig de priemgetallen met elkaar. Dit geeft een gigantisch getal van 1024 bits lang. Dat is de kracht van de versleuteling, de zogeheten RSA-1024 bit encryptie. Het getal van 1024 bits, de modulus, maak je aan iedereen bekend en is dus onderdeel van de publieke sleutel. In de modulus zitten je twee priemgetallen verstopt, en zijn alleen terug te vinden door het getal te ontbinden in factoren. Zo is het getal 15 te ontbinden is de factoren 5 en 3. Klinkt simpel? Probeer het eens met een getal ter grootte van een half A4tje, dan weet je waarom computers zo krachtig moeten zijn om een versleutelde boodschap te kraken.
4. Bedenk een vercijferexponent. Dit getal is wiskundig gerelateerd aan de twee priemgetallen. Dit maak je ook aan iedereen bekend. De publieke sleutel bestaat nu uit de modulus en de vercijferexponent.
5. Gebruik een bekende formule om je vercijferde boodschap te versleutelen. De formule ziet er zo uit:
E(x) = xe mod m
E(x) is het versleutelde bericht. x is het bericht, zoals het eruit ziet in bits. e is de vercijferexponent. m is de modulus. mod m betekent dat je de modulus blijft aftrekken van xe totdat het resultaat kleiner is dan m.
Een aanvaller die het versleutelde bericht onderschept kan deze formule, samen met de publieke sleutel, niet gebruiken om het originele bericht te ontcijferen. Hij loopt dan tegen het ‘RSA probleem’ aan, een puzzel die bij zulke grote getallen zo moeilijk is dat de huidige wiskunde hem niet kan oplossen.
6. Bereken je ontcijferexponent aan de hand van je geheime priemgetallen en je vercijferexponent. Dit is je privésleutel, en kan je gebruiken om het RSA probleem te omzeilen. Het ontcijferen gaat als volgt:
D(y) = yd mod m
D(y) is het ontsleutelde bericht. y is versleutelde bericht. d is de ontcijferexponent.
Hieronder nog eenmaal een samenvatting van de RSA encryptie: 1. Kies grote priemgetallen p en q (minstens 300 cijfers elk). 2. Bepaal de modulus m = p x q. 3. Bereken n = (p-1)(q-1). 4. Kies een vercijferexponent e waarvoor de grootste gemene deler met n gelijk is aan 1. 5. Bereken de ontcijferexponent d zo, dat e x d = 1 mod n. 6. Maak de getallen m en e bekend. Samen vormen ze de publieke sleutel. 7. Houd d geheim. Dat is de privésleutel. 8. Vercijferen: E(x) = xe mod m 9. Ontcijferen: D(y) = yd mod m
De RSA-mannen, van links naar rechts: Adi Shamir, Ron Rivest en Len Adleman.
Dit is RSA encryptie in een notendop. Het zwakke punt van RSA, dat een makkelijk doelwit is voor supersterke computers zoals quantumcomputers, ligt in het ontbinden van de modulus in factoren, oftewel je geheime priemgetallen. Het ontcijferen van een 1024-bit encryptie kost een netwerk moderne computers jaren. Een quantumcomputer zou het in enkele uren moeten kunnen. Volledig functionerende quantumcomputers bestaan nog niet, maar veel langer dan twintig jaar kan het volgens de wetenschap niet duren.
McEliece encryptie
Gelukkig is RSA niet de enige vorm van encryptie. Dertig jaar geleden bedacht Robert McEliece de gelijknamige McEliece encryptie. Deze vorm van encryptie introduceert moedwillig fouten in het verstuurde bericht, die geen enkele computer vandaag de dag kan ontcijferen. Wat mooier is, naar verwachting zal ook de extra rekenkracht van quantumcomputers niet voldoende zijn om de code te breken. McEliece encryptie werkt als volgt:
1. Verander je bericht in een code van 512 bits.
2. Deze code verander je met de hulp van een matrix in een codewoord van 1024 bits. Dit is een 1024-bit encryptie. De matrix is je publieke sleutel, en ziet eruit als een tabel gevuld met nullen en enen. De grootte van de tabel is afhankelijk van de lengte van het codewoord (in dit geval 1024 bit) en de lengte van het bericht (hier 512 bit).
3. Introduceer met de hulp van een algoritme op willekeurige plaatsen vijftig fouten in het codewoord. Enen worden nullen, nullen worden enen en het codewoord is onherkenbaar geworden. Dit is de cyphertekst die je naar de ontvanger verstuurt. Dit doe je omdat iedereen het codewoord van stap 2 kan ontcijferen omdat iedereen bij je publieke sleutel, de matrix, kan.
4. De ontvanger gebruikt zijn privésleutel om de cyphertekst weer om te bouwen naar het originele codewoord. De privésleutel is een decodeeralgoritme dat fouten in een code kan herkennen en herstellen.
Een voorbeeld van een hele kleine McEliece matrix. De matrix is gevuld met bits verandert een bericht in een codewoord. De lengte en breedte van de matrix is afhankelijk van de lengte van het bericht en de lengte van het codewoord.
De toegevoegde fouten maken McEliece haast onkraakbaar omdat de code met fouten vreselijk moeilijk is te onderscheiden van een willekeurige bitreeks. De reden dat McEliece tot nu toe niet erg populair was is de grootte van de publieke sleutel, oftewel de matrix. Een gemiddelde matrix bij McEliece encryptie heeft maar liefst 219 vakjes. Dat is maximaal 524288 bits.
Hoe groot is dit getal? Denk terug aan 1024, het getal van een half A4tje. Schrijf 219 uit, en je hebt een boek van 256 bladzijden – te groot voor de chips op de huidige generatie betaalpasjes. Wetenschappers denken echter dat binnen tien à twintig jaar, tegen de tijd dat de eerste quantumcomputers hun intrede doen, chips sterk genoeg zijn om McEliece aan te kunnen.
Quantumcomputers hebben massa’s meer rekenkracht dan de modernste computers van vandaag. Hiermee kunnen ze RSA encryptie zonder problemen kraken.
Codes kraken
De komst van de quantumcomputer is niet de enige reden om encryptie up to date te houden. Computerkracht blijft immers groeien, dankzij de Wet van Moore. Deze wet, genoemd naar de oprichter van Intel Gordon Moore, voorspelt dat elke achttien maanden de hoeveelheid informatie verdubbelt die op een chip van een vierkante millimeter past. Met meer informatie neemt ook de rekenkracht van de chip, en dus de computer, toe.
Nu gebruiken de meeste banken voor hun betaalverkeer nog RSA-1024 bit encryptie, maar deskundigen raden banken al langer aan over te schakelen op RSA-2048. In de praktijk betekent dat dubbel zo grote priemgetallen, van minstens driehonderd cijfers lang. Deze getallen leveren een modulus op van 2048 bits. Een netwerk van de modernste computers doet er jaren over om zo’n getal te ontbinden in factoren.
Een netwerk van de modernste computers doet er jaren over om een goede RSA of McEliece encryptie te kraken.
In het najaar van 2008 publiceerden wetenschappers van de TU Eindhoven een manier om ook McEliece encryptie te ontcijferen, maar gaven ook meteen een advies om de methode weer veilig te maken. De standaard methode om een bericht te versleutelen met McEliece levert een codewoord van 1024 bits op met daarin 50 fouten. Door de lengte van het codewoord te veranderen in 1632 bits wordt het weer onmogelijk voor moderne computers om een McEliece encryptie binnen afzienbare tijd te kraken. Ook kan het aantal fouten worden verminderd tot slechts 34.
Helaas levert deze voorzorgsmaatregel wel een grotere matrix op, dus erg praktisch is het nog niet. Gelukkig hoeft dat ook niet, want zolang de quantumcomputer nog in de kinderschoenen staat kunnen we dankzij RSA zonder problemen onze creditcard blijven gebruiken.