Verschlüsseln mit elliptischen Kurven
Elliptische Kurven bilden die Grundlage für moderne asymmetrische Kryptografie. Mathematisch sind sie verhältnismäßig komplex, aber ihre Funktionsweise lässt sich dennoch anschaulich erklären. Wie also funktionieren sie?
- Golo Roden
Elliptische Kurven bilden die Grundlage für moderne asymmetrische Kryptografie. Mathematisch sind sie verhältnismäßig komplex, aber ihre Funktionsweise lässt sich dennoch anschaulich erklären. Wie also funktionieren sie?
Elliptische Kurven sind mathematische Funktionen, die eine bestimmte Form aufweisen. Die größte Besonderheit ist, dass der Funktionswert als Quadrat dargestellt wird, was dazu führt, dass sich eine elliptische Kurve symmetrisch zur X-Achse verhält. Die grundlegende Form lautet:
y^2 = x^3 + a*x + b
In gewissem Sinne ähnelt eine elliptische Kurve einem Polynom dritten Grades, durch das Quadrat von y verhält sich die Kurve allerdings ganz anders. Dennoch gibt es Ähnlichkeiten zu Polynomen, so stellen beispielsweise die Faktoren a und b die Koeffizienten der Kurve dar. Ihre Wahl bestimmt die grundlegende Form der Kurve.
Eine Besonderheit ergibt sich, wenn man beide Koeffizienten auf den Wert 0 setzt – in diesem Fall enthält die Kurve nämlich einen Knick im Nullpunkt des Koordinatensystems, weshalb man in diesem Fall von einer Singularität spricht (und es sich auch nicht mehr um eine Kurve im eigentlichen Sinne handelt).
Empfohlener redaktioneller Inhalt
Mit Ihrer Zustimmmung wird hier ein externes YouTube-Video (Google Ireland Limited) geladen.
Ich bin damit einverstanden, dass mir externe Inhalte angezeigt werden. Damit können personenbezogene Daten an Drittplattformen (Google Ireland Limited) übermittelt werden. Mehr dazu in unserer Datenschutzerklärung.
Rechnen auf elliptischen Kurven
Wählt man zwei beliebige Punkte P und Q auf einer elliptischen Kurve, kann man diese mit einer Geraden verbinden. Diese Gerade hat die Eigenschaft, dass sie die Kurve in einem dritten Punkt schneidet. Spiegelt man diesen Punkt wiederum an der X-Achse, erhält man einen Punkt, der die Summe der beiden ursprünglichen Punkte darstellt. Auf diesem Weg (eine Gerade ziehen und spiegeln) lässt sich die Summe zweier beliebiger Punkte ermitteln.
Dieser Vorgang lässt sich nun wiederholen: Sucht man einen weiteren zufälligen Punkt R, verbindet R anschließend mit dem Punkt P+Q und spiegelt dann erneut, dann erhält man als Ergebnis die neue Summe (P+Q)+R. Dieses Verfahren kann man nun beliebig fortführen, um die Summe stets um einen weiteren Punkt zu ergänzen.
Da es unpraktisch ist, sich ständig neue Punkte suchen zu müssen, gibt es eine vereinfachte Variante dieses Verfahrens. Bewegt man P und Q zu Beginn nämlich aufeinander zu, bis sie übereinander liegen, kann man auf Q verzichten. Statt eine Gerade durch zwei Punkte zu ziehen, führt man nun die Tangente an P ein – auch sie wird die elliptische Kurve wieder in einem weiteren Punkt schneiden, den man anschließend spiegeln kann.
Das Ergebnis ist die Summe von P mit sich selbst, also P+P oder 2P. Verbindet man nun 2P wieder mit P, erhält man einen weiteren Schnittpunkt, den man wiederum spiegeln kann, und erhält auf dem Weg 3P. Auch dieses Verfahren lässt sich nun endlos fortsetzen, um auch 4P, 5P, 6P oder schließlich NP zu konstruieren. Eine wichtige Frage lautet nun: Angenommen, P und NP sind gegeben, wie lässt sich dann N herausfinden?
Empfohlener redaktioneller Inhalt
Mit Ihrer Zustimmmung wird hier ein externes YouTube-Video (Google Ireland Limited) geladen.
Ich bin damit einverstanden, dass mir externe Inhalte angezeigt werden. Damit können personenbezogene Daten an Drittplattformen (Google Ireland Limited) übermittelt werden. Mehr dazu in unserer Datenschutzerklärung.
Schneller auf elliptischen Kurven rechnen
Die triviale Antwort lautet, dass man das durch Ausprobieren herausfindet: Man muss von P ausgehend lediglich so lange Summen bilden, bis man schließlich beim Punkt NP herauskommt – schon kennt man den Wert von N. Das Verfahren ist also für denjenigen, der NP konstruiert, genauso aufwendig wie für denjenigen, der N aus NP ermitteln möchte.
Allerdings gibt es eine Abkürzung zum Konstruieren von NP. Elliptische Kurven sind nämlich aus mathematischer Sicht nichts anderes als Gruppen, weshalb die Rechenregeln für Gruppen für sie gelten. Das bedeutet, dass man an Stelle von 3P+P beispielsweise auch 2P+2P rechnen kann und dabei zum gleichen Ergebnis 4P kommt.
Das kann man sich nun zunutze machen, um NP auch für große N effizient zu berechnen. Dazu konvertiert man N zunächst in die Binärdarstellung, aus 227 würde also beispielsweise 11100011. Das bedeutet, dass sich der Wert für 227P als
128P + 64P + 32P + 2P + P
berechnen lässt. Diese Werte wiederum lassen sich durch Verdoppeln mit logarithmischem Aufwand aus P bestimmen. Das beschleunigt die Berechnung von 227P dramatisch. Dieses Verfahren, das als "double and add" bekannt ist, lässt sich jedoch nicht ohne Weiteres umkehren: Um aus dem Punkt 227P zu ermitteln, dass N dem Wert 227 entspricht, ist deutlich höherer Aufwand erforderlich.
Dieses Ungleichgewicht kann man sich nun in der Kryptografie zunutze machen, denn letztlich handelt es sich bei der Addition auf elliptischen Kurven nun um eine Falltürfunktion: Während der Rechenweg in die eine Richtung sehr einfach ist, ist er in die andere Richtung sehr aufwendig. Tatsächlich handelt es sich bei dem genannten Problem um den "diskreten Logarithmus der elliptischen Kurven", was dem Grundproblem von RSA ähnelt.
Empfohlener redaktioneller Inhalt
Mit Ihrer Zustimmmung wird hier ein externes YouTube-Video (Google Ireland Limited) geladen.
Ich bin damit einverstanden, dass mir externe Inhalte angezeigt werden. Damit können personenbezogene Daten an Drittplattformen (Google Ireland Limited) übermittelt werden. Mehr dazu in unserer Datenschutzerklärung.
Elliptische Kurven für Verschlüsselung
Angenommen, Alice und Bob möchten verschlüsselt kommunizieren, einigen sie sich zunächst (öffentlich) auf eine gemeinsame elliptische Kurve, indem sie deren Koeffizienten festlegen. Außerdem wählen sie gemeinsam einen Startpunkt P. Anschließend wählen Alice und Bob jeweils im Geheimen ihren privaten Schlüssel A beziehungsweise B und berechnen daraus anschließend per "double and add" ihren jeweiligen öffentlichen Schlüssel AP und BP.
Alice gibt ihren öffentlichen Schlüssel AP nun an Bob, und Bob gibt seinen öffentlichen Schlüssel BP an Alice. Beide multiplizieren den öffentlichen Schlüssel des anderen nun mit ihrem eigenen privaten Schlüssel:
Alice: BP + BP + … + BP = BP * A
Bob: AP + AP + … + AP = AP * B
Da es sich bei elliptischen Kurven wie bereits erwähnt um Gruppen handelt, kann man P jeweils aus dem Ergebnis ausklammern. Auf dem Weg kommen Alice und Bob unabhängig voneinander auf den gleichen geheimen Punkt (AB)*P. Für einen Angreifer ist dieser geheime Punkt ohne Kenntnis mindestens eines privaten Schlüssels nicht einfach zu rekonstruieren.
Alice und Bob verschlüsseln ihre Nachricht nun symmetrisch, beispielsweise mit AES, und verwenden als Schlüssel schlichtweg die X-Koordinate des gemeinsam berechneten geheimen Punkts.
Obwohl das Verfahren aus mathematischer Sicht hervorragend funktioniert, weist es in der Praxis eine Schwäche auf: Die Koordinaten der Punkte werden sehr schnell sehr groß und übersteigen rasch den Wertebereich gängiger Datentypen. Das Gleiche gilt für die Nachkommastellen, weshalb es rasch zu Rundungsfehlern und Ungenauigkeiten kommt – womit Alice und Bob unter Umständen nicht mehr auf den gleichen geheimen Punkt kommen.
Empfohlener redaktioneller Inhalt
Mit Ihrer Zustimmmung wird hier ein externes YouTube-Video (Google Ireland Limited) geladen.
Ich bin damit einverstanden, dass mir externe Inhalte angezeigt werden. Damit können personenbezogene Daten an Drittplattformen (Google Ireland Limited) übermittelt werden. Mehr dazu in unserer Datenschutzerklärung.
Elliptische Kurven in der Praxis
Aus diesem Grund beschränkt man elliptische Kurven in der Praxis auf ganzzahlige Werte, indem man sie noch um eine Modulodivision durch eine Primzahl p ergänzt:
y^2 = x^3 + a*x + b mod p
Das Ergebnis ist dann keine Kurve mehr, sondern eine Punktewolke, wobei die Koordinaten der Punkt nun ganzzahlig und in überschaubarer Größe vorliegen. Die grundlegenden Eigenschaften von elliptischen Kurven bleiben dabei allerdings erhalten. Auch in diesem Fall lässt sich "double and add" nicht effizient umkehren.
Damit lassen sich elliptische Kurven nun nicht nur mathematisch, sondern auch ganz praktisch für die Verschlüsselung anwenden.
Empfohlener redaktioneller Inhalt
Mit Ihrer Zustimmmung wird hier ein externes YouTube-Video (Google Ireland Limited) geladen.
Ich bin damit einverstanden, dass mir externe Inhalte angezeigt werden. Damit können personenbezogene Daten an Drittplattformen (Google Ireland Limited) übermittelt werden. Mehr dazu in unserer Datenschutzerklärung.
Fazit
Anders als RSA und andere asymmetrische Verfahren lassen sich elliptische Kurven sehr anschaulich und visuell erklären. Trotzdem sind sie aus mathematischer Sicht eine hervorragende und starke Grundlage für Verschlüsselung. Die grundlegenden Konzepte sind dabei nach wie vor die gleichen wie bei anderen asymmetrischen Verfahren.
Auch im Zusammenhang mit elliptischen Kurven kommt ein Hybridverfahren zum Einsatz, es bedarf einer Falltürfunktion, es gibt einen privaten und einen öffentlichen Schlüssel – die Grundbausteine der Kryptografie bleiben also auch mit elliptischen Kurven die gleichen. ()
