Cramer-Shoup-Kryptosystem

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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.

Das Verfahren[Bearbeiten]

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

Schlüsselerzeugung[Bearbeiten]

  • Zuerst wählt man eine (hier multiplikativ geschriebene) zyklische Gruppe G von Primordnung q und in dieser zwei Erzeuger g_1, g_2. 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[Bearbeiten]

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^r m Das ist die Verschlüsselung der Nachricht wie bei ElGamal.
  • \alpha = H(u_1, u_2, e), wobei H eine universal-one-way Hashfunktion oder eine kollisionsresistente Hashfunktion ist.
  • 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 (u_1, u_2, e, v).

Entschlüsselung[Bearbeiten]

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

  • Zuerst berechnet man \alpha = H(u_1, u_2, 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[Bearbeiten]

Die Korrektheit des Verfahrens folgt aus

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

Instanziierung[Bearbeiten]

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[Bearbeiten]

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