7.2 Sicherheit von asymmetrischen Verfahren

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.