Vous avez peut-être entendu d’une méthode de cryptographie utilisant des courbes, des courbes elliptiques plus précisément. Mais comment peut-on chiffrer, c’est-à-dire transformer un message clair en un message caché, avec une courbe ?

Les courbes elliptiques

Les courbes en question sont les courbes elliptiques, c’est-à-dire des courbes d’équation y² = x³ + a x + b où a et b sont des nombres, par exemple y² = x³ – 2 x + 1 ce qui peut se dessiner. On obtient la figure suivante.

Le rapport avec les ellipses, qui sont des cercles « aplatis » sur l’un de leur diamètre, est indirect puisqu’il concerne le calcul de leurs longueurs. Nous n’insisterons pas sur ce point car il n’a aucun rapport avec la cryptographie. L’intérêt est qu’on peut définir des opérations transformant les points de cette courbe en un autre. On s’approche de l’idée de chiffrement … sans encore l’avoir atteinte toutefois.

Loi de groupe sur une courbe elliptique

L’avantage des courbes elliptiques est qu’on peut y définir une loi. La figure suivante montre comment, à deux points P et Q de la courbe, on associe un point que l’on note P + Q.

On montre que cette loi + a les propriétés habituelles de l’addition des nombres, soit l’associativité, la commutativité, l’existence d’un point neutre (le point à l’infini) et d’un symétrique pour tout point (le symétrique par rapport à l’axe des abscisses justement).

Remarque : on trouvera les détails des calculs sur mon site : ici

Chiffrement

Pour chiffrer, on ne considère pas les courbes elliptiques sur le corps des nombres réels mais sur un corps fini comme Z / N où N est un nombre premier. La courbe a alors un nombre fini de points. L’idée de départ est qu’un texte peut être transformé en une suite de points de la courbe. Cela revient à écrire dans un alphabet ayant autant de signes que la courbe a de points. Notons que le problème sous-jacent n’a rien de simple mais, théoriquement, le chiffrement consiste alors à transformer un point de la courbe. La clef secrète est constituée d’un point P de la courbe et d’un nombre entier, comme 3 par exemple. On calcule ensuite P ’ = 3 P. La clef publique est alors le couple de points (P, P ’). Pour crypter un point M, le chiffreur choisit un entier, 23 par exemple, et transmet le couple (U, V) défini par : U = 23 P et V = M + 23 P ’. La connaissance du premier nombre, ici 3, suffit pour retrouver M car M = V – 3 U.

Logarithme discret

Pour retrouver le nombre choisi, 3 dans notre exemple, connaissant P et P ’, il suffit de savoir résoudre l’équation : P ’ = 3 P. L’utilisation du verbe « suffir » ne doit pas tromper. Cela ne signifie absolument pas que cela soit facile mais que, si vous savez le faire, vous savez décrypter. Le nombre 3 est alors appelé un logarithme discret ce qui n’est guère intuitif si on utilise la notation additive ci-dessus. Avec une notation multiplicative de l’opération de groupe, cela devient plus habituel puisque l’équation s’écrit alors : P ’ = P³. Dans l’ensemble des nombres usuels, 3 correspondrait au logarithme de base P de P ’ d’où le nom dans le cadre d’un groupe fini. À l’heure actuelle, ce problème est considéré comme très difficile. On estime qu’une clef de 200 bits pour les courbes elliptiques est plus sûre qu’une clef de 1024 bits pour la méthode R.S.A. Comme les calculs sur les courbes elliptiques ne sont pas compliqués à réaliser, c’est un gros avantage pour les cartes à puces où on dispose de peu de puissance, et où la taille de la clef influe beaucoup sur les performances. Les inconvénients sont de deux ordres. D’une part, la théorie des fonctions elliptiques est complexe et relativement récente. Il n’est pas exclu que l’on puisse contourner le problème du logarithme discret. D’autre part, la technologie de cryptographie par courbe elliptique a fait l’objet du dépôt de nombreux brevets à travers le monde. Cela pourrait rendre son utilisation coûteuse !