CSIDH: kommutative supersinguläre Isogenien

CSIDH (Commutative Supersingular Isogeny Diffie-Hellman, Castryck et al., 2018) ist ein isogeniebasierter Schlüsselaustausch, der das Leakage von Torsionspunkten aus SIDH vollständig vermeidet, indem er eine grundlegend andere algebraische Struktur verwendet. CSIDH arbeitet mit supersingulären Kurven über Fp (nicht über Fp2 wie SIDH). Die Härteannahme beruht auf der Kommutativität der Wirkung der Klassengruppe: Beide Parteien wenden jeweils ein geheimes Element der Klassengruppe auf eine gemeinsame Ausgangskurve an, und die Kommutativität stellt sicher, dass beide auf derselben gemeinsamen Kurve landen. Es werden keine zusätzlichen Informationen über Torsionspunkte veröffentlicht – der öffentliche Schlüssel besteht lediglich aus einer einzelnen j-Invariante. Dieses Design überstand den Angriff von Castryck und Decru auf SIDH.

Über Fp mit p = 3 mod 4 besitzen die supersingulären Kurven E einen ausgezeichneten Endomorphismus pi (den Frobenius), und ihre Endomorphismenalgebra enthält die imaginär-quadratische Ordnung Z[pi]. Die Idealklassengruppe Cl(Z[pi]) wirkt frei und transitiv auf der Menge der supersingulären Kurven über Fp (bis auf Isomorphie). Ein Ideal a in Cl(Z[pi]) wirkt auf eine Kurve E und erzeugt eine neue Kurve a * E, die als die Kurve E/E[a] berechnet wird, wobei E[a] die zugehörige Torsionsuntergruppe des Ideals a ist. Diese Wirkung ist kommutativ: a * (b * E) = b * (a * E) = [ab] * E. Dies ist die Gruppenwirkung von CSIDH und liefert ein kommutatives Analogon zu Diffie-Hellman.

Der CSIDH-Schlüsselaustausch läuft wie folgt ab. Öffentliche Parameter: eine supersinguläre Kurve E0 über Fp und kleine ungerade Primzahlen l_1, ..., l_n. Geheime Schlüssel: Alice wählt a = (a_1, ..., a_n), wobei jedes a_i in {-m, ..., m} liegt (zufällige kleine Ganzzahlen). Bob wählt b = (b_1, ..., b_n). Alices öffentlicher Schlüssel: E_A = [l_1^a_1 * ... * l_n^a_n] * E0. Bobs öffentlicher Schlüssel: E_B = [l_1^b_1 * ... * l_n^b_n] * E0. Gemeinsamer geheimer Wert: Alice wendet ihre geheimen Exponenten auf E_B an; Bob wendet seine auf E_A an. Die Kommutativität stellt sicher, dass beide E_AB = [product(l_i^(a_i + b_i))] * E0 erhalten. Der gemeinsame geheime Wert ist j(E_AB). Es werden keine zusätzlichen Punkte veröffentlicht.

Die Referenzimplementierung von CSIDH verwendet p = 4 * l_1 * l_2 * ... * l_74 - 1, wobei l_1 bis l_74 die ersten 74 ungeraden Primzahlen sind (3, 5, 7, ..., 373). Dadurch ist p ungefähr 512 Bit groß. Jede Komponente des geheimen Schlüssels a_i liegt in {-5, ..., 5} (11 Möglichkeiten pro Komponente, 74 Komponenten). Die Ordnung der Klassengruppe beträgt ungefähr sqrt(p), und der Schlüsselraum hat die Größe 11^74. Zur Berechnung jedes Isogenieschritts wird für jede Primzahl l_i die l_i-Torsionsuntergruppe bestimmt und die l_i-Isogenie mithilfe der Formeln von Velu berechnet. Mit sqrt-Velu benötigt jeder Isogenieschritt für eine große Primzahl O(sqrt(l_i)) Operationen. Der gesamte Schlüsselaustausch dauert bei CSIDH-512 auf moderner Hardware ungefähr 1–5 ms.

Das ursprüngliche CSIDH arbeitet nicht in konstanter Zeit: Die Anzahl der Velu-Schritte hängt von den Werten des geheimen Schlüssels a_i ab und kann über Seitenkanäle zur Laufzeit Informationen preisgeben. CTIDH (Constant-Time ISOGENY Diffie-Hellman, Bernstein et al., 2021) behebt dies durch ein Schlüssel-Format mit fester Gewichtung und eine sorgfältig entwickelte Isogenieberechnung in konstanter Zeit. Geheime CTIDH-Schlüssel sind auf Vektoren beschränkt, für die die Summe der Absolutwerte festgelegt ist (z. B. sum |a_i| = 130). Die Isogenieberechnung läuft unabhängig von den Werten des geheimen Schlüssels in einer festen Anzahl von Schritten ab und verwendet Dummy-Isogenieberechnungen, um Schritte aufzufüllen, bei denen der geheime Exponent null ist. CTIDH erreicht eine ähnliche Sicherheit wie CSIDH-512 und bietet strikte Garantien für konstante Laufzeit, die für den Einsatz in eingebetteten Systemen geeignet sind.

Die Quantensicherheit von CSIDH ist differenzierter zu betrachten als bei gitterbasierten Verfahren. Der beste Quantenangriff verwendet Kuperbergs Algorithmus (2005) für das Hidden-Shift-Problem und bricht die Struktur der Wirkung der Klassengruppe in subexponentieller Zeit L(1/2) = exp(O(sqrt(log p))). Das ist deutlich besser als der beste klassische Angriff mit sqrt(p), wodurch Quantencomputer die Sicherheit von CSIDH gegenüber klassischen Angreifern erheblich schwächen. Für eine 128-Bit-Sicherheit nach dem Aufkommen von Quantencomputern (gegen den Angriff L(1/2)) benötigt CSIDH eine Primzahl p mit ungefähr 5000 Bit (CSIDH-5000) – im Vergleich zu 512 Bit für eine klassische 128-Bit-Sicherheit. Für CSIDH-512 werden lediglich 62–72 Bit Quantensicherheit geschätzt, also deutlich weniger als die Anforderungen von NIST Level 1.

Die Sicherheit von CSIDH beruht auf dem Inversenproblem der Gruppenwirkung (Group Action Inverse Problem, GAIP): Gegeben E_A = a * E0 und E0, soll a gefunden werden. Der beste bekannte Algorithmus ist eine Pohlig-Hellman-ähnliche Reduktion in Kombination mit Baby-Step-Giant-Step und benötigt klassisch O(sqrt(|Cl|)) ~ O(p^{1/4}). Die quantenmechanische Schwierigkeit (Kuperberg) macht CSIDH weniger quantensicher als LWE-basierte Verfahren. Der beste Quantenangriff auf LWE (Gitter-Sieving) bietet konservativere Sicherheitsmargen. Der Vorteil von CSIDH ist seine Kompaktheit: CSIDH-512 hat 64 Byte große öffentliche Schlüssel (nur die j-Invariante), verglichen mit 800 Byte bei ML-KEM-512. Für Anwendungen, die die kleinstmöglichen Schlüssel benötigen und geringere quantenmechanische Sicherheitsmargen akzeptieren, bleibt CSIDH interessant.

Mehrere CSIDH-Varianten versuchen, die Einschränkungen bei der Quantensicherheit zu beheben. BSIDH (B für „better“) verwendet Basiskurven höheren Grades und Produkte elliptischer Kurven, um die Größe der Klassengruppe zu erhöhen und die Berechnung dennoch schnell zu halten. Csurf (CSIDH on the surface) arbeitet mit einer anderen Menge supersingulärer Kurven, um eine schnellere Berechnung der Gruppenwirkung zu ermöglichen. CSIDH-Vorschläge mit höherem Geschlecht verwenden Jacobimannigfaltigkeiten von Kurven des Geschlechts 2 über Fp und bieten dadurch einen größeren Raum für die Gruppenwirkung mit potenziell besseren quantenmechanischen Sicherheitsmargen. Keine dieser Varianten wurde bisher weitverbreitet eingesetzt oder von NIST berücksichtigt, unter anderem weil die Analyse der Quantensicherheit von CSIDH-Varianten noch fortlaufend weiterentwickelt wird und weniger ausgereift ist als bei gitterbasierten Verfahren.

CSIDH und SIDH unterscheiden sich grundlegend. Kommutativität: CSIDH verwendet eine kommutative Gruppenwirkung (Klassengruppe); SIDH ist ein nicht interaktiver Schlüsselaustausch auf Basis nicht kommutativer Isogenien mit zusätzlichen Torsionspunkten. Grundkörper: CSIDH arbeitet über Fp, SIDH über Fp2 (quadratische Erweiterung). Größe des öffentlichen Schlüssels: CSIDH benötigt 64 Byte (eine einzelne j-Invariante über Fp); SIDH benötigt mindestens 324 Byte (Kurve plus zwei Fp2-Punkte). Sicherheit: CSIDH hat den Angriff von Castryck und Decru überstanden; SIDH wurde gebrochen. Quantensicherheit: CSIDH benötigt Primzahlen mit 5000 Bit für eine quantenmechanische 128-Bit-Sicherheit; vor dem klassischen Angriff bot SIDH eine vergleichbare Quantenresistenz. Leistung: CSIDH-512 benötigt etwa 1–5 ms; SIDH war ähnlich schnell, CSIDH-5000 wäre jedoch deutlich langsamer.

Die Kommutativität von CSIDH ermöglicht einen nicht interaktiven Schlüsselaustausch (NIKE): Alice veröffentlicht E_A = a * E0, Bob veröffentlicht E_B = b * E0. Später kann jede Person ohne weitere Kommunikation das gemeinsame Geheimnis aus einem der beiden öffentlichen Schlüssel berechnen: Alice berechnet a * E_B = a * (b * E0) = ab * E0; Bob berechnet b * E_A = b * (a * E0) = ab * E0. Diese NIKE-Eigenschaft ist für Anwendungen wertvoll, bei denen ein interaktiver Schlüsselaustausch unpraktisch ist – etwa bei der E-Mail-Verschlüsselung, wenn Absender und Empfänger nicht gleichzeitig online sind. NIKE mit CSIDH ist analog zu Diffie-Hellman-NIKE, aber quantensicher. ML-KEM (basierend auf LWE) unterstützt NIKE nicht ohne Weiteres und benötigt dafür ein zusätzliches Protokolldesign.

CSIDH wurde noch nicht standardisiert und wird bisher nicht in Produktivsystemen eingesetzt. Es ist ein aktives Forschungsthema, für das Implementierungen verfügbar sind: CTIDH (konstante Laufzeit), csidh-reference (Python, für Lehrzwecke) und supersingular-isogeny-toolbox (optimiertes C). Das wichtigste Hindernis für eine Bereitstellung ist die Quantensicherheit: Die geschätzte Quantensicherheit von CSIDH-512 liegt mit 62–72 Bit unter NIST Level 1 (128 Bit), wodurch es für Post-Quanten-Anwendungen mit erforderlicher NIST-Konformität ungeeignet ist. CSIDH-5000 würde die Sicherheitsanforderung erfüllen, wäre aber erheblich langsamer. Die Forschung arbeitet weiter an einer besseren Analyse der Quantensicherheit und an Varianten, die diese Lücke schließen. Stand 2024 bleibt CSIDH jedoch ein Forschungsprototyp und ist noch keine bereit für den produktiven Einsatz geeignete kryptografische Primitive.

Warum ermöglicht die kommutative Gruppenwirkung der Klassengruppe von CSIDH einen nicht interaktiven Schlüsselaustausch?

CSIDH verwendet die kommutative Gruppenwirkung der Klassengruppe Cl(Z[pi]) auf supersingulären Kurven über Fp, wobei pi der Frobenius-Endomorphismus ist. Öffentliche Schlüssel bestehen aus einzelnen j-Invarianten (64 Byte). Es werden keine zusätzlichen Torsionspunkte veröffentlicht, wodurch die Schwachstelle von SIDH vermieden wird. Die Gruppenwirkung der Klassengruppe ist kommutativ und ermöglicht dadurch NIKE. Der beste klassische Angriff benötigt O(p^{1/4}); der beste Quantenangriff (Kuperberg) läuft in subexponentieller Zeit L(1/2), sodass für eine quantenmechanische 128-Bit-Sicherheit Primzahlen mit 5000 Bit erforderlich sind. CTIDH bietet eine Implementierung mit konstanter Laufzeit. CSIDH-512 bietet nur etwa 65 Bit Quantensicherheit. CSIDH ist nicht standardisiert; die Forschung konzentriert sich auf Varianten, die bei kompakten Schlüsseln eine bessere Quantenresistenz erreichen.