Quelltext der Seite Rabin-Kryptosystem

Das '''Rabin-Kryptosystem''' ist innerhalb der [[Kryptologie]] ein [[asymmetrisches Kryptosystem]], dessen Sicherheit [[Beweisbare Sicherheit|beweisbar]] auf dem [[Faktorisierungsproblem]] beruht und das mit [[RSA-Kryptosystem|RSA]] verwandt ist. Es lässt sich auch zur [[Elektronische Signatur|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 <math> y = x^2 \bmod n</math> gibt.

== Geschichte ==

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

== Schlüsselerzeugung ==

Wie alle [[asymmetrisches Kryptosystem|asymmetrischen Kryptosysteme]] verwendet auch das Rabin-Kryptosystem einen [[öffentlicher Schlüssel|öffentlichen Schlüssel]] (Public Key) und einen [[geheimer Schlüssel|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 <math>p, q</math> zwei möglichst große [[Primzahl|Primzahlen]], häufig kurz als <math>p, q \in \mathbb{P}</math> geschrieben, für die eine bestimmte [[#Kongruenzbedingung|Kongruenzbedingung]] gelten muss. Der [[öffentlicher Schlüssel|öffentliche Schlüssel]] <math>n</math> wird durch Multiplikation der beiden Zahlen erzeugt, also <math>n = p \cdot q</math>. Der [[geheimer Schlüssel|geheime Schlüssel]] ist das Paar <math>(p, q)</math>. Anders ausgedrückt: Wer nur <math>n</math> kennt, kann ver- aber nicht entschlüsseln, wer dagegen <math>p</math> und <math>q</math> kennt, kann damit auch entschlüsseln. Wären <math>p</math> und <math>q</math> keine Primzahlen, so ließe sich das Verfahren nicht anwenden.

<u>Beispiel:</u>

Wenn man <math>p = 7</math> und <math>q = 11</math> annimmt, dann ergibt sich daraus der öffentliche Schlüssel <math>n = p \cdot q = 77</math>. <math>7</math> und <math>11</math> 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 <math>10^{200}</math> und größer).

== Kongruenzbedingung ==

Im Rabin-Kryptosystem werden die Primzahlen <math>p</math> und <math>q</math> normalerweise so gewählt, dass die
Kongruenzbedingung <math>p\equiv q\equiv 3\pmod{4}</math> gilt.

Diese Bedingung vereinfacht und beschleunigt die Entschlüsselung. 
Allgemein gilt nämlich: Sei <math>r</math> eine Primzahl mit <math>r \equiv 3 \pmod{4}</math> und <math>a \in \mathbb{Z}</math> mit <math>a \equiv b^2 \pmod{ r}</math>, dann findet man eine Quadratwurzel <math>s</math> von <math>a</math> mit

:<math>s\equiv a^{\frac{r+1}{4}} \pmod{r}</math>.
Es gilt also

:<math>s^2 \equiv a^{\frac{r+1}{2}} \equiv b^{r+1} \equiv b^2 \equiv a \pmod{r}</math>
wegen <math>b^{r-1} \equiv 1 \pmod{r}</math> nach dem [[Kleiner fermatscher Satz|kleinen Fermatschen Satz]].

Da <math>r</math> eine Primzahl ist, gilt zudem entweder <math>s\equiv b\pmod{r}</math> oder <math>s\equiv -b\pmod{r}</math>.

Wegen <math>7 \equiv 11 \equiv 3 \pmod{4}</math> ist die Kongruenzbedingung im Beispiel bereits erfüllt.

== Verschlüsselung ==

Mit dem Rabin-Verfahren lassen sich beliebige [[Klartext (Kryptographie)|Klartexte]] <math>m</math> aus der Menge <math>\{0, \ldots, n-1 \}</math> verschlüsseln. Alice, die einen solchen Klartext verschlüsseln will, muss dazu nur den öffentlichen Schlüssel <math>n</math> des Empfängers Bob kennen. Sie berechnet dann den [[Geheimtext]] <math>c</math> nach der Formel
:<math>c \equiv m^2 \pmod{n}</math> 

Im praktischen Einsatz bietet sich die Verwendung von [[Blockchiffre]] an.

In unserem Beispiel sei <math>P = \{ 0, ..., 76 \}</math> der Klartextraum, <math>m = 20</math> der Klartext. Der Geheimtext ist hierbei nun <math>c \equiv m^2 \pmod{n} \equiv 15 \pmod{n}</math>.

Dabei muss man beachten, dass für genau vier verschiedene <math>m</math> das <math>c</math> den Wert 15 aufweist, nämlich für <math>m \in \{ 13, 20, 57, 64 \}</math>. Jeder [[Quadratischer Rest|quadratische Rest]] <math>c</math> hat genau vier verschiedene Quadratwurzeln modulo <math>n=pq</math>.

== Entschlüsselung ==

[[bild:Entschlüsselung (symmetrisches und asymmetrisches Kryptosystem) Schema.svg|thumb|300px|Entschlüsselung]]

Bei der [[Entschlüsselung]] wird aus dem [[Geheimtext]] unter Verwendung des [[geheimer Schlüssel|geheimen Schlüssels]] wieder der [[Klartext (Kryptographie)|Klartext]] berechnet.

Das genaue mathematische Vorgehen wird nun beschrieben:

Seien allgemein <math>c</math> und <math>r</math> bekannt, gesucht wird <math>m \in \{ 0,  ..., n-1 \}</math> mit <math>m^2 \equiv c \, \pmod{r}</math>. Für zusammengesetzte <math>r</math> (beispielsweise unsere <math>n</math>) existiert kein effizientes Verfahren zur Bestimmung von <math>m</math>. Bei einer Primzahl <math>r \in \mathbb{P}</math> (in unserem Fall <math>p</math> und <math>q</math>) lässt sich jedoch der [[chinesischer Restsatz|chinesische Restsatz]] ausnutzen.

In unserem Fall sind nun [[Quadratwurzel]]n <math> m_p, m_q</math> gesucht:
:<math>m_p^2 \equiv c \pmod{p}</math>
und
:<math>m_q^2 \equiv c \pmod{q}</math>

Wegen obiger Kongruenzbedingung können wir wählen:
:<math>m_p \equiv c^{\frac{p+1}{4}} \pmod{p}</math>
und
:<math>m_q \equiv c^{\frac{q+1}{4}} \pmod{q}</math>.

In unserem Beispiel ergeben sich <math>m_p = 1</math> und <math>m_q = 9</math>.

Mit Hilfe des [[Erweiterter euklidischer Algorithmus |erweiterten euklidischen Algorithmus]] werden nun <math>y_p, y_q</math> mit <math>y_p \cdot p + y_q \cdot q = 1</math> bestimmt. In unserem Beispiel erhalten wir <math>y_p = -3, y_q = 2</math>.

Nun werden unter Ausnutzung des [[chinesischer Restsatz|chinesischen Restsatzes]] die vier Quadratwurzeln <math>+r</math>, <math>-r</math>, <math>+s</math> und <math>-s</math> von <math>c + n \mathbb{Z} \in \mathbb{Z} / n \mathbb{Z}</math> berechnet (<math>\mathbb{Z} / n \mathbb{Z}</math> steht hierbei wie üblich für die [[Menge (Mathematik)|Menge]] der [[Restklasse]]n modulo <math>n</math>; die vier Quadratwurzeln liegen in der Menge <math>\{ 0, ..., n-1 \}</math>):
:<math>\begin{align}
r  &= ( y_p \cdot p \cdot m_q + y_q \cdot q \cdot m_p) \pmod{n} \\
-r &= n-r \\
s  &= ( y_p \cdot p \cdot m_q - y_q \cdot q \cdot m_p) \pmod{n} \\
-s &= n-s
\end{align}</math>

Eine dieser Quadratwurzeln <math>\mod \, n</math> ist wieder der anfängliche Klartext <math>m</math>. Im Beispiel gilt <math>m \in \{ 64, \mathbf{20}, 13, 57 \}</math>.

== Bewertung ==
=== Effektivität ===

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 ===

Bei der Verschlüsselung muss eine Quadrierung <math>\mod \, n</math> durchgeführt werden. Das ist effizienter als [[RSA-Kryptosystem|RSA]] mit dem Exponenten 3.

Die Entschlüsselung erfordert die Anwendung des [[chinesischer Restsatz|chinesischen Restsatzes]] und je eine [[modulare Exponentiation]] <math>\mod \, p</math> und <math>\mod \, q</math>. Die Effizienz der Entschlüsselung ist mit [[RSA-Kryptosystem|RSA]] vergleichbar.

=== Sicherheit ===

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-Kryptosystem|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 [[Chosen-Ciphertext-Angriff|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,<ref>{{Internetquelle |url=http://cacr.uwaterloo.ca/hac/ |titel=Handbook of Applied Cryptography |hrsg= |datum= |zugriff=2006-05-23 |sprache=en}}</ref> hält die Äquivalenz unter der Annahme, dass das Wurzelziehen ein zweigeteilter Prozess ist (1. Wurzel <math>\mod\ p</math> und Wurzel <math>\mod\ q</math> ziehen und 2. Chinesischen Restsatzalgorithmus anwenden).

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

== Literatur ==
*Johannes Buchmann: ''Einführung in die Kryptographie'', 2., erweiterte Auflage. Springer, Berlin u. a. 2001 ISBN 3-540-41283-2 (S. 125 ff.)
*Michael O. Rabin: ''[http://www.lcs.mit.edu/publications/specpub.php?id=780 Digitalized Signatures and Public-Key Functions as Intractable as Factorization]''. MIT-LCS-TR 212, MIT Laboratory for Computer Science, Januar 1979 (englischer Originalaufsatz)

== Einzelnachweise ==
<references />

[[Kategorie:Asymmetrisches Verschlüsselungsverfahren]]