Hoe priemgetallen het internet veilig houden
We zouden er van versteld staan moest jij niet weten wat een priemgetal is, maar laten we voor de volledigheid beginnen bij het begin. Een priemgetal is een getal dat uitsluitend deelbaar is door één en zichzelf. Denk daarbij aan 2, 3, 5, 7 en 11 maar neem zeker niet aan dat priemgetallen per definitie lage getallen zijn. Ook 2393, 4177 of 7867 voldoen aan de definitie.
Er lijken oneindig veel priemgetallen te bestaan maar het is niet eenvoudig om zomaar een immens getal te bekijken en te deduceren of het ondeelbaar is door alles behalve één en zichzelf. Het hoogste gekende priemgetal is (op het moment van dit schrijven) 274,207,281 -1. Niet de meest voor de hand liggende schrijfwijze, maar om het volledig te noteren zouden we ongeveer acht jaarabonnementen aan een gemiddeld magazine nodig hebben: het bestaat uit 22.338.618 cijfers.
Meer dan prestige
De zoektocht naar priemgetallen is geen prestigezaak voor verveelde wiskundigen. De getallen hebben een bijzonder praktisch nut en de mathematische logica erachter is een fundamentele bouwsteen in tal van applicaties in de moderne digitale wereld. Dat komt omdat ieder geheel getal zonder uitzondering uitgedrukt kan worden als een product van uitsluitend andere priemgetallen.
Die ontbinding in priemfactoren is een fundamenteel theorema in de wiskunde. Denk je er over na, dan is dat logisch. Priemgetallen zijn getallen die je niet verder uit elkaar kan trekken. Ontbind je een groot getal in steeds kleinere getallen, dan is het onvermijdelijk dat je na verloop van tijd op priemen strandt.
Brute kracht
Het is niet zo moeilijk om een relatief laag geheel getal te ontbinden in priemfactoren. Je hebt er je hersenen en een beetje tijd voor nodig en hebt het waarschijnlijk op de lagere school moeten doen. Hoe groter de getallen, hoe moeilijker de ontbinding wordt. Er is immers, voor zover wiskundigen weten, geen efficiënte formule waarmee je eender welk getal kan ontbinden.
Er bestaan natuurlijk wel technieken, maar uit hoe meer cijfers een getal bestaat, hoe moeilijker en minder efficiënt die worden. Een brutekrachtaanval op het getal 8 voor de ontbinding in 2 x 2 x 2 is niet zo moeilijk, maar wanneer een krachtige supercomputer de opdracht krijgt om een getal met 500 cijfers te ontbinden in priemfactoren, dan heeft die meer tijd nodig dan de totale leeftijd van de aarde.
Er bestaat met andere woorden geen wiskundige maar wel een praktische limiet voor de grootte van getallen die we kunnen ontbinden in priemfactoren en op dat feit is moderne computerbeveiliging gebouwd. Dat verdient een beetje verduidelijking.
Onbeveiligde beveiliging
Eerst en vooral staan we even stil bij de manier waarop een beveiligde connectie tussen computers tot stand komt. Beveiligde verbindingen over het internet worden per definitie opgezet in een onbeveiligde omgeving. Dat gebeurt door encryptiesleutels uit te wisselen. Die sleutels zijn publiek te onderscheppen, maar ze dienen enkel om data te versleutelen. De sleutel voor de decryptie verschilt van de encryptiekey, en die wordt niet zomaar verzonden.
De absurde rekenkracht die nodig is om getallen in factoren te ontbinden maakt die werkwijze mogelijk. Beeld je ter illustratie twee gigantische priemgetallen in, bestaande uit honderden cijfers. Wanneer je die priemgetallen met elkaar vermenigvuldigt, krijg je een enorm getal dat deelbaar is door één, zichzelf en de twee priemgetallen waaruit het is opgebouwd. De priemen vermenigvuldigen om het grote getal te krijgen is niet moeilijk, maar andersom is het praktisch onmogelijk om, zelfs met ’s werelds krachtigste supercomputer, het enorme getal terug in z’n factoren te ontbinden.
Publieke sleutel
Het grote getal kan in dit geval dienst doen als publieke sleutel. Die sleutel wordt over het internet verzonden om de beveiligde verbinding op te zetten. De computer die de key ontvangt, versleutelt er data mee, maar kan die zelf niet ontcijferen. Dat kan geen enkele computer, behalve degene die de publieke sleutel in eerste instantie genereerde. Dat systeem is immers op de hoogte van de twee priemgetallen waaruit de publieke sleutel bestaat.
Onderschept een hacker de sleutel dan kan hij data versleutelen, maar zonder de twee oorspronkelijke priemgetallen is decryptie onmogelijk. Twee computers die sleutels uitwisselen met elkaar kunnen zo beveiligd over het internet communiceren. Ze krijgen ieder een sleutel, coderen er data mee, zenden die naar hun respectievelijke communicatiepartner en enkel daar kan de data ontcijferd worden. Hoe de encryptie zelf precies in z’n werk gaat, is een ander verhaal, voor dit artikel is het belangrijk te weten dat priemgetallen het fundament van het proces zijn.
RSA en kredietkaarten
Grote priemgetallen zorgen er dus voor dat een beveiligde verbinding kan ontstaan over een initieel onbeveiligd netwerk. Het principe schuilt achter de versleuteling van e-mails, maar ook achter het verzenden van betaalkaartinformatie of het doorgeven van persoonlijke gegevens. Er bestaan heel wat encryptiealgoritmes die gebruik maken van de ontbinding in factoren, waarvan RSA het bekendste is. RSA, een afkorting opgebouwd uit de eerste letters van de voornamen van de uitvinders, is populair bij het opzetten van een beveiligde verbinding voor kredietkaartbetalingen.
Niet waterdicht
Priemgetallen zijn dus meer dan een aardigheid binnen de moderne wiskunde, ze zijn van levensbelang voor de beveiliging van de digitale wereld. Het systeem heeft echter één fundamenteel probleem: het is perfect mogelijk om de encryptie te kraken, zolang je maar voldoende tijd hebt. Het duurt al snel duizenden jaren om de decryptiesleutel te vinden en tegen dan is de ontcijferde data toch waardeloos, en is iedereen die er iets mee te maken had al lang dood. Computerkracht staat natuurlijk niet stil, en hoe sneller computersystemen worden, hoe minder tijd ze nodig hebben om een publieke sleutel te breken.
In 2009 was RSA-768 de standaard. De 768 bit-encryptie maakte gebruik van een getal met 232 cijfers als sleutel. Enkele onderzoekers onder leiding van Thorsten Kleinjung lieten zich daar niet door afschrikken en ze gingen de sleutel te lijf. Niet met één computer, maar met een netwerk van honderden toestellen voorzien van geavanceerde ontbindingsalgoritmes.
Het netwerk deed er twee jaar over maar de RSA-768-sleutel werd gekraakt. Op die twee jaar verzette het computernetwerk het equivalent van 2.000 jaar rekenen door een single-core 2,2 GHz AMD Opteron-cpu. Het resultaat leverde de onderzoekers 50.000 dollar op: een beloning uitgevaardigd door de RSA-stichters zelf.
Upgrade
Twee jaar is al bij al niet zo lang en met de snelle vooruitgang van computerkracht was het meteen duidelijk dat RSA-768 geen plaats meer had in de beveiligingswereld. Vandaag spreken we van 1024 bit-encryptie met getallen bestaande uit 309 cijfers en voorlopig heb je nog een combinatie van supercomputers en een tijdsmachine nodig om daar doorheen te kauwen. Schuw je niet weg van een uitdaging? Dan kan je 100.000 dollar verdienen door de wiskundigen van de wereld ongelijk te geven.
Quantumgevaar
Ook RSA-1024 zal niet eeuwig veilig blijven. Traditionele computers voorblijven door de gebruikte getallen te verhogen is niet zo moeilijk, maar onderzoek naar een niet zo traditionele computer geniet dezer dagen hoge prioriteit. Quantumcomputers werken op een totaal andere manier.
Omdat bits in een quantumsysteem 0, 1 of 0 én 1 kunnen zijn, kan een quantumcomputer verschillende scenario’s tegelijkertijd contempleren. Wiskundigen vrezen dat een functionele quantumcomputer, die z’n beloftes nakomt, zelfs door de meest geavanceerde priemgetallen-encryptie kan breken in seconden, waarna het gedaan is met de beveiliging van het internet zoals we die vandaag kennen.
We zouden er van versteld staan moest jij niet weten wat een priemgetal is, maar laten we voor de volledigheid beginnen bij het begin. Een priemgetal is een getal dat uitsluitend deelbaar is door één en zichzelf. Denk daarbij aan 2, 3, 5, 7 en 11 maar neem zeker niet aan dat priemgetallen per definitie lage getallen zijn. Ook 2393, 4177 of 7867 voldoen aan de definitie.
Er lijken oneindig veel priemgetallen te bestaan maar het is niet eenvoudig om zomaar een immens getal te bekijken en te deduceren of het ondeelbaar is door alles behalve één en zichzelf. Het hoogste gekende priemgetal is (op het moment van dit schrijven) 274,207,281 -1. Niet de meest voor de hand liggende schrijfwijze, maar om het volledig te noteren zouden we ongeveer acht jaarabonnementen aan een gemiddeld magazine nodig hebben: het bestaat uit 22.338.618 cijfers.
Meer dan prestige
De zoektocht naar priemgetallen is geen prestigezaak voor verveelde wiskundigen. De getallen hebben een bijzonder praktisch nut en de mathematische logica erachter is een fundamentele bouwsteen in tal van applicaties in de moderne digitale wereld. Dat komt omdat ieder geheel getal zonder uitzondering uitgedrukt kan worden als een product van uitsluitend andere priemgetallen.
Die ontbinding in priemfactoren is een fundamenteel theorema in de wiskunde. Denk je er over na, dan is dat logisch. Priemgetallen zijn getallen die je niet verder uit elkaar kan trekken. Ontbind je een groot getal in steeds kleinere getallen, dan is het onvermijdelijk dat je na verloop van tijd op priemen strandt.
Brute kracht
Het is niet zo moeilijk om een relatief laag geheel getal te ontbinden in priemfactoren. Je hebt er je hersenen en een beetje tijd voor nodig en hebt het waarschijnlijk op de lagere school moeten doen. Hoe groter de getallen, hoe moeilijker de ontbinding wordt. Er is immers, voor zover wiskundigen weten, geen efficiënte formule waarmee je eender welk getal kan ontbinden.
Er bestaan natuurlijk wel technieken, maar uit hoe meer cijfers een getal bestaat, hoe moeilijker en minder efficiënt die worden. Een brutekrachtaanval op het getal 8 voor de ontbinding in 2 x 2 x 2 is niet zo moeilijk, maar wanneer een krachtige supercomputer de opdracht krijgt om een getal met 500 cijfers te ontbinden in priemfactoren, dan heeft die meer tijd nodig dan de totale leeftijd van de aarde.
Er bestaat met andere woorden geen wiskundige maar wel een praktische limiet voor de grootte van getallen die we kunnen ontbinden in priemfactoren en op dat feit is moderne computerbeveiliging gebouwd. Dat verdient een beetje verduidelijking.
Onbeveiligde beveiliging
Eerst en vooral staan we even stil bij de manier waarop een beveiligde connectie tussen computers tot stand komt. Beveiligde verbindingen over het internet worden per definitie opgezet in een onbeveiligde omgeving. Dat gebeurt door encryptiesleutels uit te wisselen. Die sleutels zijn publiek te onderscheppen, maar ze dienen enkel om data te versleutelen. De sleutel voor de decryptie verschilt van de encryptiekey, en die wordt niet zomaar verzonden.
De absurde rekenkracht die nodig is om getallen in factoren te ontbinden maakt die werkwijze mogelijk. Beeld je ter illustratie twee gigantische priemgetallen in, bestaande uit honderden cijfers. Wanneer je die priemgetallen met elkaar vermenigvuldigt, krijg je een enorm getal dat deelbaar is door één, zichzelf en de twee priemgetallen waaruit het is opgebouwd. De priemen vermenigvuldigen om het grote getal te krijgen is niet moeilijk, maar andersom is het praktisch onmogelijk om, zelfs met ’s werelds krachtigste supercomputer, het enorme getal terug in z’n factoren te ontbinden.
Publieke sleutel
Het grote getal kan in dit geval dienst doen als publieke sleutel. Die sleutel wordt over het internet verzonden om de beveiligde verbinding op te zetten. De computer die de key ontvangt, versleutelt er data mee, maar kan die zelf niet ontcijferen. Dat kan geen enkele computer, behalve degene die de publieke sleutel in eerste instantie genereerde. Dat systeem is immers op de hoogte van de twee priemgetallen waaruit de publieke sleutel bestaat.
Onderschept een hacker de sleutel dan kan hij data versleutelen, maar zonder de twee oorspronkelijke priemgetallen is decryptie onmogelijk. Twee computers die sleutels uitwisselen met elkaar kunnen zo beveiligd over het internet communiceren. Ze krijgen ieder een sleutel, coderen er data mee, zenden die naar hun respectievelijke communicatiepartner en enkel daar kan de data ontcijferd worden. Hoe de encryptie zelf precies in z’n werk gaat, is een ander verhaal, voor dit artikel is het belangrijk te weten dat priemgetallen het fundament van het proces zijn.
RSA en kredietkaarten
Grote priemgetallen zorgen er dus voor dat een beveiligde verbinding kan ontstaan over een initieel onbeveiligd netwerk. Het principe schuilt achter de versleuteling van e-mails, maar ook achter het verzenden van betaalkaartinformatie of het doorgeven van persoonlijke gegevens. Er bestaan heel wat encryptiealgoritmes die gebruik maken van de ontbinding in factoren, waarvan RSA het bekendste is. RSA, een afkorting opgebouwd uit de eerste letters van de voornamen van de uitvinders, is populair bij het opzetten van een beveiligde verbinding voor kredietkaartbetalingen.
Niet waterdicht
Priemgetallen zijn dus meer dan een aardigheid binnen de moderne wiskunde, ze zijn van levensbelang voor de beveiliging van de digitale wereld. Het systeem heeft echter één fundamenteel probleem: het is perfect mogelijk om de encryptie te kraken, zolang je maar voldoende tijd hebt. Het duurt al snel duizenden jaren om de decryptiesleutel te vinden en tegen dan is de ontcijferde data toch waardeloos, en is iedereen die er iets mee te maken had al lang dood. Computerkracht staat natuurlijk niet stil, en hoe sneller computersystemen worden, hoe minder tijd ze nodig hebben om een publieke sleutel te breken.
In 2009 was RSA-768 de standaard. De 768 bit-encryptie maakte gebruik van een getal met 232 cijfers als sleutel. Enkele onderzoekers onder leiding van Thorsten Kleinjung lieten zich daar niet door afschrikken en ze gingen de sleutel te lijf. Niet met één computer, maar met een netwerk van honderden toestellen voorzien van geavanceerde ontbindingsalgoritmes.
Het netwerk deed er twee jaar over maar de RSA-768-sleutel werd gekraakt. Op die twee jaar verzette het computernetwerk het equivalent van 2.000 jaar rekenen door een single-core 2,2 GHz AMD Opteron-cpu. Het resultaat leverde de onderzoekers 50.000 dollar op: een beloning uitgevaardigd door de RSA-stichters zelf.
Upgrade
Twee jaar is al bij al niet zo lang en met de snelle vooruitgang van computerkracht was het meteen duidelijk dat RSA-768 geen plaats meer had in de beveiligingswereld. Vandaag spreken we van 1024 bit-encryptie met getallen bestaande uit 309 cijfers en voorlopig heb je nog een combinatie van supercomputers en een tijdsmachine nodig om daar doorheen te kauwen. Schuw je niet weg van een uitdaging? Dan kan je 100.000 dollar verdienen door de wiskundigen van de wereld ongelijk te geven.
Quantumgevaar
Ook RSA-1024 zal niet eeuwig veilig blijven. Traditionele computers voorblijven door de gebruikte getallen te verhogen is niet zo moeilijk, maar onderzoek naar een niet zo traditionele computer geniet dezer dagen hoge prioriteit. Quantumcomputers werken op een totaal andere manier.
Omdat bits in een quantumsysteem 0, 1 of 0 én 1 kunnen zijn, kan een quantumcomputer verschillende scenario’s tegelijkertijd contempleren. Wiskundigen vrezen dat een functionele quantumcomputer, die z’n beloftes nakomt, zelfs door de meest geavanceerde priemgetallen-encryptie kan breken in seconden, waarna het gedaan is met de beveiliging van het internet zoals we die vandaag kennen.
