Nachdem wir nun schon ein paar Grundprinzipien kennegelernt haben, stellt sich natürlich die Frage, wie werden D und E realisiert und wie sicher sind diese Verfahren damit?
Um ein public key-Verfahren sicher zu machen, muß die "legale" Benutzung relativ einfach und leicht durchzuführen sein. Der Besitzer beider Schlüsselteile, des öffentlichen und des geheimen, kann seine Absicht, die Nachricht zu entschlüsseln oder zu prüfen, schnell durchführen.
Dem potentiellen Angreifer stehen aber auch nicht wenige Informationen zur Verfügung: der öffentliche Schlüssel und der Geheimtext bzw. das unterschriebene Dokument.
Die "illegale" Berechnung des fehlenden Teils muß deswegen außerordentlich aufwendig sein, das heißt, sie darf zwar theoretisch möglich sein, aber sie muß wenigstens praktisch unmöglich sein.
Um das zu erreichen, werden sogenannte Falltürfunktionen benutzt. In der Theorie sind das mathematische Funktionen, die sich sehr einfach anwenden lassen; ihre Umkehrung jedoch läßt sich nur mit zu großem Aufwand berechnen.
Das Problem dabei ist, daß es äußerst schwierig ist zu beweisen, ob eine Falltürfunktionrfunktion vorliegt.
Für solche Anwendungen benutzt man in der Regel zwei mathematische Operationen, die diesen Bedingungen aller Kenntnis nach gehorchen:
Solche System liefern also grundsätzlich schon eine Methode mit, wie man sie knacken kann. Es ist also hier, im Gegensatz zu symmetrischen Verfahren, nicht die Frage, ob man das System knacken kann, sondern ob es eine wirksamere Methode als die schon bekannte gibt, wie man an die Lösung kommt.
Das Problem an der Sache ist, daß man darüber nichts weiß. Man weiß nicht, ob es nicht vielleicht doch schnellere Methoden gibt, die Umkehrung zu berechnen; man weiß nicht, ob es nicht trickreiche andere Zugänge gibt, mit dem man das Problem der Umkehrung umgehen kann.
Man gründet die Sicherheit solcher Verfahren also auf folgende Punkte:
Mit anderen Worten: man kann die Sicherheit des Verfahrens nicht beweisen - ja noch schlimmer: man macht die Sicherheit des Verfahrens von der momentanen Unfähigkeit abhängig, eine flotte Lösung zu finden.
Im Jahre 1993 wurde eine alte Wette wieder aufgegriffen, die im Jahre 1977 ausgesprochen wurde [24]. Es ging um die Herausforderung, eine 129-stellige Zahl in ihre 2 Primzahlfaktoren zu faktorisieren. Die Zahl bekam den Namen "RSA-129", da dieses Problem den direkten Schlüssel zur Sicherheit des RSA-Verfahrens darstellt.
RSA-129 = 1143816257578888676692357799761466120102182 9672124236256256184293570693524573389783059 7123563958705058989075147599290026879543541 (129 digits, checksum = 105443)
Abb. 7.4: RSA-129
Als symbolischer Preis wurden, wie in der Kryptologie schon Tradition, einhundert US-Dollar ausgesetzt. 16 Jahre später wollte ein Gruppe Wissenschaftler einen Rechnerpool ausnutzen, der einzigartig ist und bisher noch nicht in dieser Weise ausgenutzt wurde: das Internet.
Am 25. August 1993 erschien dieser Artikel in der Usenet-newsgroup sci.math.research:
Newsgroups: sci.math.research From: explorer@iastate.edu (Michael Graff) Subject: Large factoring attempt on RSA-129 Approved: Daniel Grayson <dan@math.uiuc.edu> Date: Tue, 24 Aug 1993 22:17:56 GMT Summary: Workers needed for a factoring attack on rsa-129 Message-ID: <explorer.746230676@tbird.cc.iastate.edu> Sender: Daniel Grayson <dan@math.uiuc.edu> Originator: dan@symcom.math.uiuc.edu Organization: Iowa State University, Ames IA Lines: 72 CALL FOR PARTICIPANTS --------------------- In 1977, a 129-digit integer appeared in the pages of Scientific American. This number, the RSA challenge modulus or RSA-129, has not yet been successfully factored. Factoring it, a 425-bit number, would be a major milestone in cryptography, as it would show that current technology is able to break commonly-used RSA- cryptosystem keys within a reasonable time. Excerpted from the RSA Factoring Challenge news: The "RSA challenge" published in the August 1977 issue of Scientific American (in Martin Gardner's column) is still open, and the $100 prize offer still stands. This prize can be won by factoring the RSA modulus published there, which is: RSA-129 = 114381625757888867669235779976146612010218296721242362 562561842935706935245733897830597123563958705058989075 147599290026879543541 (129 digits, checksum = 105443) --- End of RSA Factoring Challenge news --- As with several other recent large scale factoring projects, we propose to attack this number with a very large number of workstations independently operating at dozens of research and corporate networks around the world. We are soliciting volunteers to provide compute cycles to help us towards our goal. With the permission of the authors, we will use the publicly available code of the Lenstra/Manasse Factoring by Email project, with modifications by Paul Leyland for RSA-129. The sieving will be distributed around the Internet, with relations transferred to a central site by email or ftp as convenient. Combining the relations and matrix elimination will be performed at ISU, using a combination of structured Gauss and a MasPar dense matrix eliminator. Each participant will be provided with complete source code for the siever. You can easily verify that the program takes no input from your machines and does not pose a security risk. It requires only an email connection to transmit partial results - the software does not require communication with other machines except for this purpose. It is easy to install, and is designed so that it will take up no CPU cycles on your machine when interactive users or other important processes are active. If preferred, articipants can accumulate the results locally and ftp them to the central site manually. The project currently has around 500 workstations which are ready to begin sieving. However, to finish in a reasonable amount of time, this count needs to increase greatly. We are attempting to enroll around 10,000 workstations in this project. This is a call for participants, who have workstations or MasPars at their disposal and would like to participate in this project. All contributions help a great deal. There is a $100 prize associated with factoring this number. The prize, if we win it, will be donated to the GNU project of the Free Software Foundation to help generate more of the excellent software they currently provide. For more information, please mail rsa129-request@iastate.edu. We will respond to all questions quickly. --Michael Graff [project coordinator/programmer] --Derek Atkins [coordinator/programmer] --Paul Leyland [advisor/programmer] --Daniel Ashlock [faculty advisor ISU] -- Michael Graff <explorer@iastate.edu> Speaking for myself, not Project Vincent Voice: (515)294-4994 for ISU or the ISUCC Iowa State Univ Comp Center Fax: (515)294-1717 Ames, IA 50011 -=*> PGP key on pgp-public-keys@pgp.iastate.edu <*=-
Listing 7.1: Kooperationsaufruf "RSA-129"
Im Laufe der Zeit nahmen über 600 Helfer in mehr als 20 Ländern aus allen 5 Kontinenten dieser Erde an dem Projekt teil. Jeder bekam denselben Programmquelltext, der auf dem eigenen System installiert werden mußte. Die Teilergebnisse wurden automatisch per e-mail an die Koordinatoren gesandt, die regelmäßig über den Stand der Berechnungen berichteten.
Nach nicht einmal acht Monaten hatte die Gemeinschaft der Rechner mit einer geschätzten Leistung von 5000 MIPs etwas geschafft, was man bisher nur in Gedankenexperimenten durchgespielt hatte: Die Zahl wurde erfolgreich faktorisiert.
RSA-129 = 1143816257578888676692357799761466120102182 9672124236256256184293570693524573389783059 7123563958705058989075147599290026879543541 = 4905295108476509491478496199038981334177646 38493387843990820577 * 2769132993266709549961988190834461413177642 967992942539798288533
Selbstverständlich wurde nicht einfach die Zahl veröffentlicht, sondern mit ihr auch eine durch sie verschlüsselte Nachricht, mit bekanntem öffentlichen Schlüssel.
Der entschlüsselte Text war die Türe zu den $100 - die Lösung war die Nachricht:
THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE
Der enthaltene Text ist trotz oder gerade wegen seines scheinbar sinnlosen Inhaltes ein wunderbares Beispiel für mehrere Dinge:
Nachdem diese Meisterleistung bekannt wurde, rauschte es im Blätterwald. Es war die Rede von "RSA-Verfahren geknackt!" - und ähnliche, sehr unscharfe Formulierungen schreckten die Anwender des Verfahrens RSA auf. Deswegen soll an dieser Stelle noch einmmal betont werden: Wie man RSA knackt (zumindest die naheliegendste Methode), war von Anfang an bekannt, nämlich durch Faktorisierung. Das Problem war niemals, ob man es könnte, sondern stets, wie schnell man es durchführen kann.
Wir werden im Abschnitt über RSA noch ein paar weitere Details dazu erfahren.