[informatik-bonn] heise online: RSA-576 geknackt
- From: Philipp Kirchner <mail@xxxxxxxxxxxxxxxxxx>
- To: informatik-bonn@xxxxxxxxxxxxx
- Date: Tue, 9 Dec 2003 09:14:45 +0100
Diese Meldung aus dem heise online-Newsticker wurde Ihnen
von "Philipp Kirchner <mail@xxxxxxxxxxxxxxxxxx>" gesandt.
Wir weisen darauf hin, dass die Absenderangabe nicht verifiziert
ist. Sollten Sie Zweifel an der Authentizität des Absenders haben,
ignorieren Sie diese E-Mail bitte.
--------------------------------------------------------------------
Jaja, immer die Bonner Mathematiker...
--------------------------------------------------------------------
RSA-576 geknackt
Nur kurz nach der Entdeckung der bislang größten bekannten Primzahl[1]
haben zwei Teams unabhängig voneinander Erfolge mit der Faktorisierung
großen Zahlen mit Hilfe der Methode des General Number Field Sieve[2]
gemeldet. Jens Franke von der Universität Bonn[3] knackte die von der Firma
RSA Security[4] 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[5]. Unterstützt wurde Franke vom Bundesamt
für Sicherheit in der Informationstechnik (BSI[6]), 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[7] 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[8] die 228stellige Mersenne-Zahl
2757-1 komplett zu faktorisieren[9]. 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[10]. Eine
umfangreiche Linksammlung zum Thema Faktorisierung großer Zahlen finden
Interessierte bei CiteSeer[11]. (as[12]/c't)
URL dieses Artikels:
http://www.heise.de/newsticker/data/as-08.12.03-000/
Links in diesem Artikel:
[1] http://www.heise.de/newsticker/data/as-02.12.03-000/
[2] http://mathworld.wolfram.com/NumberFieldSieve.html
[3] http://www.uni-bonn.de/
[4] http://www.rsasecurity.com/
[5] ftp://ftp.math.uni-bonn.de/people/franke/mpqs4linux/
[6] http://www.bsi.de
[7] http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html
[8] http://www.nfsnet.org
[9] http://www.nfsnet.org/ann-2_757M_1.html
[10] http://www.nfsnet.org/join.html
[11] http://citeseer.nj.nec.com/398050.html
[12] mailto:as@xxxxxxxxxxx
--------------------------------------------------------------------
Copyright 2003 by Heise Zeitschriften Verlag
Other related posts:
- » [informatik-bonn] heise online: RSA-576 geknackt
