Courbes elliptiques : les maths dans ta poche

Voici l'équation y² = x³ − x + 1. Si tu la traces, tu obtiens une ligne courbée — une courbe elliptique. Ça ressemble à quelque chose sorti d'un livre de maths auquel tu ne penses plus jamais. Mais c'est exactement ce genre de ligne qui se trouve dans la puce de ta carte d'identité, derrière le petit cadenas de ton navigateur, et sous Bitcoin. Dans ce chapitre, tu vas cliquer dessus et voir pourquoi.

Les mots dont tu as besoin

Courbe: Simplement une ligne courbée dans un graphique : tous les points (x, y) pour lesquels une équation est vraie. Une parabole est une courbe. Celle-ci est un peu plus intéressante.
Additionner des points: Voici l'idée bizarre. Sur cette courbe, tu peux « additionner » deux points et obtenir un troisième point sur la même courbe. Pas en additionnant les coordonnées, mais avec une règle de tracé : tire une ligne par les deux points, regarde où elle coupe la courbe une troisième fois, et reflète ce point par rapport à l'axe des x. Voilà : c'est P + Q.
Doubler: P + P. Tu n'as qu'un seul point, donc tu prends la tangente — la ligne qui touche la courbe en P exactement — et tu fais le même tour.
Arithmétique modulaire (modulo): Calculer uniquement avec des nombres entiers de 0 jusqu'à une limite, en recommençant à 0 après cette limite. Tu connais ça du chapitre 6, où c'était le moteur sous Diffie–Hellman. Ici, tu vois ce que ça fait à un graphique.

Clique sur la courbe

Tout se passe dans ton navigateur. Rien n'est envoyé au serveur.

Clique quelque part sur la ligne. C'est P. Clique une deuxième fois pour Q. La démo trace la ligne, trouve le troisième point d'intersection, le reflète, et montre P + Q.
Clique sur Effacer, choisis un point et appuie sur Doubler. Continue ensuite à cliquer sur Additionner P encore une fois : 3·P, 4·P, 5·P… Les points bondissent sur toute la courbe.
Fais glisser a et b. La forme change — parfois la ligne se scinde en deux morceaux. Cherche la position où elle forme un pli : elle est inutilisable, et la démo dit pourquoi.
Appuie sur Arithmétique modulaire (modulo 97). Même équation, seulement avec des nombres entiers. Regarde ce qu'il reste de la ligne. Choisis un point et additionne à nouveau.

a =

b =

Ce que tu viens de voir

Sur la ligne lisse, tu pouvais encore un peu « sentir » où tu te trouvais. Après trois additions, tu es à peu près là, après quatre, à peu près là. Mais dès que tu es passé à l'arithmétique modulaire, la ligne s'est effondrée en un nuage de points sans aucun motif. Et l'addition fonctionnait toujours — mêmes formules, mêmes règles — sauf que le résultat saute maintenant dans tous les sens sur le plan.

Maintenant, tout le secret. Suppose que je choisisse un point P et que je l'additionne à lui-même 1 000 000 de fois. Un ordinateur peut faire ça à toute vitesse — il existe une astuce qui ne demande qu'une trentaine d'étapes. Je te donne P et le point final. Peux-tu deviner que c'était 1 000 000 de fois ? Sur le nuage de points de 97, encore oui : il n'y a qu'une centaine de points, et tu essaies simplement tout. Mais la courbe dans ta carte d'identité a environ 2³⁸⁴ points. Ce nombre a 116 chiffres. Personne n'essaie tout, même pas un superordinateur, même pas en un milliard d'années.

Tout essayer n'est d'ailleurs même pas l'attaque la plus maligne. Il existe un raccourci, trouvé par John Pollard en 1978, qui demande à peu près la racine carrée du nombre de points : environ 2¹⁹² étapes. Ce nombre a encore 58 chiffres, et personne n'y arrive non plus. Les cryptographes comptent toujours avec le meilleur raccourci connu, jamais avec « tout essayer ». Ça va compter dans un instant.

C'est ça, la clé privée : le nombre de fois. La clé publique est le point final. Tout le monde peut voir le point final ; personne ne peut remonter en arrière. Exactement le cadenas ouvert du chapitre précédent — mais avec un graphique au lieu de nombres premiers.

Combien de points ? On pourrait croire : modulo 97, donc 97 points. Ça ne marche pas comme ça. En mode horloge, la démo les compte pour toi. Avec a = −1 et b = 1, il y en a par hasard exactement 97, plus le point à l'infini : 98. Reviens à la ligne lisse, déplace a ou b et rebascule : tu obtiens alors par exemple 80, 106 ou 117. Impossible de deviner le nombre, mais il n'est jamais loin de 97. Helmut Hasse a démontré en 1933 qu'il ne s'écarte jamais de plus de 2√p de p + 1 ; pour 97, ça donne entre 79 et 117. Pour P-384, le nombre de points est connu exactement, et c'est lui-même un nombre premier. Ce n'est pas un hasard : la courbe a été choisie pour ça.

Pourquoi des courbes et pas simplement RSA

	RSA (nombres premiers)	Courbes elliptiques
Aussi sûr avec	une clé de 3072 bits	une clé de 256 bits
La meilleure attaque connue demande	environ 2¹²⁸ étapes	environ 2¹²⁸ étapes
Ça fait	un nombre de 925 chiffres	un nombre de 78 chiffres
Tient sur une carte à puce ?	tout juste	largement
Inventé en	1977	1985, par Neal Koblitz et Victor Miller, indépendamment l'un de l'autre

Des clés douze fois plus courtes pour la même sécurité. Ça ne veut pas dire que RSA est mal conçu. « Aussi sûr » veut dire : la meilleure attaque connue demande autant d'étapes des deux côtés. Contre RSA, les attaquants disposent depuis le début des années 1990 d'un outil malin, le crible algébrique, qui factorise bien plus vite que tout essayer. Contre une courbe bien choisie, personne n'a rien trouvé de pareil ; le raccourci de Pollard reste ce qu'il y a de mieux. RSA doit donc prendre de plus grands nombres pour donner autant de travail à l'attaquant.

C'est pourquoi le monde bascule : les cartes d'identité belges les plus récentes utilisent une courbe (nommée P-384), les cartes plus anciennes utilisent encore RSA. P-384 se situe une marche au-dessus du tableau : environ 2¹⁹² étapes. Avec RSA, il faudrait pour ça 7680 bits, un nombre de 2312 chiffres. Le petit cadenas de ton navigateur convient de la clé avec une courbe. Ta clé Bitcoin est un point sur une courbe ; l'adresse que tu communiques est l'empreinte de ce point (voir chapitre 3).

La règle pour a et b. En faisant glisser les curseurs, tu as vu que certaines positions donnent un pli ou une boucle. Mathématiquement : si 4a³ + 27b² = 0, la courbe est « dégénérée » et l'addition ne fonctionne plus partout. Les cryptographes choisissent donc a et b avec soin — et ils les publient, pour que tout le monde puisse vérifier qu'aucune faiblesse secrète n'y est cachée. Cette méfiance est un métier en soi.

Voici les maths : un groupe

Ce que tu viens de faire — « additionner » des points avec une règle de tracé — a toutes les propriétés d'une addition ordinaire. C'est associatif : (P + Q) + R = P + (Q + R), même si tu ne le vois pas tout de suite. Il y a un « zéro » (le point à l'infini, que tu as rencontré quand la ligne devenait verticale). Chaque point a un opposé (son image miroir). Les mathématiciens appellent un tel ensemble muni d'une telle opération un groupe. C'est le premier chapitre de l'algèbre abstraite, la matière dans laquelle tu apprends que les nombres, les rotations d'un cube et les points sur une courbe jouent tous, au fond, au même jeu. C'est au programme de la première année de tout cursus universitaire en mathématiques.

Et ce jeu va bien au-delà des codes secrets. Les mouvements d'un Rubik's Cube forment un groupe, avec plus de 43 trillions de positions. Les chimistes classent les molécules selon leur groupe de symétrie et s'en servent pour prédire quelle lumière une molécule peut absorber. Il existe exactement 230 sortes de symétrie possibles pour un cristal ; on les a dénombrées en 1891, grâce à la théorie des groupes. Les physiciens construisent leur description des plus petites particules, le Modèle standard, sur des groupes. Et le QR code d'un billet de concert se lit encore quand il manque un coin, grâce à de l'algèbre sur un ensemble fini de nombres, comme ici. La cryptographie n'est qu'un petit coin de ce monde.

Attention : ce n'est pas le groupe lui-même qui protège ta carte d'identité. Les groupes sont partout, et la plupart ne servent à rien pour garder un secret. L'horloge avec l'addition ordinaire est aussi un groupe, et là tu remontes en une seule division. La sécurité tient à une seule question sur ce groupe-là, à laquelle personne n'a trouvé de réponse rapide : combien de fois a-t-on additionné P ? Que ça paraisse difficile n'est pas une preuve. C'est une hypothèse qui tient depuis plus de quarante ans.

Remarque d'ailleurs ce dont tu n'as pas eu besoin. Pour comprendre pourquoi RSA est difficile à remonter, il faut d'abord savoir des choses sur les nombres premiers et la factorisation, et c'est une matière à soi seule. Ici, une droite qui coupe une courbe a suffi. Les cryptographes disent donc souvent que les courbes sont pour un débutant justement plus faciles à saisir que RSA : la difficulté n'est pas cachée dans les mathématiques du dessous, elle est posée sur la table. Que tu aies lu chapitre 7.1 d'abord et ce chapitre ensuite est donc un ordre historique, pas un ordre de difficulté.