Kryptographie XIII

Wie sicher ist Verschlüsselung mit elliptischen Kurven?

Gestern hatten wir berichtet, daß die National Security Agency in den nächsten 10 Jahren die Verschlüsselung im Internet umstellen will: statt RSA soll für den Schlüsselaustausch in Zukunft ECC verwendet werden.

ECC (Elliptic Curve Cryptography) ist der Sammelbegriff für kryptographische Verfahren, die elliptische Kurven benutzen. Die Sicherheit aller dieser Verfahren beruht letztlich darauf, daß man für (die meisten) elliptischen Kurven keine effektiven Möglichkeiten hat, “diskreten Logarithmen” zu berechnen. Das heißt, es ist (für einen fest gewählten Punkt P) zwar leicht, n als nP=P+…+P (n-fache Summe) zu verschlüsseln, ein Hacker, der nP kennt, kann aber nicht n zurückberechnen. (Die Bezeichnung “diskreter Logarithmus” erklärt sich daraus, daß in der Gruppentheorie die Addition als Multiplikation und nP dann als Pⁿ geschrieben wird.) Auf diesem (auf Diffie-Hellman zurückgehenden) Prinzip aufbauend gibt es dann diverse Verfahren wie die El Gamal-Verschlüsselung und die El Gamal-Signatur.

Heute wollen wir noch einen kurzen Überblick geben, nach welchen Kriterien die verwendeten elliptischen Kurven ausgewählt werden.

Vorab ein Wort darüber, wie man den Zeitbedarf oder Speicherplatz von Algorithmen mißt. Es ist natürlich klar, daß der zeitliche Aufwand von der Anzahl der Eingabedaten (hier also der Anzahl der Punkte der elliptischen Kurve abhängt). Sagen wir, ein Algorithmus braucht für eine Kurve mit n Punkten eine bestimmte Anzahl f(n) an Schritten. Man unterscheidet (beim Zeitbedarf) grob 3 Arten von Algorithmen:
-die in polynomialer Zeit (d.h. sehr schnellen), für die f(n) kleiner als n^k (für irgendein k) ist
– die in subexponentieller Zeit (d.h. auch noch ziemlich schnellen), für die f(n) kleiner als kⁿ (für irgendein k) ist
– die in exponentieller Zeit (d.h. langsamen), die nicht in subexponentieller Zeit laufen.

In der Kryptographie gelten Verschlüsselungsverfahren als unsicher, wenn es Entschlüsselungs-Algorithmen in subexponentieller (oder gar polynomieller) Zeit gibt.

Es gibt eine Reihe von Algorithmen zum Knacken elliptischer Kurven, die aber alle exponentielle Zeit brauchen. Ich verlinke mal einfach die entsprechenden Wikipedia-Artikel: der Babystep-Giantstep-Algorithmus, der Pohlig-Hellman-Algorithmus, der Pollard ρ-Algorithmus und der Pollard λ-Algorithmus. Wegen ihres hohen Zeit- und Speicher-Aufwandes sind diese Algorithmen nicht praktikabel und stellen also keine Gefahr dar.

Darüber hinaus gibt es aber noch Algorithmen, die für sehr spezielle elliptische Kurven tatsächlich Entschlüsselung in subexponentieller Zeit erreichen. Diese speziellen elliptischen Kurven dürfen dann natürlich in der Verschlüsselung nicht verwendet werden.

Konkret dürfen sogenannte ‘supersinguläre’ und ‘anomale’ Kurven nicht verwendet werden. Das sind Kurven mit einer bestimmten Anzahl von Punkten. Nach dem Satz von Hasse hat ja eine elliptische Kurve modulo p “ungefähr” p+1 Punkte.
Eine “supersinguläre” Kurve ist eine Kurve, für die die Anzahl der Punkte genau p+1 ist. (Jedenfalls, wenn man modulo einer Primzahl p≥5 rechnet. Die allgemeine Definition wäre komplizierter¹.) Für supersinguläre Kurven gibt es den MOV-Algorithmus², der in subexponentieller Zeit entschlüsselt.
Eine “anomale” elliptische Kurve ist eine Kurve, für die die Anzahl der Punkte genau p ist. Für anomale Kurven gibt es den SSSA-Algorithmus, der in subexponentieller Zeit entschlüsselt.

In der Praxis verwendet man ohnehin nur eine relativ kleine Auswahl von elliptischen Kurven. Die NSA, die ja in den nächsten Jahren elliptische Kurven zur Grundlage aller Verschlüsselung im Internet machen will, nutzt z.Zt. eine überschaubare Liste von zu verwendenden elliptischen Kurven:
“In choosing an elliptic curve as the foundation of a public key system there are a variety of different choices. The National Institute of Standards and Technology (NIST) has standardized on a list of 15 elliptic curves of varying sizes. Ten of these curves are for what are known as binary fields and 5 are for prime fields. Those curves listed provide cryptography equivalent to symmetric encryption algorithms (e.g. AES, DES or SKIPJACK) with keys of length 80, 112, 128, 192, and 256 bits and beyond.

For protecting both classified and unclassified National Security information, the National Security Agency has decided to move to elliptic curve based public key cryptography. Where appropriate, NSA plans to use the elliptic curves over finite fields with large prime moduli (256, 384, and 521 bits) published by NIST. ”

¹ Allgemein, über einem Körper F mit pⁿ Elementen, heißt eine elliptische Kurve E(F) “supersingulär”, wenn pⁿ+1-#E(F) durch p teilbar ist.
(Das hat nichts mit Singularitäten im Sinne der Algebraischen Geometrie zu tun.)
² Der MOV-Algorithmus benutzt die Weil-Paarung, um die Berechnung diskreter Logarithmen in E(F) auf die (etwas einfachere) Berechnung diskreter Logarithmen in der multiplikatven Gruppe F^x zurückzuführen.

Teil 1, Teil 2,Teil 3, Teil 4, Teil 5, Teil 6, Teil 7, Teil 8, Teil 9, Teil 10, Teil 11, Teil 12