Elliptische krommen: de wiskunde in je zak

Dit is de vergelijking y² = x³ − x + 1. Teken je ze, dan krijg je een gebogen lijn — een elliptische kromme. Dat lijkt iets uit een wiskundeboek waar je nooit meer aan denkt. Maar precies deze soort lijn zit in de chip van je identiteitskaart, achter het slotje in je browser, en onder Bitcoin. In dit hoofdstuk ga je erop klikken en zien waarom.

Woorden die je zo nodig hebt

Kromme: Gewoon een gebogen lijn in een grafiek: alle punten (x, y) waarvoor een vergelijking klopt. Een parabool is een kromme. Dit is een iets spannendere.
Punten optellen: Dit is het rare idee. Op deze kromme kan je twee punten "optellen" en krijg je een derde punt op dezelfde kromme. Niet door de coördinaten op te tellen, maar met een tekenregel: trek een lijn door de twee punten, kijk waar die de kromme nog een derde keer snijdt, en spiegel dat punt in de x-as. Klaar: dat is P + Q.
Verdubbelen: P + P. Je hebt maar één punt, dus je neemt de raaklijn — de lijn die de kromme in P precies raakt — en doet dezelfde truc.
Klokrekenen (modulo): Rekenen met alleen gehele getallen van 0 tot een grens, waarbij je na de grens opnieuw bij 0 begint. Ken je uit hoofdstuk 6, waar het de motor onder Diffie–Hellman was. Hier zie je wat het met een grafiek doet.

Klik op de kromme

Alles gebeurt in je browser. Er wordt niets naar de server gestuurd.

Klik ergens op de lijn. Dat is P. Klik een tweede keer voor Q. De demo trekt de lijn, vindt het derde snijpunt, spiegelt het, en toont P + Q.
Klik Wis, kies één punt en druk op Verdubbel. Blijf dan klikken op Tel P er nog eens bij: 3·P, 4·P, 5·P… De punten springen over de hele kromme.
Schuif aan a en b. De vorm verandert — soms splitst de lijn in twee stukken. Zoek de stand waar ze een knik krijgt: die is onbruikbaar, en de demo zegt waarom.
Druk op Klokrekenen (modulo 97). Zelfde vergelijking, alleen gehele getallen. Kijk wat er van de lijn overblijft. Kies een stip en tel weer op.

a =

b =

Wat je net gezien hebt

Op de vloeiende lijn kon je nog een beetje "voelen" waar je zat. Na drie keer optellen zit je ongeveer dáár, na vier keer ongeveer daar. Maar zodra je op klokrekenen overschakelde, viel de lijn uit elkaar in een wolk van stippen zonder enig patroon. En het optellen werkte nog steeds — dezelfde formules, dezelfde regels — alleen springt het resultaat nu kruis en dwars over het vlak.

Nu het hele geheim. Stel dat ik een punt P kies en het 1 000 000 keer bij zichzelf optel. Dat kan een computer razendsnel — er is een truc waardoor het maar een dertigtal stappen kost. Ik geef jou P en het eindpunt. Kan jij uitzoeken dat het 1 000 000 keer was? Op de stippenwolk van 97 nog wel: daar staan maar een honderdtal punten, en je probeert ze gewoon allemaal. Maar de kromme in je identiteitskaart heeft ongeveer 2³⁸⁴ punten. Dat getal heeft 116 cijfers. Niemand probeert dat af, ook geen supercomputer, ook niet in een miljard jaar.

Alles aflopen is trouwens niet eens de slimste aanval. Er bestaat een kortere weg, in 1978 gevonden door John Pollard, die ongeveer de vierkantswortel van het aantal punten nodig heeft: zo'n 2¹⁹² stappen. Dat getal heeft nog altijd 58 cijfers, en ook dat haalt niemand. Cryptografen rekenen altijd met de beste kortere weg die ze kennen, nooit met alles aflopen. Dat blijkt zo meteen belangrijk.

Dát is de private sleutel: het aantal keren. De publieke sleutel is het eindpunt. Iedereen mag het eindpunt zien; niemand kan terugtellen. Precies het open hangslot uit het vorige hoofdstuk — maar met een grafiek in plaats van priemgetallen.

Hoeveel stippen? Je zou denken: modulo 97, dus 97 punten. Zo werkt het niet. Bij klokrekenen telt de demo ze voor je. Met a = −1 en b = 1 zijn het er toevallig precies 97, plus het punt op oneindig: 98. Ga terug naar de vloeiende lijn, schuif aan a of b en schakel opnieuw over: dan worden het er bijvoorbeeld 80, 106 of 117. Raden kan je het aantal niet, maar ver van 97 zit het nooit. Helmut Hasse bewees in 1933 dat het altijd binnen 2√p van p + 1 blijft; voor 97 is dat tussen 79 en 117. Bij P-384 is het aantal punten exact bekend, en het is zelf een priemgetal. Dat is geen toeval: de kromme is daarop uitgekozen.

Waarom krommen en niet gewoon RSA

	RSA (priemgetallen)	Elliptische krommen
Even veilig bij	sleutel van 3072 bits	sleutel van 256 bits
Beste bekende aanval kost	ongeveer 2¹²⁸ stappen	ongeveer 2¹²⁸ stappen
Dat is	een getal van 925 cijfers	een getal van 78 cijfers
Past op een chipkaart?	met moeite	ruim
Bedacht in	1977	1985, door Neal Koblitz en Victor Miller, los van elkaar

Twaalf keer kortere sleutels voor dezelfde veiligheid. Dat wil niet zeggen dat RSA slecht in elkaar zit. "Even veilig" betekent: de beste aanval die we kennen, kost aan beide kanten evenveel stappen. Tegen RSA hebben aanvallers sinds het begin van de jaren negentig een slim stuk gereedschap, de getallenlichamenzeef, dat veel sneller ontbindt dan alles aflopen. Tegen een goed gekozen kromme heeft niemand zoiets gevonden; daar is de kortere weg van Pollard nog altijd het beste wat er bestaat. RSA moet dus grotere getallen nemen om de aanvaller evenveel werk te bezorgen.

Daarom stapt de wereld over: de nieuwste Belgische identiteitskaarten gebruiken een kromme (met de naam P-384), oudere kaarten nog RSA. P-384 zit een trede hoger dan de tabel: ongeveer 2¹⁹² stappen. Met RSA heb je daarvoor 7680 bits nodig, een getal van 2312 cijfers. Het slotje in je browser spreekt de sleutel af met een kromme. Je Bitcoin-sleutel is een punt op een kromme; het adres dat je doorgeeft is de vingerafdruk van dat punt (zie hoofdstuk 3).

De regel voor a en b. Bij het schuiven zag je dat sommige standen een knik of een lus geven. Wiskundig: als 4a³ + 27b² = 0, is de kromme "ontaard" en werkt het optellen niet meer overal. Cryptografen kiezen a en b dus met zorg — en ze publiceren ze, zodat iedereen kan controleren dat er geen geheime zwakte in verstopt zit. Dat wantrouwen is een vak op zich.

Dit is wiskunde: een groep

Wat je net deed — punten "optellen" met een tekenregel — heeft alle eigenschappen van gewoon optellen. Het is associatief: (P + Q) + R = P + (Q + R), al zie je dat niet meteen. Er is een "nul" (het punt op oneindig, dat je tegenkwam toen de lijn verticaal werd). Elk punt heeft een tegengestelde (zijn spiegelbeeld). Wiskundigen noemen zo'n verzameling met zo'n bewerking een groep. Dat is het eerste hoofdstuk van abstracte algebra, het vak waarin je leert dat getallen, draaiingen van een kubus en punten op een kromme diep vanbinnen hetzelfde spelletje spelen. Het staat in het eerste jaar van elke universitaire opleiding wiskunde.

En dat spelletje gaat veel verder dan geheimschrift. De zetten van een Rubiks kubus vormen een groep, met ruim 43 triljoen standen. Scheikundigen ordenen moleculen volgens hun symmetriegroep en voorspellen daarmee welk licht een molecule kan opslorpen. Er bestaan precies 230 soorten symmetrie die een kristal kan hebben; dat werd in 1891 uitgeteld, met groepentheorie. Natuurkundigen bouwen hun beschrijving van de kleinste deeltjes, het Standaardmodel, op groepen. En de QR-code op een concertticket scant nog als er een hoek af is, dankzij algebra met een eindig aantal getallen, net als hier. Cryptografie is maar één hoekje van die wereld.

Let wel: de groep zelf maakt je identiteitskaart niet veilig. Groepen zijn overal, en de meeste zijn voor geheimen nutteloos. Klokrekenen met gewoon optellen is ook een groep, en daar reken je met één deling terug. De veiligheid hangt aan één vraag over deze ene groep, waar niemand een snel antwoord op gevonden heeft: hoeveel keer werd P opgeteld? Dat het moeilijk lijkt, is geen bewijs. Het is een vermoeden dat al meer dan veertig jaar standhoudt.

Merk trouwens op wat je hier niet nodig had. Om te snappen waarom RSA moeilijk terug te rekenen is, moet je eerst iets weten over priemgetallen en ontbinden in factoren, en dat is een vak op zich. Hier had je genoeg aan een lijn die een kromme snijdt. Cryptografen zeggen daarom vaak dat krommen voor een beginner juist makkelijker te vatten zijn dan RSA: de moeilijkheid zit niet verstopt in de wiskunde eronder maar ligt gewoon op tafel. Dat je eerst hoofdstuk 7.1 gelezen hebt en dit hoofdstuk pas daarna, is dus historische volgorde, geen volgorde van moeilijkheid.