<< . .

. 28
( : 33)



. . >>

p’1
Angreifer A sein Ziel, indem er wie folgt vorgeht:

A berechnet U ≡ N N ’1 (mod (p ’ 1)).

A ermittelt s als Lösung von X ≡ s U (mod (p ’ 1)).

A berechnet mit dem chinesischen Restsatz (beachte ggT(p ’ 1, p) = 1) eine
Lösung R des Systems von Kongruenzgleichungen:

X ≡ R U (mod (p ’ 1)) und X ≡ R (mod p) .

A kann nun (R , s ) als gültige Signatur zum Klartext N angeben.

Ein Teilnehmer T veri¬ziert die gef¤lschte Signatur, es gilt n¤mlich:

A R (R )s = A R U Rs U = gU (a R+k s) = gU N = gN .

Nun begründen wir, dass für das R der so erhaltenen Signatur im Allgemeinen
R > p ’ 1 gilt. Angenommen, es gilt R ¤ p ’ 1. Dann folgt aus R ≡ R (mod p)
schon R = R , also

R ≡ R U (mod (p ’ 1)) ” R (U ’ 1) ≡ 0 (mod (p ’ 1))
” (p ’ 1) | R (U ’ 1) .

Im Fall ggT(R, p ’ 1) = 1 kann man R kürzen, es folgt U = 1 und damit N = N .
Ein Angreifer hat dadurch nichts erreicht. Gilt aber ggT(R, p ’ 1) = 1, so muss U
und damit auch N speziell gew¤hlt werden. Dass dies eintreten kann, zeigt das
folgende Beispiel.
12.3 Das ElGamal-Signaturverfahren 215

Beispiel
Wir benutzen die Daten aus dem Beispiel von Seite 213. Der Angreifer w¤hlt
N = 14 und erh¤lt U = 10 und s = 12. Dann ist (14, 12) eine gültige Signa-
tur, wie man leicht nachrechnet.

Signieren von zuf¤lligen Datens¤tzen. Ein Angreifer kann einen zuf¤lligen Da-
tensatz signieren: Er w¤hlt Zahlen i, j ∈ {0, . . . , p ’ 2} mit ggT(j, p ’ 1) = 1 und
berechnet
R ≡ gi A j (mod p) ,
s ≡ ’R j’1 (mod (p ’ 1)) ,
N ≡ ’R i j’1 (mod (p ’ 1)) .
Es ist dann (R, s) die gültige Signatur des Dokuments N , da gilt:
’1 ’1
A R Rs = A R (gi A j )’R j = A R g’R i j A’R = gN .

Bemerkung
Ein vorgebenes N zu signieren, erfordert das Au¬‚ösen der Gleichung:
A R Rs = gN in Z — nach (R, s) .
p

Es gibt keinen Anhaltspunkt dafür, wie man das machen könnte, aber auch kein
bekanntes Problem, zu dem es ¤quivalent ist.

Kennt man k, so kennt man a; k darf also nur einmal verwendet werden. Die
beim ElGamal-Signaturverfahren zuf¤llig gew¤hlte Zahl k mit gk = R darf nur
einmal verwendet werden. Wird k n¤mlich zwei Mal benutzt, sind also (R, s1 )
eine Signatur zu N1 sowie (R, s2 ) eine Signatur zu N2 , so gilt
A R Rs1 = gN1 und A R Rs2 = gN2 .
Es folgt

gN2 ’N1 = A R Rs2 R’s1 A’R = Rs2 ’s1 = gk (s2 ’s1 )
Wegen o(g) = p ’ 1 erhalten wir hieraus
N2 ’ N1 ≡ k (s2 ’ s1 ) (mod (p ’ 1)) .
Falls ggT(s2 ’ s1 , p ’ 1) = 1, so kann man k aus dieser Konguenzgleichung be-
stimmen. Gilt zudem ggT(R, p ’ 1) = 1, so erh¤lt man aus k dann den geheimen
Schlüssel a von E aus der Kongruenzgleichung
N1 ’ a R ≡ k s1 (mod (p ’ 1)) .

Bemerkung
Im Beispiel oben konnte ein Angreifer selbst einen Datensatz signieren, wenn R
und p ’ 1 nicht teilerfremd sind. Genau aus diesem Grund kompromittiert das
den geheimen Schlüssel nicht, obwohl dasselbe R verwendet wird.
216 12 Signaturverfahren

12.4 Digital Signature Standard “ DSS
Der Digital-Signatur-Standard DSS (auch DSA genannt) wurde 1991 von der
NIST vorgeschlagen und ist seit etwa 1994 Standard. DSS ist eine etwas ef¬zien-
tere Variante des eben beschriebenen ElGamal-Signaturverfahrens.

12.4.1 Das Signaturverfahren DSS
Es seien p und q Primzahlen mit

2159 < q < 2160 , 2511+64 t < p < 2512+64 t , t ∈ {0, . . . , 8} und q | p ’ 1 .

Dann gibt es wegen Satz 6.12 und Lemma 6.6 eine Untergruppe G von Z — mit
p
|G| = q. Wegen Lemma 6.5 ist G zyklisch, d. h. G = g mit einem g ∈ G.

Der Teilnehmer T erzeugt seinen öffentlichen und gehei-
Schlüsselerzeugung.
men Schlüssel:

Für ein a ∈ {2, . . . , q ’ 1} sei A = g a .

Der öffentliche Schlüssel ist (p, q, g, A).

Der geheime Schlüssel ist a.

Wir erkl¤ren eine (wohlde¬nierte) Abbildung f : Z — ’ Z q wie folgt: Für jedes
p
— sei r ∈ {0, . . . , q ’ 1} der Rest, der bei Division von x durch q entsteht,
x ∈ Zp x
wir setzen
f (x) := r x ∈ Z q .

Erzeugung der Signatur. Es sei N ∈ Z q das von T zu signierende Dokument.
In der Praxis ist N ein Hashwert des tats¤chlichen Dokuments.

T w¤hlt zuf¤llig ein k ∈ {1, . . . , q ’ 1} mit ggT(k, q) = 1.

T berechnet R = gk ∈ Z — und
p

’1
(—) s = (N + a f (R)) k ∈ Zq .

Falls s = 0, so w¤hle ein neues k.

Es ist ( f (R), s) ∈ Z q — Z q die Signatur von N .


Veri¬kation der Signatur. Der Empf¤nger E erh¤lt das Dokument N mit der
dazugehörigen Signatur ( f (R), s) und veri¬ziert diese:

E berechnet u1 = N s’1 ∈ Z q und u2 = f (R) s’1 ∈ Z q .

E überprüft, ob f (gu1 Au2 ) = f (R).
12.4 Digital Signature Standard “ DSS 217

Falls Gleichheit vorliegt, akzeptiert E die Signatur, sonst nicht.

In der Tat gilt im Falle der Echtheit der Signatur (beachte die Gleichung in (—)):
’1 +a f (R) s’1
f (gu1 Au2 ) = f (gN s ) = f (gk ) = f (R) ,

wobei wir wieder die Restklassen N , f (R) ∈ Z q mit ihren kleinsten positiven
Repr¤sentanten identi¬ert haben.


12.4.2 Vorteile und andere Unterschiede

Die Unterschiede zum Signaturverfahren von ElGamal sind

das Vorzeichen in (—),


f (R) statt R in der Signatur,


• zur Veri¬kation benötigt man nur zwei Exponentiationen (mit Exponenten
von 2160 Bit), ElGamal benötigt drei.

Ein weiterer nicht zu untersch¤tzender Vorteil ist die mit 320 Bit relativ kleine
L¤nge der Signatur.
Die Angriffe beim ElGamal-Verfahren sind analog auch beim DSS-Verfahren
möglich.


12.4.3 Signaturverfahren nach Schnorr *

Das Signaturverfahren nach Schnorr ist auch eine Variante des ElGamal-Verfah-
rens. Wir verwenden die Bezeichnungen, die in Abschnitt 12.3.1 eingeführt wur-
den. Es sei also p eine Primzahl, g eine Primitivwurzel modulo p, g = Z — , p
A = g a für ein a ∈ {2, . . . , p ’ 2}, (p, g, A) der öffentliche Schlüssel und a der
geheime Schlüssel des Empf¤ngers E.
Weiter sei P die Klartextmenge und h : P — Z p ’ Z p’1 eine Hashfunktion. Ein
Teilnehmer T, der ein Dokument N ∈ P signieren will, geht wie folgt vor:

T bestimmt zuf¤llig k ∈ {1, . . . , p ’ 1}.

T berechnet R = gk und s = k ’ a h(N , R) ∈ Z p’1 .

Es ist dann (s, h(N , R)) ∈ Z p’1 — Z p’1 die Signatur zu N ∈ P.

Die Veri¬kation ist einfach. Bei Vorliegen einer korrekten Signatur gilt

gs Ah(N ,R) = gk = R ,

also ist zu prüfen, ob h(N , R) = h(N , gs gh(N , R) ) gilt.
218 12 Signaturverfahren

Aufgaben

Wie kann man aus dem Rabin-Verfahren ein Signaturverfahren machen?
12.1

12.2 Es ist g = 3 eine Primitivwurzel modulo der Primzahl p = 2011. Der ge-
heime Schlüssel von E ist 101. Das zu signierende Dokument ist N = 1111. Be-
stimmen Sie die ElGamal-Signatur mit k = 1000 und veri¬zieren Sie diese.

12.3 Es sei p ≡ 3 (mod 4) eine Primzahl, und G = Z — = g mit p ’ 1 =
p
g q, g, q ∈ N. Für A = g a sei (G, g, A) der öffentliche Schlüssel eines ElGamal-

Signaturverfahrens. Dabei sei f : G ’ Z p’1 gegeben durch

falls x = p ’ 1
x,
f (x) = .
falls x = p ’ 1
0,

Zeigen Sie:
p’3
≡ g (mod p);
(a) q 2

(b) γ ∈ Z mit gq γ ≡ aq (mod p) kann mit der Komplexit¤t O( g) bestimmt
werden.
p’3
(c) Mit s = 2 (N ’ q γ) ist (q, s) eine gültige Signatur für N .
12.4 Das Protokoll von Fait-Shamir
Es sei n = p q mit Primzahlen p, q. Der Teilnehmer T w¤hlt ein geheimes Element
s ∈ Z n , berechnet v := s2 und veröffentlicht (v, n), um seine Identit¤t etwa ge-
genüber C nachzuweisen. Dazu durchlaufen sie t-mal (t ∈ N) folgendes Protokoll:

T w¤hlt zuf¤llig r ∈ Z n , berechnet x = r2 und übermittelt x an C;
C w¤hlt zuf¤llig b ∈ {0, 1} und schickt b an T;
T schickt u = sb r an C;
C prüft u2 = vb x.

Zeigen Sie:

(a) Wer s kennt, kann das Protokoll erfolgreich durchlaufen.
(b) Wie groß ist die Betrugswahrscheinlichkeit für jemanden, der s nicht kennt?
(c) Beim Ablauf des Protokolls entsteht eine Folge (xi , bi , ui )i=1,...,t . Diese Folge
kann auch in polynomialer Zeit simuliert werden, ohne dass man s kennt.
Daher kann keine Information über das Geheimnis übertragen worden sein.
Man spricht von einem Zero-Knowledge-Protokoll.
13 Elliptische Kurven *

Das ElGamal-Verschlüsselungsverfahren kann auf jeder zyklischen Gruppe im-
plementiert werden. In der additiven Gruppe (Z n , +) bietet das Verfahren keine
Sicherheit (vgl. Abschnitt 9.1.4), da in dieser Gruppe das diskrete Logarithmen-
problem mit dem euklidischen Algorithmus leicht gelöst werden kann. In der
Gruppe Z — hingegen ist das Verfahren sehr rechenaufw¤ndig, da die Primzahl p
p
von der Größenordnung 1024 Bit zu w¤hlen ist.
Im vorliegenden Kapitel führen wir elliptische Kurven ein. Das sind algebrai-
sche Kurven, die eine Gruppenstruktur tragen. Soweit bisher bekannt ist, hat
das ElGamal-Verschlüsselungsverfahren auf elliptischen Kurven zwei wesentli-
che Vorteile:

• Das diskrete Logarithmenproblem ist im Allgemeinen schwer zu lösen.

• Man kann ef¬zient rechnen und kommt mit kleinen Schlüssell¤ngen aus.

Die Gruppen scheinen also gut für die Praxis geeignet. Das ElGamal-Verfahren
auf elliptischen Kurven ist die bisher wohl bestuntersuchte und auch bestens
funktionierende Alternative für das RSA-Verfahren.
Um elliptische Kurven einführen zu können, ist ein Blick in die projektive Geome-
trie nötig. Wir führen die projektive Ebene PG(2, F) über einem beliebigen Körper
F ein. Dabei gehen wir vom dreidimensionalen Vektorraum F3 aus. Wir erkl¤ren
die eindimensionalen Untervektorr¤ume im F3 als Punkte und die zweidimen-
sionalen Untervektorr¤ume im F3 als Geraden. Die Punktmenge E einer ellip-
tischen Kurve wird aus der Nullstellenmenge eines homogenen Polynoms vom
Grad 3 gewonnen. Durch die Wahl einer unendlich fernen Geraden U in PG(2, F)
zerf¤llt E in einen af¬nen Teil und den unendlich fernen Punkt O = U © E. Wir de-
¬nieren auf der Punktmenge E eine Verknüpfung +, indem wir zeigen, dass jede
Gerade, die E in mindestens zwei Punkten schneidet, mit E genau drei Schnitt-
punkte hat (wobei Vielfachheiten zu berücksichtigen sind). Die Verknüpfung ist “
etwas salopp formuliert “ so gemacht, dass die Summe dieser drei Schnittpunkte
das neutrale Element O ergibt. Dabei ist O der unendlich ferne Punkt.
In diesem Kapitel bezeichne F stets einen Körper.



13.1 Projektive Ebenen
Af¬ne Ebenen wurden bereits im Abschnitt 5.3.1 eingeführt. Im Folgenden betra-
chen wir projektive Ebenen und den Zusammenhang zu ihren af¬nen Verwandten.
220 13 Elliptische Kurven *

13.1.1 De¬nition projektiver Ebenen
Es sei P eine Menge, und G sei eine Menge von Teilmengen von P, d. h. G ⊆
Pot(P ). Das Paar (P, G) heißt projektive Ebene, falls die folgenden drei Bedin-
gungen erfüllt sind:

(P1) Zu je zwei Punkten P, Q ∈ P mit P = Q existiert genau eine Gerade G ∈ G
mit P, Q ∈ G.

(P2) Für je zwei Geraden G, H ∈ G gilt |G © H| = 1 (d. h. zwei verschiedene
Geraden schneiden sich in genau einem Punkt).

(P3) Es gibt vier Punkte, von denen je drei nicht auf einer Geraden liegen.

Für die nach (P1) eindeutig bestimmte Gerade G durch P und Q schreiben wir
G = P, Q. Die Menge P nennt man die Punktmenge und die Menge G die Gera-
denmenge der projektiven Ebene (P, G).
Der wesentliche Unterschied zu den af¬nen Ebenen ist offensichtlich: In einer af-
¬nen Ebene gibt es Geraden, die sich nicht schneiden, in einer projektiven Ebene
nicht “ es gibt keine Parallelen. Bevor wir zu den Zusammenh¤ngen zwischen
projektiven und af¬nen Ebene kommen, konstruieren wir die für uns wesentli-
che Klasse von Beispielen projektiver Ebenen “ die projektive Koordinatengeometrie
über einem (beliebigen) Körper F.


Die projektive Ebene PG(2, F)
13.1.2

Es sei F3 der (gewöhnliche) dreidimensionale F-Vektorraum über dem Körper F.
Wir erkl¤ren auf der Menge F3 \ {0} eine „quivalenzrelation. Für a, b ∈ F3 \ {0}
setzen wir:
a ∼ b : ” ∃ » ∈ F \ {0} mit » a = b .
Für die „quivalenzklasse von a bzgl. ∼ schreibt man [a] oder auch (a1 : a2 : a3 ),
falls a = (a1 , a2 , a3 ) ∈ F3 \ {0}.

Bemerkung
Nimmt man zu der „quivalenzklasse [a] noch den Nullvektor (0, 0, 0) dazu, so
erh¤lt man den eindimensionalen Untervektorraum F a.
Nun betrachten wir die Quotientenmenge:

P := (F3 \ {0})/ ∼ = [a] ; a ∈ F3 \ {0} .

Für zwei verschiedene Punkte P = Q ∈ P, etwa P = [a], Q = [b], setzen wir

P, Q := {[» a + μ b] ; », μ ∈ F, (», μ) = (0, 0)} .

Mit der Wahl » = 1 und μ = 0 bzw. » = 0 und μ = 1 folgt sofort P, Q ∈ P, Q.
13.1 Projektive Ebenen 221

Die Menge P, Q heißt Verbindungsgerade von P, Q. Wir bilden nun die Menge
s¤mtlicher Verbindungsgeraden durch jeweils zwei verschiedene Punkte:

G := P, Q ; P, Q ∈ P, P = Q .
Die Geraden in G können wir mithilfe zweidimensionaler Untervektorr¤ume be-
schreiben. Den Punkten auf der Geraden P, Q entsprechen genau diejenigen ein-
dimensionalen Untervektorr¤ume, die im zweidimensionalen Untervektorraum
F a + F b als Teilmengen enthalten sind. Dabei beachte man, dass die Bedingung
P = Q für P = [a] und Q = [b] gleichwertig zur linearen Unabh¤ngigkeit der
Vektoren a, b ∈ F3 ist. Etwas formaler ausgedrückt:

[c] ∈ [a], [b] ” F c ⊆ F a + F b ” c ∈ F a + F b.
Aus der linearen Algebra ist die Koordinatendarstellung für Hyperebenen von
Vektorr¤umen bekannt. Auf unseren Fall angewendet, kann man jeden zweidi-
mensionalen Untervektorraum in F3 als Lösungsmenge einer linearen Gleichung
(genauer: als Nullstellenmenge einer Linearform) beschreiben. Übertragen auf
Geraden in der projektiven Ebene bedeutet das für c = (c1 , c2 , c3 ):

[c] ∈ [a], [b] ” u1 c1 + u2 c2 + u3 c3 = 0
für ein u = (u1 , u2 , u3 ) ∈ F3 \ {0}. Es wird h¤u¬g nützlich sein, Geraden auf
diese Weise darzustellen.

Lemma 13.1
Es ist (P, G) eine projektive Ebene.

Beweis. Wir haben zu zeigen, dass die Bedingungen (P1), (P2) und (P3) gelten.
(P1) Die Existenzaussage ist klar, die Eindeutigkeit folgt aus (P2).
(P2) Es seien G, H ∈ G, G = H. Es gibt linear unabh¤ngige (a, b, c), (a , b , c ) ∈
F3 mit:

G = {(x : y : z) ∈ P ; a x + b y + c z = 0} und
H = (x : y : z ) ∈ P ; a x + b y + c z = 0 .

Es folgt

G © H = (x : y : z) ∈ P ; a x + b y + c z = 0 und a x + b y + c z = 0 .

Dieses lineare Gleichungssystem hat als Lösungsmenge einen eindimensionalen
Untervektorraum. Dieser de¬niert einen Punkt in P. Folglich gilt |G © H| = 1.
(P3) Die vier verschiedenen Punkte (1 : 0 : 0), (0 : 1 : 0), (0 : 0 : 1), (1 : 1 : 1)
erfüllen die geforderte Bedingung.
Es heißt
PG(2, F) := (P, G)
die projektive Ebene über F.
222 13 Elliptische Kurven *

Bemerkung
Obwohl der unterliegende Vektorraum F3 dreidimensional ist, schreiben wir
PG(2, F), weil diese Geometrie in einem pr¤zisierbaren Sinne zweidimensional ist.
Außerdem werden wir einen engen Zusammenhang mit AG(2, F) feststellen.

Für unsere Zwecke ist PG(2, F) das wichtigste Beispiel einer projektiven Ebene.
Wir zeigen ein weiteres interessantes Beispiel.


Beispiel
Die kleinste projektive Ebene besteht aus sieben Punkten.
Eine Veranschaulichung ¬ndet man in der nebenstehenden
Skizze. Die sieben Geraden enthalten je drei Punkte (auch
der Kreis ist eine Gerade!).


13.1.3 Jede projektive Ebene liefert viele af¬ne Ebenen

Wenn wir aus der Punktmenge P einer projektiven Ebene eine (beliebige) Gerade
U entfernen und auch aus jeder Geraden die U zugehörigen Punkte entfernen, so
erhalten wir eine af¬ne Ebene (vgl. die De¬nition auf Seite 87). Das ist der Inhalt
des folgenden Lemmas.


Lemma 13.2
Es seien (P, G) eine projektive Ebene und U eine Gerade, d. h. U ∈ G. Wir setzen

PU := P \ U , GU := {G © PU ; G ∈ G \ {U}} = {G \ U ; G ∈ G \ {U}} .

Dann ist (PU , GU ) eine af¬ne Ebene.


Beweis. (A1) folgt direkt aus (P1).
(A2) Es seien G ∈ GU und G ∈ G mit G = G \ U. Für P ∈ PU \ G. Setze

Q := G © U H := P Q \ U ∈ GU .
und

Es gilt dann P ∈ H, G © H = …. Jede andere Gerade hat wegen (P2) mit G einen
Schnittpunkt, der in PU liegt.
Nach Aufgabe 13.1 hat jede Gerade in (P, G) mindestens drei Punkte, daher hat
jede Gerade in (PU , GU ) mindestens zwei Punkte.
(A3) siehe Aufgabe 13.2.

<< . .

. 28
( : 33)



. . >>