Isogénies de courbes elliptiques : fondements mathématiques

Une isogénie entre deux courbes elliptiques E et E' sur un corps k est une application rationnelle non constante phi: E -> E' qui est également un homomorphisme de groupes — elle préserve la loi de groupe de E et celle de E'. Toute isogénie phi possède une isogénie duale phi_hat: E' -> E telle que phi_hat composée avec phi soit égale à la multiplication par deg(phi) sur E. Le degré d’une isogénie est la cardinalité de son noyau : une isogénie de degré l possède un noyau de cardinalité l. Les isogénies généralisent la multiplication scalaire : la multiplication par n est une isogénie de E vers elle-même, de degré n^2. Les isogénies sur les corps finis se calculent comme des fonctions rationnelles (polynômes) qui peuvent être évaluées efficacement.

Les formules de Vélu (1971) fournissent des formules explicites pour calculer une isogénie phi: E -> E/G étant donné un sous-groupe G de E. La courbe image E/G = E' et l’application rationnelle phi sont entièrement déterminées par G. Les formules de Vélu calculent les coefficients de la courbe image et l’application rationnelle sous forme de fonctions rationnelles de degré égal à |G|. Pour un sous-groupe noyau G d’ordre premier l, l’isogénie est de degré l et se calcule en O(l) opérations. Les algorithmes sqrt-Velu (Bernstein et al., 2019) réduisent ce coût à O(sqrt(l)) opérations pour les grandes valeurs de l, ce qui permet les isogénies efficaces à grand nombre premier de CSIDH. Les formules de Vélu constituent l’outil de calcul central de toute la cryptographie fondée sur les isogénies.

Les courbes elliptiques sur un corps fini Fp peuvent être organisées en graphe d’isogénies. Les sommets sont les invariants j des courbes elliptiques (un invariant canonique qui détermine la courbe à isomorphisme près). Les arêtes sont des l-isogénies : chaque courbe ordinaire possède exactement l+1 l-isogénies sortantes pour un petit nombre premier l (en raison de la structure des sous-groupes de l-torsion). Le graphe des l-isogénies sur Fp est un graphe (l+1)-régulier. La propriété de Ramanujan de ces graphes (graphes expanseurs) signifie que les marches aléatoires sur ceux-ci se mélangent rapidement, ce qui fournit l’hypothèse de difficulté à la base de la cryptographie fondée sur les isogénies : des marches aléatoires de longueur O(log p) produisent des distributions uniformes sur les invariants j.

Les courbes elliptiques sur Fp se répartissent en deux catégories. Les courbes ordinaires ont un p-rang non trivial, ce qui signifie qu’il existe p^2 classes d’isomorphisme et un graphe d’isogénies complexe en forme de volcan (cratères et niveaux). Les courbes supersingulières ont un p-rang nul et se trouvent toutes dans un unique graphe d’isogénies connexe sur Fp2. Le nombre d’invariants j supersinguliers sur Fp est approximativement p/12. SIDH et SIKE utilisent des courbes supersingulières, car leur graphe d’isogénies est un graphe de Ramanujan à forte expansion et dépourvu de structure en volcan susceptible de révéler la direction de la marche. CSIDH utilise également des courbes supersingulières, mais sur Fp (et non Fp2), en exploitant une structure algébrique différente.

La cryptographie fondée sur les isogénies repose sur deux problèmes difficiles apparentés. Problème des isogénies supersingulières (SSIP) : étant données deux courbes elliptiques supersingulières E et E' sur Fp2, trouver une isogénie phi: E -> E'. Problème de calcul d’une isogénie supersingulière (CSSI) : étant donnés E, E' = phi(E) et le degré de phi, trouver phi. Le meilleur algorithme classique pour SSIP s’exécute en O(p^{1/4}). Le meilleur algorithme quantique (recherche de griffes de Tani) s’exécute en O(p^{1/6}). Pour p = 2^{434}, cela donne une sécurité classique de 128 bits. Ces accélérations quantiques sont nettement moins importantes que l’accélération exponentielle de l’algorithme de Shor contre RSA/ECC, ce qui rend les schémas fondés sur les isogénies sûrs à l’ère post-quantique.

SIDH (Diffie-Hellman par isogénies supersingulières) utilise un nombre premier de structure particulière p = 2^a * 3^b - 1 qui garantit que la courbe E sur Fp2 possède des points de 2^a-torsion (l’ensemble des points P tels que 2^a * P = 0) ainsi que des points de 3^b-torsion accessibles. Le secret d’Alice est une isogénie de degré 2^a phi_A: E -> E_A dont le noyau est engendré par un élément aléatoire de la 2^a-torsion. Le secret de Bob est une isogénie de degré 3^b phi_B: E -> E_B. Ils échangent les images des points de torsion : Alice publie E_A et phi_A(P_B), phi_A(Q_B). Bob publie E_B et phi_B(P_A), phi_B(Q_A). Cela permet à chaque partie de calculer des isogénies à partir de la courbe de l’autre et d’aboutir au même invariant j commun.

L’anneau des endomorphismes End(E) d’une courbe elliptique est l’anneau de toutes les isogénies de E vers elle-même (y compris les multiplications scalaires). Pour les courbes ordinaires sur Fp, End(E) est un ordre dans un corps quadratique imaginaire. Pour les courbes supersingulières, End(E) est un ordre maximal dans une algèbre de quaternions ramifiée en p et à l’infini. La structure de End(E) détermine entièrement la courbe à isomorphisme près. Le problème de l’anneau des endomorphismes — calculer End(E) étant donnée E — est réputé difficile (équivalent à SSIP pour les courbes supersingulières). L’attaque de Castryck-Decru contre SIDH/SIKE a exploité des informations supplémentaires divulguées par le protocole SIDH pour reconstruire efficacement une partie de l’anneau des endomorphismes, cassant ainsi le schéma.

Une isogénie de degré l phi: E -> E' peut être représentée par un polynôme de degré l (ou l/2 après une optimisation par symétrie utilisant le fait que les inverses de points ont la même coordonnée x). Calculer phi(P) pour un point P donné nécessite O(l) multiplications à l’aide des formules de Vélu. Pour SIDH avec l = 2^a proche de 2^216, cela semble prohibitif, mais SIDH exploite le fait que les isogénies de degré 2^a peuvent être décomposées en une chaîne de a isogénies de degré 2 — chaque isogénie de degré 2 est peu coûteuse, et une chaîne de a étapes produit une isogénie de degré 2^a. De même pour 3^b. Les algorithmes sqrt-Velu permettent d’effectuer les calculs d’isogénies à grand nombre premier impair de CSIDH en O(sqrt(l)) plutôt qu’en O(l), ce qui rend CSIDH pratique.

SIKE (encapsulation de clé par isogénies supersingulières) était un candidat de la compétition PQC de NIST qui a franchi tous les tours jusqu’au quatrième, où il a été cassé. SIKE se distinguait par les plus petites tailles de clés parmi tous les candidats de NIST : 374 octets pour SIKEp434 (niveau 1 de NIST). En comparaison, ML-KEM-512 possède des clés publiques de 800 octets. Cette compacité était possible parce que le secret partagé est dérivé d’un seul invariant j (un élément de corps d’environ 430 bits). Cette compacité avait un coût : SIKE était 100 à 1000 fois plus lent que les autres candidats. Lorsque Castryck et Decru ont cassé SIKE en juillet 2022 au moyen d’une attaque classique s’exécutant en quelques minutes sur un ordinateur portable, SIKE a été immédiatement éliminé de la compétition de NIST.

La cryptographie fondée sur les isogénies occupe une position unique parmi les approches post-quantiques. Tailles des clés : bien plus petites que celles des approches fondées sur les réseaux (ML-KEM : plus de 800 octets) ou des signatures fondées sur les fonctions de hachage (SLH-DSA : clé publique de 32 à 49 octets, mais signatures de 7856 à 49856 octets). Performances : bien plus lentes que toutes les autres solutions (SIKE était 100 à 1000 fois plus lent que ML-KEM). Hypothèse de sécurité : distincte de LWE (utilisé dans ML-KEM/ML-DSA), de SIS ou des fonctions de hachage — elle offre une diversité cryptographique. Fondement de la sécurité post-quantique : le problème du chemin d’isogénie ne possède aucun algorithme quantique en temps polynomial connu, contrairement à RSA/ECC, que l’algorithme de Shor casse complètement. La cassure classique de SIKE montre que la difficulté des isogénies est encore à l’étude, contrairement au problème LWE, bien étudié.

Malgré la cassure de SIKE, la cryptographie fondée sur les isogénies demeure un domaine de recherche actif. SQISign (signature courte par quaternion et isogénie) est un schéma de signature fondé sur les isogénies avec des signatures de 177 octets (contre 2420 octets pour ML-DSA au niveau 2) — les plus petites signatures PQC connues. SQISign utilise le problème difficile consistant à calculer une isogénie de degré prescrit entre deux courbes supersingulières données, formalisé comme le problème de l’anneau des endomorphismes. FESTA (chiffrement rapide fondé sur des attaques de torsion supersingulière) est une nouvelle conception de KEM qui évite les données auxiliaires supplémentaires des points de torsion ayant rendu SIDH vulnérable. CTIDH (CSIDH à temps constant) améliore les performances de CSIDH. Ces schémas maintiennent la pertinence de la recherche sur les isogénies, même après l’élimination de SIKE.

Qu’est-ce qu’une isogénie entre courbes elliptiques ?

Une isogénie est une application rationnelle phi: E -> E' qui est un homomorphisme de groupes, dont le degré est égal à la cardinalité de son noyau. Les formules de Vélu calculent la courbe image et l’application à partir du sous-groupe noyau. Les graphes d’isogénies organisent les courbes en sommets reliés par des arêtes l-isogénies formant des graphes de Ramanujan (l+1)-réguliers. Les courbes supersingulières (utilisées dans SIDH/SIKE/CSIDH) ont des graphes d’isogénies à forte expansion. Les problèmes SSIP et CSSI sous-tendent la sécurité des isogénies. SIDH utilise la structure des points de torsion avec des chaînes alternées d’isogénies de degré 2 et 3. Le calcul de l’anneau des endomorphismes est équivalent à SSIP. SQISign et FESTA représentent des axes de recherche post-SIKE actifs qui utilisent la difficulté du problème de l’anneau des endomorphismes.