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.^[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.

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

• Zuerst wählt man eine (hier multiplikativ geschriebene) zyklische Gruppe ${\displaystyle G}$ von Primordnung ${\displaystyle q}$ und in dieser zwei Erzeuger ${\displaystyle g_{1},g_{2}}$. Zusätzlich muss noch eine kryptologische Hashfunktion ${\displaystyle 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 ${\displaystyle x_{1},x_{2},y_{1},y_{2},z\in \mathbb {Z} _{q}}$ gewählt.
• Aus diesen wird der öffentliche Schlüssel ${\displaystyle c=g_{1}^{x_{1}}g_{2}^{x_{2}},d=g_{1}^{y_{1}}g_{2}^{y_{2}},h=g_{1}^{z}}$ berechnet.

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

• Es wird ein zufälliges ${\displaystyle r\in \mathbb {Z} _{q}}$ gewählt.
• ${\displaystyle u_{1}=g_{1}^{r},u_{2}=g_{2}^{r}}$
• ${\displaystyle e=h^{r}m}$ Das ist die Verschlüsselung der Nachricht wie bei ElGamal.
• ${\displaystyle \alpha =H(u_{1},u_{2},e)}$, wobei ${\displaystyle H}$ eine universal-one-way Hashfunktion oder eine kollisionsresistente Hashfunktion ist.
• ${\displaystyle 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 ${\displaystyle (u_{1},u_{2},e,v)}$.

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

• Zuerst berechnet man ${\displaystyle \alpha =H(u_{1},u_{2},e)}$ und überprüft ob ${\displaystyle 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 ${\displaystyle m=e/(u_{1}^{z})}$.

Die Korrektheit des Verfahrens folgt aus

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

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

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 (englisch, cwi.nl). 
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 (englisch, ecrypt.eu.org [PDF; 2,4 MB]).  Originals 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@2Vorlage:Webachiv/IABot/www.ecrypt.eu.org
3. ↑ European Network of Excellence in Cryptology II (Hrsg.): ECRYPT II Yearly Report on Algorithms and Keysizes (2009–2010). 2010, S. 52 (englisch, ecrypt.eu.org [PDF; 2,4 MB]).  PDF 2,4MB (Memento des Originals 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@2Vorlage:Webachiv/IABot/www.ecrypt.eu.org