RSA-576 (beendet)

RSA Security hat einen Wettbewerb zur Faktorisierung großer Zahlen ausgeschrieben. Damit soll gezeigt werden, dass bei bestimmten Verschlüsselungsverfahren für die Gewährleistung der Sicherheit bestimmte Mindestlängen bei den Schlüsseln notwendig sind und andererseits genügend große Schlüssel mit der aktuell zur Verfügung stehenden Hardware nicht "geknackt" werden können.

Faktorisieren bedeutet die Zerlegung einer Zahl in alle ihre Primfaktoren. Für große Zahlen sind dabei keine wirklich schnellen Algorithmen bekannt, so dass man im allgemeinen nur eine (wenn auch eingeschränkte) Menge von Zahlen darauf hin testen kann, ob es sich um Primfaktoren der ursprünglichen Zahl handelt.

Bei der zu faktorisierenden Zahl in diesem Wettbewerb handelt es sich um: 188198812920607963838697239461650439807163563379417382700763356422988859715234665485319 060606504743045317388011303396716199692321205734031879550656996221305168759307650257059.

Im allgemeinen werden für die Faktorisierung großer Zahlen Sieb-Verfahren eingesetzt. Bei diesem Projekt werden stattdessen zufällig erzeugte Zahlen darauf hin getestet, ob sie Teiler der zu faktorisierenden Zahl sind. Das ist nicht sehr erfolgsversprechend, so dass irgendwann keine Arbeit mehr ausgegeben wurde und man einen besseren Algorithmus programieren wollte.

Die Zahl wurde Ende 2003 erfolgreich von einem projektunabhängigen Team faktorisiert. Zu dieser Zeit war RSA 576 aber längst eingestellt.

Inhalt

1 Projektübersicht
- 1.1 Projektstatus
- 1.2 Projektlinks
2 Clientprogramm
3 Meldungen

Projektübersicht

RSA-576
Name	RSA-576
Kategorie	Kryptographie
Ziel	Faktorisierung einer 576 Bit großen Zahl
Kommerziell	nein
Homepage	offline, hier Archive.org Link

Es ist uns leider nicht bekannt, wo auf der Welt dieses Projekt zu Hause ist.

Projektstatus

Projektstatus
Status	beendet
Beginn	03.10.2002
Ende	01.01.2003

Projektlinks

	(nicht mehr online)
Hintergrundinfos	www.theneoproject.com/faqs.html
Download	www.theneoproject.com/dloads.html
FAQ	www.theneoproject.com/faqs.html
Statistiken	www.theneoproject.com/tempstats.htm
Forum	www.theneoproject.com/wbboard/main.php

Clientprogramm

Betriebssysteme

	Windows
	Linux
	DOS
	BSD
	Solaris
	Java (betriebssystemunabhängig)

Client-Eigenschaften

Funktioniert auch über Proxy
Normal ausführbares Programm
Als Bildschirmschoner benutzbar
Kommandozeilenversion verfügbar
Personal Proxy für Work units erhältlich
Work units auch per Mail austauschbar
Quellcode verfügbar
Auch offline nutzbar
Checkpoints

Besonderheiten

Für Januar 2003 ist ein Linux-Client angekündigt.
Seit 1.0.515 ist der Client mehrsprachlich, d.h. man kann ihn mit einer deutschen Benutzeroberfläche betreiben.
Die Zahlen der anderen RSA-Faktorisierungs-Wettbewerbe sind ebenfalls im Client enthalten, so dass auch diese Projekte automatisch mit der gleichen Software berechnet werden können, sofern die Faktorisierung des aktuellen Schlüssels gelingen sollte.
Der Client ist auch für Nutzer ohne ständige Internetverbindung geeignet, da einstellbar ist, nach wievielen WUs der Client wieder den Server kontaktieren soll.
Neben diesem Projekt lässt sich auch sehr gut ein zweites Projekt gleichzeitig betreiben, da im Client eingestellt werden kann, welchen prozentualen Anteil an der gesamten zur Verfügung stehenden CPU-Zeit er nutzen soll. Damit kann man eine flexible Aufteilung der Rechenzeit zwischen den Clients erreichen.

Verwendeter Algorithmus

Zuerst wird eine zufällige Zahl erzeugt, die halb so viele Stellen wie die zu faktorisierende Zahl hat (und maximal so groß ist wie deren Wurzel ist).
Diese Zahl wird solange inkrementiert, bis mit Miller's Primzahltest als wahrscheinliche Primzahl eingestuft wird.
Nun wird geprüft, ob die zu faktorisierende Zahl durch diese mögliche Primzahl teilbar ist. Wenn ja, dann ist das Projektziel erreicht.
Leider ist dieser Fall sehr unwahrscheinlich. :-) Deshalb wird jetzt von der vorher erzeugten Zahl die erste Stelle gestrichen. Das Resultat der Streichung wird jetzt wieder als möglicher Teiler genommen (so wie die anfangs zufällig erzeugte Zahl).
Das Inkrementieren, Testen und Streichen wird solange wiederholt, bis die als Teiler in Frage kommende Zahl nur noch 18 Stellen hat. Danach wird eine neue Zufallszahl erzeugt.