Menü

RSA-576 geknackt

Nur kurz nach der Entdeckung der bislang größten bekannten Primzahl haben zwei Teams unabhängig voneinander Erfolge mit der Faktorisierung großen Zahlen mit Hilfe der Methode des General Number Field Sieve gemeldet. Jens Franke von der Universität Bonn knackte die von der Firma RSA Security unter RSA-576 gestellte Aufgabe, die 174-ziffrige Zahl:

18819881292060796383869723946165043980716356337941 73827007633564229888597152346654853190606065047430 45317388011303396716199692321205734031879550656996 221305168759307650257059

zu faktorisieren und zwar in

3980750 8642406493 7397125500 5503864911 9906436234 2526708406 3851895759 4638895726 1768583317
×
4727721 4610743530 2536223071 9730482246 3291469530 2097116459 8521711305 2071125636 3590397527

Damit steht Franke das von RSA ausgelobte Preisgeld in Höhe von 10.000 US-Dollar zu. Einen Teil der Linux-Software zur Faktorisierung stellt er auf seiner Website zur Verfügung. Unterstützt wurde Franke vom Bundesamt für Sicherheit in der Informationstechnik (BSI), das die Schlußarbeit übernahm. Entgegen anderer Meldungen sei das BSI aber nur zu einem "kleinen Teil" an der Arbeit beteiligt gewesen, betonte Referatsleiter Michael Boehm gegenüber heise Security. Als nächste Herausforderung warten nun RSA-640 bis RSA-2048 mit 193 bis zu 617 Dezimalziffern. Immerhin gibt es im letzten Fall 200.000 US-Dollar zu verdienen.

Die Firma RSA Security sponsert die Herausforderung, da sie sich davon Ermutigungen für die Forschung in der Zahlentheorie erhofft. Außerdem sollen die Bemühungen neue Erkenntnisse für die Kryptographie-Entwicklung und die die Eignung bestimmter Schlüssellängen für unterschiedliche Anforderungen bringen.

Parallel zum Knacken von RSA-576 schaffte es das auf Number Field Sieve spezialisierte Internet-Projekt NFSNET die 228stellige Mersenne-Zahl 2757-1 komplett zu faktorisieren. Hierzu musste der immerhin 213stellige Cofaktor zerlegt werden, der sich nach circa fünf Monaten Rechenzeit auf bis zu 120 Maschinen zu

p79 = 572213702 2002067824 2482279750 9585774915 1312827809 3884069623 4625318212 8916964593

p134 = 2403 3821640983 5080887362 7340300596 5446689002 3563443321 3056506664 3193813901 1197710904 2426941205 4543072714 9147426656 7777424732 5292327559

ergab. Das NFSNET ist inzwischen dabei, 2811-1 mit der Methode des Number Field Sieve zu zerlegen und sucht noch nach Mitstreitern. Eine umfangreiche Linksammlung zum Thema Faktorisierung großer Zahlen finden Interessierte bei CiteSeer. (as)

Anzeige
Zur Startseite
Anzeige