Dark ITSec

RSA (Rivest, Shamir und Adleman)

RSA wurde von Rivest, Shamir und Adleman entwickelt und 1978 publiziert. Es ist ein System zur asymmetrischen Signatur und Konzelation, was zwar schnell, aber im Vergleich zu anderen Systemen nicht sicherer ist.

Zur Schlüsselerzeugung müssen die folgenden 4 Schritte durchlaufen werden:

  1. Man wählt zwei Primzahlen p und q, die ungefähr die gleiche Länge haben.
  2. Man berechnet: n = p*q und F(n) = (p-1)(q-1).
  3. Nun wählt man c so, daß gilt: 3 <= c < F(n) und ggT(c, F(n)) = 1.
  4. Dann berechnet man d mit dem speziellen Euklidschen Algorithmus, so daß gilt: c*d = 1 mod F(n), d.h. (c*d) mod F(n) = 1.

Öffentliche Schlüssel sind c und n, die geheimen sind d, p und q.

Sei m der zu verschlüsselnde Klartext. Dann funktioniert die Verschlüsselung folgendermaßen: (mc mod n) ist der Schlüsseltext. Beim Decodieren berechnet man mit [(mc)d mod n] den Klartext.

Beispiel
Wähle p = 5; q = 11 => n = 55; F(n) = 40;

Nun wählt man z.B. c = 7 (nach oben genannten Bedingungen) und berechnet d (Euklidscher Algorithmus):
40 = 5 * 7 + 5
 7 = 1 * 5 + 2
 5 = 2 * 2 + 1
 1 = 5 - 2 * 2
   = 5 - 2 * (7 - 1 * 5)
   = 3 * 5 - 2 * 7
   = 3 * (40 - 5 * 7) -- 27
   = 3 * 40 - 17 * 7
=> d = -17

Da d nicht negativ sein darf und da die zur Schlüsselgenerierung aufgeführte Bedingung (4.) auch dannnoch erfüllt ist, wenn man zu d ein Vielfaches von F(n) addiert, wählen wir für d den Wert -17 + 40 = 23, denn -17 = 23 mod 40 => d = 23.

Für einen beliebigen Klartext, z.B. m = 2 ergibt sich:
Verschlüsselung
27 mod 55 = 18 (Codewort)
Entschlüsselung
1823 mod 55 = 2 (Klartext)

Beim Einsatz von RSA als Konzelationssystem kann jeder mit den öffentlichen Schlüsseln c und n einen Klartext verschlüsseln und einen codierten Text an einen Inhaber der geheimen Schlüssel schicken. Nur dieser ist in der Lage, den Text mit Hilfe des geheimen Dechiffrierschlüssels wieder zu entschlüsseln; die Vertraulichkeit der mitgeteilten Daten bleibt also gewahrt.

Möchte man RSA als Signatursystem einsetzen, so sind nun der Testschlüssel t (entspricht c) und n öffentlich bekannt; geheim sind nach wie vor p und q, sowie der Signaturschlüssel s (entspricht d).

Um sich auszuweisen, verschlüsselt man nun einen Klartextblock mit Hilfe des geheimen Schlüssels und schickt den Klartext gemeinsam mit der Signatur (= dem verschlüsselten Text) an einen Empfänger. Dieser decodiert die Signatur mittels des öffentlich bekannten Testschlüssels und vergleicht den geschickten Klartext mit dem durch die Decodierung herausbekommenen. Nur wenn diese identisch sind, ist erwiesen, daß der Übersender der Botschaft derjenige ist, für den er sich ausgibt.

Es gibt zwei Arten von Angriffen auf RSA, den existentiellen Angriff und den selektiven. Beim existentiellen Brechen kann der Angreifer eine zufällige Nachricht entschlüsseln bzw. einen "sinnlosen" Klartext signieren. Das selektive Brechen dagegen ermöglicht dem Angreifer, eine ganz spezielle Nachricht zu decodieren bzw. einen von ihm frei wählbaren Klartext zu signieren.

Beispiel für existentielles Brechen des Signatursystems:
Bekannt sind zwei Klartexte m1 und m2 und dazu die passenden Signaturen m1s und m2s. Also lassen sich m3 und m3s folgendermaßen berechnen:

m3 := m2 * m1 mod n

m3s := m2s * m1s mod n

Beispiel für selektives Brechen des Signatursystems:
Man wählt einen beliebigen Klartext m3 und eine Zufallszahl r und berechnet m2 := m3 * rt (wobei t der öffentliche Testschlüssel ist). Dann läßt man m2 unterschreiben und erhält m2s.

Aus m2s = (m3 * rt)s = m3s * rt*s = m3s * r mod n berechnet man m3s, indem man m2s durch die Zufallszahl r modulo n dividiert.

Da alle bekannten Angriffe auf RSA auf die multiplikative Struktur von RSA aufbauen, erhält man durch zusätzliche Einbindung einer nicht-multiplikativen Hashfunktion ein relativ sicheres asymmetrisches Konzelations- bzw. Signatursystem.

Anstatt nur den Klartext m zu verschlüsseln, werden nun eine Zufallszahl z, der Klartext k und das Ergebnis der Hashfunktion h(z, k) aus Zufallszahl und Klartext verschlüsselt. Ebenso erhält der Empfänger nicht den reinen Klartext, sondern ein z', ein k' und die Hashfunktion h(z, k). Man bildet nun ebenfalls die Hashfunktion aus z' und k' und vergleicht diese mit der empfangenen Hashfunktion. Ist also h(z', k') = h(z, k) wurde der Klartext nicht verändert. Andernfalls wurde die Nachricht gefälscht.

RSA zählt zu den "wohluntersuchten" Systemen, kann aber nicht als "kryptographisch stark" eingestuft werden, da es bis heute noch keinen Beweis für die Sicherheit von RSA gibt. Obwohl bisher keine Angriffe auf das verbesserte RSA bekannt sind, kann man diese nicht ausschließen.

RSA ist den anderen Systemen dann vorzuziehen, wenn weniger Wert auf absolute Sicherheit als vielmehr auf Effizienz und Geschwindigkeit gelegt wird, die durch geschickte Wahl der Eingangsparameter um ein Vielfaches gesteigert werden kann.

Die Sicherheit von RSA beruht auf der Annahme, daß die Faktorisierung von n in die Primzahlen p und q mit heutigen Rechnern sehr schwer und zeitaufwendig ist. Sollte jedoch ein Verfahren für die schnelle Faktorisierung entdeckt werden, so verliert RSA genau wie viele andere, ähnlich aufgebaute Systeme seinen Nutzen.