imported>Aka: Leerzeichen vor Maßeinheit, Kleinkram

2025-05-28T18:54:58Z

Leerzeichen vor Maßeinheit, Kleinkram

Neue Seite

Das '''Cramer-Shoup-Kryptosystem''' ist ein von [[Ronald Cramer]] und [[Victor Shoup]] entwickeltes [[asymmetrisches Kryptosystem]], das als eine Erweiterung des [[Elgamal-Verschlüsselungsverfahren]]s aufgefasst werden kann.<ref>{{Literatur |Autor=Ronald Cramer and Victor Shoup |Titel=A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack |Sammelwerk=Proceedings of Crypto 1998 |Datum=1998 |Seiten=13–25 |Sprache=en |Online=http://homepages.cwi.nl/~cramer/papers/cs.ps}}</ref> 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-Problem]]s.

== Das Verfahren ==
Wie alle asymmetrischen Verschlüsselungen besteht auch das Cramer-Shoup-Verfahren aus drei [[Algorithmus|Algorithmen]].

=== Schlüsselerzeugung ===
* Zuerst wählt man eine (hier multiplikativ geschriebene) [[zyklische Gruppe]] <math>G</math> von Primordnung <math>q</math> und in dieser zwei Erzeuger <math>g_1, g_2</math>. Zusätzlich muss noch eine [[kryptologische Hashfunktion]] <math>H</math> festgelegt werden. Diese Werte sind öffentliche Parameter und können von mehreren Benutzern gleichzeitig genutzt werden.
* Dann werden als geheimer Schlüssel zufällige <math>x_1, x_2, y_1, y_2, z \in \mathbb{Z}_q </math> gewählt.
* Aus diesen wird der öffentliche Schlüssel <math>c = g_1^{x_1} g_2^{x_2}, d = g_1^{y_1} g_2^{y_2}, h = g_1^{z}</math> berechnet.

=== Verschlüsselung ===
Um eine Nachricht <math>m \in G</math> mit dem öffentlichen Schlüssel <math>(c,d,h)</math> zu verschlüsseln geht man wie folgt vor:

* Es wird ein zufälliges <math>r \in \mathbb{Z}_q</math> gewählt.
* <math>u_1 = g_1^r, u_2 = g_2^r</math>
* <math>e = h^r m</math> Das ist die Verschlüsselung der Nachricht wie bei ElGamal.
* <math>\alpha = H(u_1, u_2, e)</math>, wobei <math>H</math> eine universal-one-way Hashfunktion oder eine kollisionsresistente Hashfunktion ist.
* <math>v = c^r d^{r\alpha}</math>. 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 [[Sicherheitsbegriff#Non-Malleability (NM)|Nicht-Verformbarkeit]]
Das Chiffrat besteht dann aus <math>(u_1, u_2, e, v)</math>.

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

* Zuerst berechnet man <math>\alpha = H(u_1, u_2, e)</math> und überprüft ob <math>u_1^{x_1} u_2^{x_2} (u_1^{y_1} u_2^{y_2})^{\alpha} = v</math>. Falls das nicht der Fall ist, wird die Entschlüsselung abgebrochen und eine [[Fehlermeldung]] ausgegeben.
* Falls nicht, berechnet man den Klartext <math>m = e / (u_1^z)</math>.

=== Korrektheit ===

Die Korrektheit des Verfahrens folgt aus
: <math> u_1^{z} = g_1^{r z} = h^r</math> und <math>m = e / h^r</math>.

== Instanziierung ==

Als Sicherheitsniveau wählen wir die Standardlänge für generische Anwendungen von 128 bit.<ref name="ECRYPT S30-32">{{Literatur |Hrsg=European Network of Excellence in Cryptology II |Titel=ECRYPT II Yearly Report on Algorithms and Keysizes (2009–2010) |Datum=2010 |Seiten=30–32 |Sprache=en |Online=[http://www.ecrypt.eu.org/documents/D.SPA.13.pdf ecrypt.eu.org] |Format=PDF |KBytes=2400}} {{Webarchiv |url=http://www.ecrypt.eu.org/documents/D.SPA.13.pdf |text=PDF 2,4 MB |wayback=20100821072710 |archiv-bot=2019-03-11 06:18:16 InternetArchiveBot}}</ref>
Daraus ergibt sich eine Ausgabelänge von 256 bit für die Hashfunktion.<ref name="ECRYPT S30-32" /> SHA-256 kann als kollisionsresistent angenommen werden.<ref name="ECRYPT S52">{{Literatur |Hrsg=European Network of Excellence in Cryptology II |Titel=ECRYPT II Yearly Report on Algorithms and Keysizes (2009–2010) |Datum=2010 |Seiten=52 |Sprache=en |Online=[http://www.ecrypt.eu.org/documents/D.SPA.13.pdf ecrypt.eu.org] |Format=PDF |KBytes=2400}} {{Webarchiv |url=http://www.ecrypt.eu.org/documents/D.SPA.13.pdf |text=PDF 2,4 MB |wayback=20100821072710 |archiv-bot=2019-03-11 06:18:16 InternetArchiveBot}}</ref>

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

== Einzelnachweise ==
<references />

[[Kategorie:Asymmetrisches Verschlüsselungsverfahren]]

Cramer-Shoup-Kryptosystem - Versionsgeschichte

imported>Aka: Leerzeichen vor Maßeinheit, Kleinkram