ECC – Elliptische-Kurven-Kryptografie

Abkürzung: ECC

Die Abkürzung ECC ist doppelt belegt: In der Übertragungs- und Speichertechnik steht sie für Error Correction Code und hat mit Kryptografie nichts zu tun. Im englischen Sprachraum wird für die Kryptografie meist Elliptic Curve Cryptography ausgeschrieben.

Das Verfahren ist keine neue Idee, sondern eine andere Rechenumgebung für eine bekannte: Statt modulo einer großen Primzahl zu rechnen, rechnet man in der Punktemenge einer elliptischen Kurve über einem endlichen Körper. Die zugrunde liegende Einwegfunktion bleibt der diskrete Logarithmus — siehe Public Key.

Warum kürzere Schlüssel genügen

Gegen den klassischen diskreten Logarithmus greifen Siebverfahren, die den Angriff erheblich beschleunigen. Auf elliptischen Kurven sind sie nicht anwendbar; dort bleibt im Wesentlichen das Durchprobieren mit generischen Verfahren. Der Aufwand eines Angriffs wächst damit deutlich günstiger mit der Schlüssellänge:

Die Folgen sind praktisch spürbar: kleinere Zertifikate, kürzere Handshakes, weniger Rechenzeit je Verbindungsaufbau und ein Verfahren, das auf eingebetteter Hardware und Chipkarten überhaupt erst sinnvoll umsetzbar ist.

Wie gerechnet wird

Auf den Punkten einer elliptischen Kurve ist eine Verknüpfung definiert, die sich wie eine Addition verhält: Aus zwei Punkten entsteht ein dritter. Wendet man sie wiederholt auf denselben Punkt an, erhält man die Skalarmultiplikation — einen Punkt G mit einer Zahl k vervielfachen.

Das ist die Einwegfunktion des Verfahrens. Aus k und G ergibt sich k·G leicht; aus G und k·G das k zu bestimmen, ist der diskrete Logarithmus auf der Kurve und praktisch unlösbar.

Der private Schlüssel ist damit die Zahl k, der öffentliche Schlüssel der Punkt k·G. Mehr braucht es im Kern nicht.

Die Kurve ist ein Parameter

Anders als bei RSA, wo die Schlüssellänge fast alles ist, gehört bei ECC die Kurve selbst zu den Festlegungen — mit Basispunkt, Körpergröße und Ordnung der Gruppe. Eigene Kurven zu wählen ist ein zuverlässiger Weg in die Katastrophe; verwendet werden benannte Kurven, deren Parameter geprüft und veröffentlicht sind:

Die Kurve P-256 heißt in der OpenSSL-Welt prime256v1 und bei der SECG secp256r1 — drei Namen für dasselbe, eine Verwechslungsquelle beim Vergleich von Konfigurationen.

Zwei Verfahrenswelten

Elliptische Kurven tragen beides, aber getrennt:

Schlüsseleinigung. ECDH, in der heute üblichen Form mit flüchtigen Schlüsseln als ECDHE. Auf Curve25519 heißt die Variante X25519 und ist in TLS 1.3 die Standardwahl. Siehe Diffie-Hellman.

Signatur. ECDSA ist die verbreitete Form und in Zertifikaten der gängige Gegenspieler zu RSA. EdDSA auf Edwards25519 ist die jüngere Konstruktion — schneller, ohne die unten beschriebene Zufallszahlenfalle, inzwischen die Vorgabe bei SSH-Schlüsseln.

Die Zufallszahl bei ECDSA

Hier liegt die bekannteste Falle des Verfahrens, und sie ist unverzeihlich scharf: Wird für zwei Signaturen dieselbe Zufallszahl verwendet, lässt sich der private Schlüssel daraus berechnen. Nicht erraten, nicht annähern — berechnen.

Der prominenteste Fall war 2010 eine Spielkonsole, deren Signaturschlüssel genau auf diese Weise öffentlich wurde, weil der Hersteller einen festen Wert eingesetzt hatte. Dasselbe Muster ist seither mehrfach in Geldbörsen-Software und auf eingebetteten Geräten mit schwacher Entropiequelle aufgetreten.

RFC 6979 beseitigt die Ursache, indem die Zahl nicht zufällig gewählt, sondern deterministisch aus Schlüssel und Nachricht abgeleitet wird. EdDSA macht dasselbe von Haus aus — das ist einer der Hauptgründe, es zu bevorzugen.

Die Vertrauensfrage

Die NIST-Kurven tragen eine offene Frage mit sich: Ihre Parameter sind aus Startwerten abgeleitet, deren Herkunft nie erklärt wurde. Ein Nachweis für eine Hintertür existiert nicht, aber nach den Vorgängen um den Zufallszahlengenerator Dual_EC_DRBG ist das Unbehagen nicht leicht wegzuwischen.

Daraus sind zwei Gegenbewegungen entstanden. Curve25519 und Edwards25519 sind so entworfen, dass sich jede Konstante aus dem Entwurfsziel begründen lässt. Und die Brainpool-Kurven aus RFC 5639 — entwickelt im Umfeld von BSI und secunet — leiten ihre Parameter nachvollziehbar aus Ziffern von π und e ab.

Für den deutschen Behördenbereich ist das mehr als eine Fußnote: Teil 1 der BSI TR-02102 führt beide Familien, und in Ausschreibungen und Zulassungsumfeldern tauchen die Brainpool-Kurven regelmäßig verbindlich auf.

Implementierungsfallen

Zwei Fehler kommen in der Praxis wiederholt vor:

Ungeprüfte Punkte. Nimmt eine Seite einen übermittelten Punkt an, ohne zu prüfen, dass er auf der vereinbarten Kurve liegt, kann ein Angreifer sie auf eine schwächere Kurve zwingen und daraus Teile des privaten Schlüssels gewinnen. Die Prüfung ist Pflicht, nicht Vorsicht.

Laufzeitabhängige Rechnung. Hängt die Dauer der Skalarmultiplikation von den Bits des Schlüssels ab, lässt sich dieser aus Zeitmessungen rekonstruieren. Curve25519 ist unter anderem deshalb entworfen, weil sie eine Umsetzung in konstanter Zeit erleichtert.

Elliptische Kurven und der Quantenrechner

Der Vorteil kürzerer Schlüssel kehrt sich hier um: Der Shor-Algorithmus löst den diskreten Logarithmus auf Kurven ebenso wie modulo einer Primzahl, und weil die Schlüssel kleiner sind, sind elliptische Verfahren voraussichtlich sogar früher betroffen als RSA mit großen Modulen.

Die Antwort ist nicht eine größere Kurve, sondern ein anderes Verfahren — im Übergang parallel zum bisherigen betrieben. In TLS 1.3 ist das als X25519MLKEM768 im Einsatz. Siehe Post-Quantum-Kryptografie.