• 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. über duerenhoff GmbH, Raum Ingolstadt
  2. Hottgenroth Software GmbH & Co. KG, Flammersfeld (Westerwald)

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. IT-Sicherheit für Webentwickler
    31. Mai - 1. Juni 2021, online
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.  


Anzeige
Spiele-Angebote
  1. (u. a. Sniper Ghost Warrior 3 - Season Pass Edition für 4,99€, Sherlock Holmes: The Devil's...
  2. 9,99€
  3. 11,99€

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
       


Razer Kyio Pro Webcam - Test

Webcams müssen keine miese Bildqualität haben, wie Razers Kyio Pro in unserem Test beweist.

Razer Kyio Pro Webcam - Test Video aufrufen
Programm für IT-Jobeinstieg: Hoffen auf den Klebeeffekt
Programm für IT-Jobeinstieg
Hoffen auf den Klebeeffekt

Aktuell ist der Jobeinstieg für junge Ingenieure und Informatiker schwer. Um ihnen zu helfen, hat das Land Baden-Württemberg eine interessante Idee: Es macht sich selbst zur Zeitarbeitsfirma.
Ein Bericht von Peter Ilg

  1. Arbeitszeit Das Sechs-Stunden-Experiment bei Sipgate
  2. Neuorientierung im IT-Job Endlich mal machen!
  3. IT-Unternehmen Die richtige Software für ein Projekt finden

Weclapp-CTO Ertan Özdil: Wir dürfen nicht in Schönheit und Perfektion untergehen!
Weclapp-CTO Ertan Özdil
"Wir dürfen nicht in Schönheit und Perfektion untergehen!"

Der CTO von Weclapp träumt von smarter Software, die menschliches Eingreifen in der nächsten ERP-Generation reduziert. Deutschen Perfektionismus hält Ertan Özdil aber für gefährlich.
Ein Interview von Maja Hoock


    Fiat 500 als E-Auto im Test: Kleinstwagen mit großem Potenzial
    Fiat 500 als E-Auto im Test
    Kleinstwagen mit großem Potenzial

    Fiat hat einen neuen 500er entwickelt. Der Kleine fährt elektrisch - und zwar richtig gut.
    Ein Test von Peter Ilg

    1. Vierradlenkung Elektrischer GMC Hummer SUV fährt im Krabbengang seitwärts
    2. MG Cyberster MG B Roadster mit Lasergürtel und Union Jack
    3. Elektroauto E-Auto-Prämie übersteigt in 2021 schon Vorjahressumme

      •  /