<< . .

. 22
( : 33)



. . >>

Rabin-Verfahrens genauso schwierig ist wie das Faktorisieren von n. Beim RSA-
Verfahren ist dies nicht bekannt.


9.1 Der Dif¬e-Hellman-Schlüsselaustausch
Es sei p eine Primzahl. Wir beschreiben den Dif¬e-Hellman-Schlüsselaustausch in
der multiplikativen zyklischen Gruppe Z — der Ordnung p ’ 1 (siehe Satz 6.12).
p
168 9 Die Verfahren von Dif¬e und Hellman, ElGamal und Rabin

Jedes erzeugende Element der Gruppe Z — wird eine Primitivwurzel modulo p
p
— genau •(p ’ 1) Primitivwurzeln mo-
genannt. Nach Korollar 6.3 (b) besitzt Z p
dulo p, dabei bezeichnet • die Euler™sche •-Funktion.

Beispiel

Es ist 2 eine Primitivwurzel modulo 13, d. h. 2 = Z13 , da o(2) = 12:

k 1 2 3 4 5 6 7 8 9 10 11 12
k
2 2 4 8 3 6 12 11 9 5 10 7 1

Wegen Korollar 6.3 (a) sind die •(12) = 4 Primitivwurzeln modulo 13 die vier
1 5 7 11
Elemente 2 = 2, 2 = 6, 2 = 11, 2 = 7.


9.1.1 Der Schlüsselaustausch nach Dif¬e-Hellman
Beim Dif¬e-Hellman-Schlüsselaustausch wird ein (geheimer) Schlüssel über
einen öffentlichen, nicht gesicherten Kanal ausgetauscht, um dann mit einem
symmetrischen Verfahren zu kommunizieren. Eine abstrakte Version des Verfah-
rens wurde als Anwendung auf Seite 77 dargestellt.
ga

"
unsichere Leitung
Db H@
@@
˜˜ (p, g)
@@
˜˜ @@
˜˜
˜˜ gb
g ab g ab
Im hiesigen Kontext funktioniert das Verfahren so:

D und H einigen sich auf eine Primzahl p und eine Primitivwurzel g modulo
p : Es ist (p, g) öffentlich bekannt.

D w¤hlt ein a ∈ {2, . . . , p ’ 2}, bestimmt g a ∈ Z — und sendet A := g a an H
p
(der Exponent a bleibt geheim).

H w¤hlt ein b ∈ {2 , . . . , p ’ 2}, bestimmt gb ∈ Z — und sendet B := gb an D
p
(der Exponent b bleibt geheim).

D berechnet B a = g ab , H berechnet Ab = g ab .

Es haben dann D und H beide den geheimen Schlüssel g ab , obwohl g ab selbst
nicht über den unsicheren Kanal ausgetauscht wurde. Entscheidend ist die ein-
fache Tatsache, dass g ab = gba gilt. Vergleiche auch dazu die Anwendung auf
Seite 77. Der geheime Schlüssel kann nun etwa dazu dienen, um mit einem sym-
metrischen Verfahren zu kommunizieren.
9.1 Der Dif¬e-Hellman-Schlüsselaustausch 169

Beispiel
Es sei p = 17. Es ist 3 eine Primitivwurzel modulo 17.
7
7
D w¤hlt a = 7 ’ 3 = 11 =4
13
.
Austausch
4 4
H w¤hlt b = 4 ’ 3 = 13 =4
11

D und H haben beide den geheimen Schlüssel 4.

Bemerkung

Bei diesem Beispiel mit g = 3 ∈ Z17 kann ein Angreifer natürlich sofort g ab aus
g a und gb ermitteln. Es sind 7 = Logg (11) und 4 = Logg (13) leicht zu bestimmen,
folglich ist g28 = 4 der geheime Schlüssel. In der Praxis ist p so zu w¤hlen, dass
das diskrete Logarithmenproblem (vgl. Abschnitt 6.2.3) schwierig zu lösen ist.


9.1.2 Das Dif¬e-Hellman-Problem
Ein Angreifer, der den Schlüsselaustausch beobachtet, kennt die Größen

p , g , g a , gb , aber nicht a , b , g ab .

Das Dif¬e-Hellman-Problem lautet wie folgt:
Berechne g ab aus den Größen g, g a und gb .
Kann man das diskrete Logarithmenproblem lösen, so kann man auch das Dif¬e-
Hellman-Problem lösen. Man bestimme die diskreten Logarithmen a und b aus
den Gleichungen c = g a und d = gb und dann g ab mittels der dann bekann-
ten Größen g, a, b. Es ist bisher unbekannt, ob man das Dif¬e-Hellman-Problem
lösen kann, ohne diskrete Logarithmen berechnen zu können.

9.1.3 Der Mann in der Mitte
Wir beschreiben einen möglichen Angriff auf das eben geschilderte Verfahren von
Dif¬e und Hellman “ der Mann in der Mitte.
Die Teilnehmer D und H haben sich über einen unsicheren Kanal auf die Größen
p und g geeinigt. Ein Angreifer M kann also das Paar (p, g) beobachten. Noch
vor dem Austausch weiterer Größen zwischen D und H stellt sich M zwischen
die ahnungslosen D und H und geht dann wie folgt vor:

M f¤ngt g a von D ab und leitet ein g a mit einem nur ihm bekannten a an H
weiter (H denkt, g a kommt von D).

M f¤ngt gb von H ab und leitet ein gb mit einem nur ihm bekannten b an D
weiter (D denkt, gb kommt von H).

D bildet mit seinem a den vermeintlich geheimen Schlüssel gb a .
170 9 Die Verfahren von Dif¬e und Hellman, ElGamal und Rabin

H bildet mit seinem b den vermeintlich geheimen Schlüssel g a b .

Weil M sowohl g a als auch gb als auch die Größen a , b kennt, kann M eben-
falls die Schlüssel gb a und g a b bilden.

M kann und muss jeden Geheimtext von D mit gb a entschlüsseln, und mit g a b
wieder verschlüsselt an H weiterreichen. Analog verf¤hrt er mit Nachrichten
von H an D.
Wenn dem Mann M in der Mitte ein Text entgeht, so ¬‚iegt er wahrscheinlich auf.
ga ga

 
M
DW HA
W AA
}}
} AA
}} AA
˜}} gb
gb
gb a ga b
Bemerkung
Varianten dieses Angriffs sind eine Bedrohung für jedes Verfahren der asymme-
trischen Kryptogra¬e. Schwachstelle ist die Übergabe des öffentlichen Schlüssels.
Wenn sich hier jemand dazwischen schalten kann, ist die gesamte Kommunika-
tion ungesichert. Für dieses Problem ist keine mathematische Lösung bekannt
(vielleicht auch gar nicht möglich). Es ist nur durch besondere Sorgfalt der Be-
nutzer einzud¤mmen.

9.1.4 Weitere Gruppen für das Dif¬e-Hellman-Verfahren
Das Dif¬e-Hellman-Verfahren kann offenbar in jeder endlichen zyklischen Grup-
pe G = g implementiert werden. Um Ef¬zienz und Sicherheit zu gew¤hrleisten,
sind solche Gruppen zu w¤hlen, in denen die Gruppenoperationen leicht durch-
führbar sind, das diskrete Logarithmenproblem (eigentlich das Dif¬e-Hellman-
Problem) aber schwer zu lösen ist. Günstige Gruppen sind die bereits benutzten
zyklischen Gruppen
Z — mit einer Primzahl p und
• p

• zyklische Untergruppen von elliptischen Kurven (diese werden wir in Ka-
pitel 13 behandeln).
Ungünstig sind die (additiven) zyklischen Gruppen
Z n mit n ∈ N.

In der additiven zyklischen Gruppe Z n ist das Berechnen diskreter Logarithmen
ef¬zient möglich. Wir begründen das. Man beachte zuerst, dass Potenzen wegen
der additiven Schreibweise zu Vielfachen werden. Nach Korollar 6.3 (a) gilt:

g = Z n ” ggT(g, n) = 1 .
9.2 Das ElGamal-Verschlüsselungsverfahren 171

Aus der Kenntnis von g und c = a · g kann leicht der diskrete Logarithmus a =
Logg c berechnet werden. Es ist hierzu nur die Kongruenzgleichung:

X g ≡ c (mod n)
zu lösen. Dies ist mit mithilfe des euklidischen Algorithmus aus Satz 4.10 ef¬zient
machbar: Man bestimme Zahlen x, y ∈ Z mit
1 = ggT(g, n) = x g + y n .
Es gilt dann c = (x c) g + y c n, also a g ≡ c (mod n) mit a := x c. Folglich ist nur
die ganze Zahl x zu bestimmen, um den diskreten Logarithmus a zu erhalten.
Wegen ggT(g, n) = 1 ist a + nZ nach Korollar 4.19 die Menge aller Lösungen.

Bemerkung
Man erkennt hier, dass es nicht die Struktur der Gruppe ist, die das DLP schwie-
rig macht “ alle zyklischen Gruppen derselben Ordnung sind isomorph. Es ist
vielmehr die Art der Beschreibung, die das bewirkt.

9.2 Das ElGamal-Verschlüsselungsverfahren
Das ElGamal-Verfahren ist verwandt mit dem Dif¬e-Hellman-Verfahren. Aber es
ist ein asymmetrisches Verschlüsselungsverfahren und kein Schlüsselaustausch.
Es gibt einen öffentlichen Schlüssel (p, g, A) und einen geheimen Schlüssel a.
Wir schildern die Funktionsweise.
C=(B, c)

!
G E
(p, g, A)


9.2.1 Schlüsselerzeugung
Gegeben seien eine Primzahl p, eine Primitivwurzel g modulo p und ein festes
a ∈ {2, . . . , p ’ 2}. Wir setzen A := g a . Beim ElGamal-Verschlüsselungsver-
fahren sind
(p, g, A) der öffentliche Schlüssel;

a (das a mit A = g a ) der geheime Schlüssel des Empf¤ngers E.


9.2.2 Verschlüsselung
Der Sender G sendet an E eine verschlüsselte Nachricht. Dazu besorgt sich G den
öffentlichen Schlüssel (p, g, A) von E. Es sei N ∈ Z — der Klartext.
p
G w¤hlt zuf¤llig eine Zahl b ∈ {2, . . . , p ’ 2}.
G berechnet B := gb ∈ Z — und c := Ab N ∈ Z — .
p p

G sendet den Geheimtext C = (B, c) an E.
172 9 Die Verfahren von Dif¬e und Hellman, ElGamal und Rabin

9.2.3 Entschlüsselung
Erh¤lt der Empf¤nger E vom Sender G den Geheimtext C = (B, c), so berechnet
er mit seinem geheimen Schlüssel a das Element B’a c. Es gilt n¤mlich wegen
B = gb , c = Ab N und A = g a :

B’a c = g’a b Ab N = g’a b g a b N = N ,

und damit erh¤lt E den Klartext N ∈ Z — zurück.
p

Beispiel
Es sei p = 17. Das Element g = 3 ist eine Primitivwurzel modulo 17. Der Empf¤n-
ger E w¤hlt als geheimen Schlüssel a = 3 und hat somit den öffentlichen Schlüssel
(17, 3, 10).

Der Sender G verschlüsselt den Klartext 5 ∈ Z17 . Er w¤hlt b = 2 und erh¤lt den
Geheimtext (B, c) = (9, 7), den er an E sendet.
’3 —
Der Empf¤nger E erh¤lt nun wegen 9 = 8 in Z17 durch Berechnen von
’3
·7 = 8·7 = 5
9

den Klartext 5 zurück.

Man kann das ElGamal-Verfahren auf beliebige endliche zyklische Gruppen
G = g verallgemeinern. Wir werden das Verfahren in Kapitel 14 für zyklische
Untergruppen von elliptischen Kurven erneut schildern.

9.2.4 Zur Sicherheit des ElGamal-Verfahrens
Wir versetzen uns in die Situation eines Angreifers: Ein Angreifer, der den Aus-
tausch einer verschlüsselten Nachricht beobachtet, kennt die Größen

g , g a , gb , c = g a b N .

Kann der Angreifer A das Dif¬e-Hellman-Problem lösen, d. h., A kann aus g,
g a und gb das Element g a b bestimmen, so kann er auch das ElGamal-Verfahren
brechen. Er berechnet N = g’ab c. Kann andererseits A das ElGamal-Verfahren
brechen, d. h., A kann N aus der Gleichung c = g a b N bestimmen, so kann er
auch das Dif¬e-Hellman-Problem lösen. Er berechnet g a b = N ’1 c . Damit ist
gezeigt: Das Brechen des ElGamal-Verfahrens ist algorithmisch ¤quivalent zum
Lösen des Dif¬e-Hellman-Problems.
Das Dif¬e-Hellman-Problem kann gelöst werden, wenn man diskrete Logarith-
men berechnen kann. Um gegen die bekannten Algorithmen zum Berechnen
der diskreten Logarithmen gewappnet zu sein, sollte die Primzahl, die beim
ElGamal-Verfahren in Z — benutzt wird, etwa von der Größenordnung 1 024 Bit
p
sein. Wir werden in Kapitel 10 Algorithmen zum Berechnen diskreter Logarith-
men besprechen.
9.3 Das Rabin-Verschlüsselungsverfahren * 173

Bemerkung
Durch die Tatsache, dass die Primzahl p beim ElGamal-Verfahren in Z — etwa von
p
der Größenordnung von n beim RSA-Verfahren ist, ist das ElGamal-Verfahren in
Z — aufw¤ndiger als das RSA-Verfahren, da B = gb und c = Ab N zu berechnen
p
sind. Beim RSA-Verfahren ist hingegen nur N e zu berechnen. Implementiert man
aber das Verfahren von ElGamal auf einer elliptischen Kurve, wobei man etwa
die gleichen Sicherheitsanforderungen stellt, so ist ElGamal sogar ef¬zienter als
RSA, weil man mit deutlich kleineren Parametern auskommt.


9.2.5 Ein Angriff
Wird der Exponent b, den der Sender zum Chiffrieren seiner Nachricht N be-
nutzt, mehrfach zur Verschlüsselung von Nachrichten verwendet, so kann ein
Klartext durch einen Known-Plain-Text-Angriff ermittelt werden. Einem Angreifer
A ist ein zusammengehöriges Klartext-Geheimtext-Paar (N , C) bekannt. Folglich
kennt A auch das Element c = Ab N . Damit kann A aus einem weiteren Ge-
heimtext C = (B, c ), der mit demselben b erzeugt wurde, den dazugehörigen
Klartext N aus c = Ab N ermitteln; er berechnet dazu:

c’1 N c = A’b N ’1 N Ab N = N .

Folglich kann N aus c, c und N ermittelt werden. Es ist also bei jedem Durch-
gang ein neues b aus der Menge {2, . . . , p ’ 2} zu w¤hlen. Das hat einen wei-
teren Vorteil: Man kann zweimal denselben Klartext verschicken, ohne dass ein
Angreifer das merkt. Die Geheimtexte sind verschieden.

9.3 Das Rabin-Verschlüsselungsverfahren *
Das Problem, eine natürliche Zahl in ein Produkt von Primzahlen zu faktorisie-
ren, wird als außerordentlich schwierig angesehen. Ist n ein Produkt von zwei
Primzahlen p und q der Größenordnung 512 Bit, wie sie beim RSA-Verfahren
verwendet werden, so braucht ein moderner Rechner unvertretbar lange Zeit, um
die Primzahlen p und q zu ermitteln. Wir werden moderne und ef¬ziente Faktori-
sierungsalgorithmen in Kapitel 11 vorstellen. Es ist aber offen, ob nicht bereits in
n¤chster Zukunft ein Verfahren entdeckt wird, mittels dessen die Faktorisierung
deutlich ef¬zienter möglich ist.
Das Verfahren von Rabin ist ein Public-Key-Verfahren mit einem öffentlichen
Schlüssel n, der ein Produkt zweier Primzahlen ist. Das Verfahren zu brechen
ist algorithmisch ¤quivalent zur Faktorisierung der Zahl n.


9.3.1 Quadratwurzeln modulo n

Es sei n ∈ N. Ein Element b ∈ Z — heißt eine Quadratwurzel modulo n von
n
2
a ∈ Z — , falls b = a; das Element a nennt man dann ein Quadrat modulo n.
n
174 9 Die Verfahren von Dif¬e und Hellman, ElGamal und Rabin

Beispiel

In Z15 = {1, 2, 4, 7, 8, 11, 13, 14} sind die Elemente 1 und 4 die Quadrate. Das
Element 1 hat die Quadratwurzeln 1, 4, 11, 14 und das Element 4 die Quadrat-
wurzeln 2, 7, 8, 13.

Es ist kein Zufall, dass jedes Quadrat in Z15 genau vier Wurzeln hat.

Lemma 9.1
Es sei n = p1 · · · pt mit verschiedenen ungeraden Primzahlen p1 , . . . , pt . Ein Element
a ∈ Z — besitzt keine oder genau 2t Quadratwurzeln.
n

Beweis. Wegen Lemma 7.5 können wir Z — mit Z —1 — · · · — Z —t identi¬zieren. Ist
n p p
— — · · · — Z — eine Quadratwurzel von a = (a , . . . , a ), so
b = (b1 , . . . , bt ) ∈ Z p1 t
1
pt
ist offenbar jedes Element von W := {(±b1 , . . . , ±bt )} eine Quadratwurzel von
a. Ist nun c = (c1 , . . . , ct ) ∈ Z —1 — · · · — Z —t eine weitere Quadratwurzel von
p p
a = (a1 , . . . , at ), so ist ci eine Nullstelle des Polynoms X 2 ’ ai über dem Körper
Z pi für alle i = 1, . . . , t. Somit ist ci = ±bi für alle i = 1, . . . , t (siehe Satz 3.9), d. h.
c ∈ W. Damit ist W die Menge aller Quadratwurzeln, und es gilt |W| = 2t .

Bemerkung
Wie der Beweis zeigt, erh¤lt man die Quadratwurzeln b modulo n von a folgen-
dermaßen aus den Quadratwurzeln von ai modulo pi für i = 1, . . . , t:
Gegeben ist ein Element (b1 , . . . , bt ) ∈ W. Es gilt folglich bi ≡ ai (mod pi ) für
2

i = 1, . . . , t. Bestimme mit dem chinesischen Restsatz 7.4 ein Element b ∈ Z mit
b ≡ bi (mod pi ) für i = 1, . . . , t .
Es ist dann b eine Quadratwurzel von a modulo n.

Wir halten für sp¤tere Zwecke eine einfache Folgerung fest.

Korollar 9.2
Es sei n = p1 · · · pt mit verschiedenen ungeraden Primzahlen p1 , . . . , pt . Dann existie-
•(n)
ren genau 2t Quadrate in Z — . n

Beweis. Wir betrachten die Abbildung
Z— ’ Z—
n n
q: .
’a 2
a

Jedes Quadrat b ∈ Z — hat nach Lemma 9.1 genau 2t Quadratwurzeln, d. h.
n
|q’1 (b)| = 2t . Da Z — die disjunkte Vereinigung von Mengen der Form q’1 (b)
n
mit einem Quadrat b in Z — ist, erhalten wir für die Anzahl der Quadrate in Z — :
n n

|Z — | •(n)
|q(Z — )| = = t.
n
n
|q’1 (b)| 2
Das ist die Behauptung.
9.3 Das Rabin-Verschlüsselungsverfahren * 175

9.3.2 Quadratwurzeln modulo p ≡ 3 (mod 4)
2
Es sei p eine Primzahl kongruent 3 modulo 4. Ist a ein Quadrat in Z — , a = b
p
p+1
für ein b ∈ Z — , so gilt für das Element a ∈ Z — (wegen p ≡ 3 (mod 4) ist
4
p p
p+1
∈ N):
4
p+1 p’1 p’1
2 +1
p+1
=b =b =b b = ±b ,
2 2
a 4

p’1 p’1
) ¤ 2, d. h. b = ±1. Es folgt, dass
2 2
da nach dem Satz 6.9 (a) von Euler gilt o(b
das Element
p+1

<< . .

. 22
( : 33)



. . >>