Rabin-Kryptosystem

Das Rabin-Kryptosystem ist innerhalb der Kryptologie ein asymmetrisches Kryptosystem, das auf einem Faktorisierungsproblem beruht und mit RSA verwandt ist. Es lässt sich prinzipiell auch zur Signatur verwenden. In der Praxis findet das Verfahren allerdings wegen bestimmter Angriffsmöglichkeiten kaum Anwendung.

Geschichte

Das Verfahren entstand Mitte der 1970er Jahre. Entwickelt wurde es von Michael Rabin. Das Rabin-Kryptosystem war das erste asymmetrische Kryptosystem, dessen Sicherheit auf mathematischem Weg bewiesen werden konnte.

Schlüsselerzeugung

Wie alle asymmetrischen Kryptosysteme verwendet auch das Rabin-Kryptosystem einen öffentlichen und einen geheimen Schlüssel. Der öffentliche dient später der Verschlüsselung und kann veröffentlicht werden, während der geheime nur den Empfängern der Nachricht bekannt sein darf.

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

Seien $p$ und $q$ zwei möglichst große Primzahlen, häufig kurz als $p,q\in \mathbb {P}$ geschrieben, für die eine bestimmte Kongruenzbedingung gelten muss (s. unten). Der öffentliche Schlüssel $n$ wird durch Multiplikation der beiden Zahlen, also $n=p\cdot q$. Der geheime Schlüssel ist das Paar $(p,q)$. Anders ausgedrückt: Wer nur $n$ kennt, kann ver- aber nicht entschlüsseln, wer dagegen $p$ und $q$ kennt, kann damit auch entschlüsseln. Zum Erzeugen des öffentlichen Schlüssels müssen die Zahlen $p$ und $q$ müssen bekannt sein: Der öffentliche Schlüssel lässt sich nur genau aus den beiden Primzahlen erzeugen.

Seien beispielhaft $p=7$, $q=11$ (in der praktischen Anwendung handelt es sich um sehr viel größere Zahlen, um die Entschlüsselung durch Dritte so schwierig wie möglich zu machen). Daraus ergibt sich der öffentliche Schlüssel $n=p\cdot q=77$.

Kongruenzbedingung

Um später schnell entschlüsseln zu können, wird im Rabin-Kryptosystem eine bestimmte Kongruenzbedingung ausgenutzt. Nachfolgend wird sie beschrieben:

Für $p$ und $q$ muss die Kongruenzbedingung:

$\left({\frac {-1}{p}}\right)=\left({\frac {-1}{q}}\right)=-1$ (siehe auch Legendre-Symbol)

beziehungsweise

$p\equiv q\equiv 3\,{\bmod {\,}}4$

gelten. In der Formel steht Fehler beim Parsen (Konvertierungsfehler. Der Server („/media/api/rest_“) hat berichtet: „Cannot get mml. TeX parse error: Extra close brace or missing open brace“): {\displaystyle \mod } für den Modulo-Operator. Für eine eine Erläuterung solcher Kongruenzbedingungen siehe Modulo. Die beiden Bedingungen sind gleichwertig, da $\left({\frac {-1}{p}}\right)=-1$ und $p\equiv -1\,{\bmod {\,}}4$ beziehungsweise $p\equiv 3\,{\bmod {\,}}4$ äquivalent sind.

Allgemein gilt nämlich für $r\in \mathbb {P}$ mit $r\equiv 3\,{\bmod {\,}}4$ und $a\in \mathbb {Z}$ mit $a\equiv b^{2}\,{\bmod {\,}}r$:

$a^{\frac {(r+1)}{4}}\equiv {\sqrt {a}}\,{\bmod {\,}}r$ (Beweis).

Diese Eigenschaft dient dazu, später die Entschlüsselung zu erleichtern.

Wegen $7\equiv 11\equiv 3\,{\bmod {\,}}4$ ist die Kongruenzbedingung für das Beispiel erfüllt.

Verschlüsselung

Datei:Verschlüsselung (asymmetrisches Kryptosystem).png

Verschlüsselung

Nebenstehende Abbildung veranschaulicht die Verschlüsselung von Klartexten mit asymmetrischen Kryptosystemen wie dem in diesem Artikel beschriebenen. Ein Klartext wird in einen Geheimtext unter Verwendung eines öffentlichen Schlüssels verwandelt.

Für das Rabin-Kryptosystem wird nachfolgend dieser Prozess auf mathematischem Weg präzisiert:

Sei nun $P=\{0,...,n-1\}$ der Klartextraum (er besteht also aus Zahlen) und $m\in P$ der Klartext. Nun lässt sich der Geheimtext $c$ durch

$c=m^{2}\,{\bmod {\,}}n$

bestimmen. Dabei ist c der Quadratische Rest von zu der Quadratzahl m² zum Modulo der Schlüssel-Zahl n. Im praktischen Einsatz bietet sich die Verwendung von Blockchiffre an.

In unserem Beispiel sei $P=\{0,...,76\}$ der Klartextraum, $m=20$ der Klartext. Der Geheimtext ist hierbei nun $c=m^{2}\,{\bmod {\,}}n=15$.

Dabei muss man beachten, dass für genau vier verschiedene $m$ das $c$ den Wert 15 aufweist, nämlich für $m\in \{13,20,57,64\}$. Ähnliches gilt für die meisten $c$.

Entschlüsselung

Entschlüsselung

Auch die Entschlüsselung in asymmetrischen Kryptosystemen im Allgemeinen und im Rabin-Kryptosystem im Speziellen ist nebenstehend in einer Abbildung dargestellt. Der zuvor durch Verschlüsselung entstandene Geheimtext wird unter Verwendung des geheimen Schlüssels wieder in den Klartext gewandelt.

Das genaue mathematische Vorgehen wird nun beschrieben:

Seien allgemein $c$ und $r$ bekannt, gesucht wird $m\in \{0,...,n-1\}$ mit $m^{2}\equiv c\,{\bmod {\,}}r$. Für zusammengesetzte $r$ (beispielsweise unsere $n$) existiert kein effizientes Verfahren zur Bestimmung von $m$. Ansonsten, wenn also $r\in \mathbb {P}$ (in unserem Fall $p$ und $q$), dann lässt sich jedoch der chinesische Restsatz ausnutzen.

In unserem Fall sind nun die Quadratwurzeln

$m_{p}={\sqrt {c}}\,{\bmod {\,}}p$

und

$m_{q}={\sqrt {c}}\,{\bmod {\,}}q$

gesucht.

Wegen obiger Kongruenzbedingung gilt:

$m_{p}=c^{\frac {(p+1)}{4}}\,{\bmod {\,}}p$

und

$m_{q}=c^{\frac {(q+1)}{4}}\,{\bmod {\,}}q$.

In unserem Beispiel ergeben sich $m_{p}=1$ und $m_{q}=9$.

Mit dem erweiterten euklidischen Algorithmus werden nun $y_{p}$ und $y_{q}$, mit $y_{p}\cdot p+y_{q}\cdot q=1$, bestimmt. In unserem Beispiel erhalten wir $y_{p}=-3$ und $y_{q}=2$.

Nun werden unter Ausnutzung des chinesischen Restsatzes die vier Quadratwurzeln $+r$, $-r$, $+s$ und $-s$ von $c+n\mathbb {Z} \in \mathbb {Z} /n\mathbb {Z}$ berechnet ($\mathbb {Z} /n\mathbb {Z}$ steht hierbei wie üblich für die Menge der Restklassen modulo $n$; die vier Quadratwurzeln liegen in der Menge $\{0,...,n-1\}$):

$r=(y_{p}\cdot p\cdot m_{q}+y_{q}\cdot q\cdot m_{p})\,{\bmod {\,}}n$, $-r=n-r$

und

$s=(y_{p}\cdot p\cdot m_{q}-y_{q}\cdot q\cdot m_{p})\,{\bmod {\,}}n$, $-s=n-s$.

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

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 mir 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 $\mod \,n$ 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 Exponenziation $\mod \,p$ und $\mod \,q$. Die Effizienz der Entschlüsselung ist mit 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 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, wir 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.

Da bei der Kodierung nur die quadratischen Reste verwendet werden (im Beispiel $n=77$ 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 3540412832 (S. 125 ff.)
• Michael O. Rabin: Digitalized Signatures and Public-Key Functions as Intractable as Factorization. MIT-LCS-TR 212, MIT Laboratory for Computer Science, Januar 1979 (englischer Originalaufsatz)