<< . .

. 13
( : 33)



. . >>

Gruppe. Das ist Inhalt des Satzes von Lagrange:

Satz 6.4 (Lagrange)
Ist U Untergruppe einer endlichen Gruppe G, so ist |U| ein Teiler von |G|, kurz

|U| | |G| ;

insbesondere gilt o(a) | |G| für jedes a ∈ G.

Beweis. Wir begründen vorab, dass {a U ; a ∈ G} eine Partition der (endlichen)
Menge G ist: Für jedes a ∈ G ist a U = …, und wegen 1 ∈ U gilt G = a∈G a U.
Es sei a u = b v mit u, v ∈ U ein Element aus dem Durchschnitt a U © b U zweier
Elemente a U und b U aus {a U ; a ∈ G}. Dann liegen die Elemente b’1 a und a’1 b
in U, folglich gilt a U ⊆ b U und b U ⊆ a U, d. h. a U = b U.
Es ist {a U ; a ∈ G} eine Partition der endlichen Menge G. Somit ist G disjunkte
Vereinigung endlich vieler Nebenklassen:

G = a1 U ∪ · · · ∪ ar U .

Da für jedes i ∈ {1, . . . , r} gilt |ai U| = |U| “ es ist n¤mlich ι : U ’ ai U, u ’ ai u
eine Bijektion “, folgt |G| = r |U|.
6.1 Algebraische Grundlagen der Exponentiationschiffren 97

Beispiel
Die Gruppe (Z16 , +) kann wegen |Z16 | = 16 höchstens Untergruppen der Ord-
nungen 1, 2, 4, 8 und 16 haben. Wir listen alle Untergruppen von Z16 auf, es gibt
zu jeder möglichen Ordnung genau eine Untergruppe:

0 = {0}, 8 = {0, 8}, 4 = {0, 4, 8, 12},
2 = {0, 2, 4, 6, 8, 10, 12, 14}, 1 = Z16 .




6.1.3 Untergruppen zyklischer Gruppen
Das letzte Beispiel zeigt, dass s¤mtliche Untergruppen der zyklischen Gruppe
(Z16 , +) zyklisch sind. Das ist kein Zufall.

Lemma 6.5
Es sei G = a eine zyklische Gruppe. Dann ist auch jede Untergruppe U von G zyklisch.
Und zwar gilt U = {1} oder U = at , wobei t die kleinste natürliche Zahl mit der
Eigenschaft at ∈ U ist.


Beweis. Es sei U eine Untergruppe von G = {ak ; k ∈ Z}, U = {1}, und t sei
die kleinste natürliche Zahl mit at ∈ U. Ein solches t existiert auch in der Tat: Ist
n¤mlich ak ∈ U für ein k ∈ Z, so ist auch a’k ∈ U. Es gilt at ⊆ U. Und aus
ak ∈ U mit k = q t + r ∈ Z und 0 ¤ r < t (Division mit Rest) folgt andererseits

ar = ak’q t = ak (at )’q ∈ U ,

sodass r = 0 gilt wegen der Minimalit¤t von t; d. h.

ak = aq t = (at )q ∈ at .

Das beweist U ⊆ at und schließlich die Gleichheit U = at .

Wir halten noch ein Ergebnis zu endlichen zyklischen Gruppen fest, das wir ge-
legentlich benutzen werden: Wir betrachten eine zyklische Gruppe G = a der
n
endlichen Ordnung n, d. h. |G| = o(a) = n. Ist d ein Teiler von n, so ist a d eine
Untergruppe von G, die nach Lemma 6.2 die Ordnung d hat.

Lemma 6.6
Ist G = a eine zyklische Gruppe mit |G| = n, so existiert zu jedem Teiler d von n eine
n
Untergruppe U von G mit |U| = d, n¤mlich U = a d .

Die Untergruppe U ist sogar eindeutig bestimmt, siehe Aufgabe 6.3.
98 6 Exponentiationschiffren

6.1.4 Faktorgruppen
Ist U eine Untergruppe einer abelschen Gruppe (G, ·), so kann man auf der Men-
ge G/U := {a U ; a ∈ G} der Nebenklassen a U eine neue Multiplikation erkl¤-
ren. Wir de¬nieren für a U, b U ∈ G/U:

(a U) · (b U) := a b U .

Diese Verknüpfung ist wohlde¬niert, und es gilt:

Lemma 6.7
Es ist (G/U, ·) eine (abelsche) Gruppe mit neutralem Element U, die sogenannte Fak-
torgruppe modulo U. Ist G endlich, so gilt |G/U| = |G|/|U|.

Beweis. Der erste Teil ist aus der linearen Algebra bekannt, der zweite Teil steht
im Beweis zum Satz 6.4 von Lagrange.

Einfache und wohlbekannte Beispiele liefern die Untergruppen n Z, n ∈ N, der
additiven Gruppe Z. Es ist Z/nZ = Z n (siehe auch Seite 3).

Beispiel

Ist U = 17 die zweielementige Untergruppe von Z18 (vgl. das Beispiel auf Seite
95), so gilt wegen 13 ∈ 5 U und 11 ∈ 7 U:

Z18 /U = {U , 5 U , 7 U} = 5 U = 7 U .
— —
Man beachte: |Z18 /U| = |Z18 |/|U| = 6/2 = 3.



6.1.5 Der Satz von Cauchy

Es muss keineswegs zu jedem Teiler t der Gruppenordnung einer endlichen
Gruppe G auch eine Untergruppe der Ordnung t existieren. Ist jedoch t eine Prim-
zahl, so ist die Existenz gesichert.

Satz 6.8 (Cauchy)
Es sei G eine endliche abelsche Gruppe der Ordnung n. Zu jedem Primteiler p von n
existiert ein Element a ∈ G mit o(a) = p.

Beweis. Wir setzen n = p m mit m ∈ N und beweisen die Behauptung per Induk-
tion nach m. Für m = 1 folgt die Behauptung aus dem Satz 6.4 von Lagrange. Es
sei nun m ∈ N.
o(a)
1. Fall: Es existiert ein a ∈ G mit p | o(a). Dann ist a ∈ G ein Element der
p

Ordnung p.
6.1 Algebraische Grundlagen der Exponentiationschiffren 99

2. Fall: Es existiert kein a ∈ G mit p | o(a). Mit dem Satz von Lagrange folgt dann
für jedes a ∈ G \ {1} wegen ggT(p, o(a)) = 1:
m
|G/ a | = p < pm.
o(a)
∈N

Nach Induktionsvoraussetzung existiert ein b a ∈ G/ a mit o(b a ) = p.
Das Element b a ist das Bild von b ∈ G unter dem (kanonischen) Epimorphis-
mus π : G ’ G/ a , g ’ g a . Wegen der Homomorphie von π gilt:

(π(b))o(b) = π bo(b) = π(1) = a .

Da a das neutrale Element in G/ a ist, folgt mit (iii) in Lemma 6.1 (b) wegen
o(π(b)) = p:
p | o(b) ,
sodass dieser 2. Fall tats¤chlich gar nicht eintreffen kann.

Beispiel
— —
Wegen •(8) = 4 gilt |Z8 | = 4. Es ist 2 der einzige Primteiler von |Z8 |, und es

sind 3, 5, 7 Elemente der Ordnung 2. Obwohl 4 ein Teiler von |Z8 | ist, existiert

kein Element in Z8 der Ordnung 4; 4 ist keine Primzahl.


6.1.6 Die S¤tze von Euler und Fermat

Wir ziehen aus dem Satz von Lagrange eine Reihe von wichtigen Schlüssen, die
fundamental für die Kryptologie sind.

Korollar 6.9
Ist G eine endliche Gruppe, so gilt für jedes a ∈ G:
a|G| = 1 (Satz von Euler).
(a)

Für m ≡ 1 (mod |G|) gilt am = a.
(b)

Beweis. (a) Nach dem Satz von Lagrange ist die Ordnung von a ∈ G ein Teiler
der Gruppenordnung |G|. Nach Lemma 6.1 (b) gilt ao(a) = 1, damit folgt die
Behauptung aus (iii) in Lemma 6.1 (b).
(b) Es sei n := |G|. Gilt m ≡ 1 (mod n), so existiert ein q ∈ Z mit m ’ 1 = n q. Es
folgt
am = a1+n q = a (an )q = a
denn an = 1, wie in Teil (a) gezeigt.
Ein wichtiger Spezialfall der Aussage in (b) ist der (kleine) Satz von Fermat:
100 6 Exponentiationschiffren

Korollar 6.10 (Kleiner Satz von Fermat)
Es sei p eine Primzahl. Für alle a ∈ Z gilt a p ≡ a (mod p).

Beweis. Ist a = 0, so liegt a in der multiplikativen Gruppe Z — der Ordnung p ’ 1.
p
Die Behauptung folgt dann aus Korollar 6.9 (b) wegen p ≡ 1 (mod p ’ 1). Für
a = 0 ist die Aussage unmittelbar klar.



Die Gruppen Z — sind zyklisch
6.1.7 p


Die Gruppen Z —ν , p eine Primzahl und ν ∈ N, sind in der Kryptologie wichtig,
p
besonderes im Fall ν = 1. Ist ν = 1, d. h. Z —ν = Z — , so handelt es sich um die
p
p
multiplikative Gruppe des endlichen Körpers Z p . Wir zeigen nun, dass Z — für
p
jede Primzahl p eine zyklische Gruppe ist.
Wir betrachten vorab eine beliebige endliche abelsche Gruppe G und nennen

µ(G) := kgV {o(a) ; a ∈ G}

den Exponenten von G.
Nach dem Satz 6.4 von Lagrange gilt µ(G) | |G|. Wir können sogar zeigen:

Lemma 6.11
In einer endlichen abelschen Gruppe G gibt es ein Element b mit o(b) = µ(G).

Beweis. Es sei µ(G) = m1 · · · mr eine Zerlegung in teilerfremde Primzahlpotenzen
m1 , . . . , mr . Da µ(G) das kleinste gemeinsame Vielfache aller Elementordnungen
ist, existiert zu jedem mi ein ai ∈ G mit o(ai ) = mi k i für ein k i ∈ N. Nach
k
Lemma 6.2 gilt dann o(ai i ) = mi . Wegen Aufgabe 6.2 gilt somit für das Element
k
k k
b = a11 · · · ar r ∈ G wegen der Teilerfremdheit der Ordnungen der Elemente ai i :

r
∏ o(ai i ) = m1 · · · mr .
k
o(b) =
i=1

Für das Element b gilt daher o(b) = µ(G).

Mit diesem Lemma folgt, dass eine endliche abelsche Gruppe genau dann zy-
klisch ist, wenn µ(G) = |G| erfüllt ist. Damit können wir nun den folgenden
wichtigen Satz begründen:

Satz 6.12
Jede endliche Untergruppe G der multiplikativen Gruppe K — eines Körpers K ist zyklisch.
Insbesondere ist für jede Primzahl p die Gruppe Z — zyklisch.
p
6.1 Algebraische Grundlagen der Exponentiationschiffren 101

Beweis. Wir w¤hlen in G ein Element mit o(b) = µ(G) und zeigen µ(G) = |G|.
Nach dem Satz von Euler (Korollar 6.9 (a)) gilt µ(G) ¤ |G|.
Jedes Element a ∈ G ist Nullstelle des Polynoms f = X µ(G) ’ 1 ∈ K[X]. Da
dieses Polynom nach Satz 3.9 höchstens µ(G) = deg f Nullstellen haben kann,
gilt andererseits auch |G| ¤ µ(G), d. h. |G| = µ(G).

6.1.8 Die Gruppen Z —ν , p = 2, sind zyklisch
p

Wir zeigen nun, dass Z — für jede ungerade Primzahlpotenz n = pν , p = 2, zy-
n
klisch ist. Den Beweis bereiten wir mit einer Hilfsaussage vor.

Lemma 6.13
Für jede ungerade Primzahlpotenz pν , ν ≥ 1, gilt:
ν’1 ν’1
≡ 1 (mod pν ) , (1 + p) p ≡ 1 (mod pν+1 ) .
(1 + p) p

Beweis. Wir zeigen die Behauptung mit vollst¤ndiger Induktion nach ν.
ν’1
Die Behauptung stimmt für ν = 1 und sei richtig für ein ν ≥ 1, d. h. (1 + p) p =
ν mit p k. Es folgt
1+kp
p
p
pν νp
(k pν ) j

(1 + p) = (1 + k p ) =
j
j=0
p ’ 1 2 2ν+1
= 1 + k pν+1 + + · · · ≡ 1 + k pν+1 (mod pν+2 ) .
kp
2
Die Aussage gilt also auch für ν + 1.
Damit können wir nun zeigen:

Satz 6.14 (Gauß)
Für jede ungerade Primzahlpotenz pν ist die multiplikative Gruppe Z —ν eine zyklische
p
Gruppe der Ordnung (p ’ 1) pν’1 .

Beweis. Wir kürzen a := a + pν Z ab. Wegen Satz 6.12 existiert ein a ∈ Z derart,
dass a + p Z ∈ Z — die Ordnung p ’ 1 hat. Aus ao(a) ≡ 1 (mod pν ) folgt ao(a) ≡
p
1 (mod p), und damit gilt p ’ 1 | o(a) nach (iii) in Lemma 6.1. Es gelte etwa
o(a) = r (p ’ 1). Dann gilt o(ar ) = p ’ 1. Damit ist ein Element der Ordnung
p ’ 1 in Z —ν gefunden. Wir geben nun in Z —ν ein Element der Ordnung pν’1 an.
p p
pν’1
Wegen der Kongruenz in Lemma 6.13 gilt 1 + p = 1, wegen der Inkongruenz
pν’2
= 1. Damit folgt o(1 + p) = pν’1 nach (iii) in Lemma
in Lemma 6.13 gilt 1 + p
6.1 (b). Wegen ggT(p ’ 1, pν’1 ) = 1 ergibt sich mit Aufgabe 6.2
o(a · 1 + p) = (p ’ 1) pν’1 .
Nun ist |Z —ν | = •(pν ) = (p ’ 1) pν’1 , also Z —ν = a · 1 + p . Daher ist Z —ν
p p p
zyklisch.
102 6 Exponentiationschiffren

Wir haben begründet, dass die Gruppen Z —ν für jede Primzahl p = 2 und jede
p
natürliche Zahl ν zyklisch sind. In jeder solchen Gruppe existiert damit ein a ∈
Z —ν mit
p
Z —ν = a , es gilt o(a) = •(pν ) = (p ’ 1) pν’1 .
p

Dies ist eine reine Existenzaussage, wie man konkret ein solches erzeugendes
Element a zu einer Primzahlpotenz pν berechnet, ist dabei noch völlig offen. Das
Problem ist, Erzeuger von Z — zu ¬nden, dann zeigt der Beweis, wie man Erzeu-
p

ger von Z pν gewinnen kann.
Es ist keine Formel bekannt, nach der ein erzeugendes Element a von Z — be- p
stimmt werden kann. Im Allgemeinen ist es sehr mühsam, ein passendes a zu
ermitteln. Für unsere (eher theoretischen) Zwecke ist das Wissen über die Exis-
tenz eines solchen Elements aber meistens völlig ausreichend.
Ist Z — zyklisch, so nennt man jedes Z — erzeugende Element a, d. h., es gilt a =
n n
Z — , eine Primitivwurzel modulo n.
n

Bemerkung
Nach C. F. Gauß ist bekannt, für welche Zahlen n die Gruppe Z — zyklisch sind:
n
— ist genau dann zyklisch, wenn n = 2 oder n = 4 oder n = pν oder
Die Gruppe Z n
n = 2 pν mit einer ungeraden Primzahl p und natürlichen Zahl ν (vgl. Korollar 13.12
in [14]).


6.2 Das Pohlig-Hellman-Verfahren *

In den S¤tzen von Euler und Fermat steckt die Idee für ein Verschlüsselungsver-
fahren, bei dem das Verschlüsseln wie auch das Entschlüsseln durch Potenzbil-
dung erfolgt.



Das Pohlig-Hellman-Verfahren in Z —
6.2.1 p


Wir erl¤utern das Pohlig-Hellman-Verfahren in der multiplikativen Gruppe Z — des
p
endlichen Körpers Z p .
Gegeben ist eine Primzahl p. Der zu verschlüsselnde Klartext N sei als ein Ele-
ment von Z — dargestellt. Das ist eine (zyklische) multiplikative Gruppe mit p ’ 1
p
Elementen (siehe Satz 6.12). Nun erzeugen wir die beiden Schlüssel e (zum Ver-
schlüsseln) und d (zum Entschlüsseln):
Für die Zahl e w¤hlt man eine zu p ’ 1 teilerfremde natürliche Zahl. Nach
Satz 4.20 existiert eine natürliche Zahl d mit

e d ≡ 1 (mod p ’ 1) ,

die man mithilfe des euklidischen Algorithmus (siehe Satz 4.10) berechnen kann.
6.2 Das Pohlig-Hellman-Verfahren * 103

Nun dem Korollar 6.9 (b) zum Satz von Euler gilt (N e )d = N . Damit können wir
den Klartext N durch Potenzbildung verschlüsseln. Der Geheimtext C entsteht aus
dem Klartext N durch
C = Ne.
Wir erhalten den Klartext durch erneute Potenzbildung zurück, d. h., wir ent-
schlüsseln:
C d = (N e )d = N e d = N .


6.2.2 Das Kryptosystem

Wir beschreiben nun das Verfahren etwas allgemeiner. Anstelle von Z — kann eine
p
beliebige endliche abelsche Gruppe G gew¤hlt werden.
Es sei G eine endliche abelsche Gruppe der Ordnung n. Die Pohlig-Hellman-
Chiffre ist ein symmetrisches Kryptosystem mit

Klartextmenge P = G;


Geheimtextmenge C = G;


Schlüsselmenge K = {a ∈ N ; ggT(a, n) = 1} mit n = |G|;


Verschlüsselungsfunktion f : P — K ’ C de¬niert durch f (N , e) =

f e (N ) = N e für N ∈ P, e ∈ K;

Entschlüsselungsfunktion g : C — K ’ P de¬niert durch g(C, d) = gd (C) =

C d für C ∈ C, wobei für den Schlüssel d ∈ K gilt

d e ≡ 1 (mod n) .

Dabei wird d mit dem euklidischen Algorithmus zu e ∈ K gem¤ß Satz 4.20 be-
stimmt. Es gilt dann für jedes N ∈ G nach Korollar 6.9 (b):

f d ( f e (N )) = f d (N e ) = N e d = N .



6.2.3 Zur Sicherheit des Pohlig-Hellman-Verfahrens

Angenommen, einem Angreifer f¤llt ein Geheimtext C ∈ G in die H¤nde, wobei
das Pohlig-Hellman-Verfahren zur Erzeugung des Geheimtextes C = N e ver-
wendet wurde. Der Angreifer kennt zwar die Gruppe G und deren Ordnung |G|,
aber allein mit diesen Informationen kann er nicht auf den Klartext N zurück-
schließen. Ist dem Angreifer nicht nur ein Geheimtext, sondern auch ein zugehö-
riger Klartext bekannt, die Rede ist also von einem Known-Plain-Text-Angriff, so
104 6 Exponentiationschiffren

ist das Finden des geheimen Schlüssels e zum Lösen des diskreten Logarithmen-
problems ¤quivalent: Bestimme aus der Kenntnis von C und N eine Zahl e mit

C = Ne.

<< . .

. 13
( : 33)



. . >>