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.<ref>{{#invoke:Vorlage:Literatur|f}}</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-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 <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 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">{{#invoke:Vorlage:Literatur|f}} <templatestyles src="Webarchiv/styles.css" />{{#if:20100821072710
| {{#ifeq: 20100821072710 | *
| {{#if: PDF 2,4 MB | {{#invoke:WLink|getEscapedTitle|PDF 2,4 MB}} | {{#invoke:Webarchiv|getdomain|http://www.ecrypt.eu.org/documents/D.SPA.13.pdf}} }} (Archivversionen)
| {{#iferror: {{#time: j. F Y|20100821072710}}
| {{#if: || }}Der Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
| {{#if: PDF 2,4 MB | {{#invoke:WLink|getEscapedTitle|PDF 2,4 MB}} | {{#invoke:Webarchiv|getdomain|http://www.ecrypt.eu.org/documents/D.SPA.13.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: 2019-03-11 06:18:16 InternetArchiveBot | 2019-03-11 06:18:16 InternetArchiveBot | }} | des Vorlage:Referrer }} vom {{#time: j. F Y|20100821072710}} im Internet Archive{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}}
}}
| {{#if:
| {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
| {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
| 16= {{#if: PDF 2,4 MB | {{#invoke:WLink|getEscapedTitle|PDF 2,4 MB}} | {{#invoke:Webarchiv|getdomain|http://www.ecrypt.eu.org/documents/D.SPA.13.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: 2019-03-11 06:18:16 InternetArchiveBot | 2019-03-11 06:18:16 InternetArchiveBot | }} | des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
| 9 = {{#if: PDF 2,4 MB | {{#invoke:WLink|getEscapedTitle|PDF 2,4 MB}} | {{#invoke:Webarchiv|getdomain|http://www.ecrypt.eu.org/documents/D.SPA.13.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: 2019-03-11 06:18:16 InternetArchiveBot | 2019-03-11 06:18:16 InternetArchiveBot | }} | des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
| #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!{{#if: || }}
}}
| c|{{{webciteID}}}}} {{#if: PDF 2,4 MB | {{#invoke:WLink|getEscapedTitle|PDF 2,4 MB}} | {{#invoke:Webarchiv|getdomain|http://www.ecrypt.eu.org/documents/D.SPA.13.pdf}} }} ({{#if: {{#if: 2019-03-11 06:18:16 InternetArchiveBot | 2019-03-11 06:18:16 InternetArchiveBot | }} | des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}}
| {{#if:
| Vorlage:Webarchiv/Today
| {{#if:
| Vorlage:Webarchiv/Generisch
| {{#if: PDF 2,4 MB | {{#invoke:WLink|getEscapedTitle|PDF 2,4 MB}} | {{#invoke:Webarchiv|getdomain|http://www.ecrypt.eu.org/documents/D.SPA.13.pdf}} }}
}}}}}}}}{{#if:2019-03-11 06:18:16 InternetArchiveBot
| Vorlage:Webarchiv/archiv-bot
}}{{#invoke:TemplatePar|check
|all = url=
|opt = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
|cat = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
|errNS = 0
|template = Vorlage:Webarchiv
|format = *
|preview = 1
}}{{#ifexpr: {{#if:20100821072710|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
}}{{#if:
| {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
| web.archive.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}}
| webcitation.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}}
| archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
}}{{#if:
| {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
| }}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
}}
| {{#if:
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
}}
}}{{#if:{{#invoke:URLutil|isHostPathResource|http://www.ecrypt.eu.org/documents/D.SPA.13.pdf}}
|| {{#if: || }}
}}{{#if: PDF 2,4 MB
| {{#if: {{#invoke:WLink|isBracketedLink|PDF 2,4 MB}}
| {{#if: || }}
}}
| {{#if: || }}
}}{{#switch:
|addlarchives|addlpages= {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
}}{{#ifeq: {{#invoke:Str|find|http://www.ecrypt.eu.org/documents/D.SPA.13.pdf%7Carchiv}} |-1
|| {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www.ecrypt.eu.org/documents/D.SPA.13.pdf%7C4}}%7Chttp}} |-1
|| {{#switch: {{#invoke:Webarchiv|getdomain|http://www.ecrypt.eu.org/documents/D.SPA.13.pdf }}
| abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org =
| #default = {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
}}
}}
}}</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">{{#invoke:Vorlage:Literatur|f}} <templatestyles src="Webarchiv/styles.css" />{{#if:20100821072710
| {{#ifeq: 20100821072710 | *
| {{#if: PDF 2,4 MB | {{#invoke:WLink|getEscapedTitle|PDF 2,4 MB}} | {{#invoke:Webarchiv|getdomain|http://www.ecrypt.eu.org/documents/D.SPA.13.pdf}} }} (Archivversionen)
| {{#iferror: {{#time: j. F Y|20100821072710}}
| {{#if: || }}Der Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
| {{#if: PDF 2,4 MB | {{#invoke:WLink|getEscapedTitle|PDF 2,4 MB}} | {{#invoke:Webarchiv|getdomain|http://www.ecrypt.eu.org/documents/D.SPA.13.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: 2019-03-11 06:18:16 InternetArchiveBot | 2019-03-11 06:18:16 InternetArchiveBot | }} | des Vorlage:Referrer }} vom {{#time: j. F Y|20100821072710}} im Internet Archive{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}}
}}
| {{#if:
| {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
| {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
| 16= {{#if: PDF 2,4 MB | {{#invoke:WLink|getEscapedTitle|PDF 2,4 MB}} | {{#invoke:Webarchiv|getdomain|http://www.ecrypt.eu.org/documents/D.SPA.13.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: 2019-03-11 06:18:16 InternetArchiveBot | 2019-03-11 06:18:16 InternetArchiveBot | }} | des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
| 9 = {{#if: PDF 2,4 MB | {{#invoke:WLink|getEscapedTitle|PDF 2,4 MB}} | {{#invoke:Webarchiv|getdomain|http://www.ecrypt.eu.org/documents/D.SPA.13.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: 2019-03-11 06:18:16 InternetArchiveBot | 2019-03-11 06:18:16 InternetArchiveBot | }} | des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
| #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!{{#if: || }}
}}
| c|{{{webciteID}}}}} {{#if: PDF 2,4 MB | {{#invoke:WLink|getEscapedTitle|PDF 2,4 MB}} | {{#invoke:Webarchiv|getdomain|http://www.ecrypt.eu.org/documents/D.SPA.13.pdf}} }} ({{#if: {{#if: 2019-03-11 06:18:16 InternetArchiveBot | 2019-03-11 06:18:16 InternetArchiveBot | }} | des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}}
| {{#if:
| Vorlage:Webarchiv/Today
| {{#if:
| Vorlage:Webarchiv/Generisch
| {{#if: PDF 2,4 MB | {{#invoke:WLink|getEscapedTitle|PDF 2,4 MB}} | {{#invoke:Webarchiv|getdomain|http://www.ecrypt.eu.org/documents/D.SPA.13.pdf}} }}
}}}}}}}}{{#if:2019-03-11 06:18:16 InternetArchiveBot
| Vorlage:Webarchiv/archiv-bot
}}{{#invoke:TemplatePar|check
|all = url=
|opt = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
|cat = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
|errNS = 0
|template = Vorlage:Webarchiv
|format = *
|preview = 1
}}{{#ifexpr: {{#if:20100821072710|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
}}{{#if:
| {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
| web.archive.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}}
| webcitation.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}}
| archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
}}{{#if:
| {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
| }}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
}}
| {{#if:
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
}}
}}{{#if:{{#invoke:URLutil|isHostPathResource|http://www.ecrypt.eu.org/documents/D.SPA.13.pdf}}
|| {{#if: || }}
}}{{#if: PDF 2,4 MB
| {{#if: {{#invoke:WLink|isBracketedLink|PDF 2,4 MB}}
| {{#if: || }}
}}
| {{#if: || }}
}}{{#switch:
|addlarchives|addlpages= {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
}}{{#ifeq: {{#invoke:Str|find|http://www.ecrypt.eu.org/documents/D.SPA.13.pdf%7Carchiv}} |-1
|| {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www.ecrypt.eu.org/documents/D.SPA.13.pdf%7C4}}%7Chttp}} |-1
|| {{#switch: {{#invoke:Webarchiv|getdomain|http://www.ecrypt.eu.org/documents/D.SPA.13.pdf }}
| abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org =
| #default = {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
}}
}}
}}</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 />