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  von Primordnung  und in dieser zwei Erzeuger . Zusätzlich muss noch eine kryptologische Hashfunktion  festgelegt werden. Diese Werte sind öffentliche Parameter und können von mehreren Benutzern gleichzeitig genutzt werden.
 Dann werden als geheimer Schlüssel zufällige  gewählt.
 Aus diesen wird der öffentliche Schlüssel  berechnet.

Verschlüsselung 
Um eine Nachricht  mit dem öffentlichen Schlüssel  zu verschlüsseln geht man wie folgt vor:

 Es wird ein zufälliges  gewählt.

 Das ist die Verschlüsselung der Nachricht wie bei ElGamal.
, wobei  eine universal-one-way Hashfunktion oder eine kollisionsresistente Hashfunktion ist.
. 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 .

Entschlüsselung 
Um ein Chiffrat  mit dem geheimen Schlüssel  zu entschlüsseln führt man zwei Schritte durch.

 Zuerst berechnet man  und überprüft ob . Falls das nicht der Fall ist, wird die Entschlüsselung abgebrochen und eine Fehlermeldung ausgegeben.
 Falls nicht, berechnet man den Klartext .

Korrektheit 

Die Korrektheit des Verfahrens folgt aus
  und .

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 . Dazu wählt man eine Primzahl  mit einer Länge von 3248 bit, so dass die Gruppe eine multiplikative Untergruppe von Primordnung  hat, wobei  eine Länge von 256 bit haben sollte. Das heißt, dass  gelten muss.
Aus der Wahl der Parameter ergibt sich eine Länge von  bit für den geheimen Schlüssel, und  bit für den öffentlichen Schlüssel. Ein Chiffrat ist  bit lang.

Einzelnachweise 

Asymmetrisches Verschlüsselungsverfahren