elikaski/ecc_attacksAttaques connues sur la cryptographie à courbe elliptique
Ces dernières années, l'approche de la cryptographie à courbes elliptiques est devenue populaire en raison de sa grande efficacité et de sa robustesse. Le but de cet article est de présenter ce sujet de manière relativement plus claire que ce qui existe aujourd'hui sur Internet.
Dans cet article, je présenterai ce que sont les courbes elliptiques, les opérations de base que l'on peut effectuer sur elles, et comment elles peuvent être utilisées dans un contexte cryptographique. La majeure partie de cet article consiste en des exemples d'attaques connues sur des implémentations incorrectes ou de mauvaises utilisations de celles-ci. Tout au long de l'article, j'essaie de séparer l'explication en une partie intuitive et de haut niveau, et une partie mathématique qui entre davantage dans les détails. Le lecteur est invité à se concentrer sur la partie qui l'intéresse à cet endroit, et à passer les parties qui l'intéressent moins.
Bonne lecture !
En général, une courbe elliptique est une sorte de ligne courbe. Un exemple en est la parabole, dont l'équation est de la forme $𝑦 = 𝑎𝑥^2 + 𝑏𝑥 + 𝑐$ et qui ressemble à ceci :
Dans le contexte de la cryptographie, il est courant d'utiliser des courbes elliptiques dont l'équation est de la forme
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏$
Par exemple, une courbe elliptique correspondant à l'équation $𝑦^2 = 𝑥^3 − 3𝑥 + 3$ ressemble à ceci :
L'équation de la courbe définit la relation entre la coordonnée 𝑥 d'un point de la courbe et sa coordonnée 𝑦. Dans un contexte cryptographique, on restreint 𝑥, 𝑦, 𝑎, 𝑏 à des nombres entiers, et on limite les calculs à être effectués modulo un grand nombre premier. L'équation de la courbe elliptique est donc :
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏\ \ \ \ (mod\ 𝑝)$.
Cela signifie que nous avons un nombre fini de points sur la courbe. Dans le langage mathématique, la courbe est définie sur un corps fini d'ordre 𝑝. Par conséquent, désormais, toute coordonnée 𝑥 n'aura pas nécessairement un point correspondant sur la courbe, car il se peut que la coordonnée 𝑦 qui lui correspond ne soit pas un entier.
L'ensemble des points de la courbe est constitué de paires d'entiers (𝑥, 𝑦) qui satisfont l'équation de la courbe. En plus de ces points, un autre point spécial appelé « Infini » est défini, et il est noté 𝒪. Dans le langage mathématique, ce point est l'élément neutre de l'ensemble des points de la courbe par rapport à l'opération d'addition, que nous définirons dans la section suivante. Le nombre de points de la courbe (y compris le point 𝒪) est appelé « ordre de la courbe ».
Une autre observation est que les courbes elliptiques sont symétriques par rapport à l'axe des X. Cela signifie que si le point 𝑃 = (𝑥, 𝑦) est sur la courbe, alors le point −𝑃 = (𝑥, −𝑦) est également sur la courbe. En fait, ces points sont considérés comme des « inverses » l'un de l'autre (d'où la notation −𝑃 pour le second point), et le résultat de l'opération d'addition entre eux est défini comme étant l'élément neutre 𝒪.
Un théorème appelé théorème de Hasse fournit une estimation de #𝐸, l'ordre de la courbe, et est de l'ordre de grandeur de Θ(𝑝). Plus précisément :
$𝑝 + 1 − 2\sqrt𝑝 ≤ 𝐸 ≤ 𝑝 + 1 + 2\sqrt𝑝$
Étant donné deux points de la courbe, il est possible de définir une opération d'addition entre eux, qui aboutit à un troisième point également situé sur la courbe. Pour trouver ce point géométriquement, on trace une ligne entre les deux points donnés, et on la prolonge jusqu'à ce qu'elle coupe la courbe en un troisième point. Ce point est réfléchi par rapport à l'axe des 𝑋, et le point résultant est défini comme le résultat de l'addition.
Voici un schéma qui montre comment, étant donnés les points 𝑃 et 𝑄, le point 𝑃 + 𝑄 peut être trouvé :
Une question qui peut surgir de cette description est : que se passe-t-il si la ligne tracée entre les deux points ne recoupe pas la courbe ? Dans ce cas, on dit que la ligne coupe la courbe à l'« infini », et le résultat de l'addition est le point 𝒪. Remarquez que ce cas se produit si la ligne tracée est verticale, c'est-à-dire si l'on essaie d'additionner un point 𝑃 avec son point inverse, −𝑃 :
Deux identités de base découlent de ceci. Pour tout point 𝑃, on a :
𝑃 + 𝒪 = 𝑃
𝑃 + (−𝑃) = 𝒪
Une autre question qui découle de la description géométrique est : comment additionner un point à lui-même ? Nous avons vu que pour additionner deux points différents 𝑃 et 𝑄, on trace une ligne entre eux et on regarde le point d'intersection de son prolongement avec la courbe. Intuitivement, on laisse 𝑃 constant, et on regarde la ligne qui se crée à mesure que l'on déplace 𝑄 « de plus en plus près » de 𝑃, jusqu'à ce que 𝑄 fusionne avec 𝑃. Ce que l'on obtient est une ligne de plus en plus « tangente » à la courbe au point 𝑃, et c'est exactement la ligne que l'on considérera lorsque l'on voudra additionner 𝑃 à lui-même :
