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.