<<

. 4
( 9)



>>


(A2) Es seien G = c + F b ∈ G und a ∈ A \ G. Wir setzen G := a + F b. Wegen a ∈
G sind die Nebenklassen G und G des Untervektorraums F b disjunkt, folglich
gilt G © G = ….
Ist nun G eine weitere Gerade mit G © G = … durch a, so können wir
G = a + F d mit einem d = 0 setzen. Die Gleichung a + » d = c + μ b hat dann
keine Lösung (», μ) ∈ F2 . Daher können die Vektoren b, d ∈ F2 nicht linear un-
abh¤ngig sein. Es folgt F b = F d und damit G = G .
(A3) Die drei Punkte a := (0, 0), b := (1, 0), c := (0, 1) erfüllen die gewünschte
Bedingung.
Es heißt
AG(2, F) := (A, G)
die af¬ne Ebene über F. Es ist AG(2, F) die wichtigste Klasse von Beispielen für
af¬nen Ebene. Wir geben ein weiteres interessantes Beispiel.

Beispiel
Es ist A = {a, b, c, d} mit G = {{a, b} , {a, c} , {a, d} , {b, c} , {b, d} , {c, d}}
eine af¬ne Ebene, genannt das Minimalmodell einer af¬nen Ebene. Es ist die
af¬ne Ebene mit der geringsten An-
zahl von Punkten. Nach Aufgabe 5.2
hat n¤mlich jede af¬ne Ebene mindes-
tens vier Punkte. Die Geraden sind die
zweielementigen Teilmengen von A.

5.3.3 Netze
Es sei K eine Menge und G ⊆ Pot(K) mit |G| ≥ 2 für alle G ∈ G. Das Paar (K, G)
heißt Netz, wenn gilt:

(A1)™ Zu a, b ∈ K, a = b, gibt es höchstens ein G ∈ G mit a, b ∈ G; im Fall der
Existenz schreiben wir a, b für dieses G.

(A2) (Parallelenaxiom) Zu G ∈ G und a ∈ K \ G existiert genau eine Gerade
G ∈ G mit a ∈ G und G © G = ….

(A3)™ Es gibt mindestens drei Geraden, die paarweise Schnittpunkte besitzen.

Weil aus (A3) leicht (A3)™ folgt, ist klar, dass jede af¬ne Ebene ein Netz ist.
Zwei Geraden G, H eines Netzes heißen parallel, wenn G = H oder G © H = ….
Für die zur Geraden G durch den Punkt a ∈ K eindeutig bestimmte Parallele
schreiben wir {a G}. Es gilt also a ∈ {a G. Ein Netz (K, G) heißt
G}
endlich, falls |K| ∈ N.

Lemma 5.4
Es sei (K, G) ein endliches Netz, dann gilt:
5.3 Beweisbar perfekte Systeme * 89

(a) ist eine „quivalenzrelation.

(b) Es existiert q mit |G| = q für alle G ∈ G.

(c) Für alle G ∈ G sei [G] = {H ∈ G ; G H} die Parallelklasse von G, dann ist
|[G]| = q.
(d) |K| = q2 .

(e) Zu a ∈ K ist r = |{G ∈ G ; a ∈ G}| = |G/ | ¤ q + 1 unabh¤ngig von a.

(f) Ist (K, G) eine af¬ne Ebene, so gilt r = q + 1.

Beweis. (a) Offenbar ist re¬‚exiv und symmetrisch. Es seien G, H, L ∈ G, G H,
H L und G © L = …. Für a ∈ G © L erhalten wir G = {a H} = L. Daher ist
transitiv.
(b) Es seien G, H ∈ G. Im Fall G = H gilt natürlich |G| = |H|. Wir werden also
ab jetzt G = H annehmen. Dann gibt es a ∈ G und b ∈ H \ G, und für L = a, b
gilt L ¦ G, H. Die Abbildung π : G ’ H , a ’ {a L} © H ist bijektiv. In der Tat
ist die Inverse durch b ’ {b L} © G gegeben. Daher gilt |G| = |H| =: q, und
alle Geraden haben dieselbe Anzahl von Elementen.
(c) Es sei H ∈ G mit G ¦ H. Die Existenz ergibt sich aus (A3)™. Die Abbildung
H ’ [G] , x ’ {x G} ist offenbar wohlde¬niert und besitzt die Umkehr-
abbildung [G] ’ H , L ’ L © H, denn jede Gerade aus [G] besitzt genau einen
Schnittpunkt mit H. Daher sind die beiden Abbildungen bijektiv und mit (b) folgt
die Behauptung.
(d) Das Parallelenaxiom besagt, dass

K= H.
H∈[G]

Wegen (a) ist diese Vereinigung disjunkt. Daher folgt mit (b), (c) wie behauptet:

|K| = |H| · |[G]| = q2 .

(e) Wegen (A2) gilt r := |{G ∈ G ; a ∈ G}| = |G/ |, denn in jeder „quivalenz-
klasse paralleler Geraden gibt es genau ein Element durch a. Daher ist diese Zahl
auch unabh¤ngig von a.
Es seien nun a ∈ K, H ∈ G, a ∈ H. Für jede Gerade G durch a gilt G H oder
G © H = …. Daher gibt es wegen (A1)™ höchstens |H| + 1 = q + 1 solche Geraden.
(f) Im Fall einer af¬nen Ebene kann man jeden Punkt von H tats¤chlich mit a
verbinden, somit gilt r = |H| + 1.
Die Zahl q aus Teil (b) des Lemmas heißt die Ordnung des Netzes (K, G).
Beispiel
Es sei (A, G) = AG(2, F) die af¬ne Ebene über einem endlichen Körper F mit
q = |F| Elementen. Die Ordnung der af¬nen Ebene (A, G) ist q. Da es nach Satz
90 5 Symmetrische Authenti¬kation

3.10 zu jeder Primzahlpotenz pn einen endlichen Körper mit pn Elementen gibt,
existiert auch zu jeder Primzahlpotenz pn eine af¬ne Ebene der Ordnung pn .

Bemerkung
Es gibt viele af¬ne Ebenen, die nicht zu einem AG(2, F) isomorph sind, aber alle
zur Zeit bekannten af¬nen Ebenen haben eine Primzahlpotenz als Ordnung.

Um ein Netz zu bekommen, das keine af¬ne Ebene ist, kann man aus der Ge-
radenmenge G einer af¬nen Ebene einige Klassen paralleler Geraden entfernen.
Man erh¤lt so eine Teilmenge G von G, und es ist dann (K, G ) ein Netz. Wegen
des Fehlens von Geraden gilt die Eigenschaft (A1) nicht.

5.3.4 Netze liefern perfekte kartesische Systeme
Wir sind jetzt in der Lage, beweisbar sichere, perfekte Authenti¬kationssysteme
anzugeben. In einem sp¤ter zu pr¤zisierenden Sinn sind af¬ne Ebenen die besten.

Lemma 5.5
Es sei (K, G) ein (endliches) Netz der Ordnung q. Dann ist S = (G/ , G, K, f ) mit

f : G/ — K ’ G ; ([A], k) ’ {k A}

ein perfektes kartesisches Authenti¬kationssystem mit Betrugswahrscheinlichkeit p = 1 .
q

Beweis. Offenbar ist S ein Kryptosystem. Es ist kartesisch, denn zu jeder Nach-
richt G ist der Datensatz [G] eindeutig festgelegt, es gilt fˆ(G) = [G].
Wir nehmen an, dass der Schlüssel k benutzt wird, und bestimmen die Betrugs-
wahrscheinlichkeit p. Dazu untersuchen wir die beiden Angriffsarten.
Impersonation: Um x = [G ] einzuschleusen, muss der Angreifer H ∈ [G ] w¤h-
len. Da es genau ein H mit k ∈ H gibt, ist
1 1
p= =
|[G]| q
nach Lemma 5.4 (c).
Substitution: Es werde die gültige Nachricht G abgefangen. Dann gilt k ∈ G. Um
[G ] mit G ∈ [G ] einzuschleusen, kann wieder H ∈ [G ] gew¤hlt werden oder
k ∈ G jeweils mit Betrugswahrscheinlichkeit p = |G| = 1 . Man beachte, dass
1
q
H ∈ [G ] bzw. k ∈ G ¤quivalent sind, denn

H © G = k ” H = {k G }.

Sowohl bei der Impersonation als auch bei der Substitution gilt also
1 1
p= = .
|K|
q

Folglich ist das System S perfekt.
5.3 Beweisbar perfekte Systeme * 91

Die aus Netzen bzw. af¬nen Ebenen abgeleiteten Authenti¬kationssystem haben
nicht nur beweisbare Sicherheit, das Sicherheitsniveau ist einstellbar. Soll eine
bestimmte Betrugswahrscheinlichkeit unterschritten werden, muss man nur den
Körper groß genug w¤hlen.
Dabei sind af¬ne Ebenen insofern optimal, als bei vorgegebener Größe der
Schlüsselmenge K = q2 die Anzahl der Datens¤tze mit q + 1 maximal ist.
Die aus einer af¬nen Ebene der Form AG(2, Z p ) abgeleiteten Authenti¬kations-
systeme können auch ef¬zient implementiert werden.

5.3.5 Perfekte kartesische Systeme liefern Netze
Interessanterweise gilt auch die Umkehrung: Jedes perfekte kartesische Authen-
ti¬kationssystem liefert ein Netz. Wir benutzen für solche Authenti¬kationssys-
teme die in der De¬nition auf Seite 84 eingeführten Bezeichnungen K(c) und fˆ.

Lemma 5.6
Es sei (P, C, K, f ) ein kartesisches Authenti¬kationssystem mit |P| ≥ 3. Setze G :=
{K(c) ; c ∈ C}. Dann ist (K, G) ein Netz der Ordnung q = |K|, und es gilt |P| ¤
q + 1. Im Fall |P| = q + 1 ist (K, G) eine af¬ne Ebene.

Beweis. Es seien c, c ∈ C, c = c . Lemma 5.2 (c) besagt |K(c) © K(c )| ¤ 1. Das
ist (A1)™.
Für x = fˆ(c) und k ∈ K gilt G := K( f (x, k)) © K(c) = … oder G = K(c) (falls
k ∈ K(c)), also gibt es eine Parallele zu K(c) durch k. Falls K(c ) eine weitere
Parallele zu K(c) durch k ist, so gilt K(c) © K(c ) = …, also fˆ(c ) = fˆ(c). Daraus
folgt K(c ) = G und (A2) ist gezeigt.
Da jedes x ∈ P eine Parallelklasse de¬niert, gilt (A3)™. Damit ist gezeigt, dass
(K, G) ein Netz ist. Aus Lemma 5.4 (d) folgt q = |K|, und mit Lemma 5.4 (e)
ergibt sich |P| ¤ q + 1.
Es gelte nun |P| = q + 1. Es seien k, k ∈ K, k = k und G ∈ G eine Gerade durch
k . Wir zeigen die Existenz von k, k . Falls k ∈ G, sind wir fertig. Andernfalls gibt
es in jeder Parallelklasse eine Gerade Gi durch k. Diese können nach Lemma 5.4
(c) mit i = 0, . . . , q durchnummeriert werden. Ohne Einschr¤nkung gilt G0 G
und Gi © G = k i . Wegen |G| = q gilt daher G = {k1 , . . . , k q }. Somit gibt es i0 mit
k = k i0 , und Gi0 ist die Verbindungsgerade von k und k . Das zeigt (A1). Und wie
schon erw¤hnt folgt (A3) aus (A3)™.
Es soll nicht verschwiegen werden, dass diese Systeme auch gravierende Nach-
teile haben. So kann ein Schlüssel nur einmal verwendet werden. In der Tat: Es
seien zu einem Schlüssel k ∈ K zwei Nachrichten G und H bekannt, die mit k au-
thenti¬ziert wurden. In der geometrischen Deutung sind k ein Punkt und G, H
Geraden mit k ∈ G, H. Wegen (A1)™ muss also k = G © H gelten, und der Schlüs-
sel kann von jedem bestimmt werden.
Man beachte die „hnlichkeit dieser Systeme zum One-Time-Pad: Für jeden neuen
Datensatz muss ein neuer Schlüssel gew¤hlt werden.
92 5 Symmetrische Authenti¬kation

Bemerkung
In der Literatur werden Netze gelegentlich in einer ganz anderen Form als ortho-
gonale Arrays beschrieben. Die Darstellungen sind aber ¤quivalent.

5.4 Ausblick: Mehrfach perfekte Systeme *
Eine entsprechende Theorie wurde für Authentikationssysteme entwickelt, bei
denen der Angreifer mehrere Nachrichten beobachten kann, bevor er seine ge-
f¤lschte einspielt. Positiv formuliert, können die Benutzer n ∈ N Datens¤tze mit
demselben Schlüssel authenti¬zieren.
Der Satz von Fåk [11] besagt, dass die Schlüsselmenge sehr groß sein muss.

Satz 5.7 (Fåk)
Es sei (P, C, K, f ) ein Authenti¬kationssystem, bei dem man mindestens n Datens¤tze
mit demselben Schlüssel verschlüsseln kann. Dann gilt für die Betrugswahrscheinlich-
keit:
p ≥ |K|’ n+1 .
1




In dieser allgemeinen Form wurde der Satz in der Arbeit [23] von Rosenbaum
bewiesen.
Gilt im Satz von Fåk p = |K|’ n+1 , so spricht man von n-fach perfekten Authen-
1


ti¬kationssystemen.
Auch zu solchen Systemen gibt es Beispiele, die auf geometrischen Strukturen
basieren.

Aufgaben
5.1 Wir untersuchen das zweite Beispiel auf S. 84.
(a) Bestimme die Betrugswahrscheinlichkeit p und vergleiche das Ergebnis mit
der Schranke im Satz 5.1 von Gilbert, MacWilliams und Sloane.
(b) Ist das System perfekt?
(c) Bestimme K(m1 ) und f ’1 (m1 ).
(d) Ist das System kartesisch?
5.2 Zeigen Sie, dass jede af¬ne Ebene mindestens vier Punkte besitzt. Zeigen
Sie weiter, dass eine af¬ne Ebene mit genau vier Punkten, das Minimalmodell
(pr¤ziser: isomorph dazu) sein muss. Ist das Minimalmodell ein AG(2, F) mit
geeignetem Körper F ?
5.3 Es seien G, H ∈ G mit G ¦ H. Zeigen Sie, dass die Abbildung G — H ’ K,
(u, v) ’ {u H} © {v G} bijektiv ist. Folgern Sie erneut |K| = q2 .
5.4 Zeigen Sie, dass die Umkehrung von Lemma 5.4 (f) gilt, dass also im Fall
r = q + 1 das Netz eine af¬ne Ebene ist.
6 Exponentiationschiffren

Das Pohlig-Hellman-Verfahren ist eine sogenannte Exponentiationschiffre. Ein Klar-
text N , aufgefasst als Element einer Gruppe G, wird verschlüsselt, indem eine
Potenz von N gebildet wird: N ’ N e . Die Zahl e ist dabei der geheime Schlüs-
sel des Senders. Der Geheimtext C = N e wird dann durch den Empf¤nger ent-
schlüsselt, indem die Umkehrabbildung dieser Potenzfunktion f e : a ’ ae ange-
wandt wird. Im Fall einer endlichen Gruppe ist dies wieder eine Potenzfunktion
f d : a ’ ad . Der Exponent d ist dabei so zu w¤hlen, dass C d = (N e )d = N gilt.
Es ist d der geheime Schlüssel des Empf¤ngers. Wir werden sehen, dass ein sol-
ches d unter geeigneten Voraussetzungen immer existiert und ef¬zient bestimmt
werden kann.
Das Ver- und Entschlüsseln erfolgt beim Pohlig-Hellman-Verfahren durch Potenz-
bildung, daher der Begriff Exponentiationschiffre.
Im Allgemeinen sind bei einer Exponentiationschiffre hohe Potenzen von Grup-
penelementen zu bilden. Wir zeigen, wie diese Potenzbildung ef¬zient mit der
sogenannten schnellen Exponentiation durchgeführt werden kann.
Die algebraische Grundlage des Pohlig-Hellman-Verfahrens wie auch aller wei-
teren Exponentiationschiffren, die wir in den folgenden Kapiteln vorstellen, bil-
det der Satz von Lagrange mit seinen wichtigen Folgerungen, die auch als S¤tze
von Euler und Fermat bekannt sind. Diese S¤tze bilden das Fundament jeder Ex-
ponentiationschiffre und damit den algebraischen Schwerpunkt dieses Kapitels.
Wir werden in einem ersten Abschnitt diese S¤tze wie auch zahlreiche weitere
Ergebnisse, die wir im Folgenden benötigen werden, herleiten.

6.1 Algebraische Grundlagen der Exponentiationschiffren
Wir leiten in diesem Abschnitt viele wichtige Aussagen für (endliche, abelsche)
Gruppen her, wobei einige Aussagen aus der Vorlesung zur linearen Algebra be-
kannt sind. Dieser Abschnitt ist grundlegend für alle modernen Verfahren der
Kryptologie.
Das neutrale Element einer Gruppe G bezeichnen wir im Allgemeinen mit 1. Die
M¤chtigkeit |G| nennen wir die Gruppenordnung.

6.1.1 Ordnungen von Gruppenelementen
Für jedes Element a einer Gruppe (G, ·) ist die Menge
a := {an ; n ∈ Z} ⊆ G
eine Untergruppe von G “ man nennt sie die von a erzeugte Untergruppe von G.
Eine Gruppe G heißt zyklisch, wenn es ein a ∈ G mit a = G gibt.
94 6 Exponentiationschiffren

Dabei heißt eine nichtleere Teilmenge U von G bekanntlich Untergruppe, wenn
für alle a, b ∈ U gilt ab’1 ∈ U.

Beispiel
Die additiven Gruppen (Z, +) und (Z n , +) sind zyklisch, es gilt Z = 1 und
Z n = 1 . Beachte, dass hier 0 und 0 die neutralen Elemente sind.

Die multiplikative Gruppe Z8 = {1, 3, 5, 7} ist nicht zyklisch, da a2 = 1 für

jedes Element a ∈ Z8 gilt.

Für jede Primzahl p ist die multiplikative Gruppe Z — zyklisch (das wird in
p
Satz 6.12 bewiesen). Diese Tatsache ist für viele Kryptosysteme grundlegend.

Für jede ungerade Primzahl und jedes ν ∈ N ist Z —ν zyklisch (das wird in Satz
p
6.14 bewiesen).

Für jedes Element a einer Gruppe (G, ·) wird die M¤chtigkeit der von a erzeugten
Untergruppe die Ordnung von a in G genannt, in Zeichen:

o(a) := | a | ,

wobei o(a) := ∞ gesetzt wird, falls a unendlich ist. Das folgende Ergebnis ist
aus der linearen Algebra bekannt. Man vgl. auch die Aufgabe 6.1.

Lemma 6.1
Es sei a ein Element einer Gruppe G.

Wenn a unendliche Ordnung hat, so folgt aus i = j stets ai = a j .
(a)

Wenn a endliche Ordnung n hat, d. h. o(a) = n ∈ N, so ist n die kleinste natürli-
(b)
che Zahl mit an = 1, und es gilt für s, t ∈ Z:

(i) a = {1, a, a2 , . . . , an’1 },
(ii) as = at ” o(a) | s ’ t,
(iii) as = 1 ” o(a) | s.
Wir werden diese Tatsachen im Folgenden h¤u¬g benutzen. Vor allem die Aus-
sage in (iii) sollte man sich gut einpr¤gen.
Ist die Ordnung eines Gruppenelements a ∈ G endlich, so kann man die Ordnun-
gen der Potenzen von a nach einer einfachen Formel bestimmen, es gilt n¤mlich:

Lemma 6.2
Ist a ein Element der endlichen Ordnung n einer Gruppe G, so gilt für jedes k ∈ Z
n
o(ak ) = .
ggT(n, k)
6.1 Algebraische Grundlagen der Exponentiationschiffren 95

Beweis. Wir setzen d := ggT(n, k) und t := o(ak ) und zeigen t = n . Es gilt:
d

n k
(ak ) d = (an ) d = 1 ,

man beachte, dass d und n natürliche Zahlen sind. Wegen der Aussage (iii) in
k
d
Lemma 6.1 (b) folgt hieraus t | n .
d
Zu d gibt es nach dem euklidischen Algorithmus, siehe Satz 4.10, Zahlen r, s ∈ Z
mit d = r n + s k, d. h. 1 = r n + s d . Damit erhalten wir für t die Darstellung:
k
d

n k
t = tr +ts .
d d

Wenn wir zeigen können, dass n ein Teiler des zweiten Summanden t s d ist, so k
d
können wir aus obiger Darstellung von t folgern, dass n die Zahl t teilt.
d
Es gilt ak t = (ak )t = 1. Mit der Aussage (iii) in Lemma 6.1 (b) folgt o(a) = n | t k,
also gilt n | t d , woraus die Behauptung folgt: n | t.
k
d d


Beispiel

Die multiplikative Gruppe Z18 ist zyklisch, es gilt:

Z18 = 5 = {1, 5, 7, 11, 13, 17} .

Wegen
0 1 2 3 4 5
5 = 1 , 5 = 5 , 5 = 7 , 5 = 17 , 5 = 13 , 5 = 11

erhalten wir für die Ordnungen der Elemente von Z18 aus o(5) = 6:

6 6 6
o(1) = = 1 , o(5) = = 6 , o(7) = = 3,
ggT(6, 0) ggT(6, 1) ggT(6, 2)
6 6 6
o(11) = = 6 , o(13) = = 3 , o(17) = = 2.
ggT(6, 5) ggT(6, 4) ggT(6, 3)

Insbesondere sind 5 und 11 die einzigen erzeugenden Elemente von Z18 .

Für unsere Zwecke ist eine unmittelbare Folgerung aus Lemma 6.2 für die erzeu-
genden Elemente einer zyklischen Gruppe wesentlich:

Korollar 6.3
Ist G = a eine zyklische Gruppe der endlichen Ordnung n, so gilt:

(a) Für k ∈ Z gilt G = ak ” ggT(n, k) = 1.

(b) Die Gruppe G besitzt genau •(n) erzeugende Elemente “ dabei bezeichnet • die
Euler™sche •-Funktion (siehe Abschnitt 4.3.4).
96 6 Exponentiationschiffren

Beispiel

Ist Z — zyklisch, so gibt es genau •(•(n)) erzeugende Elemente, z. B. hat Z18
n
genau •(•(18)) = •(6) = 2 erzeugende Elemente (vgl. obiges Beispiel). Und in
der additiven Gruppe (Z p , +) für eine Primzahl p ist jedes von 0 verschiedene
Element ein erzeugendes Element, da •(p) = p ’ 1 gilt.

Bemerkung
Wir haben in diesem Kapitel Untergruppen einer Gruppe (G, ·) betrachtet, die
von einem Element a ∈ G erzeugt werden: a = {an ∈ G ; n ∈ Z}. Wir können
allgemeiner auch Untergruppen betrachten, die von endlich vielen a1 , . . . , an ∈ G
erzeugt werden. Wir beschr¤nken uns auf den Fall, dass G kommutativ ist. Dann
ist
ν
a1 , . . . , an := a11 · · · aνn ; ν1 , . . . , νn ∈ Z
n

ebenso eine Untergruppe von G “ die von a1 , . . . , an erzeugte Untergruppe von
G. Man beachte, dass a1 , . . . , an die Menge aller Produkte aller Potenzen der
Elemente a1 , . . . , an ∈ G ist.


6.1.2 Der Satz von Lagrange

Lemma 6.2 legt den Verdacht nahe, dass die Ordnungen von Gruppenelementen
endlicher Gruppen Teiler der Gruppenordnung sind (vgl. auch das Beispiel auf
Seite 95). Tats¤chlich gilt dies allgemeiner für jede Untergruppe einer endlichen
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.

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 .


Geheimtextmenge C = Z n .


Schlüsselmenge K = {e ∈ N ; ggT(e, •(n)) = 1} (oft erw¤hnt man auch n

in der Schlüsselmenge, d. h. K = {(n, e) ∈ N — N ; ggT(e, •(n)) = 1}).

Verschlüsselungsfunktionen f e mit e ∈ K de¬niert durch f e (N ) = N e für

N ∈ P.

Entschlüsselungsfunktionen f d mit d ∈ K de¬niert durch f d (C) = C d für

C ∈ C, wobei
e d ≡ 1 (mod •(n)) .
7.1 Das Verfahren von Rivest, Shamir und Adleman 113

Dabei wird d mit dem euklidischen Algorithmus (siehe Satz 4.10) zu e ∈ K be-
stimmt.
In Lemma 7.1 zeigen wir, dass das Verfahren funktioniert, d. h. dass das Ent-
schlüsseln eines verschlüsselten Klartextes N wieder den Klartext N liefert:

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


Bemerkung
Die Zahlen n = p q und e sind öffentlich bekannt. Einem Angreifer darf die Zahl
•(n) = (p ’ 1) (q ’ 1) (siehe das Beispiel auf Seite 75) nicht bekannt sein, er
kann sonst ebenso wie der Empf¤nger mithilfe des euklidischen Algorithmus den
geheimen Schlüssel d ermitteln.
W¤hlt man für die Zahlen p und q große Primzahlen, so ist es im Allgemeinen
schwierig, aus der Kenntnis von n = p q die Primfaktoren p und q und damit
•(n) = (p ’ 1) (q ’ 1) zu ermitteln. In der Praxis werden die Primzahlen p und
q von der Größenordnung 512 Bit gew¤hlt. Bei der Wahl der Primzahlen p und
q sind noch weitere Aspekte zu berücksichtigen, auf die wir in Abschnitt 7.4.1
eingehen werden.

Man beachte, dass die Voraussetzungen des folgenden Lemmas genau die Situa-
tion im RSA-Kryptosystem wiedergeben:

Lemma 7.1
Es seien p = q Primzahlen, n = p q, d, e ∈ N mit ggT(e, •(n)) = 1, e d ≡
1 (mod •(n)) und a ∈ Z. Dann gilt aed ≡ a (mod n).

Beweis. Wegen e d ≡ 1 (mod •(n)) existiert ein r ∈ Z mit e d = 1 + r •(n) =
1 + r (p ’ 1) (q ’ 1). Nach dem Satz 6.10 von Fermat gelten die folgenden Kon-
gruenzen:

aed ≡ a1+r(p’1)(q’1) ≡ a (a p’1 )r(q’1) ≡ a (mod p) ,
aed ≡ a1+r(p’1)(q’1) ≡ a (aq’1 )r(p’1) ≡ a (mod q) .

Die erste Kongruenz besagt p | aed ’ a, die zweite q | aed ’ a. Da p und q verschie-
dene Primzahlen sind, gilt somit auch p q | aed ’ a, d. h. aed ≡ a (mod n).

Die Kongruenz aed ≡ a (mod n) bedeutet aber nichts anders als die Gleichheit
aed = a in Z n . Damit folgt aus Lemma 7.1 die Korrektheit des RSA-Verfahrens:
Der Empf¤nger R erh¤lt den Geheimtext C = N e ∈ Z n und berechnet mit seinem
geheimen Schlüssel d durch Potenzieren den Klartext:

C d = N ed = N ∈ Z n .
114 7 Das RSA-Verfahren

7.1.2 Die Schlüsselerzeugung
Beim RSA-Verfahren sind die beiden Zahlen n und e öffentlich bekannt. Wir
fassen von nun an die beiden Zahlen zum öffentlichen Schlüssel (n, e) zusam-
men. Wir schildern die Schlüsselerzeugung, also die Erzeugung des öffentlichen
Schlüssels (n, e) und des geheimen Schlüssels d durch den Empf¤nger R:
R w¤hlt zwei Primzahlen p = q.
R berechnet n := p q, •(n) = (p ’ 1) (q ’ 1) (siehe das Beispiel auf Seite 75).
R w¤hlt ein e ∈ N mit 1 < e < •(n) und ggT(e, •(n)) = 1.
R berechnet d ∈ N mit e d ≡ 1 (mod •(n)).
Es sind dann (n, e) der öffentliche Schlüssel von R und d der geheime Schlüssel
von R. Es sind auch die Größen p, q, •(n) geheim zu halten. Ist n¤mlich einem
Angreifer eine dieser drei Größen bekannt, so kann er d berechnen.

7.1.3 Die Verschlüsselung
Die Erzeugung des Geheimtextes C aus dem Klartext N ist einfach: Der Sender
S besorgt sich den öffentlichen Schlüssel (n, e) des Empf¤ngers R und geht wie
folgt vor:
S codiert seine Nachricht in den Klartext N ∈ Z n .
S berechnet den Geheimtext C := N e ∈ Z n .
S sendet den Geheimtext C an R.


7.1.4 Die Entschlüsselung
Die Entschlüsselung
C ’ Cd = N
mit dem geheimen Schlüssel d klappt wegen Lemma 7.1.

Beispiel
Es seien p = 7 und q = 11. Dann gilt n = 77, •(n) = 6 · 10 = 60. Die Wahl e = 13
erfüllt ggT(e, 60) = 1. Damit hat R den öffentlichen Schlüssel (n, e) = (77, 13).
Mit dem euklidischen Algorithmus berechnet R seinen geheimen Schlüssel d:

1 ≡ 37 · 13 (mod 60) ,

sodass d = 37.
Nun will S an R die Nachricht N = 7 ∈ Z77 senden. Dazu besorgt sich S den
öffentlichen Schlüssel (n, e) = (77, 13) und verschlüsselt N = 7 zu
13
C = Ne = 7 = 35 .
7.1 Das Verfahren von Rivest, Shamir und Adleman 115

Der Geheimtext C = 35 ∈ Z77 wird an R gesandt. Dieser entschlüsselt den Ge-
heimtext mit seinem geheimen Schlüssel d = 37:

37
C d = 35 =7

und erh¤lt so den Klartext N = 7 ∈ Z77 zurück. Es ist bemerkenswert, dass das
funktioniert, obwohl N = 7 in Z77 nicht invertierbar ist.



7.1.5 Hybridverfahren

Der Rechenaufwand beim RSA-Verfahren ist im Allgemeinen um ein Vielfaches
höher als der bei einem symmetrischen Verfahren. Wir werden weitere Public-
Key-Verfahren kennenlernen, aber auch diese sind erheblich teurer als die sym-
metrischen Verfahren. Mithilfe eines einfachen Tricks kann durch ein Public-Key-
Verfahren ein ef¬zienteres symmetrisches Verfahren genutzt werden. Wir gehen
von folgender Situation aus. S will an R eine Nachricht N senden. Der öffentliche
Schlüssel von R sei (n, e).

S verschlüsselt einen Klartext N mit einem symmetrischen Verfahren zu ei-
nem Geheimtext C.

Den Schlüssel k zum Entschlüsseln dieser Nachricht C verschlüsselt S (nach
einer passenden Codierung) mit dem öffentlichen Schlüssel (n, e) des Emp-
f¤ngers R zu k .

S sendet das Paar (C, k ) an den Empf¤nger R.

R entschlüsselt k mit seinem geheimen Schlüssel des Public-Key-Verfahrens
und erh¤lt den Schlüssel k.

R benutzt dann k, um aus C den Klartext N zu erhalten.

Solche Verfahren werden Hybridverfahren genannt, weil sie die Vorteile der
symmetrischen mit den Vorteilen der asymmetrischen Kryptogra¬e verbinden.

Bemerkung
Der im Allgemeinen höhere Rechenaufwand eines Public-Key-Verfahrens ist hier
auf das Ver- und Entschlüsseln eines Schlüssels, also einer meist sehr kurzen Se-
quenz, beschr¤nkt. Bei AES etwa, das h¤u¬g mit RSA gekoppelt wird, liegt die
Schlüssell¤nge zwischen 128 und 256 Bit.
Eine andere Methode, einen Schlüssel über einen unsicheren Kanal auszutau-
schen, um dann mit einem symmetrischen Verfahren kommunizieren zu können,
ist der Dif¬e-Hellman-Schlüsselaustausch. Darauf gehen wir in Kapitel 9 ein.
116 7 Das RSA-Verfahren

7.1.6 Zur Sicherheit von RSA
Wir versetzen uns nun die Lage eines Angreifers A:
C=N e

!
(n,e)
S R

A

Ein Angreifer A, dem ein Geheimtext C ∈ Z n des Senders S an den Empf¤nger
R in die H¤nde ger¤t, erh¤lt den Klartext N durch Lösen eines der folgenden
Probleme:
• Bestimme den geheimen Schlüssel d, d. h. die Lösungsmenge der Kongru-
enzgleichung:
e X ≡ 1 (mod •(n)) .
Dazu muss der Angreifer •(n) kennen.

Bestimme die e-te Wurzel aus C in Z n , d. h. die Lösung N ∈ Z n der Glei-

chung
Xe = C .

Die Lösung der Gleichung X e = C ist auch tats¤chlich eindeutig bestimmt, da der
Homomorphismus ι e : Z n ’ Z n , a ’ ae wegen Lemma 7.1 bijektiv ist, die Po-
tenzabbildung ι d ist das Inverse zu ι e . Damit ist das Ziehen der e-ten Wurzel das
Potenzieren mit d. Folglich sind die beiden geschilderten Probleme, vor denen
der Angreifer steht, ein und dasselbe Problem.
Beim RSA-Verfahren sind, wie bereits erw¤hnt, neben dem geheimen Schlüssel
d auch die Größen p, q und •(n) geheim zu halten, da ein Angreifer mit einer
dieser drei Größen aus dem öffentlichen Schlüssel (n, e) den geheimen Schlüssel
d ermitteln kann. Wir zeigen nun, dass man mit der Kenntnis von •(n) die Prim-
teiler p und q von n ermitteln kann. Es sind n¤mlich p und q die zwei Nullstellen
eines Polynoms vom Grad 2 mit Koef¬zienten, die von n und •(n) abh¤ngen,
und die Nullstellen eines Polynoms vom Grad 2 sind einfach zu bestimmen.

Lemma 7.2
Aus n und •(n) können p und q als Nullstellen des Polynoms

f = X 2 ’ (n ’ •(n) + 1) X + n

bestimmt werden.

Beweis. Sind n und •(n) bekannt, so kann das Polynom

f = X 2 ’ (n ’ •(n) + 1) X + n ∈ Z[X]
7.2 Der chinesische Restsatz 117

aufgestellt werden. Und wegen n ’ •(n) = p q ’ (p ’ 1) (q ’ 1) = p + q ’ 1 gilt:
(X ’ p) (X ’ q) = X 2 ’ (p + q) X + p q = X 2 ’ (n ’ •(n) + 1) X + n .
Damit sind die Nullstellen von f die Primzahlen p und q.

Bemerkung
Kann man n in seine Primfaktoren n = p q zerlegen, so kann man •(n) =
(p ’ 1) (q ’ 1) berechnen. Und kann man umgekehrt •(n) aus n berechnen, so
kann man nach Lemma 7.2 die Zahl n in ihre Primfaktoren zerlegen. Die beiden
Probleme, n zu faktorisieren und •(n) zu bestimmen, sind also algorithmisch
¤quivalent.


7.2 Der chinesische Restsatz

Um weitere Fragen zur Sicherheit des RSA-Verfahrens kl¤ren zu können, brau-
chen wir den sogenannten chinesischen Restsatz aus der Zahlentheorie. Dieser
Satz liefert ein Verfahren, ef¬zient Systeme von Kongruenzgleichungen zu lö-
sen. Damit können durch RSA verschlüsselte Geheimtexte unter gewissen Vor-
aussetzungen gebrochen werden. Wir leiten in einem ersten Abschnitt den chi-
nesischen Restsatz her und ziehen dann wichtige Folgerungen für die Euler™sche
•-Funktion.


7.2.1 Der chinesische Restsatz

Es ist klar, dass das kartesische Produkt R = R1 — · · · — Rn von Ringen R1 , . . . , Rn
mit den komponentenweisen Verknüpfungen
(a1 , . . . , an ) + (b1 , . . . , bn ) = (a1 + b1 , . . . , an + bn ) und
(a1 , . . . , an ) · (b1 , . . . , bn ) = (a1 b1 , . . . , an bn )
für (a1 , . . . , an ) , (b1 , . . . , bn ) ∈ R wieder einen Ring bildet.
Wir besch¤ftigen uns mit der umgekehrten Aufgabenstellung. Man gebe in dem
Ring (R, +, ·) Unterringe U1 , . . . , Un an, sodass R ∼ U1 — · · · — Un gilt. Wir füh-
=
ren eine solche Zerlegung in ein direktes Produkt für den Ring (Z m , +, ·), m ∈ N,
durch.

Lemma 7.3
Für paarweise teilerfremde r1 , . . . , rn ∈ Z ist
’ Z r1 — · · · — Z r n
Zr1 ···rn
ψ:
k + r1 · · · r n Z ’ (k + r1 Z, . . . , k + rn Z)
ein Ringisomorphismus (d. h. bijektiv und ein additiver und multiplikativer Homomor-
phismus).
118 7 Das RSA-Verfahren

Beweis. Die Abbildung ψ ist wohlde¬niert und injektiv, da für r := r1 · · · rn gilt:

k + rZ = l + r Z ” r | l ’ k ” ri | l ’ k für alle i = 1, . . . , n
” k + ri Z = l + ri Z für alle i = 1, . . . , n
” ψ(k + r Z) = ψ(l + r Z) .

Wegen
n n
|Zr | = r = ∏ ri = ∏ |Zri | = |Zr1 — · · · — Zrn |
i=1 i=1
ist ψ auch surjektiv. Nach De¬nition der Verknüpfungen ist ψ additiv und multi-
plikativ.

<<

. 4
( 9)



>>