Cryptography Reference
In-Depth Information
um eine ezient berechenbare, nicht-triviale Eigenschaft handelt, die sich vom Klartext
auf den Chiffretext überträgt: Hat der Chiffretext das Jacobi-Symobol 1 ,sowerdendamit
mehr als die Hälfte aller Klartexte ausgeschlossen. Dies kann, neben der Tatsache, dass
S RSA ein deterministisches Kryptoschema ist, ausgenutzt werden, um einen erfolgreichen
Angreifer im Sinne von Definition 6.2.2 auf
S RSA zu konstruieren: Der Angreifer erzeugt
einfach zwei Klartexte mit Jacobi-Symbol 1 und
1 . Da diese von den Chiffretexten
abzulesen sind, kann er leicht zwischen der Verschlüsselung des einen und des anderen
Klartextes unterscheiden (siehe Aufgabe 6.7.12).
Insgesamt ist klar, dass das RSA-Kryptoschema, so wie wir es oben eingeführt ha-
ben, völlig unsicher ist. Dieses Kryptoschema findet man in ähnlicher Form in fast allen
Lehrbüchern zur Kryptographie, weshalb man im Englischen auch von »Textbook RSA«
spricht.
Während also »Textbook RSA« als asymmetrisches Kryptoschema ungeeignet ist, ver-
mutet man, dass es sich bei »Textbook RSA« um eine sogenannte Einwegfunktion mit
Hintertür handelt. Diese Vermutung ist die sogenannte RSA-Annahme .
Auf Basis dieser Annahme kann man aus »Textbook RSA« nicht nur ein sicheres
Kryptoschema konstruieren (siehe Abschnitt 6.4.3), sondern, wie wir in Kapitel 10 se-
hen werden, auch eine sichere digitale Signatur. Wir wenden uns deshalb im nächsten
Unterabschnitt den Einwegfunktionen mit Hintertür zu.
6.4.2
RSA als Einwegfunktion mit Hintertür
Kurz gesagt ist eine Einwegfunktion mit Hintertür eine Funktion, die leicht zu berechnen,
aber nur schwer zu invertieren ist, falls man das Geheimnis, die Hintertür, nicht kennt.
Genauer betrachtet man nicht einzelne Funktionen, sondern Funktionsfamilien. Wie ge-
sagt wird vermutet, dass RSA eine solche Funktionsfamilie ist: Für jeden öffentlichen
RSA-Schlüssel ( n, e ) und jedes x
Z n kann y = x e mod n leicht berechnet werden, aber,
wenn man d nichtkennt,dannsollteesschwersein, x = y d mod n allein aus y und ( n, e )
zu bestimmen.
Bevor wir aber RSA als Familie von Einwegfunktionen mit Hintertür interpretieren,
definieren wir derartige Funktionsfamilien präzise.
Definition 6.4.3 (Familie von Einwegfunktionen mit Hintertür). Eine Familie von Ein-
wegfunktionen mit Hintertür ist ein Tupel
( G, R, F,I ) ,
wobei die Komponenten wie folgt definiert sind:
- G : { 0 , 1 } ×{ 0 , 1 } ist ein zufallsgesteuerter Algorithmus zur Generierung von Pa-
rametern der Form ( i, t ) , dessen Laufzeit durch eine Konstante beschränkt ist. Wir
nennen i Index und t Hintertür (im Englischen spricht man von trapdoor ). Der In-
dex i definiert den endlichen Definitionsbereich D i . Wir bezeichnen die Menge der
Indexe und Hintertüren, die von G ausgegeben werden können, mit Ind bzw. Trap .
- R ist ein zufallsgesteuerter, polynomzeitbeschränkter Algorithmus, der bei Eingabe
von i
Ind ein Element von D i ausgibt.
Search WWH ::




Custom Search