Elliptic-Curve Kryptographie

Elliptic-Curve Kryptographie (ECC) realisiert Public-Key-Verfahren über der Gruppe von Punkten auf einer elliptischen Kurve und erreicht die gleiche Sicherheit wie RSA oder Finite-Field Diffie-Hellman mit wesentlich kleineren Schlüsseln.

Definition

Elliptic-Curve Kryptographie ist eine Public-Key-Kryptographie, deren zugrunde liegende Gruppe die Menge der Punkte auf einer elliptischen Kurve über einem endlichen Körper ist, wobei die Sicherheit auf der Schwierigkeit des diskreten Logarithmusproblems elliptischer Kurven basiert.

Scope

Dieses Thema behandelt das Gruppengesetz elliptischer Kurven über endlichen Körpern, das diskrete Logarithmusproblem elliptischer Kurven und die darauf aufbauenden Schemata: Elliptic-Curve Diffie-Hellman (ECDH), die Signaturverfahren ECDSA und EdDSA sowie moderne Kurven wie Curve25519. Es wird erläutert, warum diskrete Logarithmen elliptischer Kurven schwieriger sind als solche in endlichen Körpern (kein subexponentieller Indexkalkül) und Implementierungsaspekte wie die Wiederverwendung von Nonces in ECDSA. RSA und diskrete Logarithmus-Schemata in endlichen Körpern, die in verwandten Themen behandelt werden, sind ausgeschlossen.

Core questions

• Wie bildet die geometrische Addition von Punkten auf einer elliptischen Kurve eine kryptographische Gruppe?
• Warum ist der diskrete Logarithmus auf elliptischen Kurven schwieriger als sein Analogon in endlichen Körpern, was kleinere Schlüssel ermöglicht?
• Wie werden Diffie-Hellman und digitale Signaturen über elliptischen Kurven instanziiert?
• Was macht moderne Kurven wie Curve25519 sicherer in der Implementierung als ältere NIST-Kurven?
• Warum ist die Eindeutigkeit der Nonce pro Signatur in ECDSA entscheidend?

Key concepts

• Gruppengesetz elliptischer Kurven
• Skalarmultiplikation
• diskretes Logarithmusproblem elliptischer Kurven
• ECDH
• ECDSA
• EdDSA und Ed25519
• Curve25519
• Nonce-Wiederverwendungs-Schwachstelle
• Schlüssellänge vs. RSA

Key theories

Diskretes Logarithmusproblem elliptischer Kurven

Angesichts der Punkte P und Q = kP auf einer Kurve wird angenommen, dass die Wiederherstellung des Skalars k für gut gewählte Kurven einen vollständig exponentiellen Aufwand erfordert, da die Indexkalkül-Angriffe, die diskrete Logarithmen in endlichen Körpern schwächen, nicht anwendbar sind.

Kleinere Schlüssel für gleiche Sicherheit

Da die besten Angriffe auf diskrete Logarithmen elliptischer Kurven generische Quadratwurzelalgorithmen sind, bietet eine 256-Bit-Elliptische-Kurve eine Sicherheit von etwa 128 Bit – vergleichbar mit 3072-Bit-RSA – was schnellere Operationen und kleinere Schlüssel und Signaturen ermöglicht.

Mechanisms

Punkte auf einer elliptischen Kurve über einem endlichen Körper bilden eine abelsche Gruppe unter einem geometrischen Additionsgesetz; das wiederholte Addieren eines Basispunkts P zu sich selbst k-mal (Skalarmultiplikation, kP) ist effizient, aber die Wiederherstellung von k aus kP ist das schwierige Problem. ECDH führt Diffie-Hellman durch den Austausch von Skalarmultiplikationen eines Basispunkts durch; ECDSA und EdDSA erzeugen Signaturen aus einem pro-Nachricht-Skalar (einer Nonce) – der, wenn er wiederholt oder vorhersagbar ist, den privaten Schlüssel preisgibt, wie mehrere reale Sicherheitsverletzungen zeigten.

Clinical relevance

ECC ist die Standardwahl für Public-Keys in neuen Systemen: ECDHE bietet Forward-Secret Key Exchange in TLS 1.3, Ed25519 signiert SSH-Schlüssel, Software-Updates und Zertifikate, und Curve25519 sichert Signal, WireGuard und moderne Messaging-Dienste. Ihre kleinen Schlüssel und schnellen Operationen machen sie gut geeignet für mobile Geräte, Smartcards und ressourcenbeschränkte IoT-Hardware.

Evidence & guidelines

ECDSA ist in FIPS 186 standardisiert, ECDH in NIST SP 800-56A und EdDSA/Ed25519 in RFC 8032; Curve25519/X25519 in RFC 7748. Die moderne Praxis bevorzugt Edwards-Kurven und X25519 wegen ihrer Widerstandsfähigkeit gegenüber Implementierungsfehlern. Der Zusammenbruch von ECDSA bei Wiederverwendung von Nonces (insbesondere die Schlüssel-Extraktion der Sony PlayStation 3 im Jahr 2010) ist ein warnendes Standardbeispiel.

History

Neal Koblitz und Victor Miller schlugen 1985-1987 unabhängig voneinander die Verwendung elliptischer Kurven für die Kryptographie vor. Die Einführung verlief zunächst langsam aufgrund von Patent- und Vertrauensbedenken sowie der Komplexität der NIST-Kurven, aber ECC wurde in den 2010er Jahren dominant, da die Effizienz der Schlüssellänge wichtiger wurde und Bernsteins Curve25519 (2006) und Ed25519 schnelle, missbrauchssichere Designs boten, die heute weit verbreitet sind.

Key figures

• Neal Koblitz
• Victor Miller
• Daniel J. Bernstein
• Alfred Menezes
• Scott Vanstone

Seminal works

• koblitz1987
• hankerson2004
• katz2020

Frequently asked questions

Warum entspricht ein 256-Bit-Elliptische-Kurven-Schlüssel einem 3072-Bit-RSA-Schlüssel?

Die besten bekannten Angriffe auf den diskreten Logarithmus elliptischer Kurven sind generisch und benötigen eine Zeit, die etwa der Quadratwurzel der Gruppengröße entspricht, während Faktorisierungs- und diskrete Logarithmen in endlichen Körpern schnellere subexponentielle Algorithmen aufweisen. Daher benötigen elliptische Kurven für das gleiche Sicherheitsniveau wesentlich weniger Bits.

Sind die NIST-Elliptische-Kurven vertrauenswürdig?

Die standardmäßigen NIST P-Kurven sind weit verbreitet und es ist nicht bekannt, dass sie gebrochen wurden, aber ihre unerklärten Konstantenwahlen und die Schwierigkeit der Implementierung führten dazu, dass viele Curve25519 und Ed25519 bevorzugten, die transparente Designprinzipien haben und sicherer in konstanter Zeit implementiert werden können.