Cramer-Shoup-Kryptosystem

Das Cramer-Shoup-Kryptosystem ist ein von Ronald Cramer und Victor Shoup entwickeltes asymmetrisches Kryptosystem, das als eine Erweiterung des Elgamal-Verschlüsselungsverfahrens aufgefasst werden kann. Es war das erste praktikable Verschlüsselungsverfahren, das im Standardmodell (ohne Zufallsorakel) gegen adaptive Chosen-Ciphertext-Angriffe sicher war. Die Sicherheit des Verfahrens beruht auf der Schwierigkeit des Decisional-Diffie-Hellman-Problems.

Das Verfahren

Wie alle asymmetrischen Verschlüsselungen besteht auch das Cramer-Shoup-Verfahren aus drei Algorithmen.

Schlüsselerzeugung

• Zuerst wählt man eine (hier multiplikativ geschriebene) zyklische Gruppe $G$ von Primordnung $q$ und in dieser zwei Erzeuger $g_{1},g_{2}$. Zusätzlich muss noch eine kryptologische Hashfunktion $H$ festgelegt werden. Diese Werte sind öffentliche Parameter und können von mehreren Benutzern gleichzeitig genutzt werden.
• Dann werden als geheimer Schlüssel zufällige $x_{1},x_{2},y_{1},y_{2},z\in \mathbb {Z} _{q}$ gewählt.
• Aus diesen wird der öffentliche Schlüssel $c=g_{1}^{x_{1}}g_{2}^{x_{2}},d=g_{1}^{y_{1}}g_{2}^{y_{2}},h=g_{1}^{z}$ berechnet.

Verschlüsselung

Um eine Nachricht $m\in G$ mit dem öffentlichen Schlüssel $(c,d,h)$ zu verschlüsseln geht man wie folgt vor:

• Es wird ein zufälliges $r\in \mathbb {Z} _{q}$ gewählt.
• $u_{1}=g_{1}^{r},u_{2}=g_{2}^{r}$
• $e=h^{r}m$ Das ist die Verschlüsselung der Nachricht wie bei ElGamal.
• $\alpha =H(u_{1},u_{2},e)$, wobei $H$ eine universal-one-way Hashfunktion oder eine kollisionsresistente Hashfunktion ist.
• $v=c^{r}d^{r\alpha }$. Dieses Element stellt sicher, dass ein Angreifer nicht Teile des Chiffrats benutzen kann um weitere Chiffrate zu erzeugen und sichert so die für die Sicherheit notwendige Nicht-Verformbarkeit

Das Chiffrat besteht dann aus $(u_{1},u_{2},e,v)$.

Entschlüsselung

Um ein Chiffrat $(u_{1},u_{2},e,v)$ mit dem geheimen Schlüssel $(x_{1},x_{2},y_{1},y_{2},z)$ zu entschlüsseln führt man zwei Schritte durch.

• Zuerst berechnet man $\alpha =H(u_{1},u_{2},e)$ und überprüft ob $u_{1}^{x_{1}}u_{2}^{x_{2}}(u_{1}^{y_{1}}u_{2}^{y_{2}})^{\alpha }=v$. Falls das nicht der Fall ist, wird die Entschlüsselung abgebrochen und eine Fehlermeldung ausgegeben.
• Falls nicht, berechnet man den Klartext $m=e/(u_{1}^{z})$.

Korrektheit

Die Korrektheit des Verfahrens folgt aus

$u_{1}^{z}=g_{1}^{rz}=h^{r}$ und $m=e/h^{r}$.

Instanziierung

Als Sicherheitsniveau wählen wir die Standardlänge für generische Anwendungen von 128 bit. Daraus ergibt sich eine Ausgabelänge von 256 bit für die Hashfunktion. SHA-256 kann als kollisionsresistent angenommen werden.

Man braucht eine Gruppe, in welcher das Decisional-Diffie-Hellman-Problem schwierig zu berechnen ist, wie etwa $\mathbb {Z} _{p}^{*}$. Dazu wählt man eine Primzahl $p$ mit einer Länge von 3248 bit, so dass die Gruppe eine multiplikative Untergruppe von Primordnung $q$ hat, wobei $q$ eine Länge von 256 bit haben sollte. Das heißt, dass $q|(p-1)$ gelten muss. Aus der Wahl der Parameter ergibt sich eine Länge von $5\cdot 256=1280$ bit für den geheimen Schlüssel, und $3\cdot 3248=9744$ bit für den öffentlichen Schlüssel. Ein Chiffrat ist $4\cdot 3248=12992$ bit lang.