Cramer–Shoup-Kryptosystem

Das Cramer–Shoup-Kryptosystem ist ein von Ronald Cramer und Victor Shoup entwickeltes asymmetrisches Kryptosystem, das als eine Erweiterung des Elgamal-Kryptosystems aufgefasst werden kann.^[1] 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 additiv geschriebene) zyklische Gruppe G von Primordnung q und in dieser zwei Erzeuger g₁,g₂. 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^rm Das ist die Verschlüsselung der Nachricht wie bei ElGamal.
• α = H(u₁,u₂,e), wobei H eine universal-one-way Hashfunktion oder eine kollisionsresistente Hashfunktion ist.
• v = c^rd^rα. 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₁,u₂,e,v).

Entschlüsselung

Um ein Chiffrat (u₁,u₂,e,v) mit dem geheimen Schlüssel (x₁,x₂,y₁,y₂,z) zu entschlüsseln führt man zwei Schritte durch.

• Zuerst berechnet man α = H(u₁,u₂,e) and ü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^{r z} = h^r$ und m = e / h^r.

Instanziierung

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

Man braucht eine Gruppe in welcher der diskrete Logarithmus 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 ^[2]. 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.

Einzelnachweise

1. ↑ Ronald Cramer and Victor Shoup: A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In: Proceedings of Crypto 1998. 1998, S. 13--25 (http://homepages.cwi.nl/~cramer/papers/cs.ps).
2. ↑ ^{a b c} European Network of Excellence in Cryptology II (Hrsg.): ECRYPT II Yearly Report on Algorithms and Keysizes (2009–2010). 2010, S. 30–32 (PDF 2,4MB).
3. ↑ European Network of Excellence in Cryptology II (Hrsg.): ECRYPT II Yearly Report on Algorithms and Keysizes (2009–2010). 2010, S. 52 (PDF 2,4MB).