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 | Quelltext bearbeiten]

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

Schlüsselerzeugung[Bearbeiten | Quelltext bearbeiten]

  • 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[Bearbeiten | Quelltext bearbeiten]

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

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

Die Korrektheit des Verfahrens folgt aus

und .

Instanziierung[Bearbeiten | Quelltext 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 . 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 [2]. 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[Bearbeiten | Quelltext 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 (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 (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).