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 Pn 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 nk (für irgendein k) ist
– die in subexponentieller Zeit (d.h. auch noch ziemlich schnellen), für die f(n) kleiner als kn (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 komplizierter1.) Für supersinguläre Kurven gibt es den MOV-Algorithmus2, 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.

1 Allgemein, über einem Körper F mit pn Elementen, heißt eine elliptische Kurve E(F) “supersingulär”, wenn pn+1-#E(F) durch p teilbar ist.
(Das hat nichts mit Singularitäten im Sinne der Algebraischen Geometrie zu tun.)
2 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 Fx 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

Kommentare (2)

  1. #1 bohem
    15. März 2009

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

    Das ist natürlich korrekt, aber es lohnt einen zweiten Blick darauf was denn “es gibt Entschlüsselung-Algorithmen” genau meint. Für die obige Formulierung heißt das etwas ausführlicher “es gibt einen Algorithmus der *jede* Instanz eines Verschlüsselungsverfahrens in subexponentieller Zeit bricht”. OK, wenn es so einen Algorithmus gibt, dann ist das Verfahren gewiß als unsicher zu bezeichnen.

    Praktiker würden sagen, ein Verfahren ist unsicher, wenn es einen Algorithmus gibt, der *hinreichend viele* Instanzen eines Verschlüsselungsverfahrens in subexponentieller Zeit bricht”. Das ist ein gewaltiger Unterschied. Das prominenteste Beispiel dafür, daß dieser Unterschied praktische Relevanz besitzt, ist sicher das Merkle Hellman Kryptosystem, siehe https://en.wikipedia.org/wiki/Merkle-Hellman . Man lernt, auch die Götter der Kryptographie können irren (allerdings steckte damals die asymmetrische Kryptographie noch in den Kinderschuhen). Es zeigt aber, daß man mit der Diskussion über NP etc einfach die falsche “Metrik” gewählt hat, um die Schwere von kryptographischen Problemen zu klassifizieren. Bei “NP” ist immer der “worst-case” relevant, in der Praxis brauchen wir aber den “average-case” (was meint “alle bis auf einen beliebig kleinen Anteil”).

    In den 90ern gab es dann ein das Ajtai-Dwork Cryptosystem, das die die sehr erwünschte Eigenschaft hatte, daß eine average-case Instanz genau so schwer ist wie eine worst-case Instanz. Leider wußte man nicht wie schwer der worst-case nun wirklich ist. Ende der 90er zeigten Phong Nguyen und Jacques Stern, daß es nicht NP-hart ist.

    Tja, insgesamt ist das alles deprimierend.

    Für Praktiker sind ECC-Systeme nicht ohne Tücken. Die Mathematik dahinter ist schon etwas tricky, die Kataloge der Kurven, die “man besser nicht verwendet” sind etwas suspekt. Wer ist sich denn ziemlich sicher, daß der Katalog nicht eventbezogen (d.h. jedes Jahr zur Crypto oder Eurocrypt) erweitert wird. Bei Algorithmen, die man in Systemen verbaut, die für einen Algorithmenwechsel zehn Jahre brauchen, ist das ein unangenehmer Unsicherheitsfaktor.

    Zudem gibt es bei der ECC einen ziemlichen “Patentverhau”. Das hat den Markt sehr gelähmt. Keiner verbaut ECC wenn er fürchten muß, ein paar Jahre später Patentverletzungsklagen am Hals zu haben. Die NSA hat für *gewisse* Projekte inzwischen quasi eine Patentfreistellung erworben siehe https://www.nsa.gov/business/programs/elliptic_curve.shtml . Was sagt uns das? Sieht zumindest aus, als ob die NSA ein gewisses Vertrauen in ECC hat.

  2. #2 zitat
    3. Oktober 2009

    “ECC curves are divided into three groups, weak curves, inefficient curves, and curves patented by Certicom”
    — Peter Gutmann, 10 Aug, 2001.