Rabin-Kryptosystem

asymmetrisches Kryptosystem

Das Rabin-Kryptosystem ist innerhalb der Kryptologie ein asymmetrisches Kryptosystem, dessen Sicherheit beweisbar auf dem Faktorisierungsproblem beruht und das mit RSA verwandt ist. Es lässt sich auch zur Signatur verwenden. In der Praxis findet das Verfahren allerdings kaum Anwendung. Die Entschlüsselung ist nicht eindeutig, da es mehrere, in der Regel vier Lösungen für x der Gleichung gibt.

Geschichte

Bearbeiten

Das Verfahren wurde im Januar 1979 von Michael O. Rabin veröffentlicht. Das Rabin-Kryptosystem war das erste asymmetrische Kryptosystem, bei dem auf mathematischem Weg bewiesen werden konnte, dass es zumindest gleich schwierig zu lösen ist wie das Faktorisierungsproblem (das als nicht effizient lösbar angenommen wird).

Schlüsselerzeugung

Bearbeiten

Wie alle asymmetrischen Kryptosysteme verwendet auch das Rabin-Kryptosystem einen öffentlichen Schlüssel (Public Key) und einen geheimen Schlüssel (Private Key). Der Öffentliche dient der Verschlüsselung und kann ohne Bedenken veröffentlicht werden, während der geheime Schlüssel der Entschlüsselung dient und nur den Empfängern der Nachricht bekannt sein darf.

Es folgt nun eine genaue mathematische Beschreibung der Schlüsselerzeugung:

Seien   zwei möglichst große Primzahlen, häufig kurz als   geschrieben, für die eine bestimmte Kongruenzbedingung gelten muss. Der öffentliche Schlüssel   wird durch Multiplikation der beiden Zahlen erzeugt, also  . Der geheime Schlüssel ist das Paar  . Anders ausgedrückt: Wer nur   kennt, kann ver- aber nicht entschlüsseln, wer dagegen   und   kennt, kann damit auch entschlüsseln. Wären   und   keine Primzahlen, so ließe sich das Verfahren nicht anwenden.

Beispiel:

Wenn man   und   annimmt, dann ergibt sich daraus der öffentliche Schlüssel  .   und   sind gültige Zahlen, weil sie Primzahlen sind und die Kongruenzbedingung für sie gilt.

In Wirklichkeit werden viel größere Zahlen verwendet, um die Entschlüsselung durch Dritte schwierig zu machen (Primzahlen in der Größenordnung von   und größer).

Kongruenzbedingung

Bearbeiten

Im Rabin-Kryptosystem werden die Primzahlen   und   normalerweise so gewählt, dass die Kongruenzbedingung   gilt.

Diese Bedingung vereinfacht und beschleunigt die Entschlüsselung. Allgemein gilt nämlich: Sei   eine Primzahl mit   und   mit  , dann findet man eine Quadratwurzel   von   mit

 .

Es gilt also

 

wegen   nach dem kleinen Fermatschen Satz.

Da   eine Primzahl ist, gilt zudem entweder   oder  .

Wegen   ist die Kongruenzbedingung im Beispiel bereits erfüllt.

Verschlüsselung

Bearbeiten

Mit dem Rabin-Verfahren lassen sich beliebige Klartexte   aus der Menge   verschlüsseln. Alice, die einen solchen Klartext verschlüsseln will, muss dazu nur den öffentlichen Schlüssel   des Empfängers Bob kennen. Sie berechnet dann den Geheimtext   nach der Formel

 

Im praktischen Einsatz bietet sich die Verwendung von Blockchiffre an.

In unserem Beispiel sei   der Klartextraum,   der Klartext. Der Geheimtext ist hierbei nun  .

Dabei muss man beachten, dass für genau vier verschiedene   das   den Wert 15 aufweist, nämlich für  . Jeder quadratische Rest   hat genau vier verschiedene Quadratwurzeln modulo  .

Entschlüsselung

Bearbeiten
 
Entschlüsselung

Bei der Entschlüsselung wird aus dem Geheimtext unter Verwendung des geheimen Schlüssels wieder der Klartext berechnet.

Das genaue mathematische Vorgehen wird nun beschrieben:

Seien allgemein   und   bekannt, gesucht wird   mit  . Für zusammengesetzte   (beispielsweise unsere  ) existiert kein effizientes Verfahren zur Bestimmung von  . Bei einer Primzahl   (in unserem Fall   und  ) lässt sich jedoch der chinesische Restsatz ausnutzen.

In unserem Fall sind nun Quadratwurzeln   gesucht:

 

und

 

Wegen obiger Kongruenzbedingung können wir wählen:

 

und

 .

In unserem Beispiel ergeben sich   und  .

Mit Hilfe des erweiterten euklidischen Algorithmus werden nun   mit   bestimmt. In unserem Beispiel erhalten wir  .

Nun werden unter Ausnutzung des chinesischen Restsatzes die vier Quadratwurzeln  ,  ,   und   von   berechnet (  steht hierbei wie üblich für die Menge der Restklassen modulo  ; die vier Quadratwurzeln liegen in der Menge  ):

 

Eine dieser Quadratwurzeln   ist wieder der anfängliche Klartext  . Im Beispiel gilt  .

Bewertung

Bearbeiten

Effektivität

Bearbeiten

Die Entschlüsselung liefert zusätzlich zum Klartext drei weitere Ergebnisse, das richtige Ergebnis muss daher erraten werden. Dies ist der große Nachteil des Rabin-Kryptosystems.

Man kann aber Klartexte mit spezieller Struktur wählen. Hierdurch geht jedoch die Äquivalenz zum Faktorisierungsproblem verloren, wie sich zeigen lässt. Das System wird dadurch also geschwächt.

Effizienz

Bearbeiten

Bei der Verschlüsselung muss eine Quadrierung   durchgeführt werden. Das ist effizienter als RSA mit dem Exponenten 3.

Die Entschlüsselung erfordert die Anwendung des chinesischen Restsatzes und je eine modulare Exponentiation   und  . Die Effizienz der Entschlüsselung ist mit RSA vergleichbar.

Sicherheit

Bearbeiten

Der große Vorteil des Rabin-Kryptosystems ist, dass man es nur dann brechen kann, wenn man das beschriebene Faktorisierungsproblem effizient lösen kann.

Anders als etwa bei RSA lässt sich zeigen, dass das Rabin-Kryptosystem genauso schwer zu brechen ist wie das Faktorisierungsproblem, auf dem es beruht. Es ist somit sicherer. Wer also das Rabin-Verfahren brechen kann, der kann auch das Faktorisierungsproblem lösen und umgekehrt. Es gilt daher als sicheres Verfahren, solange das Faktorisierungsproblem ungelöst ist. Vorausgesetzt ist dabei wie bereits beschrieben aber, dass die Klartexte keine bestimmte Struktur aufweisen.

Da man auch außerhalb der Kryptologie bemüht ist Faktorisierungsprobleme zu lösen, würde sich eine Lösung rasch in der Fachwelt verbreiten. Doch das ist bislang nicht geschehen. Man kann also davon ausgehen, dass das zugrundeliegende Faktorisierungsproblem derzeit unlösbar ist. Ein Angreifer, der nur belauscht, wird daher derzeit nicht in der Lage sein, das System zu brechen.

Ein aktiver Angreifer aber kann das System mit einem Angriff mit frei wählbarem Geheimtext (englisch chosen-ciphertext attack) brechen, wie sich mathematisch zeigen lässt. Aus diesem Grund findet das Rabin-Kryptosystem in der Praxis kaum Anwendung.

Durch Hinzufügen von Redundanz, z. B. Wiederholen der letzten 64 Bit, wird die Wurzel eindeutig. Dadurch ist der Angriff vereitelt (weil der Entschlüssler nur noch die Wurzel zurückliefert, die der Angreifer schon kennt). Dadurch ist die Äquivalenz der Sicherheit zum Rabin-Kryptosystem nicht mehr beweisbar. Allerdings, laut dem Handbook of Applied Cryptography von Menezes, Oorschot und Vanstone,[1] hält die Äquivalenz unter der Annahme, dass das Wurzelziehen ein zweigeteilter Prozess ist (1. Wurzel   und Wurzel   ziehen und 2. Chinesischen Restsatzalgorithmus anwenden).

Da bei der Kodierung nur die quadratischen Reste verwendet werden (im Beispiel   sind das nur 23 der 76 möglichen Zustände), ist das Verfahren zusätzlich angreifbar.

Literatur

Bearbeiten

Einzelnachweise

Bearbeiten
  1. Handbook of Applied Cryptography. Abgerufen am 23. Mai 2006 (englisch).