« vorheriger Beitrag  · nächster Beitrag »

10.03.09 · 06:27 Uhr

Kryptographie XII

Kategorie: Technik  ·  Kommentare: 7

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 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.

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

 

Autor: Thilo· 7 Kommentare· Permalink· Trackback-URL

Tags: elliptische kurve· kryptographie· NSA· RSA