Elliptische Kurven: die Mathematik in deiner Tasche

Das hier ist die Gleichung y² = x³ − x + 1. Zeichnest du sie, bekommst du eine krumme Linie — eine elliptische Kurve. Das klingt nach etwas aus einem Mathebuch, an das du nie wieder denkst. Aber genau diese Art Linie steckt im Chip deiner Identitätskarte, hinter dem Schloss-Symbol in deinem Browser und unter Bitcoin. In diesem Kapitel klickst du darauf und siehst, warum.

Wörter, die du gleich brauchst

Kurve: Einfach eine krumme Linie in einem Graphen: alle Punkte (x, y), für die eine Gleichung stimmt. Eine Parabel ist eine Kurve. Diese hier ist eine etwas spannendere.
Punkte addieren: Das ist die verrückte Idee. Auf dieser Kurve kannst du zwei Punkte „addieren“ und bekommst einen dritten Punkt auf derselben Kurve. Nicht indem du die Koordinaten zusammenzählst, sondern mit einer Zeichenregel: zieh eine Gerade durch die zwei Punkte, schau, wo sie die Kurve ein drittes Mal schneidet, und spiegle diesen Punkt an der x-Achse. Fertig: das ist P + Q.
Verdoppeln: P + P. Du hast nur einen Punkt, also nimmst du die Tangente — die Gerade, die die Kurve in P genau berührt — und machst denselben Trick.
Uhrenrechnen (Modulo): Rechnen mit lauter ganzen Zahlen von 0 bis zu einer Grenze, wobei du nach der Grenze wieder bei 0 anfängst. Kennst du aus Kapitel 5, wo es der Motor unter Diffie–Hellman war. Hier siehst du, was es mit einem Graphen macht.

Klick auf die Kurve

Alles passiert in deinem Browser. Es wird nichts an den Server geschickt.

Klick irgendwo auf die Linie. Das ist P. Klick ein zweites Mal für Q. Die Demo zieht die Gerade, findet den dritten Schnittpunkt, spiegelt ihn und zeigt P + Q.
Klick auf Löschen, wähl einen Punkt und drück auf Verdoppeln. Klick dann immer weiter auf Noch einmal P dazu: 3·P, 4·P, 5·P… Die Punkte springen über die ganze Kurve.
Schieb an a und b. Die Form ändert sich — manchmal zerfällt die Linie in zwei Stücke. Such die Stellung, in der sie einen Knick bekommt: die ist unbrauchbar, und die Demo sagt dir, warum.
Drück auf Uhrenrechnen (Modulo 97). Dieselbe Gleichung, nur ganze Zahlen. Schau, was von der Linie übrig bleibt. Wähl einen Punkt und addiere wieder.

a =

b =

Was du gerade gesehen hast

Auf der glatten Linie konntest du noch ein bisschen „spüren“, wo du warst. Nach dreimal Addieren bist du ungefähr dort, nach viermal ungefähr da. Aber sobald du auf Uhrenrechnen umgeschaltet hast, fiel die Linie auseinander in eine Wolke von Punkten ohne jedes Muster. Und das Addieren funktionierte immer noch — dieselben Formeln, dieselben Regeln — nur springt das Ergebnis jetzt kreuz und quer über die Fläche.

Jetzt das ganze Geheimnis. Sagen wir, ich wähle einen Punkt P und addiere ihn 1 000 000 Mal zu sich selbst. Das schafft ein Computer blitzschnell — es gibt einen Trick, mit dem das nur rund dreißig Schritte kostet. Ich gebe dir P und den Endpunkt. Kannst du herausfinden, dass es 1 000 000 Mal war? Bei der Punktwolke mit 97 schon: du probierst sie einfach alle durch. Aber die Kurve in deiner Identitätskarte hat ungefähr 2³⁸⁴ Punkte. Diese Zahl hat 116 Ziffern. Die probiert niemand durch, auch kein Supercomputer, auch nicht in einer Milliarde Jahre.

Das ist der private Schlüssel: die Anzahl der Male. Der öffentliche Schlüssel ist der Endpunkt. Jeder darf den Endpunkt sehen; niemand kann zurückzählen. Genau das offene Vorhängeschloss aus dem vorigen Kapitel — nur mit einem Graphen statt mit Primzahlen.

Warum Kurven und nicht einfach RSA

	RSA (Primzahlen)	Elliptische Kurven
Gleich sicher bei	einem Schlüssel von 3072 Bit	einem Schlüssel von 256 Bit
Das ist	eine Zahl mit 925 Ziffern	eine Zahl mit 78 Ziffern
Passt auf eine Chipkarte?	mit Mühe	locker
Erfunden	1977	1985, von Neal Koblitz und Victor Miller, unabhängig voneinander

Zwölfmal kürzere Schlüssel für dieselbe Sicherheit. Darum steigt die Welt um: die neuesten belgischen Identitätskarten benutzen eine Kurve (mit dem Namen P-384), ältere Karten noch RSA. Das Schloss-Symbol in deinem Browser handelt den Schlüssel mit einer Kurve aus. Bitcoin-Adressen sind Punkte auf einer Kurve.

Die Regel für a und b. Beim Schieben hast du gesehen, dass manche Stellungen einen Knick oder eine Schleife geben. Mathematisch: wenn 4a³ + 27b² = 0, ist die Kurve „ausgeartet“ und das Addieren funktioniert nicht mehr überall. Kryptografen wählen a und b also mit Sorgfalt — und sie veröffentlichen sie, damit jeder nachprüfen kann, dass keine geheime Schwäche darin versteckt ist. Dieses Misstrauen ist ein Fach für sich.

Das ist Mathematik: eine Gruppe

Was du gerade gemacht hast — Punkte mit einer Zeichenregel „addieren“ — hat alle Eigenschaften des gewöhnlichen Addierens. Es ist assoziativ: (P + Q) + R = P + (Q + R), auch wenn du das nicht sofort siehst. Es gibt eine „Null“ (den Punkt im Unendlichen, dem du begegnet bist, als die Gerade senkrecht wurde). Jeder Punkt hat ein Gegenstück (sein Spiegelbild). Mathematiker nennen so eine Menge mit so einer Rechenregel eine Gruppe. Das ist das erste Kapitel der abstrakten Algebra, des Fachs, in dem du lernst, dass Zahlen, Drehungen eines Würfels und Punkte auf einer Kurve tief drinnen dasselbe Spiel spielen. Es steht im ersten Jahr jedes Mathematikstudiums an der Uni — und genau dieses Spiel schützt deine Identitätskarte.