<< . .

. 10
( : 33)



. . >>


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

<< . .

. 10
( : 33)



. . >>