Cryptography Reference
In-Depth Information
-
F
ist ein deterministischer, polynomzeitbeschränkter Algorithmus, der bei Eingabe
von
i ∈
Ind
und
x ∈ D
i
einen Bitvektor
y
=
F
(
i, x
)
ausgibt. Wir bezeichnen die
Menge der möglichen Ausgaben von
F
bei Eingabe von
i
mit
B
i
.
-
I
ist ein deterministischer, polynomzeitbeschränkter Algorithmus, der bei Eingabe
von
i
∈
Ind
, zugehöriger Hintertür
t
∈
Trap
, d. h., es existiert eine Folge
α
von
D
i
ausgibt mit
F
(
i, x
)=
y
.
Ist
F
(
i, ·
)
, für jedes
i ∈
Ind
, eine bijektive Funktion, so sprechen wir auch von einer
Familie von Einwegpermutationen mit Hintertür
.
Zufallsbits mit
(
i, t
)=
G
α
()
,und
y
B
i
ein
x
∈
∈
Die obige Definition fordert, dass die Funktion
F
leicht zu berechnen ist, nämlich in
Polynomzeit, und dass sie leicht zu invertieren ist, nämlich durch
I
, falls die Hintertür
bekannt ist. Was diese Definition noch nicht fasst, ist die eingangs beschriebene Ein-
wegeigenschaft, d. h., die Funktion
F
ist schwer zu invertieren, falls die Hintertür
nicht
bekannt ist. Bevor wir darauf eingehen, formulieren wir zunächst RSA als Familie von
Einwegfunktionen mit Hintertür, um ein konkretes Beispiel vor Augen zu haben.
Beispiel 6.4.1. Es sei
S
RSA
=(
X,K,G,E,D
)
das RSA-Kryptosystem mit Parame-
ter
l>
0
gemäß Definition 6.4.2. Dann ist die
RSA-Familie von Einwegfunktionen mit
Hintertür
(und Parameter
l
) wie folgt definiert:
E
RSA
=(
G, R, F,I
)
,
wobei der Algorithmus zur Generierung von Parametern
(
i, t
)
genau dem Schlüsselge-
nerierungalgorithmus
G
entspricht:
i
entspricht einem öffentlichen RSA-Schlüssel und
t
dem zugehörigen privaten RSA-Schlüssel. Ist
i
=(
n, e
)
und
t
=(
n, d
)
,dannist
D
i
=
Z
n
.
Bei gegebenem Index
i
=(
n, e
)
, wählt der Algorithmus
R
gleichverteilt ein Element aus
Z
n
. Der Algorithmus
F
stimmt genau mit
E
überein, d. h.,
F
((
n, e
)
,x
)=
x
e
mod
n
,und
I
entspricht
D
,d.h.,
I
((
n, e
)
,
(
n, d
)
,y
)=
y
d
mod
n
, für alle RSA-Tupel
(
n, p, q, m, e, d
)
,
mit
|p|
2
=
|q|
2
=
l/
2
,und
x, y ∈
Z
n
.
Es sei bemerkt, dass es sich hierbei offensichtlich um eine Familie von Einweg
permu-
tationen
mit Hintertür handelt, da
F
((
n, e
)
,
·
)
bijektiv ist.
Wir formulieren nun die geforderte Einwegeigenschaft für Einwegfunktionen. Dabei
kommt die Aufgabe des Invertierens (ohne Hintertür), dem sogenannten Invertierer zu.
Definition 6.4.4 (Invertierer für eine Familie von Einwegfunktionen mit Hintertür). Ein
Invertierer (inverter)
A
für eine Familie von Einwegfunktionen mit Hintertür
(
G, R, F,I
)
ist ein zufallsgesteuerter Algorithmus
A
, der als Eingabe einen Index
i ∈
Ind
sowie einen
Bitvektor
y
B
i
erhält und dann einen Bitvektor (aus
D
i
) zurückliefert. Die Laufzeit
von
A
ist durch eine Konstante nach oben beschränkt.
∈
Die Einwegeigenschaft wird nun in gewohnter Weise mit Hilfe eines Experimentes
beschrieben. In diesem Experiment wird von einem Invertierer
A
verlangt, ein Urbild
x
zu einem Bild
y
=
F
(
i, x
)
zu berechnen. Dabei erhält der Invertierer lediglich
i
und
y
als Eingabe, aber natürlich weder
x
noch die Hintertür
t
zu
i
.Da
F
(
i, ·
)
lediglich eine
Funktion
von
D
i
nach
B
i
ist, kann es zu
y
mehrere Urbilder geben.
