RSA Verschlüsselung

Der Name besteht aus den Anfangsbuchstaben der Hausnamen der Mathematiker Ronald Rivest, Adi Shamir und Leonard Adleman, die das Verfahren 1977 entwickelten. RSA ist ein starkes Verfahren und war im ursprünglichem Kern von PGP implementiert.

Ein entscheidender Vorteil des asymmetrischen RSA Verfahrens gegenüber symmetrischen Verfahren besteht darin, daß der Schlüsseltausch entfällt.

Für das Verständnis von RSA sind der erweiterte Euklid, der kleine Satz des Fermat bzw. der Satz von Euler und der Miller Rabin Test wichtig. (siehe Euklid und testen)

RSA - ein asymmetrisches Verschlüsselungsverfahren

Bei dieser Verschlüsselungen gibt es ein zusammengehöriges Schlüsselpaar, den geheimen privaten und den öffentlichen Schlüssel. Beide werden von einer Person erzeugt, die nur den öffenlichen Schlüssel zugänglich macht. Obwohl mit beiden Schlüsseln verschlüsselt werden kann, sind sie nicht gleichwertig. Man hat zwei Möglichkeiten mit diesen Schlüsseln umzugehen:

  • Mit dem öffentlichen Schlüssel können vertrauliche Nachrichten an seinen Herausgeber verschlüsselt werden. Der Empfänger kann die Nachricht nur mit dem zugehörigen, seinem privaten Schlüssel entschlüsseln.
  • Seinen privaten Schlüssel kann man auch zum Verschlüsseln verwenden, um zu zeigen, daß man tatsächlich der Absender der Nachricht ist. In diesem Fall kann die Nachricht nur mit dem öffentlichem Schlüssel entschlüsselt werden.

RSA Kochrezept

  1. Wähle zwei (große) Primzahlen p und q (unbedingt p ≠ q wegen der φ Funktion). Nutzte Zufallszahlen und den Miller - Rabin Test. (siehe testen)
  2. Bestimme das Produkt N = p * q.
  3. Bestimme φ(N), die Anzahl der zu N teilerfremden natürliche Zahlen, die < N sind. Weil p und q prim sind, ist φ(N) = (p - 1) * (q - 1).
  4. Wähle e beliebig mit 1 < e < φ(N), ggT(e, φ(N)) = 1. Gute Idee: e ≠ p, e ≠ q, e ≠ 1, e ≠ φ(N) - 1, z.B. eine (große) Primzahl. e und N bilden den öffentlichen Schlüssel. p, q, φ(N) bleiben geheim, bzw. werden nach der Bestimmung von d vernichtet.
  5. Bestimme d, die modular Inverse, für den privaten Schlüssel aus der Vielfachsummendarstellung ggT(e, φ(N)) = x * φ(N) + y * e. d ist die kleinste positive Zahl der Form y + k * φ(N). d und N bilden den privaten Schlüssel. d bleibt geheim. Nutze zur Berechnung von d den erweiterten Algorithmus von Euklid. (siehe Euklid)

Offene Frage: Sollten p, q und e wirklich irgendwelche Primzahlen sein oder sollten sie noch andere Bedingungen erfüllen?

Wie läuft's ab?

  1. Die zu verschlüsselnden Daten(Klartext) K werden in die Klartextzahl T konvertiert. Mit T < N (wichtig!). Notfalls wird der Klartext so in Blöcke geteilt, daß die aus den Blöcken erzeugten Klartextzahlen die Bedingung erfüllen.
  2. Die Geheimtextzahl G wird mit der Verschlüsselung G=Te mod N erzeugt.
  3. Die Klartextzahl wird durch die Entschlüsselung T = Gd mod N zurückgewonnen.
  4. Die Klartextzahl wird in Text konvertiert.

Warum funktioniert die Ver- und Entschlüsselung?

  • Verschlüsselung G=Te mod N
  • Entschlüsselung T = Gd mod N
  • Frage: Warum ist T = (Te)d mod N?
  • Wissen : e * d ≡ 1 mod φ(N) d.h.
  • e * d = r * φ(N) + 1
  • Mit Satz von Euler: aφ(m)≡ 1 mod m

Los gehts.

  • (Te)d mod N ≡
  • Te * d mod N ≡
  • Tr * φ(N) + 1 mod N ≡
  • Tr * φ(N) * T mod N ≡
  • (Tφ(N))r * T mod N ≡
  • Satz von Euler anwenden
  • 1r * T mod N ≡
  • T mod N

Bingo.

Warum soll das sicher sein?

Ein Angreifer muß aus dem öffentlichen den privaten Schlüssel ableiten. Es ist kein effektives Verfahren bekannt, um aus e und N, d zu bestimmen. Man bräuchte p und q. Dazu müßte N faktorisiert werden. Oder man müßte φ(N) herausfinden. Das sind bei hinreichend großen Zahlen ernsthafte Schwierigkeiten.
Achtung: Einen Text ver- und entschlüsseln zu können bedeutet nicht, daß p und q Primzahlen sind. Man kann ja mal z.B. Carmichael Zahlen verwenden.

Es gibt Angriffe, die sich auf unterschiedliche e und d bei gleichem N beziehen. Diese können vorkommen, wenn für eine ganze Gruppe N festgelegt wird, aber jedes Mitglied ein anderes d und e hat. e sollte nicht zu klein sein. Es muß gelten: p ≠ q;. Wie unterschiedlich sollten p und q idealer Weise sein? Fazit: das hier ist nur zum Verständnis. Im echten Leben benutze bitte PGP.

Quelltext ein-/ausblenden