This page does not exist in English yet. You are reading the Dutch version.

RSA: prime numbers

13 × 17 = 221. Dat reken je uit je hoofd. Krijg je 221 en de vraag welke twee priemgetallen dat waren, dan moet je proberen: 3? 7? 11? 13, hebbes. Een minuut werk. Maak er getallen van 300 cijfers van en die minuut wordt langer dan het heelal oud is — terwijl de vermenigvuldiging nog steeds in een fractie van een seconde gaat. Op die scheefheid staat RSA.

Woorden die je zo nodig hebt

Priemgetal: Een getal dat alleen deelbaar is door 1 en door zichzelf: 2, 3, 5, 7, 11, 13… Hoe groter je kijkt, hoe zeldzamer ze worden, maar ze houden nooit op — dat is al door Euclides bewezen, ruim tweeduizend jaar geleden.
Ontbinden in factoren: Een getal terugbrengen tot de priemgetallen waaruit het opgebouwd is. 221 wordt 13 × 17. Dat is de rekensom die RSA onmogelijk moet maken.
Valdeurfunctie: Een berekening die makkelijk vooruit gaat en onmogelijk terug — tenzij je een geheim kent, en dan gaat het toch. Als een valdeur: er vlot in, er niet meer uit, behalve als je weet waar de klink zit.
OAEP: De opvulling die voor het versleutelen bij het bericht gezet wordt: willekeurige bytes volgens een vast recept. Zonder die opvulling geeft hetzelfde bericht altijd dezelfde cijfertekst, en dat is een lek — hetzelfde probleem als een ontbrekende IV in hoofdstuk 4.

Hoe het werkt, zonder de formules

Je computer kiest twee enorme priemgetallen en houdt ze geheim.
Hij vermenigvuldigt ze. Dat product mag iedereen zien; het zit in je publieke sleutel.
Versleutelen is een berekening met dat product — klokrekenen, zoals in hoofdstuk 5, maar op een klok met honderden cijfers als omtrek.
Ontsleutelen is dezelfde soort berekening, maar je hebt er de twee priemgetallen zelf voor nodig. Die heb jij, en niemand anders.

Wie jouw publieke sleutel heeft, heeft dus het product. Om te ontsleutelen moet hij het ontbinden. Dat kan — in theorie. Alleen duurt het te lang, en dat is de hele beveiliging. Geen enkel slot, alleen een rekensom die niemand af krijgt.

Probeer het zelf

Het sleutelpaar wordt in je browser gemaakt en verdwijnt zodra je dit tabblad sluit. Je mag hier gerust de private sleutel bekijken: hij is voor deze pagina gemaakt en wordt nergens voor gebruikt. Bij een echte sleutel doe je dat nooit.

Klik Maak een sleutelpaar. Dat duurt even: je computer zoekt twee priemgetallen. Je ziet je publieke sleutel — dat blok tekst mag je aan iedereen geven.
Klik Toon de private sleutel. Vergelijk de twee blokken: de private is ruim vier keer zo lang. Daaronder staan p en q, de twee priemgetallen van stap 1, en het product dat in je publieke sleutel zit.
Klik Versleutel met de publieke sleutel. De cijfertekst is altijd exact 256 bytes, hoe kort je bericht ook is.
Klik Ontsleutel met de private sleutel. Je bericht komt terug.
Plak nu een lange tekst in het berichtveld — een paar alinea's — en versleutel. Het lukt niet. Lees waarom.

Bericht Cijfertekst (base64)

Waarom je er tegen een muur liep

RSA met een sleutel van 2048 bits kan maar 190 bytes versleutelen. Dat is geen instelling die je hoger kan zetten: het bericht moet kleiner blijven dan het getal waarmee gerekend wordt. Een grotere sleutel helpt nauwelijks en maakt alles trager. Asymmetrische versleuteling is dus niet gemaakt om berichten mee te versturen.

Waarvoor dan wel? Voor twee dingen: een verse AES-sleutel naar iemand sturen zonder iets af te spreken, en ondertekenen. Over dat tweede gaat hoofdstuk 7.1. Over hoe alles samenkomt, hoofdstuk 7.3.

Maar eerst iets mooiers. RSA rekent met priemgetallen van 600 cijfers. Er bestaat een elegantere manier die met veel kleinere getallen hetzelfde bereikt: rekenen met punten op een kromme lijn. Die zit in je identiteitskaart, in je browser, en in Bitcoin. Het volgende hoofdstuk laat je erop klikken.

Hoe groot moet zo'n sleutel zijn

Sleutel	Dat is een getal van	Oordeel
RSA-1024	309 cijfers	te klein, sinds jaren afgeraden
RSA-2048	617 cijfers	vandaag de norm
RSA-4096	1234 cijfers	ruimer, en merkbaar trager

Die traagheid is geen detail. Een sleutelpaar maken duurt merkbaar lang — je merkte het bij de eerste knop — omdat je computer moet zoeken tot hij twee priemgetallen vindt. En elke verdubbeling van de sleutellengte maakt het rekenwerk ongeveer acht keer zwaarder. Dat is precies de reden dat de wereld overstapt op krommen, en dat is hoofdstuk 6.2.

Dit is wiskunde: priemgetallen als éénrichtingsstraat

Vermenigvuldigen en ontbinden zijn elkaars omgekeerde, en toch is de ene richting triviaal en de andere onbegaanbaar. Het beste algoritme dat we kennen om een getal van 617 cijfers te ontbinden — de getallenlichaamzeef — zou op alle computers ter wereld samen langer bezig zijn dan het heelal bestaat. Niet omdat het niet kán, maar omdat het te lang duurt.

En let op wat daar staat: het beste algoritme dat we kennen. Niemand heeft bewezen dat ontbinden moeilijk is. Wordt er morgen een snelle manier gevonden, dan valt RSA op dezelfde dag om. Dat is geen doemdenken maar hoe het vak werkt: de beveiliging van het internet rust op problemen waarvan we alleen weten dat heel veel slimme mensen ze niet opgelost krégen. Dit is getaltheorie, het vak dat eeuwenlang "nutteloos maar mooi" heette.