Die bekannteste ‘Public Key’-Verschlüsselungsmethode ist RSA.
Ihre Sicherheit beruht auf der Unmöglichkeit, astronomisch große Zahlen in Primfaktoren zu zerlegen. Effektive Angriffe auf RSA gibt es nur mit ‘Quantencomputern’, die aber bisher nicht gebaut werden können.

Das größte Problem bei der verschlüsselten Übermittlung von Nachrichten ist die Geheimhaltung des Schlüssels. Ein bekanntes Beispiel dafür ist das Knacken des ENIGMA-Schlüssels im 2. Weltkrieg durch den Mathematiker Alan Turing, wodurch
den Allierten zum Beispiel bei der Invasion 1944 die deutschen Gefechtsaufstellungen in der Normandie bekannt waren.

Deshalb gelten Verfahren als besonders sicher, deren Sicherheit nicht von der Geheimhaltung des Schlüssels abhängt: sogenannte asymmetrische (‘public key’) Verfahren, bei denen man auch bei Kenntnis der Verschlüsselungsmethode nicht sofort die Entschlüsselungsmethode kennt.

Das einfachste asymmetrische Verfahren, sowohl vom Verständnis als auch für die Implementierung in Soft- und Hardware ist RSA (benannt nach den Entwicklern Rivest, Shamir und Adleman).

RSA ist eine reale Anwendung für klassische Methoden der Zahlentheorie (Euklidischer Algorithmus, Kleiner Satz von Fermat) und ist deshalb ein gern gewähltes Beispiel für Vorträge über die praktische Relevanz der Mathematik. Das hat natürlich zur Folge, daß man auch im Internet viele ausführliche Erklärungen des RSA-Algorithmus findet (z.B. hier), so daß ich mich hier vielleicht etwas knapper fassen kann.

Die Asymmetrie des RSA-Verfahrens beruht letztendlich darauf, daß es leicht ist, zwei Zahlen zu multiplizieren, daß es aber schwierig ist, aus dem Produkt auf die beiden Faktoren zu schließen.

Sender A legt zwei große Primzahlen p und q fest. Das Produkt n=pq macht er öffentlich, die Faktoren p und q teilt er aber nur einmal B mit und hält sie ansonsten geheim. Korrektur: Das Produkt n=pq und eine Zahl d macht er öffentlich.

Wir nehmen an, daß die Nachrichten (bzw. ihre einzelnen Bits) als ganze Zahlen zwischen 0 und pq vorliegen.

Der öffentliche Schlüssel besteht nun aus n und einer ganzen Zahl d. Die Zahl d wird von A nicht geheim gehalten, und ist damit nicht nur B, sondern auch einem Hacker E bekannt.

Die Verschlüsselungsfunktion ist
x –> xd modulo pq,
wobei die Schreibweise ‘modulo pq’ bedeutet, daß wir den Rest von xd nach Divsion durch pq nehmen. (Nach Verschlüsselung haben wir also wieder eine Zahl zwischen 0 und pq.)

WENN jemand p,q kennt, dann kann er mit jedem einfachen Computeralgebra-System die Entschlüsselungsfunktion berechnen. Nämlich, durch Anwendung des Euklidischen Algorithmus kann man zunächst eine ganze Zahl e berechnen, so daß
de =1 modulo (p-1)(q-1).
Und dann ist die Entschlüsselungsfunktion einfach gegeben durch
y –> ye modulo pq.
Der Beweis ist eine einfache Anwendung des Kleinen Satzes von Fermat.
(Die mathematischen Rechnungen im Detail kann man z.B. bei Kant sehr kurz und gut erklärt nachlesen.)

Um es noch einmal zusammenzufassen: p und q sind nur Sender und Empfänger bekannt, n=pq und d sind öffentlich. e kann man leicht berechnen, wenn man d und (p-1)(q-1) kennt.

Um den RSA-Algorithmus zu knacken, muß man also neben n=pq auch (p-1)(q-1) kennen. Man kann sich leicht überlegen, daß dies äquivalent dazu ist, p und q berechnen zu können. Die Frage ist also, ob man aus der Kenntnis des Produkts zweier Primzahlen die beiden Primzahlen bestimmen kann.

Nun weiß natürlich jeder, daß es kein Problem ist, Zahlen wie etwa 21 oder 35 als Produkt zweier Primzahlen zu zerlegen. Schwierig wird es aber, wenn man astronomisch große Zahlen verwendet. Es gibt diverse Algorithmen zur Primfaktorzerlegung, die aber für sehr große Zahlen alle nicht praktikabel sind.

Allerdings werden die Algorithmen immer besser und deshalb muß man immer größere Zahlen verwenden, um die Sicherheit von RSA garantieren zu können. Als RSA 1977 entwickelt wurde, galten 125-stellige Zahlen als praktisch nicht faktorisierbar, und damit also als absolut sicher für die Verwendung in der RSA-Verschlüsselung.

1999 gab es einen öffentlichen Wettbewerb zur Faktorisierung einer 140-stelligen Zahl. (Die Zahl war vorher von einer Jury als Produkt zweier großer Primzahlen ausgewählt worden, und die Jury hielt diese beiden Primzahlen während des Wettbewerbes natürlich geheim.) Die Faktorisierung gelang tatsächlich mit 4-wöchigem Einsatz von 200 Rechnern.

2003-2005 gelang die Faktorisierung einer 200-stelligen Zahl mit zweijähriger Arbeit eines Rechnerpools unter Leitung der Bonner Mathematiker Jens Franke und Thorsten Kleinjung. Für praktische Zwecke geht man heute aber noch davon aus, daß 200-stellige Zahlen mit vernünftigem Aufwand nicht faktorisierbar sind und damit also Sicherheit für das RSA-Verfahren garantieren. Aktuell gibt es eine 309-stellige Zahl, auf deren Faktorisierung von der RSA-Firma ein Preis in Höhe von 100000 US-Dollar ausgesetzt ist.

Es gibt allerdings einen Algorithmus für Quantencomputer, mit dem man Primfaktorenzerlegungen effektiv berechnen könnte, wenn es Quantencomputer geben würde. Für diesen Algorithmus erhielt Peter Shor 1998 die Nevanlinna-Medaille, eine Art Nobelpreis für Theoretische Informatik, der alle 4 Jahre vergeben wird. Damals, in den 90er Jahren, galt Shor’s Algorithmus eher als theoretischer Erfolg, weil man nicht damit rechnete, in absehbarer Zeit Quantencomputer bauen zu können. Inzwischen gibt es aber weltweit viele Experimentalphysiker, die an praktischen Realisierungen von Quantencomputern arbeiten. Vielleicht wird es also in 10 oder 20 Jahren bereits Quantencomputer geben. Aus Sicht unserer heutigen Verschlüsselungstechniken wäre dies allerdings eine Katastrophe.

Referenz: Teil 1, Teil 2

Ein Online-Formular zum Verschlüsseln von Texten mit RSA findet man hier auf mathematik.de.

Kommentare (10)

  1. #1 Rabe
    25. März 2008

    “…die Faktoren p und q teilt er aber nur einmal dem Empfänger B mit und hält sie ansonsten geheim.”

    nee, macht er nicht, B braucht sie nicht. Das war ja gerade der Trick…

  2. #2 Thilo Kuessner
    25. März 2008

    Ich bin kein Fachmann (was Kryptographie angeht), aber bei Wikipedia steht:

    (Zitat:) Gewöhnlich wird in der Praxis der private Schlüssel etwas ausführlicher gespeichert, da diese Form der Speicherung das Entschlüsseln von Krypttexten effizienter macht (mit Hilfe des Chinesischen Restsatzes). Der private Schlüssel besteht daher dann, im Gegensatz zu dem, was im Rest dieses Artikels angenommen wird, aus folgenden Komponenten:

    * N, der RSA-Modul,
    * e, der Verschlüsselungsexponent,
    * p, die erste Primzahl,
    * q, die zweite Primzahl,
    * dmod (p − 1), häufig dmp1 genannt,
    * dmod (q − 1), häufig dmq1 genannt und
    * (1 / q)mod p, häufig iqmp genannt. (Ende Zitat)

    Du hast natürlich recht, daß es völlig ausreicht, B den Entschlüsselungsexponent e mitzuteilen, und daß man dann p und q eigentlich nicht mehr braucht.

  3. #3 Rabe
    26. März 2008

    Thilo,

    das Problem ist nicht, welcher der beiden Exponenten veröffentlicht wird. Zusammen mit dem Produkt der Primzahlen. Das ganze funktioniert umgekehrt, als du es beschrieben hast. Wenn A an B etwas senden will, so verschlüsselt er es mit B’s öffentlichem Schlüssel, so dass nur B es mit seinem geheimen Schlüssel entschlüsseln kann. So machen die beiden das gegenseitig. Die geheimen Schlüssel sind so, wie sie genannt werden, geheim. Sie werden nicht ausgetauscht.

    Das Problem reduziert sich damit auf die Authentifizierung der öffentlichen Schlüssel, damit sich nicht jemand dazwischenschaltet. S.a. https://hp.kairaven.de/pgp/gpg/gpg2.html

    [oops, zur Klarstellung: ich bin nicht Kai]

  4. #4 Thilo Kuessner
    26. März 2008

    Now I’ve got it. Ist korrigiert.

  5. #5 B. Golunski
    22. April 2008

    Hallo Thilo,

    welche Sicherheit in der Mathematik gibt, daß noch unendeckte mathematische
    Methode gibt, die Multiplikation von zwei Primzahlen zu faktorisieren.
    Ob alle 3 RSA Erfinder in der USA haben nicht großen Fehler begangen?

    Ich arbeite an einem mathematischen Verfahren, die beliebige RSA Zahl zu
    faktorisieren. Es läuft Testfase, aber Idee ist folgende, wenn multipliziert man
    zwei Zahlen von rechts nach links, da gibt Methode sie von links nach rechts
    zu faktorisieren. In meinem Model die RSA Zahl ist nur Zahlenkette die sequentiell
    von links nach rechts ist faktorisiert. Ich weß nicht ob es interessiert dich,
    aber denke ich, daß Enigma Geschichte kann sich wiederholen und zwar in
    anderen und grösseren Dimension.

    Grüße aus Toulouse

    Bogdan

  6. #7 Ingo Krumpholz
    3. Oktober 2009

    Ich habe das Faktorisierungsproblem gelöst. Besuchen Sie einmal meine Website
    Faktorisierung.com

  7. #8 Thilo Kuessner
    3. Oktober 2009

    Besuchen Sie einmal meine Website
    Faktorisierung.com

    Das habe ich eben getan. Aber – wie lösen Sie denn nun das Faktorisierungsproblem? Das habe ich dort nicht gefunden.

  8. #9 Faktor Bank
    2. Dezember 2009

    Ich habe mir die Elaborate des Herrn Ingo angeschaut:
    datadromos.de, rsa-wettbewerb.de, faktorisierung.com, usw.

    Mir scheint, der Herr Ingo ist ein Mystiker.
    Nur leider funktioniert die Mystik in der Naturwissenschaft nicht,
    sofern man auch die Mathematik zu den Naturwissenschaften zählt.
    Auch wenn man sich es noch so sehr wünscht.

  9. #10 anonymus
    12. Februar 2010

    Ja, kann eindeutig bestätigen, dass Ingo ein riesiger Spinner ist!