Cryptography Reference
In-Depth Information
zeigen, dass OAEP in Verbindung mit dem RSA-Verfahren (RSA-OAEP) CCA-Sicherheit
bietet. RSA-OAEP wurde in PKCS#1 v2.1 standardisiert [190].
ElGamal hat das von ihm entwickelte Kryptoschema in [71] veröffentlicht. Die Tatsa-
che, dass, unter der DDH-Annahme, das ElGamal-Kryptoschema sicher ist, wurde zum
Beispiel in [160] bewiesen. Das Die-Hellman-Entscheidungsproblem sowie das Problem
der Berechnung des diskreten Logarithmus und der Die-Hellman-Funktion gehen be-
reits auf die Arbeit von Die und Hellman [64] zurück. Für weitere Informationen zu
diesen Problemen und deren Beziehungen verweisen wir auf die Überblicksartikel von
Boneh [42] und Odlyzko [132] sowie den Artikel von Maurer und Wolf [122]. Die Verwen-
dung der in Abschnitt 6.5.2 erwähnten elliptischen Kurven in der Kryptographie wurde
unabhängig voneinander von Koblitz [107] und Miller [127] vorgeschlagen (siehe, z. B.,
[108, 168, 101] für weitere Informationen zu elliptischen Kurven in der Kryptographie).
Neben den in diesem Buch behandelten asymmetrischen Kryptoschemen gibt es noch
viele andere. Ein prominentes Beispiel ist das oben bereits erwähnte Rabin-Kryptoschema
[136], welches ähnlich zu RSA arbeitet. Ein wichtiger Unterschied ist allerdings, dass die
Sicherheit des Rabin-Kryptoschemas allein auf der Annahme beruht, dass das Fakto-
risierungsproblem schwer zu lösen ist. Das erste Kryptoschema, dessen Sicherheit im
Sinne von Abschnitt 6.2 nachgewiesen wurde, stammt von Goldwasser und Micali [86].
Es erlaubt die Verschlüsselung eines Bits und basiert auf der Annahme, dass, gegeben ein
RSA-Modul
n
, es schwer ist, zu entscheiden, ob ein Element
c
∈
Z
n
ein quadratischer Rest
oder ein (spezieller) quadratischer Nichtrest modulo
n
ist. Das erste praktikable asym-
metrische Kryptoschema, welches CCA-Sicherheit bietet und auf weithin akzeptierten
kryptographischen Annahmen basiert (u. a. auf der DDH-Annahme), wurde von Cramer
und Shoup vorgeschlagen [57]. Im Gegensatz zu OAEP verwendet das Cramer-Shoup-
Kryptoschema kein sogenanntes Random Oracle (siehe auch Abschnitt 6.4.3). Ausgehend
von der bahnbrechenden Arbeit von Ajtai [5] wurden asymmetrische Kryptoschemen, das
erste von Ajtai und Dwork [6], sowie andere kryptographische Primitive basierend auf
sogenannten Gitterproblemen entwickelt (siehe [125] für eine Einführung in diese The-
matik). Diese auf Gittern basierende Kryptographie (
lattice-based cryptography
)istvor
allem deshalb interessant, weil die Sicherheit der kryptographischen Primitive allein dar-
auf beruht, dass bestimmte Gitterprobleme auch im
worst case
schwer zu lösen sind.
Man kann also zeigen, dass, wenn die entwickelten kryptographischen Verfahren unsicher
wären, man
alle
Instanzen des betrachteten Gitterproblems ezient lösen könnte. Im
Gegensatz dazu haben wir in diesem Buch immer
Average-Case-Annahmen
gemacht, die
viel stärker sind. Es besteht die Hoffnung, dass auf Gitter basierende kryptographische
Primitive auch dann Bestand haben werden, falls praktikable Quantencomputer Realität
werden sollten (siehe auch Abschnitt 1.4).
Eine erste rigorose Behandlung der hybriden Verschlüsselung findet sich in der bereits
erwähnten Arbeit von Cramer und Shoup [57]. Das (asymmetrische) Verfahren, um sym-
metrische Schlüssel zu verschlüsseln, wird dort mit
Key Encapsulation Mechanism (KEM)
bezeichnet. In dieser Arbeit wird u. a. gezeigt, dass, wenn sowohl das asymmetrische als
auch das symmetrische Verschlüsselungsverfahren CCA-Sicherheit bieten, dann auch das
resultierende hybride Verfahren. Cramer und Shoup gehen in ihrer Arbeit auch genauer
auf die in Abschnitt 6.6 diskutierten geringeren Anforderungen an die in einem hybriden
Schema verwendeten asymmetrischen und symmetrischen Verschlüsselungsverfahren ein.
