<< . .

. 14
( : 33)



. . >>


Sind a und c Elemente einer Gruppe (G, ·), so nennt man die kleinste nichtnega-
tive Zahl e mit
c = ae
den diskreten Logarithmus (von c zur Basis a). Man schreibt dann e = Loga (c).

Bemerkung
Ist G = a zyklisch, so hat wegen G = {ak ; k ∈ Z} jedes Element von G einen
diskreten Logarithmus zur Basis a; in nicht zyklischen Gruppen ist das nicht für
alle Elemente der Fall.

Da die Bildung von Potenzen in der Komplexit¤tsklasse P liegt (vgl. Abschnitt 6.3),
ist das diskrete Logarithmusproblem in NP . Die naive Herangehensweise zur
Lösung des diskreten Logarithmenproblems, also die sukzessive Bestimmung
der Potenzen a1 , a2 , a3 , . . . und Vergleich von ai mit c in jedem Schritt, ist daher
exponentiell in log e und bei großem e nicht ef¬zient.
Man kennt aber ef¬zientere Methoden zur Bestimmung eines solchen diskreten
Logarithmus e. Wir werden solche Methoden in Kapitel 10 ausführlich bespre-
chen. Dennoch sind alle diese Methoden nicht polynomial.
Wir halten fest: Mit allen bekannten, allgemeinen Methoden ist es schwierig, die
Zahl e aus der Kenntnis von a und c zu bestimmen, wenn die Gruppenordnung
|G| einen hinreichend großen Primteiler besitzt (siehe Kapitel 10). W¤hlt man
beim Pohlig-Hellman-Verfahren in Gruppen der Form Z — Primzahlen von der
p
Größenordnung p ≥ 2 1024 , so ist man gegen die in Kapitel 10 zuammengestellten

Angriffe gefeit. Dabei muss sichergestellt sein, dass p ’ 1 einen großen Primteiler
besitzt.
p’1
In der Praxis w¤hlt man die Primzahl p oft so, dass 2 selbst eine Primzahl ist.
Primzahlen mit dieser Eigenschaft nennt man auch sichere Primzahlen; kleine
sichere Primzahlen sind 5, 7, 11, 23, 47. Große (sichere) Primzahlen zu ¬ndet ist
schwierig, mehr dazu in Kapitel 8.


6.2.4 Zur Wahl der Gruppe

Für praktische Zwecke bieten sich zwei mögliche Typen von Gruppen an, in de-
nen das Verfahren implementiert werden kann.
Für eine Primzahl p w¤hle man die multiplikative Gruppe G = Z — .
• p

Die Ordnung dieser Gruppe ist p ’ 1. Weil Klartexte und Geheimtexte Gruppen-
elemente, also letztlich natürliche Zahlen kleiner p sind, kann die Primzahl p
6.2 Das Pohlig-Hellman-Verfahren * 105

nach Known-Plain-Text-Angriffen eventuell erraten werden. Daher sollte p nicht
als Teil des geheimen Schlüssels aufgefasst werden.

• Für einen endlichen Körper w¤hle man als G eine elliptische Kurve “ siehe
Kapitel 13.

Die Ordnung dieser Gruppe l¤sst sich mit den bekannten Darstellungsformen
nicht verheimlichen. Geheim zu halten sind also auch hier nur die Schlüssel e
und d.
Nicht zu empfehlen ist

die additive Gruppe (Z n , +) der Ordnung n.


Bei einem Known-Plain-Text-Angriff ist dem Angreifer ein Paar (N , C) ∈ Z n — Z n
mit C = e N bekannt. Durch Lösen der Kongruenzgleichung (siehe Korollar 4.19)

a X ≡ c mod n , wobei a = N und c = C

kann der Schlüssel e und hieraus dann d bestimmt werden. Das ¤quivalente Pro-
blem in Z — ist deutlich schwieriger zu lösen.
p


Bemerkung
Tats¤chlich liegt es nur am euklidischen Algorithmus, der zur Lösung von Kon-
gruenzgleichungen benutzt wird, weshalb das diskrete Logarithmenproblem in
der additiven Gruppe (Z n , +) nicht schwierig ist. Für diese spezielle Gruppe exis-
tiert ein ef¬zienter Algorithmus.
Bemerkenswert ist die Tatsache, dass es von der Beschreibung der Gruppe und
nicht von der algebraischen Struktur abh¤ngt, ob ein spezieller Algorithmus
greift. So sind die Gruppen Z — und Z p’1 isomorph, aber der euklidische Al-
p
gorithmus kann nur in Z p’1 zur Lösung des diskreten Logarithmenproblems
genutzt werden.



6.2.5 Zusammenfassung und ein Beispiel

Der Sender P will an den Empf¤nger H eine verschlüsselte Nachricht C = N e
senden, die H entschlüsselt.
C=N e

"
P H


Schlüsselerzeugung.

P und H einigen sich auf eine Primzahl p.
106 6 Exponentiationschiffren

P w¤hlt eine Zahl e ∈ {2, . . . , p ’ 2} mit ggT(e, p ’ 1) = 1. Es ist e der ge-
meinsame, geheime Schlüssel von P und H.

H bestimmt d ∈ {2, . . . , p ’ 2} mit e d ≡ 1 (mod p ’ 1) mit dem euklidischen
Algorithmus.

Chiffrierung und Dechiffrierung einer Nachricht. Der Sender P verschlüsselt
seine Nachricht mit dem geheimen Schlüssel e und sendet diese an den Empf¤n-
ger H; H entschlüsselt die Nachricht mithilfe der Zahl d:

P stellt seine Nachricht als Element N ∈ Z — dar.
p

P bildet die Potenz C := N e mit dem geheimen Schlüssel e.

P sendet den Geheimtext C an H.

H erh¤lt C, berechnet die Potenz C d = N e d = N in Z — und erh¤lt so den
p
Klartext N .

Beispiel
Gegeben ist die Primzahl p = 257. Wegen ggT(29, 256) = 1 können wir e = 29
w¤hlen. Wir bestimmen d mit dem euklidischen Algorithmus:

256 = 8 · 29 + 24 1 = 5’4
29 = 1 · 24 + 5 = 5 · 5 ’ 24
24 = 4 · 5 + 4 = ’6 · 24 + 5 · 29
5 = 1·4+1. = 53 · 29 ’ 6 · 256 .
Damit ist d = 53.
Die Schlüsselerzeugung ist hiermit abgeschlossen. P hat den geheimen Schlüssel

e = 29 zum Verschlüsseln eines Klartextes N ∈ Z257 und H hat die (geheime)
Zahl d = 53 zum Entschlüsseln eines erhaltenen Geheimtextes.
Der Sender P verschlüsselt etwa den Klartext N = 3:
29
C=3 = 69 .

Der Empf¤nger H entschlüsselt den erhaltenen Geheimtext C = 69:
53
C d = 69 = 3.
Bereits dieses einfache Beispiel mit der kleinen Primzahl p = 257 verdeutlicht ein
Problem des Verfahrens “ die rechenaufw¤ndige Exponentiation. Im folgenden
Abschnitt zeigen wir, wie diese Aufgabe ef¬zient gelöst werden kann.

Bemerkung
Das RSA-Verschlüsselungsverfahren, das wir in Kapitel 7 ausführlich beschrei-
ben werden, ist eine Chiffre vom hier beschriebenen Exponentiationstyp. Dabei
6.3 Schnelle Exponentiation 107

kann die Gruppenordnung |G| der zugrunde liegenden Gruppe G geheim ge-
halten werden. Man kann dann den Schlüssel e zum Verschlüsseln einer Nach-
richt sogar öffentlich machen, ohne den (geheimen) Schlüssel d zum Entschlüs-
seln preiszugeben. Damit ist eines der großen Probleme beim Pohlig-Hellman-
Verfahren und allen anderen symmetrischen Verfahren ausger¤umt: der Schlüs-
selaustausch.


6.3 Schnelle Exponentiation

Beim Verfahren von Pohlig-Hellman (und bei vielen anderen kryptogra¬schen
Verfahren) muss man Potenzen in einer Gruppe G berechnen. Die Aufgabe lautet:
Für a ∈ G und n ∈ N bestimme an .
Der naheliegendste Ansatz der sukzessiven Multiplikation basiert auf der übli-
chen Rekursion für Potenzen:
an = a an’1 .
Dieser Ansatz benötigt n ’ 1 Gruppenoperationen, um an zu berechnen. Diese
Methode ist also exponentiell in der Anzahl log n der Bits von n. Die schnelle
Exponentiation basiert auf folgender Rekursion für Potenzen:
§
⎪ n2
⎨ a2 , falls n gerade,
a=
n
⎪ a n’1 2 a , falls n ungerade.
© 2



Ein dazu ¤quivalenter, iterativer Algorithmus benutzt die Bin¤rdarstellung von n.
In der englischsprachigen Literatur wird der Algorithmus aus naheliegenden
Gründen oft als square and multiply bezeichnet. Der Algorithmus benötigt nur die
Assoziativit¤t der Verknüpfung. Da der Algorithmus h¤u¬g in der multiplika-
tiven Halbgruppe von Ringen angewendet wird, formulieren wir ihn gleich für
diesen allgemeinen Fall.

Lemma 6.15
Es sei a ein Element einer Halbgruppe G, und eine Zahl n ∈ N sei in Bin¤rdarstellung
gegeben:
k
‘b2
n= k = log2 n , b ∈ {0, 1}.
mit
=0

Setze a0 := abk = a und ai := abk’i a2 , 1 ¤ i ¤ k. Dann gilt:
i’1

ak = an .
(i)

Zur Berechnung von an braucht man höchstens 2 k Multiplikationen. Der Algo-
(ii)
rithmus ist also linear (bezogen auf die Verknüpfung in G).
108 6 Exponentiationschiffren

Beweis. Wir begründen mit Induktion
i
2i’
ai = a‘ =0 bk’
(—) für i = 0, . . . , k .
0 0’
Wegen a0 = a = a‘ =0 bk 2 ist der Induktionsanfang klar. Die Behauptung gelte
für i ’ 1. Wir erhalten dann:
2
i’1 i
2i’1’ 2i’
a‘ =0 bk’ = a‘ =0 bk’
ai = abk’i a2 = abk’i ,
i’1


sodass die Gleichung (—) gezeigt ist.
Setzt man in der Gleichung (—) i = k, so folgt sofort die Behauptung in (i).
Die Behauptung in (ii) folgt ebenfalls, da bei der schrittweisen Berechnung von
a1 , . . . , ak = an jeweils höchstens zwei Gruppenoperationen durchgeführt wer-
den, eine Quadrierung und möglicherweise eine Multiplikation.

Im Mittel braucht man sogar nur 1.5 log2 (n) Gruppenoperationen. Der Algorith-
mus ist also linear mit kleinen Konstanten.

Beispiel

29
Der Sender P berechnet mit der schnellen Exponentiation 3 in Z257 wegen

e = 29 = 24 + 23 + 22 + 20 ,

also
b4 = 1, b3 = 1, b2 = 1, b1 = 0, b0 = 1

vorteilhaft durch Quadrieren und Multiplizieren. Es ist a = 3:

1
a0 = ab4 = 3 = 3 ,
1 2
a1 = ab3 · a2 = 3 · 3 = 27 ,
0
1 2
a2 = ab2 · a2 = 3 · 27 = 131 ,
1
0
a3 = ab1 · a2 = 3 · 131 = 199 ,
2
2
1
a4 = ab0 · a2 = 3 · 199 = 69 .
3

Es werden dabei 7 Gruppenoperationen durchgeführt, wir fassen diese zusam-
men:
⎛ ⎞2
2
2
12
=⎝ ·3 ⎠ ·3 .
29 1 1 0 1
·3 ·3
3 3

0
Man beachte, dass die Operation ·3 , dies entspricht einer Multiplikation mit 1,
nicht ausgeführt wird.
6.3 Schnelle Exponentiation 109

Ein Angreifer kann durch Beobachtung des Stromverbrauchs (oder anderer phy-
sikalischer Größen) einer Maschine evtl. auf die Bin¤rdarstellung der Zahl e
29
schließen. Das ist an der hervorgehobenen Formel für 3 gut zu erkennen. Liegt
eine 0 vor braucht es eine Operation, liegt eine 1 vor, braucht es zwei.
Einen solchen Angriff nennt man Seitenkanalangriff. Man sollte dies bei der Im-
plementierung des Algorithmus beachten.

Bemerkung
Ist a invertierbar, so kann man auch an für n ∈ Z, n < 0, bestimmen. Man
rechnet (a’1 )’n , benötigt also einen Algorithmus zur Bestimmung von Inver-
sen. Dieser Algorithmus kann “ wenn n nicht zu groß ist “ teurer sein als die
schnelle Exponentiation.

Man beachte, dass es bei einer Implementation vorteilhaft sein kann, eine Qua-
drierfunktion zu benutzen. Quadrieren ist oft ef¬zienter möglich, als einfach
ein Element mit sich selbst zu multiplizieren. Bei der Implementierung dieses
Algorithmus sind eine Reihe von Varianten und Optimierungen möglich (siehe
z. B. [7]).




Aufgaben

6.1 Begründen Sie Lemma 6.1.

6.2 Es seien a und b Elemente einer endlichen abelschen Gruppe G = (G, ·) mit
teilerfremden Ordnungen. Zeigen Sie

o(a b) = o(a) o(b) .

6.3 Zeigen Sie, dass zu jedem Teiler d der Ordnung einer endlichen zyklischen
Gruppe genau eine Untergruppe der Ordnung d existiert (vgl. Lemma 6.6).

6.4 In einer Implementierung des Pohlig-Hellman-Verfahrens sei die Primzahl
p = 263 und e = 17 gegeben.

(a) Bestimmen Sie d mit e d ≡ 1 (mod p).
(b) Verschlüsseln Sie die Nachrichten a1 = 5 und a2 = 11.
(c) Entschlüsseln Sie die erhaltenen Geheimtexte.
(d) Versuchen Sie aus den Klartexten, den Geheimtexten und der Kenntnis von p,
auf e zu schließen (sehr rechenaufw¤ndig, benutzen Sie ein Computeralgebra-
System). Das gelingt bei a1 eindeutig, nicht aber bei a2 “ warum?
(e) Warum ist die Wahl der Primzahl dieser Aufgabe besser als die Wahl im Text?
110 6 Exponentiationschiffren

6.5 In einer Variante des Pohlig-Hellman-Verfahrens könnte man die Gruppe
G = (Z n , +) w¤hlen.

(a) Beschreiben Sie genau, wie Verschlüsselung und Entschlüsselung funktionie-
ren.
(b) Erl¤utern Sie, warum dieses Verfahren nicht sicher ist. Genauer: Zeigen Sie,
wie man aus einem bekannten Klartext-Geheimtext-Paar den Schlüssel be-
stimmen kann. Unter welchen Umst¤nden gelingt das eindeutig?

6.6 Implementieren Sie die naive und die schnelle Exponentiation und stellen
Sie Laufzeitvergleiche an. Ab wann treten spürbare Effekte auf?

6.7 Entschlüsseln Sie mit der schnellen Exponentiation den Geheimtext 69 aus
dem Beispiel auf Seite 106.
7 Das RSA-Verfahren

Durch eine Modi¬kation des Pohlig-Hellman-Verfahrens gelangen wir zum RSA-
Verfahren, benannt nach R. L. Rivest, A. Shamir und L. Adleman. Dieses Ver-
schlüsselungsverfahren wurde 1977 vorgestellt. Es ist ein asymmetrisches oder
Public-Key-Verfahren (vgl. Abschnitt 4.4). Zum Verschlüsseln einer Nachricht ist
kein vorheriger Schlüsselaustausch nötig, der Schlüssel zum Verschlüsseln eines
Klartextes ist öffentlich zug¤nglich.
Will der Sender S an den Empf¤nger R eine Nachricht N senden, so sucht S in
einem öffentlichen Verzeichnis den öffentlichen Schlüssel e von R, wendet ihn
auf seinen Klartext N an und sendet dann R den so erhaltenen Geheimtext C =
e(N ). Der Empf¤nger R hat einen geheimen Schlüssel d. Mit ihm kann er aus
dem Geheimtext C den Klartext N wiederherstellen: N = d(e(N )).
Die Sicherheit des Verfahrens beruht darauf, dass aus dem Geheimtext C = e(N )
und dem öffentlichen Schlüssel e “ der jedem zug¤nglich ist “ in vertretbarer Zeit
nicht auf den Klartext N und auch nicht auf den geheimen Schlüssel d geschlos-
sen werden kann.
Dieses geniale Prinzip hat einen wesentlichen Vorteil: Die Schlüsselverwaltung
wird deutlich vereinfacht. W¤hrend bei einem symmetrischen Verfahren, d. h., es
ist ein vorheriger Schlüsselaustausch zwischen je zwei Teilnehmern nötig, für n
Teilnehmer n (n ’ 1)/2 geheime Schlüssel ausgetauscht werden müssen, ist bei
einem Public-Key-Verfahren ein Verzeichnis aus nur n Schlüsseln nötig. Aber es
gibt auch einen Nachteil: Der Rechenaufwand bei allen bekannten asymmetri-
schen Verfahren ist deutlich höher als der bei einem symmetrischen Verfahren.
Für die Sicherheit des RSA-Verfahrens ist es wichtig, dass es im Allgemeinen sehr
schwer ist, eine (beim Verfahren benutzte und öffentlich bekannte) große natürli-
che Zahl n in ihre Primfaktoren zu zerlegen. Wir gehen auf diese und weitere
Fragen zur Sicherheit des RSA-Verfahrens ein und behandeln auch den Wiener-
Angriff, mit dem das RSA-Verfahren in einigen Spezialf¤llen gebrochen werden
kann, ohne die große natürliche Zahl n in ihre Primfaktoren zerlegen zu können.
Dieser Angriff erfordert einen etwas aufw¤ndigen Einblick in die Theorie der
(endlichen) Kettenbrüche. Dieser Aufwand lohnt sich aber, weil wir beim Fakto-
risierungsproblem in Kapitel 11 diese Theorie erneut aufgreifen werden.


7.1 Das Verfahren von Rivest, Shamir und Adleman
Das Prinzip ist einfach: In einem öffentlich zug¤nglichen Verzeichnis liegen die
offenen Schlösser aller Teilnehmer. Sie wollen an R eine geheime Nachricht schi-
112 7 Das RSA-Verfahren

cken? Packen Sie Ihre Nachricht in eine Kiste, befestigen Sie das öffentlich zu-
g¤ngliche Schloss von R an Ihre Kiste und schicken Sie die Kiste an R. Nur R hat
den Schlüssel, um das Schloss zu öffnen.

7.1.1 Das Kryptosystem
Das RSA-Verfahren ist wie das Pohlig-Hellman-Verfahren eine Exponentiations-
chiffre. Der Klartext N , aufgefasst als Element von Z n , n ∈ N, wird durch den
Sender S verschlüsselt, indem mit dem öffentlichen Schlüssel e des Empf¤ngers
R eine Potenz von N gebildet wird:
C=N e ∈Z n

!
S R
(n,e)

Der Empf¤nger R hat d als geheimen Schlüssel so bestimmt, dass

C d = (N e )d = N

erfüllt ist. Man beachte, dass beide Schlüssel, also e zum Verschlüsseln und d zum
Entschlüsseln, vom Empf¤nger R stammen. Der Schlüssel e ist öffentlich zug¤ng-
lich, sodass jeder eine Nachricht mit e verschlüsseln kann. Aber nur R kennt den
geheimen Schlüssel d, und daher kann auch nur R den Geheimtext entschlüsseln.
Nicht einmal der Sender selbst kann seine eigene Nachricht entschlüsseln.
Wir werden genauer und erinnern an die Euler™sche •-Funktion (siehe Seite 75).
Für n ∈ N gilt

•(n) = |Z — | = | {a ∈ N ; 1 ¤ a ¤ n , ggT(a, n) = 1} | .
n

Gegeben sind zwei verschiedene Primzahlen p und q. Wir setzen n = p q und
betrachten die (multiplikative) Halbgruppe (Z n , ·) der Ordnung n. Das RSA-
Verfahren ist ein asymmetrisches Kryptosystem mit:

Klartextmenge P = Z n .

<< . .

. 14
( : 33)



. . >>