Keine Zukunftsmusik mehr: Elliptische Kurven ersetzen RSA

Verschlüsselung im Internet soll in den nächsten 10 Jahren auf Elliptische-Kurven-Kryptographie umgestellt werden.

Die National Security Agency teilte das im Januar in dieser Erklärung mit und begründet es mit den in Zukunft wachsenden Anforderungen:
While at current security levels elliptic curves do not offer significant benefits over existing public key algorithms, as one scales security upwards over time to meet the evolving threat posed by eavesdroppers and hackers with access to greater computing resources, elliptic curves begin to offer dramatic savings over the old, first generation techniques.

Zur Erinnerung (Teil 2): Kryptographie funktioniert gegenwärtig so, daß mit asymmetrischen Verfahren (wie RSA oder Diffie-Hellman) Schlüssel ausgetauscht werden, und mit den ausgetauschten Schlüsseln dann das symmetrische AES-Verfahren verwendet wird. (Für AES gibt es einen festen Standard, der auf absehbare Zeit nicht geändert werden soll.)

Die bisher verwendeten Methoden zum Schlüsselaustausch, nämlich RSA (Teil 3) und Diffie-Hellman für endliche Körper (Teil 5) sind zwar gegenwärtig sicher, könnten aber mit in Zukunft zu entwickelnden Computern geknackt werden:
However, there have been several efforts aimed at designing theoretical special purpose computers that would implement the existing attack algorithms far faster than general computing resources.

Anders ist das für Elliptische-Kurven-Kryptographie:
Since their use in cryptography was discovered in 1985, elliptic curve cryptography has also been an active area of study in academia. Similar to both RSA and Diffie-Hellman, the first years of analysis yielded some degenerate cases for elliptic curve parameters that one should avoid. However, unlike the RSA and Diffie-Hellman cryptosystems that slowly succumbed to increasingly strong attack algorithms, elliptic curve cryptography has remained at its full strength since it was first presented in 1985.

NIST sieht die gegenwärtige Verwendung von RSA mit 1024-bit Parametern als bis 2010 ausreichend sicher an. Danach könnte man natürlich einfach auf 2048-bit erhöhen (d.h. man müßte die Länge der ausgetauschten Schlüssel von 80 auf 128 bits erhöhen). Dieselben Schlüssel kann man aber bei Verwendung elliptischer Kurven bereits mit 224-bit Parametern sicher austauschen. Man benötigt also ungefähr ein Zehntel an Zeit und Speicherplatz für dieselbe Sicherheit. (Bei längeren Schlüsseln steigt dieses Verhältnis noch deutlich: wenn man 256-bit Schlüssel austauschen will, sind elliptische Kurven um 1/64 effektiver als RSA.)

ECC (Elliptic Curve Cryptography) ist der Sammelbegriff für kryptographische Verfahren, die elliptische Kurven (Teil 9) benutzen. Ich hatte in Teil 10 darüber geschrieben, wie man sich Verschlüsselung mit elliptischen Kurven vorzustellen hat.

Die Sicherheit aller dieser Verfahren beruht letztlich darauf, daß man für (die meisten) elliptischen Kurven keine effektiven Möglichkeiten hat, “diskrete 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.

Natürlich sind nicht alle elliptischen Kurven für Verschlüsselung geeignet: es gibt Algorithmen, die für sehr spezielle elliptische Kurven in realistischer Zeit diskrete Logarithmen berechnen. Dazu kommt morgen noch ein kurzer Überblick.

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

Kommentare (7)

  1. #1 Chupacabra
    10. März 2009


    Kurven keine effektiven Möglichkeiten hat,

    Meinst du hier nicht »effizient« statt »effektiv«?

  2. #2 Thilo Kuessner
    10. März 2009

    Ähm, ja, ich dachte immer, im Deutschen wären das Synonyme (im Gegensatz zum Englischen, wo effective natürlich etwas anderes bedeutet)?

  3. #3 Chupacabra
    10. März 2009

    Ich wüsste nicht, dass sie im Deutschen Synonyme wären… Bin eigentlich immer von der Unterscheidung, ausgegangen, die auch Wiki http://de.wikipedia.org/wiki/Effektivit%C3%A4t macht. Oder speziell in der Inform.: http://de.wikipedia.org/wiki/Effizienz_(Informatik)

    Auf Krypto angewendet, würde ich dann sagen:
    Verfahren A ist effektiver als B, wenn es sicherer verschlüsselt. Effizienter ist ein Verfahren, wenn es weniger kostet (Laufzeit oder Speicher).

  4. #4 Thilo Kuessner
    10. März 2009

    Nun, im Zusammenhang oben ging es doch aber um die Entschlüsselung. Und die ist eben dann effektiv, wenn sie wenig Laufzeit (also nicht Monate oder Jahre) benötigt. Grundsätzlich kann man natürlich jedes Verfahren knacken. Aber wenn man dafür Jahre benötigen würde, gilt das Verfahren als sicher.

  5. #5 Chupacabra
    11. März 2009


    Grundsätzlich kann man natürlich jedes Verfahren knacken.

    Ähm, nein. Grundsätzlich gibt es Verfahren, die unknackbar sind. Sie haben die Eigenschaft der perfekten Geheimhaltung; siehe das Vernam-One-Pad-Verfahren.


    Und die ist eben dann effektiv, wenn sie wenig Laufzeit (also nicht Monate oder Jahre) benötigt.

    Gut, man kann glaube ich immer effizient durch effektiv ersetzen, je nach dem welche Sicht man auf die Sachlage hat. Wenn man sich aber über Algorithmen unterhält ist diese Sicht zumindest in der Informatik festgelegt. Kann schon sein, dass die Kryptographen dann aber sagen “ein Algorithmus ist für uns nur dann effektiv, wenn es effizient ist.”

    BTW: Nicht dass der Eindruck bei dir entsteht, ich habe nichts Besseres zu tun als diese Haarspalterei hier. 🙂 Ich verfolge sehr gerne deine Mathematik-Blogs.

  6. #6 Thilo Kuessner
    11. März 2009

    Grundsätzlich kann man natürlich jedes Verfahren knacken.
    war so gemeint: man kann einfach alle Möglichkeiten ausprobieren und kommt damit auf jeden Fall zum Ziel. Nur braucht man eben Jahrmillionen.
    Und auch irgendwelche anderen Algorithmen kommen (da es ja nun einmal nur endlich viele Möglichkeiten gibt) auf jeden Fall zum Ziel. Die Frage ist nur, in welcher Zeit.

    Siehe auch den nächsten Beitrag http://www.scienceblogs.de/mathlog/2009/03/kryptographie-xiii.php :
    Aus Sicht der Kryptographie betrachtet man Verfahren als unsicher, wenn es Algorithmen zur Entschlüsselung in subexponentieller Zeit gibt; Verfahren gelten als sicher, wenn alle (bekannten) Algorithmen exponentielle Zeit benötigen.

  7. #7 Chupacabra
    11. März 2009


    war so gemeint: man kann einfach alle Möglichkeiten ausprobieren und kommt damit auf jeden Fall zum Ziel. Nur braucht man eben Jahrmillionen.

    Ich habe dich auch so verstanden. Bei dem Vernam-One-Pad-Verfahren bringt aber auch Brute-Force nichts. Denn da ist es so, dass du dir zu jedem Paar aus Schlüsseltext und Klartext einen Schlüssel konstruieren kannst, der den Klartext in den Schlüsseltext verschlüsselt. Wenn jetzt Alice bei der Verschlüsselung immer den Schlüssel zufällig und gleichverteilt wählt, hat ein Angreifer keine Chance, verschlüsselte Texte durch Ausprobieren aller Schlüssel zu entschlüsseln.

    Das Vernam-Verfahren (übrigens, ein symmetrisches) ist an sich sehr einfach, aber selten praktikabel.


    Aus Sicht der Kryptographie betrachtet man Verfahren als unsicher, wenn es Algorithmen zur Entschlüsselung in subexponentieller Zeit gibt; Verfahren gelten als sicher, wenn alle (bekannten) Algorithmen exponentielle Zeit benötigen.

    Ist klar.