Terugblik 2022 - Wiskundige beveiliging is te kraken

Wanneer we op het internet betalingen doen, maken we voortdurend gebruik van digitale beveiligingsmechanismen. Ze zorgen ervoor dat niemand ongeoorloofd geld van onze rekening kan halen. De mechanismen maken gebruik van geheime communicatiemethodes tussen betaler en ontvanger.

Maar hoe spreek je zo’n communicatiemethode af als iedereen voortdurend kan meeluisteren – want zo is de aard van het internet? Al in 1976 formuleerden de Amerikaanse wiskundigen Whitfield Diffie en Martin Hellman een theoretisch antwoord op die vraag. In 2016 ontvingen ze er de Turing-prijs voor.

In de methode van Diffie-Hellman kiezen beide partijen elk een geheim getal – we noemen ze even a en b. Samen kiezen de partijen een ander getal g uit een bepaalde eindige maar heel grote getallenruimte. Die keuze is openbaar. Iedereen mag het resultaat kennen. De ruimte en het getal maken deel uit van een zogenaamde publieke sleutel, de twee geheime getallen zijn dan private sleutels.

De twee partijen gebruiken vervolgens elk hun private sleutel voor een machtsverheffing van het publieke getal. Zo krijgen we gᵃ aan de ene kant en gᵇ aan de andere. Daarna bezorgen ze elkaar dit resultaat, dat ze elk op hun beurt weer verheffen tot hun eigen sleutel. Dat levert hun beiden hetzelfde getal op, namelijk

(gᵇ)ᵃ=(gᵃ)ᵇ=gᵃᵇ

Dit gedeelde getal gebruiken de twee om hun berichten te versleutelen.

Nu denk je wellicht dat die gᵃ en gᵇ voor een buitenstaander wel te achterhalen zijn. In werkelijkheid is het zowat onmogelijk om de exponenten uit die machten te achterhalen. Zelfs met de snelste computers is het onbegonnen werk. Het staat bekend als het discrete-logaritmeprobleem. Het werk van Diffie en Hellman leidde dan ook tot een resem aan cryptosystemen die berusten op moeilijke problemen waarop niemand een antwoord weet. Of althans nóg niet.

Even een omweg, langs het bekende RSA-algoritme (zie ‘Het geheim dat je van de daken mag schreeuwen’, Eos nr. 7, 2019). Dat berust op hetzelfde veiligheidsprincipe, maar maakt gebruik van een ander moeilijk probleem. Om het probleem op te lossen, moet je de priemfactoren van een groot getal vinden. In 1994 ontwikkelde wiskundige Peter Shor een algoritme dat het probleem efficiënt aanpakt. Al heb je er wel een quantumcomputer voor nodig.

Specialisten zagen meteen in dat Shors algoritme ook bruikbaar is om het discrete-logaritmeprobleem te kraken. Zo werd de zogenaamde post-quantumcryptografie geboren: de zoektocht naar nieuwe moeilijke problemen die bestand zijn tegen aanvallen met een quantumcomputer.

Het Amerikaanse National Institute of Standards and Technology (NIST) coördineert de zoektocht naar zulke alternatieven. Begin juli kwam daar het zogeheten Kyber-systeem naar voren. Het is gebaseerd op het zogenaamde learning with errors-probleem, waarbij men een onbekende functie tracht te leren uit gegeven punten en hun beeld, maar waar er fouten kunnen tussenzitten. Dat levert een snel cryptosysteem op met kleine sleutels – belangrijk in tijden waarin bijna elk voorwerp smart is en veilig informatie moet kunnen uitwisselen.

Om voorbereid te zijn op aanvallen kijkt de cryptogemeenschap naar alternatieven. Een hele klasse daarvan is gebaseerd op het idee van Diffie en Hellman, maar dan in een heel andere ruimte die Shors aanval tenietdoet. Deze categorie werkt met zogenaamde elliptische krommen, of punten uit eindige getallenruimtes die oplossingen zijn van vergelijkingen van de vorm y2=x3+ax+b, waarbij a en b gegeven getallen zijn.

Bij één van die alternatieven, SIDH geheten, vertrekken twee partijen van eenzelfde elliptische kromme van een welbepaalde soort. Die ‘vervormen’ ze elk in het geheim met een transformatie die we een isogenie noemen. Ze sturen vervolgens hun vervormde kromme naar elkaar. Die vervormen ze beiden nog eens, op de geheime manier die ze voorheen kozen. Net als bij de machten komen ze zo beiden uit op een gedeeld geheim. Een luistervink krijgt kop noch staart aan de verstuurde krommen.

Zo leek het toch. Tot twee Vlaamse wiskundigen – Wouter Castryck en Thomas Decru – deze zomer toonden dat zij dat wel kunnen. Het bracht een ware schokgolf teweeg. Post-quantumcrypto is dead, long live post-quantumcrypto. Of moet ik zeggen: long live mathematics?