Skip to main content


Zutaten: Zucker, Kakaomasse (50%), Milchzucker, Weizenmehl, Vollmilchpulver, Magermilchpulver, Butterreinfett, Sahnepulver, Butter (1,4%)
Kann Spuren von Analysis und Geometrie enthalten.

37-titel_moskwa

Wie funktionieren Elliptic Curves an der Moskwa?

Rike und Max sind in Moskau. Sie sind durch die Stadt gelaufen, vom Roten Platz bis zum Gorki-Park. Hier, an der Moskwa, haben sie Antonija kennengelernt. Antonija studiert Mathe an der MGU (Moskauer Staatlichen Universität). Mit Blick auf deren Handys erklärt ihnen Antonija die Standard-Verschlüsselungstechnologien.

Max Meine Sorge ist immer, dass man wahnsinnig viel programmieren muss und eine andere Sprache spricht, man ist ein Nerd   o d e r   normal, damit du so was verstehst?

Antonija Haha, Handys finden doch alle faszinierend. Meine Eltern sind Mathematiker. Die wundern sich, wie sich die Technologien und die Mathematik geändert haben. Früher war die Entscheidung Mathe oder IT, jetzt geht das nicht mehr. In modernen Verfahren kommt alles zusammen. Wir haben Vorlesungen zu algebraischen Algorithmen und Zahlentheorie. Trudno, trudno, ich muss das verstehen, ich will später selbst eine Firma aufmachen.

Rike Dann kannst du uns doch die Elliptic Curves erklären? Vielleicht nicht so technisch, eher geometrisch?

Das Wesen von RSA

Antonija Klar. Ihr kennt doch RSA?

Rike Ja, Rechnen mit Restklassen, aus \(n\) haben wir \(\bar{n}\) bestimmt:

\(n \rightarrow \bar{n} = n^a\),

und es gibt einen inversen Algorithmus

\(\bar{n} \rightarrow \bar{n}^b=n,\)

und \(b\) ist das Inverse zu \(a\) (in einem geeigneten Raum)

\(a \cdot b = 1\)

Beispiele von Elliptic Curves

Antonija Prawilno, choroscho! Bei den Elliptic Curves gibt es viel mehr Möglichkeiten als bei RSA. Bei RSA kannst du nur den Restklassenring \(Z_N\) wählen, also geeignete Zahlen \(N\) und \(a\). Jetzt kannst du zuerst eine elliptische Kurve wählen, nehmen wir mal eine Normalform, die Weierstraß-Schreibweise:

\(E: y^2 = x^3 + ax + b\)

elliptic-curve_03

elliptic curve 05

elliptic curve 06

elliptic curve 01

Rike Also \(a\) und \(b\)?

Antonija Ja, wenn du willst, kannst du \(a, b, x, y\) aus geeigneten Bereichen wählen, einem Restklassenkörper \(Q_p\) oder aus den reellen Zahlen oder \(a, b\) ganz und \(x, y\) komplex usw.

Rike Und weiter. Wie rechnest du aus Etwas etwas Neues aus?

Ein "Rechengesetz" für Punkte auf Elliptic Curves

Antonija Das geht so: Du kannst Punkte

\(P=(x_P, y_P), Q=(x_Q, y_Q)\)

auf der Kurve \(E\) auswählen. Sehr viele! Zwischen beiden kannst du eine sinnvolle Verknüpfung erklären, ich schreibe jetzt einfach mal das \(+\) dafür, es ist aber nicht die Vektoraddition!

Rike Ok, also was ist

\(P+Q\)?

Antonija Du verbindest beide mit einer Geraden \(g\), und den Schnittpunkt von \(g\) mit \(E\) spiegelst du an der \(x\)-Achse.

Die Summe \(P+Q\)

Das Inverse

Rike Ok, und das Inverse, das Negative von \(P\)?

Antonija Das geht so: \(-P\) ist die Spiegelung an der \(x\)-Achse.

Das Negative (Inverse) \(-P\) zum Punkt \(P\)

Rike Wenn ich

\(P+(-P)\)

bestimmen will, krieg' ich keinen Schnittpunkt mit E!?

Antonija Hey, du bist ja smart! Zu \(E\) nehmen wir den Punkt O dazu, der ist überall, wo \(y=+\infty\) oder \(y=-\infty\) ist.

Rike Ok, dann schneidet \(g\) den Punkt O, O spielt die Rolle der Null bei der Addition, stimmts?

Antonija Klebo! So ist

\(P+(-P) = O\),

und \(-P\) das Inverse zu \(P\).

Ein Spezialfall der Verknüpfung

Rike Und wie geht

\(P+P\),

da habe ich Probleme, die Gerade \(g\) durch zwei identische Punkte zu legen.

Antonija Für

\(P+P=2P\)

legt man die Tangente an \(E\) in \(P\), du suchst den Schnittpunkt mit \(E\) und spiegelst ihn dann.

Die Konstruktion von \(2P\)

Ihr seht doch, das das stimmig ist, also

\(P+Q \rightarrow P+P\), wenn \(Q \rightarrow P\)

geht.

Fazit

Max Hmm, \(2P\) hat auf deiner Zeichnung sehr wenig mit \(P\) zu tun!

Antonija Stimmt, es ist nicht die Vektoraddition. Wenn du \(P\) nicht kennst, hast du Probleme, aus \(2P\) wieder \(P\) zu bestimmen, aber noch schwieriger ist es, aus \(P+Q\) wieder \(P\) zu bestimmen.

Rike Ok, jetzt weiß ich eigentlich alles, danke!

Max Ich suche \(E\) aus, Rike wählt \(P\) und Antonija programmiert den Algorithmus.

* * *

Konstruktive Berechnungsvorschriften

Für das Negative (Inverse):

\(-P:= (x_P , -y_P)\)

Für die Summe:

\(R:=-(P+Q)=(x_R, y_R)\)

mit

\(x_R:=s^2-x_P-x_Q\)

\(y_R:=y_P+s(x_R-x_P)\)

\(s:=\frac{y_P-y_Q}{x_P-x_Q}\)

Für das Doppelte:

\(R:=-2P=(x_R, y_R)\)

mit

\(x_R:=s^2-2x_P\)

\(y_R:=y_P + s(x_R-x_P)\)

\(s:=\frac{3x_P^2+a}{2y_P}\)

Übungsaufgabe

Bestimme geometrisch und rechnerisch an Beispielen \(P+Q, -P\) und \(2P\).