Je leest:

Veiligheid RSA-encryptie in gevarenzone

Veiligheid RSA-encryptie in gevarenzone

De huidige manier waarmee betalingsverkeer over het internet wordt beveiligd, wordt in hoog tempo minder veilig. Een nieuw factorisatierecord laat zien dat er geen duizenden jaren meer nodig zijn om dergelijke versleutelingen te breken.

De encryptie – het coderen van gegevens op basis van een algoritme – waarmee online transacties worden beveiligd, kan binnen enkele jaren wel eens vele malen minder effectief zijn dan we vandaag de dag denken. Hiervoor waarschuwt cryptografie-expert Arjen Lenstra, werkzaam aan de Ecole Polytechnique Fédérale de Lausanne (EPFL) in Zwitserland. Hij doet onderzoek naar de mogelijkheden om 1024-bit encryptiesleutels te kraken. Samen met onderzoekers van Nippon Telegraph and Telephone Corporation en de universiteit van Bonn heeft hij voor het eerst een getal van meer dan 1000 bits gefactoriseerd. Het vorige record met dit factorisatiealgoritme bedroeg 911 bits. Het nieuwe resultaat, 21039 – 1, is gelijk aan:

5080711 x 55 853 666 619 936 291 260 749 204 658 315 944 968 646 527 018 488 637 648 010 052 346 319 853 288 374 753 x 20 758 181 946 442 382 764 570 481 370 359 469 516 293 970 800 739 520 988 120 838 703 792 729 090 324 679 382 343 143 884 144 834 882 534 053 344 769 112 223 028 158 327 696 525 376 091 410 189 105 241 993 899 334 109 711 624 358 962 065 972 167 481 161 749 004 803 659 735 573 409 253 205 425 523 689.

In een persbericht van de EPFL zegt Lenstra dat dit getal het grootste ‘speciale’ en moeilijk te factoriseren getal is. Het getal is ‘speciaal’, omdat het een zogeheten Mersenne-getal is, dat wil zeggen: een getal van de vorm 2n – 1.

Arjen Lenstra

RSA

RSA is een encryptiealgoritme, dat ervoor zorgt dat elektronische handel veilig kan plaatsvinden. Het algoritme werd in 1977 ontworpen door Ron Rivest, Adi Shamir en Len Adleman, vandaar de afkorting RSA. Het RSA-algoritme gebruikt een systeem van publieke en private sleutels om berichten te versleutelen. De publieke sleutel wordt berekend door twee heel grote priemgetallen te vermenigvuldigen. Om de private sleutel te kunnen kraken, moeten de twee priemgetallen uit de publieke sleutel worden ‘onttrokken’. Hiervoor is echter nog wel de nodige rekenkracht en een flinke dosis geduld nodig. Nieuwe ontwikkelingen op dit gebied, waardoor de rekentijd aanzienlijk korter wordt, zouden RSA onbruikbaar kunnen maken.

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

Zeefprogramma

Het nieuw gefactoriseerde getal van 1017 bits bestaat uit drie factoren van 7, 80 en 227 cijfers lang. De onderzoekers gebruikten een ‘zeefprogramma’ ( Special Number Field Sieve, zie de links onderaan dit artikel), en voerden de berekening uit in een tijd equivalent met 95 jaar op een Pentium D 3 GHz. Lenstra ontwikkelde de Special Number Field Sieve in de late jaren 1980 samen met zijn broer Hendrik Lenstra en de wiskundigen John Pollard en Mark Manasse. Na het zeven komt een stap lineaire algebra: in totaal 146 pc’s voerden parallel berekeningen uit gedurende iets meer dan twee maanden. De resultaten waren 47 niet-triviale oplossingen van het stelstel van vergelijkingen gedefinieerd door een 70 miljoen bij 70 miljoen grote spaarse matrix. Hieruit konden de onderzoekers dan in de laatste stap de factoren berekenen.

Tijd om te veranderen

De moeilijkheid van het factoriseren van grote getallen is de basis van de beveiliging van heel wat internetverkeer, zoals elektronische banktransacties en digitale handtekeningen met RSA-encryptie. Encryptie met 1024 bit RSA-sleutels, die nog heel wijdverbreid zijn, wordt met deze factorisatie stilletjesaan achterhaald. Beveiligingsexpert Bruce Schneier raadt dan ook (al jaren) aan om grotere RSA-sleutels te gebruiken. Ook Lenstra zegt dat de uren van 1024 bit RSA-sleutels geteld zijn: “Omdat onder andere banken en webwinkels deze encryptievariant gebruiken om hun financiële transacties te beveiligen, is het zinvol om alvast aan een opvolger te gaan denken. Ik zal geen voorspellingen over de toekomst van RSA-1024 doen, maar je kunt wel zeggen dat het verstandig is om de ontwikkelingen op de voet te volgen.”

Kunnen we ook over een paar jaar alles nog veilig versturen?

Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 24 mei 2007

Discussieer mee

0

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

LEES EN DRAAG BIJ AAN DE DISCUSSIE