Kryptographie X

Verschlüsselung mit elliptischen Kurven.

Klassische Verschlüsselungsverfahren arbeiten so, daß die “Botschaften” (d.h. ihre einzelnen Bits) durch Zahlen dargestellt und diese Zahlen dann verschlüsselt werden. Statt mit Zahlen kann man aber auch mit Punkten elliptischer Kurven arbeiten (und dies wird in vielen praktischen Anwendungen auch wirklich gemacht).

Beispiele elliptischer Kurven sind unten abgebildet.

Nehmen wir einmal das linke Beispiel, also die Kurve aus allen Paaren (x,y) mit y²=x³-x. Am Schluß von Teil 9 hatten wir gezeigt, wie man auf geometrische Weise eine “Addition” von Punkten elliptischer Kurven definieren kann. Für diese “Addition” kann man (mit ein wenig Rechnen) natürlich auch eine Formel hinschreiben. (Zu finden in jedem Lehrbuch über elliptische Kurven.)

Jetzt könnte man verschlüsseln, indem man die Elemente der zu verschlüsselnden Nachricht (d.h. die einzelnen Bits) auf irgendeine Weise den Punkten unserer Kurve zuordnet und dann die Verschlüsselungsfunktion P–>nP anwendet. (n ist irgendeine fest gewählte Zahl. Mit nP ist natürlich P+P+…+P, also die Summe aus n Summanden gemeint.)

Der Punkt, warum diese Verschlüsselungsfunktion sicher ist: Die Verschlüsselungsfunktion P–>nP ist leicht zu berechnen, die Entschlüsselung nP–>P deutlich schwerer. Deshalb sind elliptische Kurven für Verschlüsselungsverfahren grundsätzlich geeignet.

Das Problem bei den oben abgebildeten Kurven ist aber, das man hier mit reellen Zahlen rechnen müßte, und beim Rechnen mit reellen Zahlen sind Rundungsfehler unvermeidlich. Außerdem kann man die Kurve nicht ‘als Ganzes’ im Computer abspeichern, weil sie ja unendlich viele Punkte hat. (Nachtrag: es gibt noch einen wichtigeren Grund, warum in der Kryptographie keine über den reellen oder komplexen Zahlen definierten elliptischen Kurven benützt. Für eine komplexe elliptische Kurve könnte man nämlich die Parametrisierung durch die Weierstrass’sche p-Funktion benutzen, um diskrete Logarithmen von Punkten zu berechnen und damit die Verschlüsselung zu knacken. Über R oder C ist Verschlüsselung mit elliptischen Kurven also leicht zu knacken.)

Man arbeitet deshalb in der Kryptographie nicht mit elliptischen Kurven, deren Koordinaten (x,y) reelle Zahlen sind, sondern man nimmt als Koordinaten (x,y) Restklassen. Das heißt man nimmt sich irgendeine Primzahl p, und rechnet dann mit Resten modulo dieser Primzahl p. (Rechnen mit Restklassen kam in Teil 7 vor, eine ausführlichere Erklärung findet man hier.)

Im Bild unten ist p=389 und man hat die elliptische Kurve mit der Gleichung

Die Anzahl der Punkte einer solchen Kurve ist übrigens “ungefähr” p+1. (“Ungefähr” heißt: die Anzahl unterscheidet sich von p+1 um höchstens 2 mal die Wurzel aus p. Das ist der Satz von Hasse.)

In der Praxis verwendet man z.B. elliptische Kurven mit 2²⁵⁶ Punkten. (Wegen dem Satz von Hasse muß man also p in dieser Größenordnung wählen.) Um dieselbe Sicherheit nicht mit elliptischen Kurven, sondern einfach mit dem üblichen Restklassen-Rechnen oder mit RSA zu erreichen, müßte man mit viel größeren Zahlen rechnen.

Um das Prinzip an einem sehr einfachen Beispiel zu veranschaulichen, nehmen wir mal die Kurve y²=x³+3x+2 über den Restklassen modulo 23. Zum Beispiel gehört dazu der Punkt (0,5) wegen 5²=2 mod 23 oder der Punkt (4,3) wegen 3²=78 mod 23. Eine Auflistung der 28 Punkte findet man hier.
Wenn wir nun einen deutschen Text verschlüsseln wollen, dann identifizieren wir die 28 Symbole des deutschen Alphabets (ich meine die 26 Buchstaben, Punkt und Leerzeichen) mit den 28 Punkten dieser elliptischen Kurve, zum Beispiel in der in der verlinkten Liste angegebenen Reihenfolge, also A entspricht (0,5), B entspricht (0,18), …, H entspricht (4,20), …, Z entspricht (20,9), Punkt entspricht (20,14) und das Leerzeichen entspricht dem Punkt im Unendlichen.
Und wenn wir jetzt etwa als Verschlüsselungsfunktion P–>2P, also n=2, gewählt haben, dann wird also jeweils der P entsprechende Buchstabe mit dem 2P=P+P entsprechenden Buchstaben verschlüsselt.
Zum Beispiel ist (0,5)+(0,5)=(4,20), also wird A durch H verschlüsselt.

(Das Beispiel war jetzt natürlich nicht praxisnah. Erstens werden in praktischen Anwendungen nicht Buchstaben, sondern Blöcke von Bits verschlüsselt. Zweitens werden in realen Anwendungen elliptische Kurven mit wesentlich mehr Punkten verwendet. Bei nur 28 Punkten wäre die Entschlüsselung notfalls auch durch brachiales Probieren machbar. Mit Computer-Hilfe eine Sache von Sekunden-Bruchteilen. Aber wir wollten ja auch nur das Prinzip veranschaulichen.)

Wie gesagt, was elliptische Kurven für die Kryptographie brauchbar macht ist, daß es zwar leicht ist, aus der Kenntnis von P Vielfache wie 2P, 3P, 4P usw. zu berechnen. Umgekehrt wäre es aber sehr schwierig, aus der Kenntnis von 3P jetzt P zurückzuberechnen. Hacker-Algorithmen, die Elliptische-Kurven-Kryptographie angreifen, müssen also versuchen, aus nP wieder P zurückzuberechnen. Solche Hacker-Algorithmen gibt es tatsächlich, sie funktionieren aber immer nur für sehr spezielle elliptische Kurven. Aktuelle Forschung in der Elliptische-Kurven-Kryptographie untersucht deshalb vor allem auch die Frage, welche elliptische Kurven mit den bekannten Hacker-Algorithmen nicht geknackt werden.

Teil 1, Teil 2,Teil 3, Teil 4, Teil 5, Teil 6, Teil 7, Teil 8, Teil 9