<< . .

. 12
( : 33)



. . >>

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

<< . .

. 12
( : 33)



. . >>