Isogenien elliptischer Kurven: mathematische Grundlagen

Eine Isogenie zwischen zwei elliptischen Kurven E und E' über einem Körper k ist eine nichtkonstante rationale Abbildung phi: E -> E', die zugleich ein Gruppenhomomorphismus ist — sie überträgt die Gruppenverknüpfung von E auf die Gruppenverknüpfung von E'. Jede Isogenie phi besitzt eine duale Isogenie phi_hat: E' -> E, sodass die Komposition von phi_hat und phi auf E der Multiplikation mit deg(phi) entspricht. Der Grad einer Isogenie ist die Größe ihres Kerns: Eine Isogenie vom Grad l hat einen Kern der Größe l. Isogenien verallgemeinern die Skalarmultiplikation: Die Multiplikation mit n ist eine Isogenie von E nach E selbst vom Grad n^2. Isogenien über endlichen Körpern werden als rationale Funktionen (Polynome) berechnet, die sich effizient auswerten lassen.

Velu-Formeln (1971) liefern explizite Formeln zur Berechnung einer Isogenie phi: E -> E/G für eine Untergruppe G von E. Die Bildkurve E/G = E' und die rationale Abbildung phi werden vollständig durch G bestimmt. Velu-Formeln berechnen die Koeffizienten der Bildkurve und die rationale Abbildung als rationale Funktionen vom Grad |G|. Für eine Kernuntergruppe G von Primordnung l hat die Isogenie den Grad l und kann mit O(l) Operationen berechnet werden. sqrt-Velu-Algorithmen (Bernstein et al., 2019) reduzieren dies für große l auf O(sqrt(l)) Operationen und ermöglichen damit die effizienten Isogenien mit großen Primzahlen in CSIDH. Velu-Formeln sind das zentrale Berechnungswerkzeug der gesamten isogeniebasierten Kryptografie.

Elliptische Kurven über einem endlichen Körper Fp lassen sich in einem Isogeniegraphen organisieren. Die Knoten sind j-Invarianten elliptischer Kurven (eine kanonische Invariante, die die Kurve bis auf Isomorphie festlegt). Die Kanten sind l-Isogenien: Jede gewöhnliche Kurve besitzt für eine kleine Primzahl l genau l+1 ausgehende l-Isogenien (aufgrund der Struktur der l-Torsionsuntergruppen). Der l-Isogeniegraph über Fp ist ein (l+1)-regulärer Graph. Die Ramanujan-Eigenschaft dieser Graphen (Expandergraphen) bedeutet, dass sich Zufallswege auf ihnen schnell durchmischen. Sie liefert die Härteannahme, auf der isogeniebasierte Kryptografie beruht: Zufallswege der Länge O(log p) erzeugen gleichmäßige Verteilungen über j-Invarianten.

Elliptische Kurven über Fp fallen in zwei Kategorien. Gewöhnliche Kurven haben einen nichttrivialen p-Rang, das heißt, es gibt p^2 Isomorphieklassen und einen komplexen Isogeniegraphen mit Vulkanstruktur (Krater und Ebenen). Supersinguläre Kurven haben den p-Rang 0 und liegen alle in einem einzigen zusammenhängenden Isogeniegraphen über Fp2. Die Anzahl der supersingulären j-Invarianten über Fp beträgt ungefähr p/12. SIDH und SIKE verwenden supersinguläre Kurven, weil ihr Isogeniegraph ein Ramanujan-Graph mit starken Expansionseigenschaften ist und keine Vulkanstruktur besitzt, die die Richtung eines Weges verraten könnte. CSIDH verwendet ebenfalls supersinguläre Kurven, jedoch über Fp (nicht Fp2), und nutzt dabei eine andere algebraische Struktur.

Isogeniebasierte Kryptografie beruht auf zwei verwandten schwierigen Problemen. Supersingular Isogeny Problem (SSIP): Gegeben seien zwei supersinguläre elliptische Kurven E und E' über Fp2. Gesucht ist eine Isogenie phi: E -> E'. Computational Supersingular Isogeny (CSSI)-Problem: Gegeben seien E, E' = phi(E) und der Grad von phi. Gesucht ist phi. Der beste klassische Algorithmus für SSIP benötigt O(p^{1/4}) Zeit. Der beste Quantenalgorithmus (Tanis Suche nach Krallen) benötigt O(p^{1/6}) Zeit. Für p = 2^{434} ergibt sich daraus eine klassische Sicherheit von 128 Bit. Diese Quantenbeschleunigungen sind deutlich geringer als die exponentielle Beschleunigung von Shors Algorithmus gegen RSA/ECC, wodurch isogeniebasierte Verfahren postquantenresistent sind.

SIDH (Supersingular Isogeny Diffie-Hellman) verwendet eine speziell strukturierte Primzahl p = 2^a * 3^b - 1, die sicherstellt, dass die Kurve E über Fp2 über 2^a-Torsionspunkte (die Menge der Punkte P mit 2^a * P = 0) und zugängliche 3^b-Torsionspunkte verfügt. Alices Geheimnis ist eine 2^a-Isogenie phi_A: E -> E_A mit einem Kern, der von einem zufälligen Element der 2^a-Torsion erzeugt wird. Bobs Geheimnis ist eine 3^b-Isogenie phi_B: E -> E_B. Die beiden Parteien tauschen die Bilder der Torsionspunkte aus: Alice veröffentlicht E_A und phi_A(P_B), phi_A(Q_B). Bob veröffentlicht E_B und phi_B(P_A), phi_B(Q_A). Dadurch kann jede Partei Isogenien von der Kurve der jeweils anderen Partei aus berechnen und gelangt zur selben gemeinsamen j-Invariante.

Der Endomorphismenring End(E) einer elliptischen Kurve ist der Ring aller Isogenien von E nach E selbst (einschließlich Skalarmultiplikationen). Für gewöhnliche Kurven über Fp ist End(E) eine Ordnung in einem imaginär-quadratischen Körper. Für supersinguläre Kurven ist End(E) eine maximale Ordnung in einer Quaternionenalgebra, die bei p und unendlich ramifiziert ist. Die Struktur von End(E) bestimmt die Kurve vollständig bis auf Isomorphie. Das Endomorphismenringproblem — die Berechnung von End(E) bei gegebenem E — gilt als schwierig (für supersinguläre Kurven ist es äquivalent zu SSIP). Der Angriff von Castryck und Decru auf SIDH/SIKE nutzte zusätzliche Informationen aus, die das SIDH-Protokoll preisgab, um effizient einen Teil des Endomorphismenrings zu rekonstruieren und das Verfahren zu brechen.

Eine Isogenie vom Grad l, phi: E -> E', kann als Polynom vom Grad l dargestellt werden (oder nach einer Symmetrieoptimierung als Polynom vom Grad l/2, wobei Punktinverse dieselbe x-Koordinate haben). Die Berechnung von phi(P) für einen gegebenen Punkt P erfordert mit Velu-Formeln O(l) Multiplikationen. Für SIDH mit l = 2^a von ungefähr 2^216 scheint dies unpraktikabel, aber SIDH nutzt die Tatsache, dass 2^a-Isogenien in eine Kette aus a einzelnen 2-Isogenien zerlegt werden können — jede 2-Isogenie ist kostengünstig, und eine Kette aus a Schritten erzeugt eine 2^a-Isogenie. Entsprechend gilt dies für 3^b. sqrt-Velu ermöglicht, dass die Berechnung von Isogenien mit großen ungeraden Primgraden in CSIDH mit O(sqrt(l)) statt O(l) ausgeführt werden kann, wodurch CSIDH praktisch nutzbar wird.

SIKE (Supersingular Isogeny Key Encapsulation) war ein NIST-PQC-Kandidat, der alle Runden bis zur vierten Runde überstand, in der er gebrochen wurde. SIKE zeichnete sich durch die kleinsten Schlüsselgrößen aller NIST-Kandidaten aus: 374 Byte für SIKEp434 (NIST Level 1). Zum Vergleich: ML-KEM-512 hat 800 Byte große öffentliche Schlüssel. Diese Kompaktheit erreichte SIKE, weil das gemeinsame Geheimnis aus einer einzelnen j-Invariante abgeleitet wird (einem Feldelement von etwa 430 Bit). Die Kompaktheit hatte ihren Preis: SIKE war 100- bis 1000-mal langsamer als andere Kandidaten. Als Castryck und Decru SIKE im Juli 2022 mit einem klassischen Angriff brachen, der auf einem Laptop nur wenige Minuten dauerte, wurde SIKE sofort aus dem NIST-Wettbewerb entfernt.

Isogeniebasierte Kryptografie nimmt unter den Postquanten-Ansätzen eine einzigartige Stellung ein. Schlüsselgrößen: deutlich kleiner als bei gitterbasierten Verfahren (ML-KEM: 800+ Byte) oder hashbasierten Signaturen (SLH-DSA: öffentlicher Schlüssel mit 32–49 Byte, aber Signaturen mit 7856–49856 Byte). Leistung: deutlich langsamer als alle Alternativen (SIKE war 100- bis 1000-mal langsamer als ML-KEM). Sicherheitsannahme: unterscheidet sich von LWE (verwendet in ML-KEM/ML-DSA), SIS oder Hashfunktionen und sorgt damit für kryptografische Diversität. Grundlage der Postquanten-Sicherheit: Für das Isogeniepfadproblem ist kein Quantenalgorithmus in Polynomialzeit bekannt, anders als bei RSA/ECC, die durch Shors Algorithmus vollständig gebrochen werden. Der klassische Bruch von SIKE zeigt, dass die Härte von Isogenieproblemen noch nicht vollständig verstanden ist, anders als das gut untersuchte LWE-Problem.

Trotz des Bruchs von SIKE bleibt die isogeniebasierte Kryptografie ein aktives Forschungsgebiet. SQISign (Short Quaternion and Isogeny Signature) ist ein isogeniebasiertes Signaturverfahren mit 177-Byte-Signaturen (gegenüber 2420 Byte bei ML-DSA für Level 2) — die kleinsten bekannten PQC-Signaturen. SQISign nutzt das schwierige Problem, eine Isogenie vorgegebenen Grades zwischen zwei gegebenen supersingulären Kurven zu berechnen, formalisiert als Endomorphismenringproblem. FESTA (Fast Encryption from Supersingular Torsion Attacks) ist ein neuer KEM-Entwurf, der die zusätzlichen Hilfsdaten zu Torsionspunkten vermeidet, die SIDH verwundbar machten. CTIDH (Constant-Time CSIDH) verbessert die Leistung von CSIDH. Diese Verfahren halten die Isogenieforschung auch nach dem Ausscheiden von SIKE relevant.

Was ist eine Isogenie zwischen elliptischen Kurven?

Eine Isogenie ist eine rationale Abbildung phi: E -> E', die ein Gruppenhomomorphismus ist und deren Grad der Größe ihres Kerns entspricht. Velu-Formeln berechnen die Bildkurve und die Abbildung ausgehend von der Kernuntergruppe. Isogeniegraphen stellen Kurven als Knoten dar, deren l-Isogenie-Kanten (l+1)-reguläre Ramanujan-Graphen bilden. Supersinguläre Kurven (verwendet in SIDH/SIKE/CSIDH) besitzen Isogeniegraphen mit starken Expansionseigenschaften. Die Probleme SSIP und CSSI bilden die Grundlage der Sicherheit von Isogenieverfahren. SIDH nutzt die Struktur von Torsionspunkten mit abwechselnden Ketten aus 2- und 3-Isogenien. Die Berechnung des Endomorphismenrings ist äquivalent zu SSIP. SQISign und FESTA sind aktive Forschungsrichtungen nach SIKE, die auf der Schwierigkeit des Endomorphismenringproblems beruhen.