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.<ref></ref> 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 <math>G</math> von Primordnung <math>q</math> und in dieser zwei Erzeuger <math>g_1, g_2</math>. Zusätzlich muss noch eine kryptologische Hashfunktion <math>H</math> festgelegt werden. Diese Werte sind öffentliche Parameter und können von mehreren Benutzern gleichzeitig genutzt werden.
Dann werden als geheimer Schlüssel zufällige <math>x_1, x_2, y_1, y_2, z \in \mathbb{Z}_q </math> gewählt.
Aus diesen wird der öffentliche Schlüssel <math>c = g_1^{x_1} g_2^{x_2}, d = g_1^{y_1} g_2^{y_2}, h = g_1^{z}</math> berechnet.

Verschlüsselung

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

Es wird ein zufälliges <math>r \in \mathbb{Z}_q</math> gewählt.
<math>u_1 = g_1^r, u_2 = g_2^r</math>
<math>e = h^r m</math> Das ist die Verschlüsselung der Nachricht wie bei ElGamal.
<math>\alpha = H(u_1, u_2, e)</math>, wobei <math>H</math> eine universal-one-way Hashfunktion oder eine kollisionsresistente Hashfunktion ist.
<math>v = c^r d^{r\alpha}</math>. 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 <math>(u_1, u_2, e, v)</math>.

Entschlüsselung

Um ein Chiffrat <math>(u_1, u_2, e, v)</math> mit dem geheimen Schlüssel <math>(x_1, x_2, y_1, y_2, z)</math> zu entschlüsseln führt man zwei Schritte durch.

Zuerst berechnet man <math>\alpha = H(u_1, u_2, e)</math> und überprüft ob <math>u_1^{x_1} u_2^{x_2} (u_1^{y_1} u_2^{y_2})^{\alpha} = v</math>. Falls das nicht der Fall ist, wird die Entschlüsselung abgebrochen und eine Fehlermeldung ausgegeben.
Falls nicht, berechnet man den Klartext <math>m = e / (u_1^z)</math>.

Korrektheit

Die Korrektheit des Verfahrens folgt aus

<math> u_1^{z} = g_1^{r z} = h^r</math> und <math>m = e / h^r</math>.

Instanziierung

Als Sicherheitsniveau wählen wir die Standardlänge für generische Anwendungen von 128 bit.<ref name="ECRYPT S30-32"> <templatestyles src="Webarchiv/styles.css" />PDF 2,4 MB (Memento des Vorlage:IconExternal vom 21. August 2010 im Internet Archive) Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2</ref> Daraus ergibt sich eine Ausgabelänge von 256 bit für die Hashfunktion.<ref name="ECRYPT S30-32" /> SHA-256 kann als kollisionsresistent angenommen werden.<ref name="ECRYPT S52"> <templatestyles src="Webarchiv/styles.css" />PDF 2,4 MB (Memento des Vorlage:IconExternal vom 21. August 2010 im Internet Archive) Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2</ref>

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

Einzelnachweise