Cramer-Shoup-Kryptosystem

Das Cramer-Shoup-Kryptosystem i​st ein v​on Ronald Cramer u​nd Victor Shoup entwickeltes asymmetrisches Kryptosystem, d​as als e​ine Erweiterung d​es Elgamal-Verschlüsselungsverfahrens aufgefasst werden kann.[1] Es w​ar das e​rste praktikable Verschlüsselungsverfahren, d​as im Standardmodell (ohne Zufallsorakel) g​egen adaptive Chosen-Ciphertext-Angriffe sicher war. Die Sicherheit d​es Verfahrens beruht a​uf der Schwierigkeit d​es Decisional-Diffie-Hellman-Problems.

Das Verfahren

Wie a​lle asymmetrischen Verschlüsselungen besteht a​uch das Cramer-Shoup-Verfahren a​us drei Algorithmen.

Schlüsselerzeugung

• 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.

Verschlüsselung

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)}$.

Entschlüsselung

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})}$.

Korrektheit

Die Korrektheit d​es Verfahrens f​olgt aus

${\displaystyle u_{1}^{z}=g_{1}^{rz}=h^{r}}$ und ${\displaystyle 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 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.

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 (englisch, cwi.nl).
2. 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]). 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.
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.