Je leest:

Digitale beveiliging met priemgetallen nadert houdbaarheidsdatum

Digitale beveiliging met priemgetallen nadert houdbaarheidsdatum

Auteur: | 14 januari 2010

Wiskundigen van het Centrum Wiskunde en Informatica (CWI) uit Amsterdam hebben met collega’s uit Frankrijk, Zwitserland en Japan een getal van 232 cijfers ontbonden in priemfactoren. Daarmee vestigden zij een record. Het rekenwerk toont aan dat het versleutelen van gegevens dat is gebaseerd op het ontbinden van grote getallen, in de toekomst niet meer veilig is.

Wiskundigen hebben een getal van 232 cijfers ontbonden in zijn twee priemfactoren, maar te laat om aanspraak te maken op een prijs van 50.000 dollar. Tot eind 2007 had RSA Laboratories, een bedrijf dat is gespecialiseerd op het gebied van digitale beveiliging, dit bedrag apart gelegd in het kader van de RSA Factoring Challenge. Het gaat hierbij om het vinden van de twee priemgetallen (getallen met precies twee delers, zoals 2, 3, 5, 7, 11, 13, …) waarvan het product gegeven is. Bij kleine getallen is dat makkelijk: je ziet onmiddellijk dat 15 het product is van de priemgetallen 3 en 5. Maar als het getal een paar honderd cijfers lang is, is het – ook voor een computer – een hele klus om de twee priemfactoren te vinden. Het prijzengeld was beschikbaar gesteld vanwege het belang in de cryptografie: met de RSA Factoring Challenge werd de robuustheid van encryptiesystemen getest. Inmiddels beschikt men over voldoende kennis, dat RSA Laboratories is gestopt met het uitkeren van prijzengeld.

RSA-encryptie

Het nieuw gefactoriseerde getal bevat, uitgeschreven in onze gewone, decimale notatie, 232 cijfers. Binair uitgeschreven (slechts gebruikmakend van nullen en enen) is het getal 768 symbolen lang. Daarom is het getal RSA-768 gedoopt. De letters RSA staan voor Rivest, Shamir en Adleman: de namen van de informatici die al in 1977 de eerste stappen zetten op het terrein van de digitale beveiliging met behulp van getallen die het product zijn van twee priemgetallen.

Met de letters RSA wordt een encryptiealgoritme aangeduid, dat ervoor zorgt dat elektronische handel, zoals online bankieren, veilig kan plaatsvinden. Het RSA-algoritme gebruikt een systeem van publieke en private sleutels om berichten te versleutelen. De publieke sleutel wordt berekend door twee grote priemgetallen te vermenigvuldigen. Om de private sleutel te kunnen kraken, moeten de twee priemgetallen uit de publieke sleutel worden gevonden en dat is erg moeilijk. Wiskundigen spreken van een NP-probleem: het vinden van de priemfactoren wordt ‘exponentieel moeilijker’ naarmate het te factoriseren getal groter wordt. Over het factoriseren van ‘RSA-768’ zou een enkele computer ongeveer 2000 jaar doen! Het resultaat na deze ellenlange rekenexercitie is dan:

1230186684530117755130494958384962720772853569595
33479219732245215172 64005072636575187452021997864
6938995647494277406384592519255732630345 373154826
8507917026122142913461670429214311602221240479274
73779408066 5351419597459856902143413 



=

3347807169895689878604416984821269081770479498371
37685689124313889828 83793878002287614711652531743
087737814467999489



x


3674604366679959042824463379962795263227915816434
30876426760322838157 39666511279233373417143396810
270092798736308917.

De naamgevers van het RSA-systeem: van links naar rechts Adi Shamir, Ron Rivest en Len Adleman

Door het rekenwerk te verdelen over honderden snelle computers, op verschillende locaties, lukte het om de twee priemfactoren van ‘RSA-768’ in niet meer dan tweeënhalf jaar tijd te vinden. Behalve van computers van het Amsterdamse CWI werd rekenkracht van computers in Duitsland (BSI en de Universiteit van Bonn), Frankrijk (INRIA Nancy), Zwitserland (EPFL) en Japan (NTT) gebruikt.

Voor gevoelige informatie zoals een creditcardcode is een 768-bit RSA-sleutel niet voldoende betrouwbaar: hiervoor worden sleutels van 1024 bits (309 decimale cijfers) gebruikt. Het factoriseren van een 1024-bit RSA-sleutel is zo’n duizend keer moeilijker dan de huidige RSA-768-kraak. Maar cryptografen voorspellen dat als de trend van het afgelopen decennium zich voortzet, de huidige standaard van 1024-bits RSA-sleutels over tien jaar even kwetsbaar zijn als de 768-bits RSA-sleutels dat nu zijn. Dat geeft aan dat het binnenkort tijd wordt om sleutels met een nog grotere lengte te gaan gebruiken, of om over te stappen op een geheel nieuw beveiligingssysteem. Want een volgend gevaar ligt op de loer: de kwantumcomputer, die in potentie een rekenkracht heeft die in no-time reusachtige RSA-sleutels lijkt te kunnen kraken.

Zie ook:

Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 14 januari 2010

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.