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 6, 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: da sind es nur rund hundert Punkte, und 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.

Alles durchprobieren ist übrigens nicht einmal der schlaueste Angriff. Es gibt eine Abkürzung, 1978 von John Pollard gefunden, die ungefähr die Quadratwurzel der Anzahl Punkte braucht: rund 2¹⁹² Schritte. Diese Zahl hat immer noch 58 Ziffern, und auch das schafft niemand. Kryptografen rechnen immer mit der besten Abkürzung, die sie kennen, nie mit Durchprobieren. Das wird gleich noch wichtig.

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.

Wie viele Punkte? Man könnte meinen: modulo 97, also 97 Punkte. So funktioniert es nicht. Beim Uhrenrechnen zählt die Demo sie für dich. Mit a = −1 und b = 1 sind es zufällig genau 97, plus der Punkt im Unendlichen: 98. Geh zurück zur glatten Linie, verschieb a oder b und schalte wieder um: dann sind es zum Beispiel 80, 106 oder 117. Erraten kannst du die Zahl nicht, aber weit weg von 97 ist sie nie. Helmut Hasse hat 1933 bewiesen, dass sie immer höchstens 2√p von p + 1 entfernt ist; bei 97 also zwischen 79 und 117. Bei P-384 ist die Anzahl der Punkte genau bekannt, und sie ist selbst eine Primzahl. Das ist kein Zufall: die Kurve wurde danach ausgesucht.

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
Bester bekannter Angriff braucht	rund 2¹²⁸ Schritte	rund 2¹²⁸ Schritte
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. Das heißt nicht, dass RSA schlecht gebaut ist. „Gleich sicher“ heißt: der beste bekannte Angriff braucht auf beiden Seiten gleich viele Schritte. Gegen RSA haben Angreifer seit Anfang der 1990er-Jahre ein raffiniertes Werkzeug, das Zahlkörpersieb, das viel schneller zerlegt als Durchprobieren. Gegen eine gut gewählte Kurve hat niemand so etwas gefunden; Pollards Abkürzung ist dort immer noch das Beste, was es gibt. RSA muss also größere Zahlen nehmen, damit der Angreifer gleich viel Arbeit hat.

Darum steigt die Welt um: die neuesten belgischen Identitätskarten benutzen eine Kurve (mit dem Namen P-384), ältere Karten noch RSA. P-384 liegt eine Stufe über der Tabelle: rund 2¹⁹² Schritte. Mit RSA bräuchtest du dafür 7680 Bit, eine Zahl mit 2312 Ziffern. Das Schloss-Symbol in deinem Browser handelt den Schlüssel mit einer Kurve aus. Dein Bitcoin-Schlüssel ist ein Punkt auf einer Kurve; die Adresse, die du weitergibst, ist der Fingerabdruck dieses Punktes (siehe Kapitel 3).

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 dieses Spiel reicht viel weiter als Geheimschrift. Die Züge eines Zauberwürfels bilden eine Gruppe, mit über 43 Trillionen Stellungen. Chemiker ordnen Moleküle nach ihrer Symmetriegruppe und sagen damit voraus, welches Licht ein Molekül schlucken kann. Es gibt genau 230 Arten von Symmetrie, die ein Kristall haben kann; abgezählt wurde das 1891, mit Gruppentheorie. Physiker bauen ihre Beschreibung der kleinsten Teilchen, das Standardmodell, auf Gruppen. Und der QR-Code auf einem Konzertticket lässt sich noch lesen, wenn eine Ecke fehlt, dank Algebra mit endlich vielen Zahlen, genau wie hier. Kryptografie ist nur eine Ecke dieser Welt.

Aber Achtung: die Gruppe selbst macht deine Identitätskarte nicht sicher. Gruppen sind überall, und die meisten taugen nicht für Geheimnisse. Uhrenrechnen mit gewöhnlichem Addieren ist auch eine Gruppe, und dort rechnest du mit einer einzigen Division zurück. Die Sicherheit hängt an einer einzigen Frage über diese eine Gruppe, auf die niemand eine schnelle Antwort gefunden hat: wie oft wurde P addiert? Dass es schwer aussieht, ist kein Beweis. Es ist eine Annahme, die seit über vierzig Jahren hält.

Merk übrigens, was du hier nicht gebraucht hast. Um zu verstehen, warum RSA schwer zurückzurechnen ist, musst du erst etwas über Primzahlen und das Zerlegen in Faktoren wissen, und das ist ein Fach für sich. Hier genügte eine Gerade, die eine Kurve schneidet. Kryptografen sagen deshalb oft, dass Kurven für Anfänger sogar leichter zu fassen sind als RSA: die Schwierigkeit steckt nicht versteckt in der Mathematik darunter, sie liegt offen auf dem Tisch. Dass du zuerst Kapitel 7.1 gelesen hast und dieses Kapitel danach, ist also historische Reihenfolge, keine Reihenfolge der Schwierigkeit.