Kürzere Schlüssel, gleiche Sicherheit

In diesen langen Schlüsseln liegt einer der Nachteile klassischer asymmetrischer Kryptoverfahren. Um ein Sicherheitslevel zu erreichen, das äquivalent zu einem symmetrischen Schlüssel von 128 Bit ist, müsste der Schlüssel 3.248 Bit lang sein. Für eine Länge von 256 Bit im symmetrischen Fall wären schon 15.424 Bit nötig, da eben bessere als exponentielle Angriffe bekannt sind. Bei elliptischen Kurven ist das noch nicht der Fall. Hier erreicht man diese Sicherheit schon mit Längen von 256 beziehungsweise 512 Bit - solange niemand ein Verfahren findet, um den diskreten Logarithmus schneller zu ermitteln.

Das schont sowohl Rechenzeit und Leistung als auch Speicherplatz, was besonders bei Smartcards oder Geräten mit begrenzter Rechenleistung wichtig ist. Und so finden elliptische Kurven beim elektronischen Personalausweis Anwendung. Flexible und energiesparende Hardware-Umsetzungen wie der vom MIT vorgestellte Chip können zur weiteren Verbreitung in Systemen mit begrenzten Ressourcen beitragen. Sei es bei eingebetteten Systemen wie Car-2-Car-Kommunikation oder bei sogenannten Smart Devices.

Hat die NSA Kurven manipuliert?

Doch nicht alle beliebigen Parameter sind für eine sichere elliptische Kurve geeignet. Unter speziellen Umständen ist es leichter möglich, den diskreten Logarithmus zu berechnen. Solche schwachen Kurven lassen sich durch Tests erkennen, zumindest für bekannte Schwachstellen.

In der Praxis berechnet sich daher nicht jeder seine eigene Kurve, sondern verwendet bereits vordefinierte und geprüfte Kurven. Dazu gehören beispielsweise die Kurven der US-Standardisierungsbehörde NIST. Die Parameter dieser Kurven wurden durch eine Hashfunktion erzeugt. Das soll vermeiden, dass jemand leicht manipulierbare Werte einschleusen kann. Doch die NIST-Kurven zogen nach den Snowden-Enthüllungen Misstrauen auf sich. Ein NSA-Mitarbeiter erzeugte die Kurven, und die Startwerte für die Hashfunktion, die er nutzte, machten skeptisch.

Warum er spezielle Werte und nicht etwa wie üblich triviale Werte oder Konstanten wie Pi verwendete, war nicht erklärbar. Daraus entstand die Angst, die NSA könnte eine öffentlich nicht bekannte Schwachstelle in der Hashfunktion ausnutzen, um von ihr gewählte schwache Parameter zu erzeugen. Denn es ist durchaus denkbar, dass ein Angreifer um weitere schwache Kurventypen weiß, dieses Wissen jedoch nicht öffentlich bekanntgibt.

Dass diese Parameter tatsächlich manipuliert waren und Schwächen aufweisen, konnte nicht bewiesen werden. Der Kryptograph Daniel J. Bernstein schlug jedoch bereits vor diesen Zweifeln vor, Kurvenparameter deterministisch zu bestimmen. 2006 veröffentlichte er die mittlerweile weit verbreitete Curve25519. Er nahm als Grundlage die Sicherheitsanforderungen und ermittelte jene Parameter, die diese erfüllen und effiziente Berechnungen erlauben. Er kam so auf eine elliptische Kurve mit der Gleichung y^2 = x^3 + 486662x^2 + x. Ihren Namen hat sie von dem endlichen Körper modulo 2^255 − 19. Wenn wir uns kurz an die vorherigen Ausflüge in die Mathematik erinnern: 2^255 − 19 beschreibt den Wertebereich, der zur Verfügung steht und ist eine sehr große Primzahl.