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. Business Intelligence Developer (m/w/d)
    Christian Funk Holding GmbH & Co. KG, Offenburg
  2. Projekt Manager FUTR HUT (m/w/d)
    Tegel Projekt GmbH, Berlin
Detailsuche

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

Golem Akademie
  1. CEH Certified Ethical Hacker v11: virtueller Fünf-Tage-Workshop
    30.05.-03.06.2022, Virtuell
  2. Entwicklung mit Unity auf der Microsoft HoloLens 2 Plattform: virtueller Zwei-Tage-Workshop
    07./08.06.2022, Virtuell
Weitere IT-Trainings

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.  


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...



Aktuell auf der Startseite von Golem.de
Strange New Worlds Folge 1 bis 3
Star Trek - The Latest Generation

Strange New Worlds kehrt zu episodenhaften Geschichten zurück und will damit Star-Trek-Fans alter Schule abholen. Das gelingt mit Bravour. Achtung, Spoiler!
Eine Rezension von Oliver Nickel

Strange New Worlds Folge 1 bis 3: Star Trek - The Latest Generation
Artikel
  1. LTE-Patent: Ford droht Verkaufs- und Produktionsverbot in Deutschland
    LTE-Patent
    Ford droht Verkaufs- und Produktionsverbot in Deutschland

    Ford fehlen Mobilfunk-Patentlizenzen, weshalb das Landgericht München eine drastische Entscheidung gefällt hat. Autos droht sogar die Vernichtung.

  2. Flowcamper: Elektro-Wohnmobil Frieda Volt auf VW-Basis vorgestellt
    Flowcamper
    Elektro-Wohnmobil Frieda Volt auf VW-Basis vorgestellt

    Das elektrische Wohnmobil Frieda Volt basiert auf einem umgebauten Volkswagen T5 oder T6 und ist mit einem 72-kWh-Akku ausgerüstet.

  3. Katastrophenschutz: Cell Broadcast funktioniert nur auf jedem fünften Handy
    Katastrophenschutz
    Cell Broadcast funktioniert nur auf jedem fünften Handy

    Der bundesweite Test zur Versendung von Warn-SMS soll verschoben werden. Zu wenig Geräte können die Technik bislang einsetzen.

Du willst dich mit Golem.de beruflich verändern oder weiterbilden?
Zum Stellenmarkt
Zur Akademie
Zum Coaching
  • Schnäppchen, Rabatte und Top-Angebote
    Die besten Deals des Tages
    Daily Deals • Borderlands 3 gratis • CW: Top-Rabatte auf PC-Komponenten • Inno3D RTX 3070 614€ • Crucial P5 Plus 2 TB 229,99€ • Preis-Tipp: Kingston NV1 2 TB 129,90€ • AVM FRITZ!Repeater 1200 AX 69€ • MindStar (u. a. Palit RTX 3050 339€) • MMOGA (u. a. Total War Warhammer 3 29,49€) [Werbung]
    •  /