Cryptography Reference
In-Depth Information
Länge ausgelobt wurden, also Zahlen der Form n = p
q für Primzahlen p und q gleicher
Länge. Die Längen der in diesem Wettbewerb zu faktorisierenden Zahlen reichen von
etwa 330 bis 2048 Bits. Der aktuelle Rekord (Stand Januar 2011) liegt bei der Fakto-
risierung der Zahl mit der Länge 768 Bits [106]. Zur Faktorisierung dieser Zahl wurde
das Zahlkörpersieb verwendet. Die Rechenzeit betrug etwa zwei Jahre auf einigen hun-
dert Computern. Auf einem 2 , 2 GHz AMD Opteron Prozessor mit 2 GB RAM und einem
Kern hätte die Berechnungszeit etwa bei 1500 Jahren gelegen. Wie in [106] erwähnt, wird
erwartet, dass es innerhalb der nächsten fünf bis zehn Jahre möglich sein wird, auch Zah-
len der Länge 1024 Bits, eine in der Praxis immer noch übliche Größe für RSA-Moduln,
zu faktorisieren. Aktuelle Standards empfehlen deshalb Zahlen in dieser Größenordnung
nicht mehr zu verwenden [184].
Der in Abschnitt 6.3 erwähnte Quantenalgorithmus, der, Quantencomputer vorausge-
setzt, es erlauben würde große Zahlen ezient zu faktorisieren, stammt von Shor [150].
In derselben Arbeit wird ein ähnlicher Algorithmus auch für das eziente Lösen des DL-
Problems vorgestellt. Wir verweisen auf das Lehrbuch von Nielsen und Chuang [131] für
weitere Informationen zu Quantencomputern und -information.
Das RSA-Verschlüsselungsverfahren wurde, wie bereits an verschiedenen Stellen im
Buch erwähnt, im Jahr 1978 von Rivest, Shamir und Adleman entwickelt [140]. Es war
das erste veröffentlichte asymmetrische Kryptoschema (siehe auch die Bemerkungen in
Abschnitt 1.2 zum britischen Geheimdienst).
Wie in Abschnitt 6.4.2 beschrieben, wird vermutet, dass RSA eine Familie von Ein-
wegfunktionen mit Hintertür ist (RSA-Annahme). Allerdings ist offen, ob diese Annahme
äquivalent ist zu der Annahme, dass das Faktorisieren großer Zahlen schwer ist; es gibt
Hinweise dafür (siehe, z. B., [3]) und dagegen (siehe, z. B., [97]).
Das Konzept der Einwegfunktion (mit Hintertür) wurde, wie auch in Abschnitt 4.10
erwähnt, bereits von Die und Hellman vorgeschlagen [64] und später von Yao [170]
formalisiert. Neben der RSA-Verschlüsselungsfunktion vermutet man, dass zum Beispiel
auch das Quadrieren modulo eines RSA-Moduls eine Einwegfunktion mit Hintertür ist.
Diese Funktion wurde von Rabin eingeführt, der gezeigt hat, dass Sie genau dann eine
Einwegfunktion (mit Hintertür) ist, wenn das Faktorisieren eines RSA-Moduls schwer ist
[136]. Diese Funktion ist die Grundlage des Rabin-Kryptoschemas (siehe unten). Eine
ausführliche Behandlung von Einwegfunktionen sowie weitere Literaturangaben finden
sich im Lehrbuch von Goldreich [80]. Das Konzept der Einwegfunktion wird uns auch im
Kontext von kryptographischen Hashfunktionen wieder begegnen (siehe Kapitel 8).
Die Sicherheit des am Anfang von Abschnitt 6.4.3 skizzierten RSA-basierten Krypto-
schemas, indem r
·
x für einen Klartext x und einen zufällig gewählten Bitvektor r mit dem
RSA-Verfahren verschlüsselt wird, folgt aus Resultaten in [7, 91] (siehe auch das Lehr-
buch von Katz und Lindell [101]). Der Standard PKCS#1 v1.5 ist in [188] beschrieben.
Der Angriff von Bleichenbacher auf das RSA-basierte PKCS#1 v1.5 Verschlüsselungs-
verfahren wurde in [39] vorgestellt. Eine gute Übersicht über Angriffe auf RSA-basierte
Verfahren bis 1999 findet sich in [43], darunter der Angriff von Bleichenbacher sowie
der in Aufgabe 6.7.15 behandelte Angriff. Das OAEP-Verfahren wurde, wie bereits in
Abschnitt 6.4.3 erwähnt, von Bellare und Rogaway entwickelt [25], allerdings war der in
dieser Arbeit präsentierte Sicherheitsbeweis fehlerhaft [151, 77, 44] (siehe auch die Erläu-
terungen dazu in [190]). In [77] konnten Fujisaki, Okamoto, Pointcheval und Stern aber
||
Search WWH ::




Custom Search