7.4.1 Das Verfahren RSA

Grundlage des Verfahrens ist ein Satz des Schweizerischen Mathematikers Leonhard Euler aus dem 18. Jahrhundert. Leonhard Euler lebte von 1703 bis 1783; die letzten 17 Jahre seines Lebens war er blind. Die Schreibweisen für die drei bekanntesten mathematischen Konstanten - e, Pi und i - sind von ihm. Als Zeitgenosse von Größen wie Voltaire lebte und arbeitete er an den Höfen Friedrichs des Großen von Preußen und Katharina der Großen von Rußland.

Wir wollen uns mit der zugehörigen Mathematik nur soweit nötig auseinandersetzen, die genaue Formulierung des Satzes und der Folgerungen findet man beispielsweise in [21, 27, 28].

Kernstück der verwendeten Strukturen ist eine simple Funktion, die Eulersche Phi-Funktion (in der angelsächsischen Literatur auch als "totient function" bezeichnet). Diese Funktion beschreibt einfach die Anzahl der natürlichen Zahlen kleiner als eine festgelegte Zahl n, die keinen gemeinsamen Teiler mit n haben außer 1.

Um das zu verdeutlichen, betrachten wir das Beispiel für "n = 10":

Unter den Zahlen

  1  2  3  4  5  6  7  8  9  10

sind genau 4 Zahlen teilerfremd zu 10:

  1  3  7  9

also gilt

  Phi(10) = 4

Ein anderes Beispiel - "n = 13":

  1  2  3  4  5  6  7  8  9  10  11  12  13

Hier gibt es genau 12 Zahlen, die dieser Bedingung genügen, denn 13 ist im Gegensatz zu 10 eine Primzahl, also nicht weiter teilbar. Damit kann sie auch keine gemeinsamen Teiler mit kleineren Zahlen haben, sonst wäre sie ja keine Primzahl. Also gilt

  Phi(13) = 12

Ein weiteres Beispiel:

  1  2  3  4  5  6

Hier gilt

  Phi(6) = 2

(nämlich die beiden Zahlen 5 und 1). Dabei ist 6 ein Produkt aus zwei verschiedenen Primzahlen. Das wird noch bedeutsam, denn aus diesem eigentlich recht einfachen Zusammenhang werden nun zwei wichtige Erkenntnisse gezogen:

  1. Wenn n eine Primzahl ist, dann gilt stets: Phi(n) = n - 1.
  2. Handelt es sich bei n um ein Produkt aus zwei verschiedenen Primzahlen p und q, so gilt stets: Phi(pq) = (p-1)(q-1).

Nun formulierte Euler, daß, wenn man zwei natürliche und zueinander teilerfremde Zahlen n und m wählt, folgender Zusammenhang gilt:

mPhi(n) mod n = 1

Wenn n und m nun sogar zwei Primzahlen sind, nennen wir sie wieder p und q, dann gilt

m(p-1)(q-1) mod pq = 1

In [21] oder in jedem Buch über Zahlentheorie ist eine Begründung (Beweis) nachzulesen, warum das so ist.

Was nützt uns das nun?

Wir benutzen die gerade beschriebenen Zusammenhänge, um damit ein public key-System zu bauen. Erinnern wir uns: Wir benötigen ein allgemeines Verfahren und zwei Schlüssel E und D, um das System anwenden zu können.

Das Verfahren ist schnell anzugeben: Will Alice an Bob eine Nachricht M verschlüsselt schicken, berechnet sie

C = E(M) = Me mod n

Will Bob die verschlüsselte Nachricht C dechiffrieren, so berechnet er

M = D(C) = Cd mod n

Die Schlüssel bestehen nun aus jeweils einem Paar:

verschlüsseln (e,n)
entschlüsseln (d,n)

Das erste Paar ist der öffentliche Teil, das zweite Paar ist der geheime Teil.

Wie berechnet man nun diese Zahlen n, e und d?

Um n zu berechnen, wählt man zwei Primzahlen p und q aus und bildet deren Produkt, also

n = p * q

Dabei müssen diese Primzahlen sehr groß sein und auch noch weiteren Bedingungen genügen, die wir noch ansprechen werden.

Obwohl es zwar relativ einfach ist, eine solche Multiplikation durchzuführen, ist es - so der heutige Stand der Mathematik - äußerst zeitaufwendig, aus dem Produkt die beiden Primzahlen zu ermittlen. Diese "Faktorisierung" ist der Schlüssel zur Wirksamkeit des Systems, zusammen mit der Multiplikation ergibt sich hier so etwas wie eine Falltürfunktion.

Nun wählt man eine sehr große natürliche Zahl d, die zu

(p-1)(q-1)

teilerfremd sein muß. Schließlich berechnet man die Zahl e als sogenanntes "multiplikatives Inverses" zu

d mod (p-1)(q-1)

Die beiden Zahlen d und e - also unsere beiden Schlüssel - stehen also nun in folgendem Verhältnis:

(e * d) mod (p-1)(q-1) = 1

Damit "heben" sich e und d auf, genauso wie 5 und 1/5 bezüglich der üblichen Multiplikation. Das ist ja auch nötig, denn wie soll sonst der Schlüssel d das entschlüsseln können, was mit e verschlüsselt wurde?

Das Interessante ist aber, daß e und d verschiedene Zahlen sind und trotzdem zueinander invers.