Elliptische Kurven – “Defending Our Nation, Securing The Future”.
Wir hatten ja in der Kryptographie-Reihe schon darüber geschrieben, daß die National Security Agency (Motto: “Defending Our Nation. Securing the Future.”) Verschlüsselung im Internet in den nächsten 10 Jahren auf Elliptische-Kurven-Kryptographie umstellen will.
Elliptische Kurven über den komplexen (oder reellen) Zahlen werden dabei aber nicht zum Einsatz kommen. Warum? Letztlich, weil diese sich als Torus darstellen lassen.
Zunächst: elliptische Kurven sind Kurven mit der Gleichung y2=x3+ax+b für geeignete Zahlen a,b (und zusätzlich noch einem “Punkt im Unendlichen”), cf. TvF 92.
Auf elliptischen Kurven ist eine “Addition” anhand der folgenden Bilder definiert:
die Gerade durch 2 Punkte schneidet die Kurve in einem 3. Punkt, dessen Spiegelbild ist (per Definition) die Summe der ersten beiden Punkte.
(“P+Q” ist also nicht R, sondern das Spiegelbild von R an der x-Achse. Im Bild oben ist (2,5)+(-2,3)=(1/4,-33/8).)
Nullelement dieser Addition ist per Definition der Punkt im Unendlichen, inverses Element ist jeweils das Spiegelbild an der x-Achse (Bild in der Mitte rechts).
Analog: wenn man das Doppelte eines Punktes definieren will (Bild rechts Mitte), nimmt man die Tangente an den Punkt, deren zweiter Schnittpunkt mit der Kurve wird an der x-Achse gespiegelt.
In der Kryptographie nutzt man aus, daß es einfacher ist ng=g+g+…+g zu berechnen als umgekehrt, wenn ng bekannt ist, daraus n zu bestimmen. (Genau funktioniert der Diffie-Hellman-Schlüsselaustausch wie folgt: Der Sender merkt sich eine Zahl a und schickt ag an den den Empfänger, der Empfänger merkt sich eine Zahl b und schickt bg an den Sender, beide können jetzt abg=bag berechnen und verwenden im weiteren abg als gemeinsamen Schlüssel. Dieser Schlüssel ist sicher, weil er nie über das Netz übertragen wurde, und weil es für einen Hacker, der ag und bg abgefangen hat, schwierig ist, daraus a und b zu berechnen.)
Damit mit einer elliptischen Kurve sicher verschlüsselt werden kann, braucht man also: es gibt kein effizientes Verfahren, um n zu berechnen, wenn man P und nP kennt.
(D.h. man kann das Diskreter-Logarithmus-Problem auf der elliptischen Kurve nicht effizient lösen.)
Letzte Woche hatten wir aber erwähnt, daß jede (komplexe) elliptische Kurve E das Bild von einem Torus C/L ist. Die Abbildung C/L–>E ist gegeben durch z–>(p(z),p'(z)/2). (p(z) ist die Weierstraß-Funktion des Gitters.)
Es gibt eine “Additionsformel” für die p-Funktion, d.h. eine Formel für p(z1+z2), die letztlich gerade besagt, daß die Addition komplexer Zahlen in C/L genau der oben durch Bilder definierten Addition von Punkten der elliptischen Kurve E entspricht.
Wenn man weiß, wie sich eine elliptische Kurve als Torus C/L schreiben läßt, dann kann man damit leicht die Diffie-Hellmann-Entschlüsselung knacken: wenn man zwei komplexe Zahlen z und nz (modulo des Gitters L) gegeben hat, erfolgt die Berechnung einfach durch Division komplexer Zahlen.
Komplexe elliptische Kurven werden also bei der ‘Verteidigung der Heimat und Sicherung der Zukunft’ nicht mitmachen dürfen. Das bleibt elliptischen Kurven über endlichen Körpern vorbehalten.
Tatsächlich hat die NSA eine relativ kleine Liste elliptischer Kurven (nämlich 15, davon 10 über binären Körpern und 5 über Primkörpern), die verwendet werden sollen. Ein pikantes Detail am Rande: auf viele Eigenschaften von elliptischen Kurven gibt es Patente von Unternehmen oder Privatpersonen, die NSA mußte für einige der vorgeschlagenen Kurven zunächst eine Lizenz erwerben. (Einzelheiten hier, vorletzter Absatz.)
Teil 1, Teil 2, Teil 3, Teil 4, Teil 5, Teil 6, Teil 7 , Teil 8, Teil 9 , Teil 10 ,Teil 11, Teil 12, Teil 13, Teil 14, Teil 15, Teil 16, Teil 17, Teil 18, Teil 19, Teil 20, Teil 21, Teil 22, Teil 23, Teil 24, Teil 25, Teil 26, Teil 27, Teil 28, Teil 29, Teil 30, Teil 31, Teil 32, Teil 33, Teil 34, Teil 35, Teil 36, Teil 37, Teil 38, Teil 39, Teil 40, Teil 41, Teil 42, Teil 43, Teil 44, Teil 45, Teil 46, Teil 47, Teil 48, Teil 49, Teil 50, Teil 51, Teil 52, Teil 53, Teil 54, Teil 55, Teil 56, Teil 57, Teil 58, Teil 59, Teil 60, Teil 61, Teil 62, Teil 63, Teil 64, Teil 65, Teil 66, Teil 67, Teil 68, Teil 69, Teil 70, Teil 71, Teil 72, Teil 73, Teil 74, Teil 75, Teil 76, Teil 77, Teil 78, Teil 79, Teil 80, Teil 81, Teil 82, Teil 83, Teil 84, Teil 85, Teil 86, Teil 87, Teil 88, Teil 89, Teil 88, Teil 90, Teil 91, Teil 92, Teil 93
Kommentare (11)