Cryptography Reference
In-Depth Information
Algorithmus 3.1 Erweiterter Euklidscher Algorithmus
Euklid(
a, b
)
Vorbedingung:
a, b ∈
Z
,
a ≥ b ≥
0
1.
Initialisiere Schleife.
a
=
a
,
b
=
b
x
0
=1
,
y
0
=0
,
x
1
=0
,
y
1
=1
2.
Schleife: Bestimme ggT gemäß ggT
(
a, b
)=
ggT
(
b, a
mod
b
)
.
Invariante: ggT
(
a, b
)=
ggT
(
a
,b
)
,
a
=
x
0
a
+
y
0
b
,
b
=
x
1
a
+
y
1
b
und
a
≥ b
≥
0
.
solange
b
=0
Führe einen Reduktionsschritt durch.
q
=
a
div
b
,
r
=
a
mod
b
a
=
b
,
b
=
r
(
x
0
,y
0
,x
1
,y
1
)=(
x
1
,y
1
,x
0
− qx
1
,y
0
− qy
1
)
Nachbedingung:
a
=
ggT
(
a, b
)=
x
0
a
+
y
0
b
polynomielle Laufzeit besitzt. Wichtig ist, dass sich das Attribut »polynomiell« auf die
Länge (!) der Eingaben bezieht: Der Algorithmus hat polynomielle Laufzeit in
log
a
und
log
b
.
Aus Satz 3.5.2 geht nun unmittelbar hervor, dass ggT
(
a, b
)
ezient mit Hilfe des
erweiterten Euklidschen Algorithmus berechnet werden kann. Aber auch die Bestimmung
des multiplikativ Inversen zu
b ∈
Z
a
,für
a ≥
2
, ist nun leicht möglich: Da ggT
(
a, b
)=1
im Fall
b
∈
Z
a
gilt, folgt aus der Nachbedingung direkt
1=
x
0
a
+
y
0
b
, woraus wir
1=
y
0
b
mod
a
schließen können. Also ist
y
0
mod
a
das multiplikative Inverse von
b
Z
a
. Die beiden Zahlen
x
0
und
y
0
, für die ggT
(
a, b
)=
x
0
a
+
y
0
b
gilt, werden
Bézout-
Koezienten
von
a
und
b
genannt.
in
3.6
Buchstaben- und blockweise Verschlüsselung
Bisher haben wir uns mit der Frage beschäftigt, wie man
eine
Nachricht
x
X
,vorher
bekannter, beschränkter Länge vertraulich übermitteln kann. Für dieses Problem haben
wir auch eine sehr befriedigende Lösung gefunden, nämlich informationstheoretisch siche-
re Kryptosysteme. Wenn man nun mehrere Nachrichten
x
0
,...,x
l−
1
∈
∈
X
oder längere
Nachrichten
x
=
x
0
···x
l−
1
∈ X
∗
verschlüsseln möchte, kann man dies tun, indem man
jedes
x
i
(interpretiert als Buchstabe oder Block) verschlüsselt und für
jeden
solchen Buch-
staben/Block einen
neuen
Schlüssel wählt. Diese Vorgehensweise liefert in der Tat ein
informationstheoretisch sicheres Verschlüsselungsverfahren, falls das zugrunde liegende
Kryptosystem informationstheoretisch sicher ist (siehe Aufgabe 3.7.11). Allerdings ist
bei diesem Verfahren der Schlüssel mindestens so lang wie der Klartext. Wie wir wissen,
kann man dies auch nicht verhindern (siehe Proposition 3.4.3), wenn man an einer si-
cheren Verschlüsselung interessiert ist. Dennoch erliegt man leicht der Versuchung, nicht
jeden Buchstaben/Block mit einem neuen Schlüssel zu verschlüsseln, sondern immer den
gleichen Schlüssel zu verwenden. Klassische Verschlüsselungsverfahren gehen in der Tat
so vor. In diesem abschließenden Abschnitt wollen wir uns überlegen, dass man diese
klassischen Verfahren leicht »brechen« kann.
