Cryptography Reference
In-Depth Information
mit bekannten Klartexten möglich. Insbesondere würde die sehr aufwändige erschöpfende
Suche (siehe Abschnitt 4.3) überflüssig sein.
Diese Diskussion verdeutlicht, dass ohne die Beschränkung der Größe des Programm-
codes keine vernünftigen Aussagen über die Sicherheit kryptographischer Verfahren, wie
etwa Block-Kryptosysteme, gemacht werden könnten.
4.6.2
Zufallssteuerung
Wir wollen in der Beschreibung von Algorithmen zukünftig den Ausdruck flip
()
erlauben.
Bei der Abarbeitung dieses Ausdrucks soll ein zufällig gewähltes Bit, ein sogenanntes
Zufallsbit
, als Ergebnis zurückgeliefert werden. Genauso wollen wir flip
(
l
)
,für
l
0
,
zulassen. Bei der Ausführung soll ein zufällig gewählter Bitvektor der Länge
l
zurückge-
liefert werden. Algorithmen, die die Operationen flip
()
und flip
(
l
)
verwenden (dürfen),
bezeichnen wir als
zufallsgesteuert
.
2
Bei gegebener Eingabe
x
werden unsere zufallsge-
steuerten Algorithmen immer eine feste, obere Schranke für ihre Laufzeit haben. Diese
obere Schranke bezeichnen wir häufig mit
t
x
oder einfach
t
. Die Wahl eines Zufallsbits
soll einen Zeitschritt erfordern. Insbesondere erfordert dann die Ausführung von flip
(
l
)
l
Zeitschritte. Damit kann ein zufallsgesteuerter Algorithmus bei Eingabe
x
und Laufzeit
≤
≥
t
in einem Lauf höchstens
t
Zufallsbits wählen.
Wir stellen uns vor, dass zufallsgesteuerte Algorithmen bei Eingabe
x
und Laufzeit
≤ t
t
von Bits (Zufallsbits) haben. Wenn flip
()
oder flip
(
l
)
aufgerufen wird, dann werden ein bzw.
l
neue
Bits aus
α
ausgelesen und als Werte von
flip
()
bzw. flip
(
l
)
zurückgegeben. Ein Zufallsbit wird also immer höchstens einmal gelesen;
es ist in diesem Sinne »frisch«. Da die Laufzeit des Algorithmus bei Eingabe
x
durch
t
beschränkt ist, ist sichergestellt, dass immer genügend neue Zufallsbits zur Verfügung
stehen. Wenn
A
(
x
:
Lesezugriff auf eine Folge
α
∈{
0
,
1
}
m
einen zufallsgesteuerten Algorithmus bezeichnet,
der einen Bitvektor der Länge
n
als Eingabe erwartet und einen Bitvektor der Länge
m
als Ausgabe liefert, dann wollen wir mit
A
α
(
x
)
das Ergebnis der Berechnung von
A
auf der Eingabe
x
bezeichnen, bei der die Zufallsbits, die die Operationen flip
()
und
flip
(
l
)
zurückliefern, gemäß
α
gewählt werden. Man beachte, dass der Lauf von
A
auf der
Eingabe
x
und mit den Zufallsbits
α
eindeutig bestimmt ist. Wir werden deshalb einen
Lauf von
A
auf Eingabe
x
mit
α
identifizieren und von einem Lauf
α
von
A
auf Eingabe
x
sprechen.
Wir werden des Weiteren
A
(
x
)
als Zufallsvariable interpretieren mit
A
(
x
)(
α
)=
A
α
(
x
)
für alle
α ∈{
0
,
1
}
n
):
{
0
,
1
}
{
0
,
1
}
t
. Der zugrunde liegende Wahrscheinlichkeitsraum ist die Gleichvertei-
t
. Insbesondere werden wir die Zufallsvariable
A
(
x
)
zur Beschreibung von
Ereignissen verwenden. Für einen Bitvektor
c
bezeichnet zum Beispiel
Prob
{A
(
x
)=
c}
die Wahrscheinlichkeit dafür, dass der Algorithmus
A
bei (fester) Eingabe
x
den Bitvek-
tor
c
ausgibt, also
Prob
lung auf
{
0
,
1
}
t
A
α
(
x
)=
c
{
A
(
x
)=
c
}
=Prob
{{
α
∈{
0
,
1
}
|
}}
(siehe auch die
Bemerkung zur Verwendung von
Prob
{·}
in Abschnitt 3.3).
2 Formal stellen wir uns unter einem zufallsgesteuerten Algorithmus eine zufallsgesteuerte Turing-
Maschine vor. In der Literatur finden sich unterschiedliche Definitionen solcher Maschinen. Eine
für unsere Zwecke geeignete Variante sind Maschinen, die mit einem Zufallsband ausgestattet sind,
d. h., einem Band, auf das vor einem Lauf der Maschine Bits (Zufallsbits) geschrieben werden, die
dann während des Laufes gelesen werden können. Auf eine formale Definition solcher Maschinen
wollen wir hier aber verzichten.
