PD Dr. Martin Kreuzer Regensburg, den 3.7.2000 Fakultät für Mathematik Universität Regensburg

Übungen zur Vorlesung “Kryptographie”

Blatt 6

(Abgabetermin: 13.7.2000)

Aufgabe 26. Gegeben sei ein Körper K und eine kubische Kurve über K mit der Gleichung y^{2} + a_{1}xy + a_{3}y = x^{3} + a_{2}x^{2} + a_{4}x + a_{6}. Zeigen Sie, daß diese Gleichung durch eine lineare Koordinatentransformation auf die folgende Gestalt gebracht werden kann:

a) y^{2} = x^{3} + ax + b (mit a, b ∈ K), falls char(K) ∉ {2, 3} gilt,

b) y^{2} = x^{3} + ax^{2} + bx + c (mit a, b, c ∈ K und ab = 0), falls char(K) = 3 gilt, und c) y^{2} + ay = x^{3} + bx + c oder y^{2} + xy = x^{3} + dx^{2} + e (mit a, b, c, d, e ∈ K), falls

char(K) = 2 gilt.

Aufgabe 27. Gegeben sei der folgende Satz:

Drei Geraden G_{1}, G_{2}, G_{3} mögen eine kubische Kurve C in neun Punkten P_{1}, …, P_{9} schneiden. Schneiden drei weitere Geraden H_{1}, H_{2}, H_{3} die Kurve C dann ebenfalls in neun Punkten Q_{1}, …, Q_{9} und gilt P_{i} = Q_{i} für i = 1, …, 8, so folgt P_{9} = Q_{9}.

Verwenden Sie diesen Satz, um das Assoziativgesetz für die Addition von Punkten auf einer elliptische Kurve zu beweisen. (Hinweis: Behandeln Sie zuerst den Fall, daß einer der drei Punkte der unendlich ferne Punkt ist.)

Aufgabe 28. Sei K = ℚ oder K = ℤ/pℤ mit p ∉ {2, 3}.

a) Schreiben Sie eine CoCoA Funktion EllipticPoint(…), die ausgehend von den Parametern a, b ∈ K einer elliptischen Kurve E(K) über K einen Punkt (x, y) ∈ E(K) berechnet.

b) Entwerfen Sie einen Zero-Knowledge Beweis, bei dem Sie mit Hilfe des Feige-Fiat-Shamir Protokolls dem Übungsleiter beweisen können, daß Sie Teilaufgabe a) richtig gelöst haben, ohne daß Sie ihm das Programm verraten. Implementieren Sie die notwendigen CoCoA Funktionen für die Schlüsselerzeugung und die Anwendungsphase aus Ihrer Sicht und der des Übungsleiters.

Aufgabe 29. Gegeben sei eine Zahl e > 0 und der Körper K = 𝔽_{q} mit q = 2^{e}.

a) Zeigen Sie, daß die Abbildung Tr : 𝔽_{q} ⟶ 𝔽_{2} die gegeben ist durch Tr(x) = ∑_{i=0}^{e−1} x^{2^{i}} surjektiv und 𝔽_{2}-linear ist.

b) Beweisen Sie, daß die Gleichung y^{2} +y = x für ein gegebenes x ∈ 𝔽_{q} genau dann in 𝔽_{q} lösbar ist, wenn Tr(x) = 0 gilt. Tip: Genau die Hälfte der Elemente x ∈ 𝔽_{q} erfüllt Tr(x) = 0.

c) Finden Sie einen Algorithmus, wie man für x ∈ 𝔽_{q} mit Tr(x) = 0 ein y ∈ 𝔽_{q} mit y^{2} + y = x finden kann. Tip: Wählen Sie eine 𝔽_{2}-Basis von 𝔽_{q} und identifizieren Sie die Elemente x, y mit ihren Koordinatenvektoren.

d) Sei E(K) eine elliptische Kurve über K. Finden Sie einen probabilistischen Algorithmus, wie man einen Punkt von E(K) berechnen kann. Tip: Unterscheiden Sie die beiden Fälle von Aufgabe 26.c.

Aufgabe 30. Gegeben seien der Körper K = ℚ oder K = ℤ/pℤ mit p ∉ {2, 3} sowie eine elliptische Kurve E(K) über K mit Gleichung y^{2} = x^{3} + ax + b.

a) Schreiben Sie eine CoCoA Funktion EllipticAdd(…), die die Summe zweier Punkte von \overline{E}(K) berechnet. Der unendlich ferne Punkt O werde dabei durch den String "InfPoint" repräsentiert.

b) Verwenden Sie die Funktion aus a), um eine CoCoA Funktion EllipticMult(…) zu schreiben, die zu gegebenen n ∈ ℤ und P ∈ \overline{E}(K) den Punkt nP ∈ \overline{E}(K) berechnet. Tip: Berechnen Sie die Punkte 2^{i}P und gehen Sie wie bei “square-and-multiply” vor.

c) Implementieren Sie die verschiedenen Teile des ECDSA Signaturverfahrens. Arbeiten Sie dabei nur über einem Körper K = ℤ/pℤ mit einer Primzahl p. Schreiben Sie dazu CoCoA Funktionen ECKeyGen(…), ECSign(…) und ECVerifiy(…).