CWI Factorisatie 512-bits getal bedreigt veiligheid E-commerce

Wetenschappers van het Centrum voor Wiskunde en Informatica (CWI)  te Amsterdam hebben op zondag 22 augustus een getal van 512 bits  gefactoriseerd, dat model staat voor 95% van de sleutels die gebruikt  worden bij de beveiliging van electronic commerce op Internet.  Hiermee is, veel eerder dan bij de start van E-commerce op Internet werd verwacht, aangetoond dat de populaire sleutelgrootte van 512 bits niet meer veilig is. Met deze 512-bits sleutels worden dagelijks grote geldstromen beveiligd.

Wetenschappers van het Centrum voor Wiskunde en Informatica (CWI)  te Amsterdam hebben op zondag 22 augustus een getal van 512 bits  gefactoriseerd, dat model staat voor 95% van de sleutels die gebruikt  worden bij de beveiliging van electronic commerce op Internet.  Hiermee is, veel eerder dan bij de start van E-commerce op Internet werd verwacht, aangetoond dat de populaire sleutelgrootte van 512 bits niet meer veilig is. Met deze 512-bits sleutels worden dagelijks grote geldstromen beveiligd.

Model
De gekraakte sleutel staat model voor de zogenaamde "publieke" sleutel in het bekende RSA public-key cryptosysteem, dat midden jaren zeventig door de onderzoekers Rivest, Shamir en Adleman van het MIT in Cambridge (USA) werd ontworpen. Tegenwoordig wordt dit systeem op  grote schaal in hardware en software gebruikt voor het beveiligen van data-transport. Het veelgebruikte SSL protocol voor Internet is hier  bijvoorbeeld op gebaseerd. Het gevonden resultaat betekent ook een wetenschappelijke doorbraak. Vijfentwintig jaar geleden schatte men dat het factoriseren van 512-bits  getallen meer dan 62 miljard jaar rekentijd zou kosten.

Snel rekenwerk
Het getal dat nu ontbonden is, aangeduid als RSA-155 omdat het uit 155 decimale cijfers bestaat, komt uit een door het Californische bedrijf  RSA Data Security opgestelde "Challenge List" die als graadmeter geldt  voor de veiligheid van RSA. Om de factoren van RSA-155 te vinden hebben ongeveer 300 zeer snelle  SGI en SUN workstations en Pentium II PCs in totaal 35 jaar staan  rekenen. Doordat deze computers grotendeels parallel, meestal buiten de kantooruren, aan dit project rekenden, kon de klus in ongeveer zeven kalendermaanden worden geklaard.  Negen organisaties hebben daartoe computertijd beschikbaar gesteld:  Citibank (USA), CWI (Nederland), CNRS (Frankrijk), Entrust Technologies (Canada), Centre Charles Hermite (Frankrijk), Lehigh University (USA), Microsoft Research (UK), Sun Microsystems  (UK) en de University of Sydney (Australie). Daarnaast is op de Cray C916 supercomputer van SARA een essentiele  stap van het rekenwerk verricht die extreem veel intern geheugen vroeg. Deze job kon in ongeveer in tien kalenderdagen worden voltooid.

Verder onderzoek
Verwacht wordt dat de de zeven kalendermaanden tot een week of zelfs een dag teruggebracht kunnen worden, omdat het grootste deel van het  rekenwerk parallel kan worden uitgevoerd. Tegenwoordig doen tienduizenden PC bezitters al mee aan grote gedistribueerde rekenprojecten, bijvoorbeeld om buitenaardse boodschappen op  te sporen. Ook de rekenstap op de supercomputer kan worden geparallelliseerd, maar dat kost veel meer moeite. Daar wordt  momenteel nog onderzoek aan gedaan.
Coordinator van het onderzoek is CWI-onderzoeker Herman te Riele.

Het getal en de gevonden factoren

RSA-155 =
109417386415705274218097073220403576120037329454492059909138421314763499842889\
34784717997257891267332497625752899781833797076537244027146743531593354333897
=
102639592829741105772054196573991675900716567808038066803341933521790711307779
*
106603488380168454820927220360012878679207958575989291522270608237193062808643 

Noot voor de redactie : De \ in het getal staat voor een regel-afbreek-teken.