<<

. 3
( 9)



>>

4.1 Komplexit¤t

Wir werden die Laufzeit von Algorithmen mit dem asymptotischen Verhalten
von Funktionen vergleichen. Dazu betrachten wir vorab reellwertige Funktionen
und fragen nach ihrem Verhalten im Unendlichen. Wir erinnern zun¤chst an einige
Begriffe aus der Analysis.
58 4 Komplexit¤t und Einwegfunktionen

4.1.1 Die Ordnung von Funktionen

Es sei X eine unbeschr¤nkte Teilmenge des R k , k ∈ N, z. B. X = N k . Für zwei
Funktionen f , g : X ’ R schreiben wir f = O(g), wenn es Zahlen C, r ∈ R >0
gibt, sodass
| f (x)| ¤ C |g(x)| für alle x ∈ X mit |x| > r .
Da wir nur Aussagen über große x machen, sprechen wir vom asymptotischen
Verhalten.
Das O soll an das Wort Ordnung erinnern. Es werden aber eher Sprechweisen wie
f ist O(g), in Worten f ist Groß-O von g, benutzt.
Streng genommen ist O(g) eine Menge von Funktionen und die Schreibweise
f = O(g) eine etwas unpr¤zise, aber nützliche Abkürzung für f ∈ O(g).
In der Praxis verwendet man oft Funktionen zum Vergleich, die besonders einfach
sind. So l¤sst man beispielsweise alle Koef¬zienten weg.
Vor den ersten Beispielen führen wir noch eine übliche Notation ein. Für jede
reelle Zahl x bezeichne

x := max {z ∈ Z ; z ¤ x}

das größte Ganze von x.

Beispiel
Konstante Funktionen X ’ R , x ’ c sind in O(1).

Jede Polynomfunktion f ∈ R[x] mit n = deg f ist in O(x n ).

Für die Funktion f mit f (x) = 1 + x2 gilt

1
f (x) = O(x) und f (x) = x + O .
x

Dabei ist die letzte Gleichung wie folgt zu verstehen:

1
f (x) ’ x = 1 + x2 ’ x ∈ O .
x

Zum Nachweis untersuche man die Grenzwerte
f (x)
lim x( f (x) ’ x) .
bzw.
lim
x
x’∞ x’∞

Für die Logarithmusfunktion loga zur Basis a gilt

log x
loga x = = O (log x) .
log a

In der O-Notation ist also die Basis des Logarithmus irrelevant.
4.1 Komplexit¤t 59

Die Anzahl der Bits einer natürlichen Zahl N ist O(log N). Genauer: Die An-
zahl f (N) der Stellen in g-adischer Darstellung, g ∈ N ≥2 , betr¤gt

f (N) = logg N + 1 = O(log N) .

Der Wert von g spielt asymptotisch keine Rolle.

Bemerkung
Für den logarithmus naturalis verwenden wir die Bezeichnung log = loge oh-
ne Angabe der Basis. Sollte es einmal (wie etwa bei den obigen asymptotischen
Betrachtungen) nicht auf die Basis ankommen, so bevorzugen wir auch im Fall
g = e die einfache Schreibweise log anstelle logg .


4.1.2 Die Laufzeit von Algorithmen

Das Ziel dieses Abschnitts ist es, die Laufzeit von Algorithmen abzusch¤tzen und
zu vergleichen. Dabei nutzen wir ein sehr grobes Maß: Wir z¤hlen die nötigen
Iterationen in Abh¤ngigkeit von der Größe der Eingabe bezogen auf eine einfa-
che Grundoperation. Wir abstrahieren dadurch von der Hardware, die natürlich
die tats¤chlich benötigte Zeit entscheidend mitbestimmt. Insbesondere kann die
Grundoperation durchaus eine größere Anzahl von Prozessorzyklen in Anspruch
nehmen und selbst zeitaufw¤ndig sein. Sie muss aber O(1) sein, darf also nicht
von der Größe der Eingabe abh¤ngen.
Unsere Angaben werden immer asymptotisch sein, dabei ignorieren wir die De-
tails der Implementierung, also die konkrete Umsetzung eines Algorithmus in eine
Programmiersprache. Auch diese beein¬‚usst durchaus erheblich die tats¤chlich
benötigte Zeit.
Asymptotische Aussagen sagen insbesondere nichts über die Laufzeit für kleine
Eingangsgrößen aus. Um darüber Ergebnisse zu erzielen, muss man die Konstan-
ten genau studieren.
Ist n die Größe der Eingabe (etwa die Anzahl der Bits) in einen Algorithmus, so
heißt der Algorithmus
polynomial, wenn die Laufzeit O(n± ), ± ∈ R >0 , ist,

linear, falls er polynomial mit ± = 1 ist,

quadratisch, falls er polynomial mit ± = 2 ist,

exponentiell, wenn die Laufzeit O(e± n ), ± ∈ R >0 , betr¤gt.

In diesem Sinne ist die Laufzeit des Einlesens der Daten linear. Insbesondere hat
das Einlesen einer natürlichen Zahl N nach dem letzten Beispiel die Laufzeit
O(log N). Wir werden im n¤chsten Abschnitt sehen, dass der übliche Algorith-
mus für die Addition natürlicher Zahlen linear, der für die Multiplikation qua-
dratisch ist.
60 4 Komplexit¤t und Einwegfunktionen

Bemerkung
Moderne Faktorisierungs-Algorithmen für natürliche Zahlen haben Laufzeiten

der Form
O(ec log N log log N ), c > 0 .
Das ist zwar nicht polynomial, aber besser als exponentiell. Man nennt sie des-
halb subexponentiell.


4.1.3 Multiplikation von Polynomen

Wir betrachten als erstes Beispiel die Laufzeit für die Multiplikation von Poly-
nomen f , g ∈ Z[X] mit beschr¤nkten Koef¬zienten. Das soll bedeuten, dass die
Asymptotik nur von m = deg f und n = deg g abh¤ngt. Das ist insbesondere für
Polynome über den Restklassenringen Z erfüllt. Hier liegen alle Koef¬zienten
zwischen 0 und ’ 1, weil sie in jedem Schritt modulo reduziert werden.
Die Formel auf Seite 35 zeigt, dass man zur Berechnung des i-ten Koef¬zienten
( f g)i von f g genau i + 1 Multiplikationen von Koef¬zienten durchführen muss.
Die Multiplikation der Koef¬zienten kann als Grundoperation gew¤hlt werden,
weil die Koef¬zienten unabh¤ngig von m und n beschr¤nkt sind. Da die Kosten
für die Addition wesentlich geringer sind, wird diese hier vernachl¤ssigt. Man
beachte auch, dass die Anzahl der Additionen ungef¤hr so groß wie diejenige
der Multiplikationen ist, sodass sich eine Berücksichtigung asymptotisch nicht
auswirken würde. Diese Überlegungen führen auf eine erste Absch¤tzung für
die Laufzeit:
(m + n + 1)(m + n + 2)
m+n
‘ (i + 1) = = O (m + n)2 .
2
i=0

Es geht aber besser: Wir nehmen ohne Einschr¤nkung m ≥ n an, dann sind für
i > n gewisse Produkte zwingend = 0. L¤sst man diese Produkte unberücksich-
tigt, so ergibt sich für die Gesamtzahl aller Multiplikationen:

(m + 1) (n + 1) = O(mn) .

Dabei wird einfach jeder Koef¬zient von f mit jedem von g kombiniert. Dieselben
Überlegungen greifen auch bei Polynomen über endlichen Ringen, wenn man
wieder die Ringmultiplikation als Grundoperation w¤hlt. Wir halten fest:

Lemma 4.1
Sind f und g Polynome über einem endlichen Ring oder über Z mit beschr¤nkten
Koef¬zienten, so betr¤gt die Laufzeit der Multiplikation dieser Polynome asymptotisch
O(deg f · deg g).

Bemerkung
Die Laufzeit des zuerst betrachteten naiven Algorithmus und die Aussage von
4.1 Komplexit¤t 61

Lemma 4.1 unterscheiden sich nicht sehr. Sind m und n ungef¤hr gleich groß,
dann sind beide quadratisch.
Ist aber n beschr¤nkt, so ist der naive Algorithmus immer noch quadratisch, w¤h-
rend das Lemma eine lineare Laufzeit liefert.

Im Folgenden untersuchen wir die Komplexit¤t einiger weiterer für kryptogra¬-
sche Anwendungen wichtiger Algorithmen.
Wie geschehen unterstellen wir bei allen Betrachtungen, dass gewisse Grund-
operationen in O(1) (also in konstanter Zeit) durchgeführt werden können.


4.1.4 Addition und Multiplikation ganzer Zahlen

Wir w¤hlen für zwei natürliche Zahlen a, b und g ∈ N ≥2 die g-adische Darstel-
lung. Das bedeutet:
m n
‘ ai g ‘ bj g j
a= und b = mit 0 ¤ ai , b j < g .
i
i=0 j=0

In der Praxis ist vor allem die Bin¤rdarstellung, d. h. der Fall g = 2 wichtig.
Der übliche (schon in der Grundschule gelehrte) Algorithmus zur Addition der
Zahlen a und b ist gegeben durch:

u0 := 0 und c := a + b + u ’ u · g für ∈ {0, . . . , max{n, m} + 1} .
+1

Dabei wird u +1 so gew¤hlt, dass 0 ¤ c < g. In jedem Schritt wird also modulo
g addiert. Man sieht leicht, dass u +1 ∈ {0, 1}. Man nennt u +1 den Übertrag an
der -ten Stelle. Es gilt dann

max{n,m}+1

a+b = c g.
=0

Mit gutem Recht kann man annehmen, dass die Bestimmung von c und u +1 in
jedem Schritt die Laufzeit O(1) hat. Das ist die Grundoperation in diesem Beispiel.
Es folgt:

Lemma 4.2
Die Laufzeit der Addition zweier Zahlen a und b aus N betr¤gt O(max{log a, log b}).

Der gezeigte Algorithmus ist also auf jeden Fall linear. Für die Multiplikation
natürlicher Zahlen geht man ganz analog vor. Die Grundoperation hierbei ist die
Multiplikation modulo g mit Übertrag, und man erh¤lt für die Laufzeit:

Lemma 4.3
Die Laufzeit der Multiplikation zweier Zahlen a und b aus N betr¤gt O(log a log b).
62 4 Komplexit¤t und Einwegfunktionen

Hierzu vergleiche man auch die Aussage in Lemma 4.1. Man kann n¤mlich
den üblichen Multiplikations-Algorithmus als Polynom-Multiplikation mit Über-
trag deuten.
Selbst bei diesen einfachen Operationen ist möglicherweise nicht das letzte Wort
gesprochen, wie zum Beispiel Aufgabe 4.3 zeigt.

Bemerkung
Der Multiplikations-Algorithmus von Schönhage und Strassen [24] hat die Kom-
plexit¤t O(n log n log log n), wobei n = log a ≈ log b. Das ist zwar besser als
unsere Laufzeitangabe in Lemma 4.3, wirkt sich aber erst ab n ≈ 10 000 in einer
tats¤chlichen Beschleunigung aus.


4.1.5 Division mit Rest

In Satz 3.2 wurde die Division mit Rest für Polynome über einem Körper einge-
führt. Sicher schon aus der Schule bekannt ist die für die Kryptologie fundamen-
tale Division mit Rest für ganze Zahlen. Der Vollst¤ndigkeit halber wiederholen
wir den Satz. Der Beweis kann fast wörtlich aus dem Beweis zu Satz 3.2 über-
nommen werden. An die Stelle der Abbildung deg tritt dabei die Betragsfunktion
| · |, wie man schon an der Formulierung sehen kann.

Satz 4.4 (Division mit Rest)
Zu ganzen Zahlen a, b, wobei b = 0, existieren eindeutig bestimmte q, r ∈ Z mit
a = b q + r und 0 ¤ r < |b| .

Bemerkung
Wir erinnern an eine Schreibweise, die aus der linearen Algebra bekannt ist. Man
sagt, zwei ganze Zahlen a und r sind kongruent modulo b, falls es ein q ∈ Z gibt
mit a = b q + r. Man schreibt dafür auch
a ≡ r (mod b) .
Der Satz zur Division mit Rest besagt, dass, im Falle b = 0, jede ganze Zahl a zu
einer Zahl r ∈ {0, . . . , |b| ’ 1} kongruent modulo b ist. Offenbar ist ≡ (mod b)
eine „quivalenzrelation, die Anzahl der „quivalenzklassen ist |b|.

Legt man den aus der Schule bekannten Algorithmus zur Division mit Rest zu-
grunde, so erhalten wir für die Laufzeit:

Lemma 4.5
Die Division mit Rest bei ganzen Zahlen a, b, wobei b = 0, d. h. die Bestimmung von
q, r ∈ Z mit a = b q + r und 0 ¤ r < |b|, hat die Laufzeit
a
O(log b log q) = O log b log .
b
4.1 Komplexit¤t 63

Eine typische Anwendung ist z. B. die Multiplikation zweier Zahlen a und b mo-
dulo m mit Faktoren 0 ¤ a, b < m: Die Division mit Rest wird auf a b angewendet,
um den kleinsten positiven Vertreter von a b ∈ Z m zu bestimmen. Man beachte,
dass a, b und a b ungef¤hr so groß wie m sind. Beide Teilschritte des Algorithmus,
n¤mlich die Multiplikation und die Division mit Rest, sind quadratisch, also kann
man zusammenfassen:

Lemma 4.6
Die Multiplikation modulo m hat die Laufzeit O((log m)2 ), ist also quadratisch.

Mit einem Beweis, der sich nicht wesentlich von dem für ganze Zahlen unter-
scheidet, ergibt sich für die Laufzeit für die Division von Polynomen mit Rest:

Lemma 4.7
Es seien a, b Polynome über einem Körper K, und es gelte b = 0. Die Division mit Rest,
also die Bestimmung von q, r ∈ K[X] mit a = b q + r und deg r < deg b, hat die
Laufzeit O(deg b deg q).


4.1.6 Komplexit¤tsklassen

Wir sagen: Ein mathematisches Problem Π gehört zur
• Komplexit¤tsklasse P , falls es einen polynomialen Algorithmus zur Lö-
sung dieses Problems gibt, und zur

• Komplexit¤tsklasse NP , falls es einen polynomialen Algorithmus gibt, der
prüfen kann, ob eine erratene Lösung korrekt ist oder nicht.
Das Symbol NP steht dabei für nondeterministic polynomial time. Gehört ein Pro-
blem zu P , so gehört es offensichtlich auch zu NP .

Beispiel
Alle bisher in diesem Kapitel untersuchten Probleme, zu denen wir Algorith-
men angegeben haben, gehören zu P . Darunter sind Addition und Multipli-
kation von ganzen Zahlen und von Polynomen, Divison mit Rest, Bestimmung
des ggT, usw.

Die Faktorisierung natürlicher Zahlen ist in NP , denn ein zu testender Teiler
kann mittels Division mit Rest überprüft werden. Es wird vermutet, ist aber
nicht bekannt, dass die Faktorisierung natürlicher Zahlen nicht zu P gehört.

Jedes Problem Π aus der Komplexit¤tsklasse NP kann durch Ausprobieren aller
Kandidaten für Lösungen gelöst werden. Diese Herangehensweise zur Lösung
des Problems Π hat aber im Allgemeinen eine exponentielle Laufzeit. Hat n¤m-
lich der Eingabewert die Größe n, so hat die Menge, die durchsucht werden muss,
64 4 Komplexit¤t und Einwegfunktionen

im Allgemeinen O (2n ) Elemente. Es müssen also auch O (2n ) Tests durchgeführt
werden. Da die Tests polynomial sind, ist der naive Algorithmus alles Durchpro-
bieren somit exponentiell.
Übrigens gibt es durchaus Probleme mit exponentiellen Lösungs-Algorithmen,
die nicht in NP liegen.

Bemerkung
Der Begriff mathematisches Problem bleibt vage. Wie beim Begriff des Algorithmus
und der Komplexit¤t würde eine pr¤zisere Fassung den Rahmen dieses Buches
sprengen. Anhand der Beispiele sollte aber ein Grundverst¤ndnis möglich sein.
Um diese Begriffe genauer fassen zu können, müssten wir den Begriff der Turing-
Maschine einführen und diskutieren. Das würde den Rahmen einer Einführung
in die algebraischen Methoden der Kryptologie verlassen. Daher verweisen wir
auf die Literatur.

Wie oben bereits festgehalten, liegt P in NP . Es ist eine offene Frage, ob die bei-
den Klassen evtl. gleich sind, ob es also zu jedem Problem aus NP einen polyno-
mialen Algorithmus zur Lösung gibt. Auf die Beantwortung dieser Frage ist ein
Preis von einer Million US-Dollar ausgesetzt. Es ist eines der Millenium-Probleme1 ,
die vom privaten Clay Mathematics Institute zusammengestellt wurden.


4.1.7 Algorithmische „quivalenz

In der Klasse NP gibt es eine re¬‚exive und transitive Relation ≺. Man schreibt

Π1 ≺ Π2 ,

wenn es einen polynomialen Algorithmus gibt, mit dem man das mathematische
Problem Π1 auf das Problem Π2 zurückführen kann. Genauer: Besitzt man ein
Orakel zur Lösung von Π2 , so kann man Π1 in polynomialer Zeit lösen. Ein Ora-
kel ist dabei eine (¬ktive) Maschine, die auf Anfrage eine Lösung eines gewissen
mathematischen Problems ausgibt. Bei uns ist das Π2 . Die Befragung eines Ora-
kels wird bei der Ermittlung von Laufzeiten vernachl¤ssigt.

Beispiel
Für die Probleme prim(N) „prüfe, ob eine gegebene natürliche Zahl N eine Primzahl
ist“ und Fak(N) „faktorisiere die natürliche Zahl N“ gilt prim(N) ≺ Fak(N), da
man prim auf das Problem der Faktorisierung zurückführen kann. Dass das keine
gute Strategie ist, soll uns hier nicht stören.

Zwei mathematische Probleme Π1 und Π2 mit Π1 ≺ Π2 und Π2 ≺ Π1 nennt
man algorithmisch ¤quivalent. Den Nachweis dafür, dass hierdurch auf NP eine
„quivalenzrelation de¬niert wird, haben wir als Übungsaufgabe formuliert.
1 http://www.claymath.org/millennium/P_vs_NP/
4.2 Der erweiterte euklidische Algorithmus 65

Bemerkung
Es ist überaus bemerkenswert, dass es Probleme Π in NP gibt, die maximal be-
züglich der Relation „≺“ sind, d. h. dass für alle Probleme Π ∈ NP gilt Π ≺ Π.
Man nennt solche maximalen Probleme NP -vollst¤ndig.
Die Frage nach der Gleichheit der Komplexit¤tsklassen P und NP l¤sst sich so-
mit auf das Studium von NP -vollst¤ndigen Problemen zurückführen.

Statt der Zeitkomplexit¤t, die wir bisher ausschließlich betrachtet haben, kann man
auch die Speicherkomplexit¤t betrachten. Es geht hierbei um die Frage, wie viel
Speicherplatz man braucht, um einen Algorithmus durchzuführen. Wir gehen
dieser Problematik nicht weiter nach und unterstellen stets unendliche Speicher-
kapazit¤t. Aber natürlich ist die Frage nach der Speicherkomplexit¤t zum Beispiel
beim Design von Smartcards durchaus relevant.
Ebenfalls wichtig ist die Frage, welche Laufzeit ein Algorithmus im Durchschnitt
(engl. avarage case) hat. Es gibt Beipiele von Algorithmen, die zwar im schlechtesten
Fall (engl. worst case) exponentiell, aber im Durchschnitt sehr schnell sind.


4.2 Der erweiterte euklidische Algorithmus

Wir halten einige einfache Aussagen zur Teilbarkeit in Z fest. Die Aussagen sind
bekannt bzw. leicht zu zeigen, daher verzichten wir auf die Beweise.



4.2.1 Teilbarkeit in den ganzen Zahlen

Wir sagen: Eine ganze Zahl b teilt eine ganze Zahl a, in Zeichen b | a, wenn es ein
q ∈ Z gibt mit a = b q. In der Kongruenzschreibweise (vgl. die Bemerkung auf Seite
62) lautet das wie folgt:
b | a ” a ≡ 0 (mod b) .

Lemma 4.8
Für ganze Zahlen a, b, c gilt:

(a) Die Relation | ist re¬‚exiv und transitiv, d. h. a | a und aus a | b und b | c folgt a | c.

(b) Aus a | b und b | a folgt |a| = |b|.

(c) 0 | a impliziert a = 0, und a | 0.

(d) Aus b | a und b | c folgt b | a x + c y für alle x, y ∈ Z.

Wir werden diese Aussagen im Folgenden h¤u¬g ohne explizites Zitat verwen-
den.
66 4 Komplexit¤t und Einwegfunktionen

4.2.2 Der erweiterte euklidische Algorithmus
Der erweiterte euklidische Algorithmus bestimmt den größten gemeinsamen
Teiler, in Zeichen ggT, zweier (oder mehrerer) ganzer Zahlen.
Sind a1 , . . . , ak ganze Zahlen, so heißt eine Zahl t ∈ Z gemeinsamer Teiler von
a1 , . . . , ak , wenn t | ai für alle i ∈ {1, . . . , k}. Die natürliche Zahl 1 ist immer
ein gemeinsamer Teiler. Ist eines der ai , etwa a1 , ungleich 0, so gilt |t| ¤ |a1 |.
Daher gibt es in diesem Fall ein größtes t ∈ N, das alle a1 , . . . , ak teilt, genannt
der größte gemeinsame Teiler der ai . Wir schreiben dafür t = ggT(a1 , . . . , ak ).
Falls alle a1 , . . . , ak gleich 0 sind, so setzt man ggT(a1 , . . . , ak ) := 0. Der ggT von
endlich vielen Zahlen liegt stets in N0 .
Lemma 4.9
Für alle a, b, q ∈ Z gilt ggT(a, b) = ggT(a + bq, b).

Beweis. Wir benutzen Lemma 4.8 (d) zweimal:

ggT(a, b) | ggT(a + bq, b) | ggT(a + bq ’ bq, b) = ggT(a, b) .

Nun folgt die Aussage aus dem Teil (b) in Lemma 4.8.
Aus dieser einfachen Beobachtung ergibt sich der erweiterte euklidische Algo-
rithmus zur Berechnung des ggT von zwei ganzen Zahlen a und b. Er bestimmt
außerdem zwei ganze Zahlen x und y mit

a x + b y = ggT(a, b) .
Ohne Einschr¤nkung dürfen wir annehmen, dass a ≥ b > 0 gilt. Wir bestimmen
durch sukzessive Division mit Rest im i-ten Schritt ganze Zahlen ri , qi , xi , yi mit
r0 = b, 0 ¤ ri < ri’1 und:
i Division mit Rest Darstellung wobei
a = q0 b + r1 r1 = ax1 + by1 =1
1 x1
= ’q0
y1
b = q1 r1 + r2 r2 = ax2 + by2 = ’q1 x1
2 x2
= 1 ’ q1 y1
y2
r1 = q2 r2 + r3 r3 = ax3 + by3 = x1 ’ q2 x2
3 x3
= y1 ’ q2 y2
y3
. . .
. . .
. . .
rk’1 = qk rk + rk+1 rk = axk + byk xk = xk’2 ’ qk’1 xk’1
k
yk = yk’2 ’ qk’1 yk’1
. . .
. . .
. . .
rn’2 = qn’1 rn’1 + rn rn = axn + byn xn = xn’2 ’ qn’1 xn’1
n
yn = yn’2 ’ qn’1 yn’1
n+1 rn’1 = qn rn + rn+1 rn+1 = 0 Stop!
4.2 Der erweiterte euklidische Algorithmus 67

Der Algorithmus bricht ab, weil die ri ∈ N0 streng monoton fallen. Wegen Lem-
ma 4.9 gilt in jedem Schritt ggT(rk , rk’1 ) = ggT(rk+1 , rk ). Daher erhalten wir per
Induktion nach k (mit den Bezeichnungen aus obiger Tabelle):

Satz 4.10 (Der euklidische Algorithmus)
Der euklidische Algorithmus bricht nach n + 1 Schritten ab. Sind a, b ganze Zahlen,
b = 0, so ist der Rest rn der ggT von a und b:

rn = ggT(a, b) .

Weiter liefert der Alorithmus ganze Zahlen x := xn und y := yn mit

ggT(a, b) = a x + b y .

Beispiel 4.11
Wir bestimmen mit dem erweiterten euklidischen Algorithmus ganze Zahlen x
und y mit ggT(840, 455) = x · 840 + y · 455:

i Division mit Rest Darstellung wobei
840 = 1 · 455 + 385 r1 = 840 x1 + 455 y1 x1 = 1
1
y1 = ’1
455 = 1 · 385 + 70 r2 = 840 x2 + 455 y2 x2 = ’1 · 1
2
y2 = 1 ’ 1 · (’1)
385 = 5 · 70 + 35 r3 = 840 x3 + 455 y3 x3 = 1 ’ 5 · (’1)
3
y3 = ’1 ’ 5 · 2
70 = 2 · 35 + 0 r4 = 0
4 Stop!

Wir erhalten
ggT(840, 455) = 35 = 6 · 840 + (’11) · 455 .

Eine einfache, aber wichtige Folgerung ist die fast offensichtliche Kennzeichnung
für den ggT.

Lemma 4.12
Für a, b ∈ Z und d ∈ N0 gilt d = ggT(a, b) genau dann, wenn

d | a und d | b, und
(i)

für jedes t ∈ Z mit t | a und t | b gilt t | d.
(ii)

Beweis. ’: (i) gilt nach Voraussetzung.
(ii) Es gelte t | a und t | b, etwa a = a t und b = b t, für ein t ∈ Z. Ist d = ggT(a, b),
so existieren nach dem euklidischen Algorithmus Zahlen x, y ∈ Z mit

d = a x + b y = a t x + b t y = (a x + b y) t ,
68 4 Komplexit¤t und Einwegfunktionen

sodass also t ein Teiler von d ist.
⇐: Nach (i) ist d ein gemeinsamer Teiler von a und b. Wegen (ii) ist jeder gemein-
same Teiler t von a und b ein Teiler von d. Daher gilt t ¤ d.

Es ist also ggT(a, b) auch maximal bezüglich der Relation | und nicht nur bezüg-
lich ¤. Eine weitere wichtige Folgerung ist:

Lemma 4.13
Teilt eine Primzahl p ein Produkt a b ganzer Zahlen a und b, so teilt p bereits einen der
Faktoren a oder b, d. h.:
p | ab ’ p | a oder p | b .

Beweis. Ist p ein Teiler von b, so sind wir fertig. Ist p kein Teiler von b, so gilt
ggT(p, b) = 1, und nach dem Satz 4.10 zum euklidischen Algorithmus existieren
ganze Zahlen x und y mit p x + b y = 1. Es folgt a p x + a b y = a. Nach Voraus-
setzung teilt p beide Summanden der linken Seite. Nach Lemma 4.8 also auch die
rechte Seite a.

Aus dieser Aussage kann man die Eindeutigkeitsaussage des Fundamentalsatzes
der Arithmetik ohne viel Mühe herleiten. Wir haben das als Aufgabe formuliert.

Satz 4.14 (Fundamentalsatz der Arithmetik)
Jede natürliche Zahl N > 1 l¤sst sich “ bis auf die Reihenfolge der Faktoren “ auf ge-
nau eine Art und Weise als ein Produkt von Primzahlpotenzen schreiben, d. h., es gibt
Primzahlen p1 , . . . , pr und natürliche Zahlen ν1 , . . . , νr ∈ N mit:
r
ν
∏ pi i .
N=
i=1

Sortiert man die Primzahlen der Reihe nach, d. h. setzt man p1 < · · · < pr , so
spricht man von der kanonischen Primfaktorzerlegung der natürlichen Zahl
N > 1.


4.2.3 Komplexit¤tsanalyse des euklidische Algorithmus *
Im folgenden Satz benutzen wir die Zahl

1+ 5
≈ 1.618 . . . < 2 ,
γ :=
2
die auch goldener Schnitt genannt wird. Es ist γ eine Nullstelle des Polynoms
x2 ’ x ’ 1, daher gilt
γ = 1 + γ’1 .
Das werden wir im Folgenden benutzen. Wir verwenden die im vorigen Ab-
schnitt eingeführten Bezeichnungen.
4.2 Der erweiterte euklidische Algorithmus 69

Satz 4.15
Für die im euklidischen Algorithmus auftretenden Variablen gilt:
log b
(a) n ¤ .
log γ

(b) |xk | ¤ |yk | ¤ für alle k ∈ {1, . . . , n}.
b a
2d , 2d

(c) Die Laufzeit des erweiterten euklidischen Algorithmus betr¤gt O(log a log b).

Beweis. Wir setzen ohne Einschr¤nkung a ≥ b > 0 voraus. Dies impliziert, dass
alle qk > 0 sind. Das werden wir mehrfach verwenden.
(a) Unter Nutzung der Beziehung 1 + γ’1 = γ zeigen wir zun¤chst

rk ≥ γn’k d für alle 0 ¤ k ¤ n

mit absteigender Induktion nach k. Der Induktionsanfang für k = n und k = n ’ 1
ist einfach:
rn = d ≥ γ0 d und rn’1 ≥ 2 d > γ d .
Für den Induktionsschluss rechnen wir:

rk’1 = qk rk + rk+1 ≥ rk + rk+1 ≥ γn’k d + γn’k’1 d
= γn’k 1 + γ’1 d = γn’k+1 d.

log b
Insbesondere gilt b = r0 ≥ γn und somit n ¤ log γ .
’qk 1
(b) Für k ∈ {1, . . . , n} und die Matrizen Qk := gilt
1 0

xk xk+1 yk yk+1
= =
und .
Qk Qk
xk’1 xk yk’1 yk

’q0
1
x1 y1
= =
Mit erh¤lt man
und
0 1
x0 y0

’q0
1 xn+1 yn+1
(—) Qn · · · Q1 = Q n · · · Q1 =
, .
0 1
xn yn

Der Knackpunkt des Beweises ist die Untersuchung der Matrizen

uk uk+1
(——) := Qn Qn’1 · · · Qk+1 .
vk vk+1

Es gilt
’qk ’qk uk + uk+1
1
uk uk+1 uk uk’1 uk
= = .
’qk vk + vk+1
1 0
vk vk+1 vk vk’1 vk
70 4 Komplexit¤t und Einwegfunktionen

Daher ist die Darstellung in (——) wohlde¬niert, und es gilt vk’1 = ’qk vk + vk+1 .
Wir zeigen mit absteigender Induktion nach k die Aussage:
r
(i) |vk | ¤ k für alle k ∈ {0, . . . , n}.
2d
Für k = n ist die Behauptung vn = 0 ¤ 2d klar; für k = n ’ 1 hat man vn’1 = 1 ¤
rn
rn’1
2d , denn rn’1 > rn = d und d | rn’1 .
Beim Induktionsschluss gehen wir von k nach k ’ 1 und beachten die Dreiecks-
ungleichung:
q r + rk+1
rk r r
+ k+1 = k k = k’1 .
|vk’1 | ¤ qk |vk | + |vk+1 | ¤ qk
2d 2d 2d 2d
Damit gilt die Behauptung in (i). Wir zeigen weiter:
(ii) xk = (’1)k |xk |, yk = (’1)k+1 |yk |, und |xk | und |yk | sind monoton wachsend
für alle k ∈ {0, . . . , n}.
Für k = 0 und k = 1 stimmen die Behauptungen offenbar. Wir führen den Induk-
tionschritt nur für xk aus (für yk geht man entsprechend vor):

xk+1 = ’qk xk + xk’1 = ’qk (’1)k |xk | + (’1)k’1 |xk’1 |
= (’1)k+1 qk |xk | + |xk’1 | .

Nach Induktionsvoraussetzung und wegen qk > 0 haben die Terme ’qk xk und
xk’1 dasselbe Vorzeichen. Daher gilt:

(’1)k+1 qk |xk | + |xk’1 | = (’1)k+1 |xk+1 | ,

und die Induktion ist komplett. Außerdem folgt |xk+1 | ≥ qk |xk | ≥ |xk |. Damit ist
(ii) gezeigt.
Das Produkt Qn Qn’1 . . . Q1 hat wegen (——) die Form

Qn Qn’1 . . . Q1 = ,
v0 v1

also gilt nach (—) die Gleichung xn = v0 . Nun zeigen (ii) und (i):

b
|xk | ¤ |xn | = |v0 | ¤ .
2d
Entsprechend ergibt sich aus (—) die Gleichung yn = ’q0 v0 + v1 und
q0 r0 + r1 a
|yk | ¤ |yn | ¤ = .
2d 2d
(c) Die k-te Division mit Rest hat nach Lemma 4.5 die Laufzeit O(log qk log rk ).
Insgesamt ergibt sich die Laufzeit:
n n
‘ log qk log rk ¤ log b log ∏ qk ¤ log b log a ,
k=0 k=0
4.3 Die primen Restklassengruppen 71

denn
a ≥ q0 r0 + r1 ≥ q0 (q1 r1 + r2 ) ≥ · · · ≥ qn qn’1 . . . q0 .
Um die Laufzeit für die Berechnung der xk abzusch¤tzen, rechnen wir
n’1 n’1
‘ log qk log xk ¤ log b log ∏ qk ¤ log b log b .
k=1 k=1

Analog ergibt sich für die yk
n’1 n’1
‘ log qk log yk ¤ log a log ∏ qk ¤ log a log b .
k=1 k=1

Da alle Teilaufgaben in O(log a log b) Schritten erledigt werden können, folgt die
Behauptung.

Bemerkung
Es ist von größter Bedeutung, dass der euklidische Algorithmus ohne eine Fak-
torisierung von a und b auskommt. Er ist sehr ef¬zient (nicht nur asymptotisch)
und spielt eine fundamentale Rolle in der Zahlentheorie und der Kryptologie.
Der Beweis zeigt auch, dass die Werte für x und y (und alle Zwischenergeb-
nisse) beschr¤nkt sind. Das impliziert polynomiale Speicherkomplexit¤t. Diese
Aussage gilt nicht nur asymptotisch und tr¤gt zur praktischen Ef¬zienz bei.
Es gibt einen analogen Algorithmus für Polynome, mit ¤hnlicher Komplexit¤t
(vgl. auch Lemma 4.7).


4.3 Die primen Restklassengruppen
In diesem Abschnitt sei eine natürliche Zahl n > 1 fest gew¤hlt.

4.3.1 Einheiten in Z n
Die Einheitengruppe des Restklassenringes (Z n , +, ·), das ist die multiplikative
Gruppe (Z — , ·) mit
n

Z — = {a ∈ Z n ; a ist invertierbar} = a ∈ Z n ; ∃ b ∈ Z n mit a b = 1 ,
n

wird auch prime Restklassengruppe modulo n genannt.

Satz 4.16
Für a ∈ Z gilt: a ∈ Z — ” ggT(a, n) = 1.
n

Beweis. Es sei a = a + n Z invertierbar. Folglich existiert ein b ∈ Z mit

1 + n Z = (a + n Z) · (b + n Z) = a b + n Z .
72 4 Komplexit¤t und Einwegfunktionen

Somit gibt es ein y ∈ Z mit a b ’ 1 = n y ∈ n Z. Jeder gemeinsame Teiler von a
und n ist ein Teiler von 1, daher folgt ggT(a, n) = 1.
Ist ggT(a, n) = 1, so existieren nach dem Satz 4.10 zum euklidischen Algorithmus
ganze Zahlen b und y mit a b + n y = 1, und es gilt

(a + n Z) · (b + n Z) = a b + n Z = 1 + n Z .

Somit ist a = a + n Z ∈ Z n invertierbar.
Nach diesem Satz gilt

Z — = {a ∈ Z n ; ggT(a, n) = 1} .
n

Beispiel
Wir geben die primen Restklassengruppen für einige kleine n an:
— — — —
Z2 = {1} , Z3 = {1, 2} , Z4 = {1, 3} , Z5 = {1, 2, 3, 4} ,
— — —
Z6 = {1, 5} , Z7 = {1, 2, 3, 4, 5, 6} , Z8 = {1, 3, 5, 7} .

In Z8 ist jedes Element zu sich selbst invers und es gilt etwa 3 · 5 = 7.

Wir ziehen einige wichtige Folgerungen. Die erste sollte aus der linearen Algebra
bekannt sein, sie wurde auch schon in Abschnitt 3.1 verwendet.

Korollar 4.17
Der Ring (Z n , +, ·) ist genau dann ein Körper, wenn n eine Primzahl ist.

Beweis. Der Ring Z n ist genau dann ein Körper, wenn alle Elemente = 0 invertier-
bar sind. Das ist nach Satz 4.16 gleichwertig dazu, dass alle Zahlen 1, . . . , n ’ 1 zu
n teilerfremd sind; und das ist genau dann erfüllt, wenn n eine Primzahl ist.

4.3.2 Lineare Kongruenzgleichungen
In Satz 4.10 zum euklidischen Algorithmus wurde die Existenz einer Darstellung
des ggT zweier ganzer Zahlen a und b gezeigt:

Es gibt x, y ∈ Z mit ggT(a, b) = a x + b y .

Wir können nun die Frage nach der Eindeutigkeit einer solchen Darstellung kl¤-
ren.

Lemma 4.18
Es seien a und b ganze Zahlen und d = ggT(a, b). Sind x, y ∈ Z mit d = a x + b y
gew¤hlt, so gilt:

b a
d = a x + b y für x , y ∈ Z ” ∃ k ∈ Z mit x = x + k und y = y ’ k .
d d
4.3 Die primen Restklassengruppen 73

Beweis. Die Richtung ⇐ erh¤lt man durch Einsetzen von x = x + k und y =
b
d
y ’ k d in a x + b y :
a


b a
ax +by = a x+k +b y’k = ax+by = d.
d d

Wir zeigen nun die Richtung ’: Aus a x + b y = d = a x + b y folgt:

a b a b
x+ y =1= x + y .
d d d d
b
Wir erhalten aus dieser Gleichung, indem wir modulo rechnen, die Kongruenz
d

a a b
x≡ x mod .
d d d

Da ggT( d , d ) = 1 kann man nach Satz 4.16 den Faktor
ab a
kürzen, und es folgt
d

b
x≡x mod ,
d

wie behauptet. Die Darstellung von y ergibt sich, indem man die resultierende
Gleichung
b
ax+by = a x+k +by
d
nach y auflöst.
Eine Gleichung der Form

a X ≡ c (mod n) mit a, c ∈ Z und n ∈ N

nennt man eine (lineare) Kongruenzgleichung. Die Lösungsmenge L der Kon-
gruenzgleichung a X ≡ c (mod n) ist die Menge aller Zahlen x ∈ Z mit n | a x ’ c,
anders ausgedrückt:

L = {x ∈ Z ; ∃ y ∈ Z mit a x + n y = c} .

Wir erhalten folglich aus Lemma 4.18:

Korollar 4.19
Es seien a, c ∈ Z und n ∈ N. Die Kongruenzgleichung

(—) a X ≡ c (mod n)

hat genau dann eine Lösung in Z, wenn d := ggT(a, n) | c. Ist x ∈ Z eine Lösung der
Kongruenzgleichung (—), so ist x + n Z die Menge aller Lösungen von (—).
d
74 4 Komplexit¤t und Einwegfunktionen

Bemerkung
Gilt d := ggT(a, n) | c, etwa c = d t, t ∈ Z, so erh¤lt man eine Lösung der
Kongruenzgleichung a X ≡ c (mod n) mit dem euklidischen Algorithmus. Man
bestimme k, l ∈ Z mit
ak+nl = d.

Multipliziert man diese Gleichung mit t, so sieht man, dass x := k t eine Lösung
der Kongruenzgleichung ist, da a x ≡ c (mod n).


Invertieren modulo n
4.3.3

Wie der Beweis von Satz 4.16 zeigt, erlaubt es der erweiterte euklidische Algo-
rithmus nicht nur zu kl¤ren, ob a ∈ Z modulo n invertierbar ist, sondern gegebe-
nenfalls das Inverse auch zu bestimmen. Weil diese Tatsache gerade in der Kryp-
tologie von so fundamentaler Bedeutung ist, halten wir sie ausdrücklich fest.

Satz 4.20
Es sei a ∈ Z, ’n < a < n, mit ggT(a, n) = 1 gegeben. Der erweiterte euklidische
Algorithmus 4.10 liefert b, y ∈ Z mit a b + n y = 1 in der Laufzeit O((log n)2 ).
Es ist b das Inverse von a im Ring Z n .


Beweis. Die Aussagen sind eine Zusammenfassung der S¤tze 4.10, 4.15 (c) und
4.16. Dabei ist zu berücksichtigen, dass a ungef¤hr so groß wie n ist.
Wir erlauben uns, an dieser Stelle nochmals auf die Bemerkung auf Seite 71 zu
verweisen. Sie zeigt, dass die Berechnung von Inversen im Ring Z n sehr ef¬zient
möglich ist. Es sei darauf hingewiesen, dass man mit dem Versuch, das Inverse
eines Elements in Z n zu bestimmen, zugleich prüft, ob es existiert. Anders aus-
gedrückt: Man muss nicht vorher testen, ob ein Inverses existiert.

Beispiel
Wir bestimmen mit dem erweiterten euklidischen Algorithmus das Inverse von
351 in Z770 :
i Division mit Rest Darstellung wobei
770 = 2 · 351 + 68 r1 = 770 x1 + 351 y1 x1 = 1
1
y1 = ’2
351 = 5 · 68 + 11 r2 = 770 x2 + 351 y2 x2 = ’5 · 1 = ’5
2
y2 = 1 ’ 5 · (’2) = 11
68 = 6 · 11 + 2 r3 = 770 x3 + 351 y3 x3 = 1 ’ 6 · (’5) = 31
3
y3 = ’2 ’ 6 · 11 = ’68
11 = 5 · 2 + 1 r4 = 770 x4 + 351 y4 x4 = ’5 ’ 5 · 31 = ’160
4
y4 = 11 ’ 5 · (’68) = 351
2 = 2·1+0 r5 = 0
5 Stop!
4.3 Die primen Restklassengruppen 75

Wir erhalten

1 = 770 · (’160) + 351 · 351 , d. h. 1 = 351 · 351 ,

somit ist 351 das Inverse zu 351 in Z770 .


4.3.4 Eulers •-Funktion

Bisher hatten wir n > 1 angenommen. Aber natürlich ist auch Z1 = {0} ein
Ring. Das Nullelement 0 ist gleichzeitig Einselement und damit invertierbar. Es

gilt also Z1 = Z1 = {0}.
Für jede natürliche Zahl n bezeichnet man mit •(n) die M¤chtigkeit von Z — :
n

•(n) = Z — .
n

Damit ist eine Abbildung • : N ’ N erkl¤rt “ die Euler™sche •-Funktion.
Die Zahl •(n) gibt wegen

Z — = {a ∈ Z n ; ggT(a, n) = 1} .
n

die Anzahl der natürlichen Zahlen aus {1, . . . , n} an, die zu n teilerfremd sind.

Beispiel
•(1) = 1 , •(2) = 1 , •(3) = 2 , •(4) = 2 , •(5) = 4 , •(6) = 2 , •(7) = 6.
•(p) = p ’ 1 für jede Primzahl p (man vergleiche das mit Satz 4.17).
Für jede Primzahlpotenz pk , k ∈ N, ¬ndet man:
1
•(pk ) = pk ’ pk’1 = pk 1’ ,
p

da unter den pk Zahlen 1, 2, . . . , pk genau die pk’1 Zahlen p, 2 p, . . . , pk’1 p
einen gemeinsamen Teiler mit pk haben. Alle anderen Zahlen zwischen 1 und
pk , das sind pk ’ pk’1 Zahlen, sind zu pk teilerfremd.
•(p q) = (p ’ 1) (q ’ 1) für verschiedene Primzahlen p und q, da unter den
Zahlen 1, . . . , p, . . . , 2 p, . . . , q p genau q Zahlen einen gemeinsamen Teiler mit
p haben und analog genau p Zahlen unter 1, . . . , q, . . . , 2 q, . . . , p q einen ge-
meinsamen Teiler mit q haben. Folglich sind genau

p q ’ p ’ q + 1 = (p ’ 1) (q ’ 1)

Zahlen unter 1, . . . , p q zu p q teilerfremd. Der Summand 1 rührt daher, dass
wir die Zahl p q nur einmal berücksichtigen dürfen.

Auf weitere interessante Eigenschaften der Euler™schen •-Funktion gehen wir in
Kapitel 7 ein.
76 4 Komplexit¤t und Einwegfunktionen

4.4 Einwegfunktionen und Hashfunktionen

Etwas salopp ausgedrückt, werden wir eine Funktion f , für die b = f (a) einfach
auszuwerten ist, aber für die a ∈ f ’1 ({b}) schwer zu bestimmen ist, eine Ein-
wegfunktion nennen. Die Existenz von echten Einwegfunktionen h¤ngt eng mit der
Frage zusammen, ob die Komplexit¤tsklassen P und NP verschieden sind. Da
diese Frage offen ist, werden wir zur Existenz von Einwegfunktionen nur Vermu-
tungen anstellen können.
Im Folgenden werden wir gelegentlich feststellen, eine Funktion sei in P oder
NP . Das soll bedeuten, dass es einen Algorithmus zur Auswertung von f gibt,
der in der entsprechenden Klasse liegt. In vielen “ gerade für diesen Abschnitt
wichtigen “ F¤llen, h¤ngt das von der Art ab, wie f beschrieben ist.


4.4.1 Einwegfunktionen

Es seien A und B Mengen. Eine Abbildung f : A ’ B heißt Einwegfunktion,
wenn gilt:
(E1) f ∈ P und f l¤sst sich tats¤chlich ef¬zient berechnen;
(E2) Das Problem Π „zu b ∈ B bestimme a ∈ A mit f (a) = b“, d. h. ¬nde ein
Element in f ’1 (b), ist für die meisten b ∈ B nicht ef¬zient lösbar. Im besten
Fall ist Π nicht in P .
Man beachte, dass das Problem Π wegen der ersten Bedingung in NP liegt.

Beispiel
Wir betrachten die Menge Ik = [2k’1 , 2k ’ 1] © N der k-Bit Zahlen. Die Multipli-
kationsabbildung
Ik — Ik ’ N
(a, b) ’ a b
kann ef¬zient ausgeführt werden (siehe Lemma 4.3). Daher ist (E1) erfüllt. Es
scheitert aber (E2) an der Formulierung für die meisten. Für kryptogra¬sche An-
wendungen sind die Ergebnisse zu h¤u¬g faktorisierbar.
Schr¤nken wir diese Abbildung aber ein, indem wir nur k-Bit Primzahlen zulas-
sen, also Elemente der Menge P k := {p ∈ Ik ; p prim}, so erhalten wir:
Pk — Pk ’N
(a, b) ’ ab
Diese Abbildung ist nach allem, was wir heute wissen, vermutlich eine Einweg-
funktion. Auf dieser Einwegfunktion basiert das bekannte RSA-Verfahren.

Bemerkung
Die Sicherheit von AES besagt im Wesentlichen, dass AES eine Einwegfunktion
in beiden Argumenten ist.
4.4 Einwegfunktionen und Hashfunktionen 77

Anwendung: Schlüsselaustausch. Gegeben sei ein Kryptosystem (P, P, K, f , g)
bei dem f (y, . ) : K ’ P für jedes y ∈ P eine Einwegfunktion ist. Außerdem
setzen wir voraus, dass f k1 und f k2 für alle k1 , k2 ∈ K vertauschbar sind, dass also
gilt f k1 —¦ f k2 = f k2 —¦ f k1 .
Wir w¤hlen ein festes x ∈ P, das öffentlich zug¤nglich ist. Zwei Teilnehmer T1
und T2 bestimmen einen gemeinsamen geheimen Schlüssel κ wie folgt:
T1 w¤hlt k1 ∈ K und publiziert y1 := f (x, k1 ).
T2 w¤hlt k2 ∈ K und publiziert y2 := f (x, k2 ).
Es ist κ := f (y2 , k1 ) = f (y1 , k2 ) der gemeinsame geheime Schlüssel, wobei T1
die erste, T2 die zweite Rechnung ausführen kann.
Unsere Voraussetzung stellt sicher, dass es nicht möglich ist, κ aus y1 oder y2 zu
berechnen.
Diese Idee geht auf Dif¬e und Hellman [9] zurück. Sie haben auch ein konkretes
Verfahren beschrieben, das in Kapitel 9 zu ¬nden ist. Dort werden einige Feinhei-
ten diskutiert, die wir hier der Einfachheit halber unterschlagen haben.


4.4.2 Hashfunktionen

Hashfunktionen “ im Deutschen auch Streuwertfunktionen genannt “ sollen evtl.
sehr große Datenmengen auf einen kleinen, aber typischen Datensatz komprimie-
ren. Sie werden in der Kryptologie h¤u¬g eingesetzt, etwa bei Signaturschemata
und auch bei symmetrischen Authenti¬kationssystemen, wie sie im folgenden
Kapitel beschrieben werden.
Es seien P, C Mengen mit |P| > |C|. Dabei darf P unendlich sein, C wird endlich
vorausgesetzt. Wir nennen eine Einwegfunktion h : P ’ C eine Hashfunktion.
Genauer müsste man Einweg-Hashfunktion sagen, aber wir sind nur an Einweg-
funktionen interessiert.

Bemerkung
Für andere Anwendungen, wie etwa die Indizierung in Datenbanken, werden
durchaus auch Hashfunktionen ohne Einwegeigenschaft benutzt.

Eine Hashfunktion h heißt kollisionsresistent, wenn es keinen ef¬zienten Algo-
rithmus gibt, mit dem x, y ∈ P gefunden werden können, für die h(x) = h(y)
gilt. H¤u¬g wird die Kollisionsresistenz in die De¬nition der Hashfunktion mit
aufgenommen.
Es gibt noch eine schw¤chere Form der Kollisionsresistenz: Zu vorgegebenem
x ∈ P gibt es keinen ef¬zienten Algorithmus, der y ∈ P ¬ndet mit h(y) = h(x).
Wegen |P| > |C| ∈ N kann die Abbildung h nicht injektiv sein. Daher gibt es
x, y mit h(x) = h(y) “ im Allgemeinen sogar sehr viele! Verlangt ist nur, dass es
schwer sein muss, solche zu ¬nden.
78 4 Komplexit¤t und Einwegfunktionen

In vielen kryptogra¬schen Anwendungen sind die Mengen P und C speziell ge-
w¤hlt: Wir erinnern an die Menge aller Wörter über dem Alphabet A (in der
Praxis ist A oft gleich Z2 ) aus Abschnitt 1.4, die wir mit A— bezeichnet haben.
Mit n ∈ N werden dann h¤u¬g Hashfunktionen h : A— ’ An benutzt. Bei sol-
chen Hashfunktionen wird also ein Datensatz beliebiger L¤nge auf einen Daten-
satz der festen L¤nge n komprimiert. Ein typischer Wert für n aus der Praxis ist
n = 160, oder größer.
Die Kollisionsresistenz stellt sicher, dass der sogenannte Hashwert h(x) unf¤lsch-
bar mit x verbunden ist. Man spricht manchmal auch von einem (kryptogra¬-
schen) Fingerabdruck. Wie der Fingerabdruck eines Menschen diesen fast sicher
identi¬zieren kann, soll der Hashwert den Datensatz x identi¬zieren.



4.4.3 Einwegfunktionen mit Hintertürchen

Auch die Idee, Einwegfunktionen mit Hintertürchen zu de¬nieren, stammt von
Dif¬e und Hellman [9]. Sie haben damit die moderne Kryptologie begründet.
Es seien A und B Mengen. Eine Abbildung f : A ’ B heißt Trapdoor-
Einwegfunktion oder Einwegfunktion mit Hintertürchen, wenn gilt:

(H1) f ist invertierbar.

(H2) Das Paar ( f , f ’1 ) ist leicht zu erzeugen.

(H3) Es gibt eine Beschreibung von f , in der f eine Einwegfunktion ist.

(H4) f ’1 ∈ P , genauer: Es gibt einen Algorithmus, mit dem f ’1 ef¬zient berech-
net werden kann.

Beispiele werden wir hierzu nicht geben. In Kapitel 7 wird gezeigt, dass das RSA-
Verfahren auf einer Einwegfunktion mit Hintertürchen basiert, die algorithmisch
¤quivalent zur Faktorisierung ist (siehe auch das Beispiel auf Seite 76).
Weitere Kandidaten für Einwegfunktionen mit Hintertürchen ergeben sich aus
dem diskreten Logarithumsproblem, wie es in Kapitel 10 beschrieben ist.



4.4.4 Anwendungen

Die Beobachtung von Dif¬e und Hellman [9] war, dass aus Einwegfunktionen mit
Hintertürchen asymmetrische Verschlüsselungs- und Signaturschemata konstru-
iert werden können: Jeder Teilnehmer T eines Netzwerks erzeugt sich ein Paar
’1
( f T , f T ) von Trapdoor-Einwegfunktionen und veröffentlicht f T in der Beschrei-
bung gem¤ß (H3).
4.4 Einwegfunktionen und Hashfunktionen 79

Anwendung: Verschlüsselung. Die Nachricht N soll an den Teilnehmer T ver-
’1
schickt werden. Dazu wird f T (N ) verschickt. Nur T kennt f T und kann daher
’1
f T ( f T (N )) berechnen. Nicht einmal der Absender kann N aus f T (N ) zurück-
gewinnen (wenn er etwa N vergessen hat), weil f T eine Einwegfunktion ist.

Anwendung: Signatur. Teilnehmer T will die Nachricht N signieren. Dazu be-
’1 ’1
rechnet T den Ausdruck f T (N ) und verschickt (N , f T (N )). Jeder kann durch
Anwenden von f T die Unterschrift veri¬zieren.
In der Praxis wird nicht die Nachricht N , die sehr groß sein kann, signiert, son-
dern ein Hashwert h(N ). Dabei ist h eine geeignete, kollisionsresistente Hash-
funktion. Der Vorteil des Einsatzes von Hashfunktionen besteht darin, dass die
Signatur eine feste L¤nge hat, unabh¤ngig von der signierten Datenmenge.
An dieser Stelle wird auch klar, warum die Hashfunktion kollisionsresistent sein
muss. Könnte ein Angreifer eine Kollision erzeugen, also x, y mit h(x) = h(y), so
könnte er versuchen, den arglosen Teilnehmer T dazu zu bewegen, die harmlos
aussehende Nachricht x zu signieren, und h¤tte dann eine gültige Unterschrift
für die Nachricht y, von der T nichts weiß.

Bemerkung
Ein Signaturschema liefert Integrit¤t und Authentizit¤t, wie sie im n¤chsten Ka-
pitel beschrieben werden. Darüber hinaus können auch juristische Kategorien
wie

• Willenserkl¤rung,
• Unwiderru¬‚ichkeit,
• Rechtsverbindlichkeit

realisiert werden.

Wichtig ist dabei, eine unlösliche Verknüpfung zwischen den Teilnehmern T
und der zugehörigen öffentlichen Abbildung f T herzustellen. Beispielsweise
muss verhindert werden, dass ein Angreifer eine gef¤lschte Abbildung f T “
etwa auf eine Webseite “ plaziert, die für T™s Abbildung gehalten wird (man
vgl. hierzu auch das Problem mit dem Mann in der Mitte auf Seite 169). Das
ist ein nichttriviales, technisches Problem, das unter dem Stichwort Public-Key-
Infrastruktur behandelt wird.




Aufgaben
4.1 Führen Sie den Beweis des Satzes 4.4 in allen Details aus.

4.2 Bestimmen Sie die Laufzeit des üblichen Algorithmus für die Division mit
Rest.
80 4 Komplexit¤t und Einwegfunktionen

4.3 Komplexit¤t der Multiplikation

(a) Beschreiben Sie die Multiplikation zweier Bin¤r-Zahlen nach der bekannten
Methode aus der Grundschule.
(b) Bestimmen Sie die Komplexit¤t des Algorithmus in (a).
(c) Berechnen Sie 1100100 · 1010101 mit dem Algorithmus in (a).
(d) Es seien a, b ∈ N in der g-adischen Darstellung

n’1 n’1
mit n = 2ν
‘ ai g , ‘ bi g i
a= b=
i
i=0 i=0

gegeben. Wir setzen
n ’1 n ’1
2 2 n
‘ ‘ a n +i gi , sodass a = a L + a H g 2
ai gi und a H :=
a L :=
2
i=0 i=0
n n
und entsprechend b = bL + b H g 2 . Nun gilt a · b = u + vg 2 + wgn mit

u = a L bL , v = a L b H + a H b L = u + w ’ (a L ’ a H )(bL ’ b H ), w = a H bH .

Zeigen Sie, dass diese Methode von Karatsuba-Ofman eine Komplexit¤t von
O(nlog2 3 ) hat.

4.4 Beweisen Sie den Fundamentalsatz der Arithmetik 4.14.

4.5 Zeigen Sie, dass die Relation algorithmisch ¤quivalent von Seite 64 eine „qui-
valenzrelation ist.

4.6 Zeigen Sie, dass Kollisionsresistenz die im Text so genannte schw¤chere Form
der Kollisionsresistenz impliziert.

4.7 Für eine Hashfunktion h : P ’ Z2 soll eine Kollision mithilfe des Ge-
n

burtstagsparadoxons (siehe Aufgabe 2.2) konstruiert werden. Man spricht von
der Geburtstags-Attacke.
Wie viele Versuche braucht man, um mit Wahrscheinlichkeit ≈ 1/2 eine Kollision
zu ¬nden, wenn n = 64, n = 128 und n = 160 ist?
5 Symmetrische Authenti¬kation

Bei den bisher behandelten kryptogra¬schen Verfahren lag das Augenmerk auf
der Vertraulichkeit. Es werden Texte zwischen Sender und Empf¤nger ausge-
tauscht, deren Inhalt für Dritte nicht erkennbar sein soll. Aber wie schon in Ab-
schnitt 3.4.1 bemerkt, ist schlichte Verschlüsselung kein Garant für Authentizit¤t
und schon gar nicht für Integrit¤t. Als anschauliches Beispiel dient ein Formular:
Durch Verschlüsselung kann zwar der Inhalt verschleiert werden, aber die Stelle,
an der eine wichtige Information (etwa ein Geldbetrag oder eine Kontonummer)
steht, ist einem Angreifer bekannt. Er kann also versuchen zu manipulieren, evtl.
ohne genau zu wissen, welchen Effekt der Eingriff hat. Authenti¬kation stellt zwei-
erlei sicher:

• Zum einen soll eine Nachricht nicht auf dem Weg vom Sender zum Emp-
f¤nger unbemerkt ver¤ndert werden können “ Stichwort Integrit¤t.

• Zum anderen soll es gewiss sein, dass eine erhaltene Nachricht wirklich
vom vorgeblichen Sender stammt “ Stichwort Authentizit¤t.

Wir besprechen in diesem Kapitel symmetrische Authenti¬kationssysteme. Hier-
bei ist zwischen den Teilnehmern ein vorheriger Schlüsselaustausch nötig. In Ka-
pitel 12 werden wir asymmetrische Systeme kennenlernen “ ein vorheriger Schlüs-
selaustausch erübrigt sich dann.
Beim sogenannten MAC, das ein sehr weit verbreitetes symmetrisches Authenti-
¬kationssystem ist, wird zu einem Text N eine Prüfsumme S erzeugt. Der Sender
schickt das Paar (N , S) an den Empf¤nger, und dieser prüft mithilfe des gehei-
men Schlüssels k, ob die Nachricht N auf dem Weg verf¤lscht worden ist und ob
sie tats¤chlich vom vorgeblichen Sender stammt.
Der Satz von Gilbert-Williams-Sloane besagt, dass bei jedem Authenti¬kationssys-
tem die Betrugswahrscheinlichkeit p größer gleich 1/ |K| ist, wobei K die Schlüs-
selmenge des Systems ist. Wir werden ein Authenti¬kationssystem perfekt nen-
nen, falls die Betrugswahrscheinlichkeit p so klein wie möglich ist.
Um schließlich perfekte Authenti¬kationssysteme angeben zu können, machen
wir einen kleinen Aus¬‚ug in die Geometrie. Die perfekten Authenti¬kationssys-
teme lassen sich n¤mlich geometrisch als sogenannte Netze charakterisieren.


5.1 Message Authentication Code

Symmetrische Authenti¬kation wird in der Praxis fast ausschließlich mit Messa-
ge Authentication Codes, kurz MAC, durchgeführt.
82 5 Symmetrische Authenti¬kation

5.1.1 Das Prinzip des MAC

Die Idee ist einfach: Gegeben seien Mengen P, K und S und eine Abbildung

± : P—K ’ S.

Dann ist
(P, P — S, K, f ) mit f (x, k) := (x, ±(x, k))
ein Kryptosystem, da die Abbildung f k = f ( . , k) : P ’ P — S offenbar injektiv
ist “ vgl. die De¬nition auf Seite 9.
Von der Abbildung ± verlangen wir noch zweierlei:
Für k = k aus K gelte stets ±k = ±k .

Für jedes k ∈ K sei ±k eine kollisionsresistente Hashfunktion (hier ist impli-

zit vorausgesetzt, dass |S| < |P|).
Sender und Empf¤nger gehen nun wie folgt vor:
Vor der Kommunikation einigen sie sich auf den gemeinsamen, geheimen
Schlüssel k ∈ K.
Um den Klartext N ∈ P zu authenti¬zieren, berechnet der Sender den Wert
S := ±(N , k), den eigentlichen MAC, und verschickt f (N , k) = (N , S).
Der Empf¤nger erh¤lt (N , S ) und überprüft mit seinem Schlüssel k, ob die
Bedingung
±(N , k) = S
erfüllt ist.
Ist diese Bedingung erfüllt, so nennt man die Nachricht (N , S ) gültig, sonst
ungültig “ unabh¤ngig davon, ob (N , S ) gleich (N , S) ist oder nicht. Folglich
kann (N , S) auf dem Weg zum Empf¤nger manipuliert worden sein und den-
noch erkennt der Empf¤nger das erhaltene (N , S ) als gültig an.
Bei einer gültigen Nachricht sind im folgenden Sinne Integrit¤t und Authentizi-
t¤t sichergestellt: Die Authentizit¤t wird dadurch gew¤hrleistet, dass außer dem
Empf¤nger nur der Sender den vereinbarten Schlüssel kennt. Die Integrit¤t be-
ruht wesentlich auf der Kollisionsresistenz der Hashfunktion ±k ; diese stellt si-
cher, dass es nicht möglich ist, zu einem gültigen S eine weitere Nachricht N zu
¬nden, für die (N , S) als gültig akzeptiert wird.
Man erkennt, dass das geschilderte Verfahren so keinerlei Geheimhaltung bietet.
Der Klartext N wird unverschlüsselt vom Sender an den Empf¤nger übermit-
telt. Wir werden daher in diesem Kapitel nicht vom Geheimtext, sondern von der
Nachricht sprechen. Beim MAC ist die Nachricht f (N , k) = (N , S).
Wir können aber auch Geheimhaltung erreichen. Dazu verschlüssele man den
Klartext N vor oder nach der Anwendung von ± mit einem symmetrischen Ver-
fahren. Folglich können wir N als Klartext oder auch als verschlüsselten Text
5.1 Message Authentication Code 83

auffassen, je nachdem, ob eine Verschlüsselung stattgefunden hat oder nicht. Um
Verwirrung zu vermeiden, sprechen wir in diesem Kapitel bei N nicht von einem
Klartext, sondern von einem Datensatz.

Bemerkung
Nicht nur das System wird MAC genannt, auch der Wert S = ±(N , k) wird oft
als MAC bezeichnet.


5.1.2 Ein Beispiel und Varianten
Der vom NIST standardisierte CMAC ist von der Bauart wie im folgenden Bei-
spiel beschrieben.

Beispiel
Es sei (An , An , K, f ) eine symmetrische Blockchiffre über dem Alphabet A der
Blockl¤nge n wie etwa AES. Die Kommunikationspartner w¤hlen einen gemein-
samen, geheimen Schlüssel k ∈ K. Auf einen Datensatz N ∈ A— , wobei A— die
Halbgruppe der Strings über dem Alphabet A bezeichnet, beliebiger L¤nge wen-
den sie den CBC-Modus aus Abschnitt 3.4.2 mit Initialisierungsblock C0 an. Sie
zerlegen also N in Wörter Ni ∈ An , i ∈ {1, . . . , r}, der L¤nge n, sodass gilt
N = N1 N2 · · · Nr . Das letzte Wort muss evtl. durch Padding aufgefüllt werden.
Dann wird rekursiv gerechnet:

Ci := f (Ni + Ci’1 , k) für i ∈ {1, . . . , r} .

Die Abbildung ± ist durch ±(N , k) := Cr de¬niert. Soll der MAC eine L¤nge
kleiner als n haben, wird einfach abgeschnitten.
In der Praxis wird h¤u¬g C0 = 0 gew¤hlt und das letzte Wort Nr des Datensatzes
maskiert, d. h., es gibt einen weiteren geheimen Schlüssel (der oft aus k gewonnen
wird), mit dem Nr vor der Anwendung von f verschlüsselt wird.

Benutzt man AES als unterliegende Blockchiffre, so betr¤gt die maximale L¤n-
ge eines MAC 128 Bit. Das scheint den Angaben aus Abschnitt 4.4.2 auf S. 78
zu widersprechen. Dort hatten wir festgehalten, dass ein Hashwert mindestens
die L¤nge 160 haben sollte, um Kollisionsresistenz sicherzustellen. Im gegebenen
Kontext können wir aber mit kleineren Werten auskommen, weil die Kommuni-
kationspartner ja den Schlüssel wechseln können.
In der Praxis legen die Kommunikationspartner fest, welche Anzahl von ungülti-
gen Nachrichten sie tolerieren wollen, bis sie einen neuen Schlüssel austauschen.
Der Erhalt einer ungültigen Nachricht wird dabei als Betrugsversuch ausgelegt.

Bemerkung
Das NIST hat neben CMAC noch zwei weitere Betriebsmodi zur Authenti¬kation
standardisiert “ CCM und GCM. Diese beiden Verfahren gew¤hrleisten außer
Authenti¬kation auch noch Geheimhaltung.
84 5 Symmetrische Authenti¬kation

5.2 Der Satz von Gilbert-MacWilliams-Sloane
Wie im obigen Beispiel gezeigt wurde, kann jedes Kryptosystem auch zur Au-
thenti¬kation eingesetzt werden. Wir nennen ein Kryptosystem (P, C, K, f ), das
zu diesem Zweck eingesetzt wird, ein Authenti¬kationssystem.

Bemerkung
Bei einem Kryptosystem muss es schwierig sein, x aus f (x, k) zu bestimmen. Bei
einem Authenti¬kationssystem hingegen muss es schwierig sein, f (x, k) zu be-
stimmen. Immer vorausgesetzt, dass man den Schlüssel k nicht kennt.

Ist (P, C, K, f ) ein Authenti¬kationssystem, so betrachten wir für einen Geheimtext
c ∈ C die Menge K(c) aller Schlüssel, für die es einen Klartext x ∈ P gibt, sodass
x mit k verschlüsselt gerade c ergibt:

K(c) := {k ∈ K ; ∃ x ∈ P : f (x, k) = c} .

Ein Authenti¬kationssystem (P, C, K, f ) heißt kartesisch, wenn für jedes c ∈ C
gilt
f ’1 (c) = {x} — K(c) mit x ∈ P .

Das bedeutet, dass es zu jedem c ∈ C genau ein x ∈ P gibt mit f (x, k) = c für
eine Auswahl von k ∈ K. Das de¬niert eine Abbildung:

fˆ : C ’ P , c ’ x ,

wobei x das eben zu c erkl¤rte, eindeutig bestimmte Element ist.

Beispiel
Bei einem MAC gilt
c = f (x, k) = (x, ±(x, k)) ,

sodass jeder MAC kartesisch ist. Die Abbildung fˆ ist einfach die Projektion auf
die erste Koordinate.

Es seien P := {a, b}, K := {1, . . . , 6} und C := {m1 , m2 , m3 }. Untenstehen-
de Tabelle beschreibt f : P — K ’ C. Ist der benutzte Schlüssel k und soll
x ∈ P gesendet werden, so muss in der Spalte k nach x gesucht werden.
Die Zeilennummer m j ist die zu senden-
de Nachricht, f (x, k) = m j . Die Tabelle
123456
zeigt sofort, dass ein Authenti¬kationssys-
m1 a b a b - -
tem vorliegt, denn für jedes k ∈ K ist die
m2 b a - - a b
Abbildung f k := f ( . , k) : P ’ C injek-
m3 - - b a b a
tiv. Dieses System ist nicht kartesisch. Vgl.
dazu Aufgabe 5.1.
5.2 Der Satz von Gilbert-MacWilliams-Sloane 85

5.2.1 Möglichkeiten zum Betrug
Gegeben ist ein Authenti¬kationssystem (P, K, C, f ). Die Betrugswahrschein-
lichkeit p ist die Wahrscheinlichkeit, mit der ein Angreifer eine als gültig an-
zuerkennende Nachricht einspielen kann. Wir unterscheiden zwei Typen von Be-
trugsversuchen, die einem Angreifer zur Verfügung stehen.
• Substitution: Eine Nachricht wird abgefangen und durch eine eigene er-
setzt.

• Impersonation: Eine eigene Nachricht wird eingespielt.
Natürlich gilt für die Betrugswahrscheinlichkeit p ≥ |K| , weil ein Angreifer ver-
1

suchen kann, den Schlüssel zu erraten. Tats¤chlich ist die Situation viel schlechter.
Das ist der Inhalt des folgenden Satzes.
Satz 5.1 (Gilbert, MacWilliams, Sloane)
Es sei (P, C, K, f ) ein (nicht notwendig kartesisches) Anthenti¬kationssystem mit gleich-
verteilter Schlüsselwahl. Für die Betrugswahrscheinlichkeit p gilt
1
p≥ .
|K|

Beweis. Bei der Impersonation hat der Angreifer mit der Nachricht c ∈ C Erfolg,
wenn der benutzte Schlüssel in K(c) liegt. Für die Betrugswahrscheinlichkeit gilt
demnach für jedes c ∈ C:
|K(c)|
p≥ .
|K|
Bei der Substitution sei c ∈ C die beobachtete gültige Nachricht. Daher muss der
Schlüssel in K(c) liegen, und wir erhalten die Absch¤tzung
1
p≥ .
|K(c)|
Wir kombinieren die beiden Resultate zu
|K(c)| 1 1
p2 ≥ · = ,
|K| |K(c)| |K|
und der Satz ist bewiesen.
Ein Authenti¬kationssystem (P, K, C, f ) heißt perfekt, wenn die Betrugswahr-
scheinlichkeit p minimal ist, d. h. wenn p = 1/ |K|.
Bevor wir Beispiele von perfekten Authenti¬kationssystemen angeben, ziehen
wir aus dem Beweis des Satzes von Gilbert, MacWilliams und Sloane einige Fol-
gerungen.
Korollar 5.2
In einem perfekten, kartesischen Authenti¬kationssystem (P, C, K, f ) gilt:
86 5 Symmetrische Authenti¬kation

(a) Für alle c ∈ C ist |K(c)| = |K|.
(b) Für alle x ∈ P gilt | f ({x} — K)| = |K|.
(c) Für c, c ∈ C mit c = c gilt
falls fˆ(c) = fˆ(c )
0,
K(c) © K(c ) =
falls fˆ(c) = fˆ(c ).
1,

Beweis. (a) Es sei c ∈ C. W¤re |K(c)| > |K|, so folgte
|K(c)| 1
= p,
>
|K| |K|
und eine Impersonation mit c w¤re mit größerer Wahrscheinlichkeit erfolgreich,
als vorausgesetzt.
W¤re |K(c)| < |K|, so folgte
1 1
> = p,
|K(c)| |K|
und eine Substitution bei beobachtetem c w¤re mit größerer Wahrscheinlichkeit
erfolgreich, als angenommen. Daher muss Gleichheit gelten.
(b) Mit (a) gilt
|K|
| f ({x} — K)| = |K| für alle c ∈ C mit fˆ(c) = x ,
=
|K(c)|
denn je |K(c)| Elemente von K werden auf ein c abgebildet.
(c) Es seien x = fˆ(c) und x = fˆ(c ). Im Fall x = x erh¤lt man wegen f ’1 (c) ©
f ’1 (c ) = … und weil das System kartesisch ist sofort die Behauptung.
Es sei nun x = x . Der Fall m := |K(c) © K(c )| > 1 würde einen Substitutionsan-
griff mit
1
m
p≥ >
|K(c)| |K|
ermöglichen “ ein Widerspruch zur Voraussetzung. Daher gilt m ¤ 1. Die Abbil-
dung
K(c) ’ C , k ’ f (x , k)
ist injektiv. Ansonsten g¤be es zwei k1 , k2 ∈ K(c) mit c := f (x , k1 ) = f (x , k2 ),
und es würde k i ∈ K(c) © K(c ) folgen, mit einem Widerspruch wie eben. Mit (b)
folgt:
f ({x } — K(c)) = |K(c)| = |K| = f ({x } — K) ,
und somit f ({x } — K(c)) = f ({x } — K). Das bedeutet K(c) © K(c ) = …, also
m = 1.

Bemerkung
Die Vereinfachungen der Beweise in diesem Abschnitt verdanken wir Herrn Bert-
ram Poettering.
5.3 Beweisbar perfekte Systeme * 87

5.3 Beweisbar perfekte Systeme *
Um Beispiele für perfekte Authentikationssysteme angeben zu können, holen wir
etwas aus. Wir führen den Begriff der af¬nen Ebene eine, den wir auch in Kapitel 13
noch brauchen werden.

5.3.1 De¬nition af¬ner Ebenen
Es sei A eine Menge, und G sei eine Menge von Teilmengen von A, d. h. G ⊆
Pot(A). Das Paar (A, G) heißt af¬ne Ebene, falls |G| ≥ 2 für alle G ∈ G und die
folgenden drei Bedingungen erfüllt sind:
(A1) Zu je zwei Elementen a, b ∈ A mit a = b existiert genau ein G ∈ G mit
a, b ∈ G; wir schreiben a, b für dieses G.

(A2) (Parallelenaxiom) Zu G ∈ G und a ∈ A \ G existiert genau ein G ∈ G mit
a ∈ G und G © G = ….

(A3) Es gibt drei Punkte a, b, c ∈ A mit c ∈ a, b.
Die Menge A nennt man die Punktmenge und die Menge G die Geradenmenge
der af¬nen Ebene (A, G). Wir benutzen für a ∈ G für ein G ∈ G geometrische
Sprechweisen wie der Punkt a liegt auf der Geraden G oder die Gerade G geht durch
den Punkt a usw.

5.3.2 Die af¬ne Ebene AG(2, F)

Es sei F2 der (gewöhnliche) zweidimensionale F-Vektorraum über dem Körper
F. Wir setzen A := F2 und

G := a + F b ; a, b ∈ F2 , b = 0 .

Dabei ist F b := {» b ; » ∈ F} der von b erzeugte Untervektorraum von F2 .
Für F = R ist (A, G) schlicht die Anschauungsebene mit Punkten und Geraden
in der üblichen Interpretation. Man beachte, dass auch in (A, G) die Geraden Ne-
benklassen von Untervektorr¤umen in F2 sind, wie man das von der Anschau-
ungsebene kennt.
Für F = R scheint es klar zu sein, dass (A, G) eine af¬ne Ebene ist, wir zeigen
dass dies für ein beliebiges F erfüllt ist “ mit den bisherigen Bezeichnungen gilt:

Lemma 5.3
Es ist (A, G) eine af¬ne Ebene.

Beweis. (A1) Es seien a, b ∈ A mit a = b gegeben. Dann ist G = a + F (b ’ a) ∈ G,
und wegen 0, 1 ∈ F gilt a, b ∈ G. Es sei H = c + F d eine weitere Gerade, die a
und b enth¤lt, etwa a = c + » d, b = c + μ d mit », μ ∈ F. Dann gilt zum einen
b ’ a ∈ F d, also F (b ’ a) = F d, und zum anderen a + F d = c + F d. Wir fassen
zusammen: H = a + F (b ’ a) = G = a, b.
88 5 Symmetrische Authenti¬kation

<<

. 3
( 9)



>>