• IT-Karriere:
  • Services:

Elliptische Kurven sehen nicht aus wie Ellipsen

Noch schwerer ist es, den diskreten Logarithmus auf elliptischen Kurven über endlichen Körpern anstatt in Restklassengruppen zu bilden. Dabei bleibt beim DH-Schlüsselaustausch mit elliptischen Kurven fast alles beim Alten. Die Gruppe an Elementen besteht aber nun nicht mehr nur aus einer Restklasse modulo p, sondern wird durch eine Kurvengleichung beschrieben.

Stellenmarkt
  1. GS electronic Gebr. Schönweitz GmbH, Rheine
  2. operational services GmbH & Co. KG, verschiedene Standorte

Elliptische Kurven sehen dabei nicht aus wie Ellipsen, der Name ist vielmehr historisch gewachsen und auf die Umfangberechnung von Ellipsen zurückzuführen. Die elliptischen Kurven werden durch die Gleichung y^2=x^3+ax+b beschrieben, sie laufen über den reellen Zahlen nirgendwo spitz zu und überschneiden sich nicht. Vom Aussehen her gibt es zwei Typen: eine Variante sieht aus wie eine Insel vor einer Küste, die andere erinnert eher an die ausgewölbte Seite eines Puzzleteils.

Statt der Multiplikation im klassischen DH-Beispiel, mit der Alice und Bob Potenzen gebildet haben, werden bei elliptischen Kurven Punkte der Kurve addiert, die zu einem neuen Punkt auf dieser Kurve führen. Die Addition ist dabei etwas speziell, am besten stellen wir sie uns bildlich vor: Addiert man einen Punkt P mit einem Punkt Q auf der Kurve, legt man eine Gerade durch die beiden Punkte und schaut, wo die Gerade die Kurve das dritte Mal schneidet. Dieser Punkt, gespiegelt an der x-Achse, ist das Ergebnis. Will man einen Punkt mit sich selbst addieren, nimmt man die Tangente des Punktes.

Fehlt noch ein Detail an der Erklärung: Für die Kryptographie werden keine elliptischen Kurven über den reellen Zahlen, sondern über endlichen Körpern verwendet. Das heißt, auch hier steht nur eine endliche Menge an Werten zur Verfügung und man nutzt wieder Restklassen, rechnet also modulo einer Zahl - einer Primzahl. Die Kurve hat dann optisch nicht mehr viel mit einer Kurve im klassischen Sinn zu tun. Es handelt sich um eine Punktwolke im Raum mit einem begrenzten Wertebereich, die zur x-Achse symmetrisch ist. Bei der Addition wird genau wie bei Kurven über reellen Zahlen bildlich gesprochen eine Gerade zwischen zwei Werten gezogen. Verlässt die Gerade den Wertebereich am rechten, linken, oberen oder unteren Rand, tritt sie einfach auf der gegenüberliegenden Seite wieder ein.

Alice und Bob in der Welt der Kurven

Nachdem sich Alice und Bob auf die Kurvenparameter a und b und einen Punkt verständigt haben, wählen sie getrennt voneinander eine zufällige geheime Zahl. Dann multiplizieren beide den öffentlichen Kurvenpunkt mit ihrer geheimen Zahl, addieren also den Punkt entsprechend oft mit sich selbst. So erhalten die beiden ihre jeweiligen öffentlichen Schlüsselpunkte. Wenn Alice Bobs öffentlichen Schlüssel mit ihrer geheimen Zahl multipliziert und Bob das gleiche mit Alices übermitteltem Punkt tut, kommen beide auf das gleiche Ergebnis, den geheimen Kurvenpunkt. Die x-Koordinate dieses Punktes nutzen sie als gemeinsamen geheimen Schlüssel, um in Zukunft ihre Nachrichten zu schützen.

Was also beim traditionellen Beispiel die zwei Primzahlen als öffentliche Parameter waren, ist nun die Kurve mit einem Punkt. Statt der Potenzierung nutzen die beiden Schlüsseltauscher die Multiplikation mit ihrer geheimen Zahl. Wie zuvor auch, müsste ein Angreifer den diskreten Logarithmus berechnen können. Der Logarithmus bedeutet auf elliptischen Kurven nicht, dass der Angreifer wie im klassischen Beispiel herausfinden muss, wie oft ein Wert multipliziert wurde. Stattdessen muss er ermitteln, wie oft Alice und Bob den öffentlichen Punkt mit sich selbst addiert haben.

Und das ist vermutlich noch schwieriger als im klassischen Verfahren. Moment, was heißt hier vermutlich? Bisher ist es noch niemandem gelungen, das Problem für beliebige Kurven schneller als in exponentieller Zeit zu lösen. Der Aufwand steigt also mit der Schlüssellänge exponentiell an. Bei den klassischen Verfahren gibt es schnellere, sogenannte subexponentielle Ansätze, die besser funktionieren als Ausprobieren. Und die dafür verantwortlich sind, dass die Schlüssel wesentlich länger sein müssen als bei ECC.

Bitte aktivieren Sie Javascript.
Oder nutzen Sie das Golem-pur-Angebot
und lesen Golem.de
  • ohne Werbung
  • mit ausgeschaltetem Javascript
  • mit RSS-Volltext-Feed
 Alice und Bob tauschen SchlüsselKürzere Schlüssel, gleiche Sicherheit 
  1.  
  2. 1
  3. 2
  4. 3
  5. 4
  6. 5
  7.  


Anzeige
Hardware-Angebote

jo-1 28. Aug 2018

sehr nett! Den Spruch merke ich mir ;-) Finde den Artikel aus 2015 hierzu übrigens sehr...

corruption 24. Aug 2018

Stimmt. Man kann z.B. bei DH zeigen, dass es mind. so schwer ist wie das Problem des...

corruption 24. Aug 2018

Im Endeffekt sind beides doch sogenannte "Hidden Subgroup Problems" über eine abelsche...

neokawasaki 19. Aug 2018

Dem kann ich mich anschließen. Unter anderem durch die Faszination an asymmetrischer...


Folgen Sie uns
       


MX 10.0 im Test: Cherrys kompakte, flache, tolle RGB-Tastatur
MX 10.0 im Test
Cherrys kompakte, flache, tolle RGB-Tastatur

Die Cherry MX 10.0 kommt mit besonders flachen MX-Schaltern, ist hervorragend verarbeitet und umfangreich programmierbar. Warum Nutzer in Deutschland noch auf sie warten müssen, ist nach unserem Test unverständlich.
Ein Test von Tobias Költzsch

  1. Argand Partners Cherry wird verkauft

IT-Freelancer: Der kürzeste Pfad zum nächsten Projekt
IT-Freelancer
Der kürzeste Pfad zum nächsten Projekt

Die Nachfrage nach IT-Freelancern ist groß - die Konkurrenz aber auch. Der nächste Auftrag kommt meist aus dem eigenen Netzwerk oder von Vermittlern. Doch wie findet man den passenden Mix?
Ein Bericht von Manuel Heckel

  1. Selbstständiger Sysadmin "Jetzt fehlen nur noch die Aufträge"

Verkehrswende: Zaubertechnologie statt Citybahn
Verkehrswende
Zaubertechnologie statt Citybahn

In Wiesbaden wird um den Bau einer Straßenbahn gestritten, eine Bürgerinitiative kämpft mit sehr kuriosen Argumenten dagegen.
Eine Recherche von Hanno Böck

  1. Fernbus Roadjet mit zwei WLANs und Maskenerkennung gegen Flixbus
  2. Mobilität Wie sinnvoll sind synthetische Kraftstoffe?

    •  /