Attaques connues sur la cryptographie à courbes elliptiques

• Introduction
• Introduction aux courbes elliptiques
• Les courbes elliptiques dans le contexte de la cryptographie
• Attaques ECC

Attaques ECDH

• L'ordre du générateur est trop petit
• L'ordre du générateur est un nombre lisse
• L'ordre du générateur est presque un nombre lisse, et la clé privée est petite
• Ne pas vérifier qu'un point est sur la courbe
• La courbe est singulière
• La courbe est supersingulière
• La courbe est anormale

Attaques ECDSA

• Ne pas hacher le message avant de le signer
• Réutiliser la même valeur de k dans différentes signatures
• Générer les valeurs de k de manière non sécurisée
• Ne pas vérifier que le générateur est valide

Conclusion

• Aperçu des attaques ECDH
• Aperçu des attaques ECDSA
• Protection contre ces attaques
• Références

Introduction

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 !

Introduction aux courbes elliptiques

Une courbe elliptique

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.

Les points sur la courbe

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𝑝$

Addition de points

É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 :

Pour additionner un point 𝑃 à lui-même, on trace une tangente à la courbe au point 𝑃, et on la prolonge jusqu'à ce qu'elle coupe la courbe en un second 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. Il est courant de noter le résultat de l'addition comme 𝑃 + 𝑃 = 2𝑃. De nouveau, si la tangente ne coupe pas la courbe en un second point, on dit qu'elle coupe la courbe à l'« infini », et le résultat de l'addition dans ce cas est le point 𝒪.

Ces descriptions géométriques visuelles illustrent bien et nous aident à comprendre comment fonctionne l'addition de points. Mais comment la calcule-t-on réellement ? Des équations mathématiques, bien sûr !

Étant donnés les points $𝑃 = (𝑥_𝑃, 𝑦_𝑃)$ et $𝑄 = (𝑥_𝑄, 𝑦_𝑄)$, le résultat de leur addition est le point $𝑅 = (𝑥_𝑅, 𝑦_𝑅)$ tel que :

$𝑥_𝑅 = 𝜆^2 − 𝑥_𝑃 − 𝑥_𝑄\ \ \ \ \ \ \ \ \ (mod\ 𝑝)$
$𝑦_𝑅 = 𝜆(𝑥_𝑃 − 𝑥_𝑅) − 𝑦_𝑃\ \ \ \ (mod\ 𝑝)$

Où 𝜆 est défini comme la pente de la droite reliant les points, s'ils sont différents, et la pente de la tangente à la courbe au point, si le point est additionné à lui-même. Formellement :

$\displaystyle𝜆 = \frac{𝑦_𝑃 − 𝑦_𝑄}{𝑥_𝑃 − 𝑥_𝑄}\ \ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 ≠ 𝑄$
$\displaystyle𝜆 = \frac{3{𝑥_𝑃}^2 + 𝑎}{2𝑦_𝑃}\ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 = 𝑄$

Les calculs mathématiques derrière l'addition de points ne sont pas essentiels pour le reste de l'article. À cet égard, nous pouvons considérer l'addition de points comme une boîte noire qui reçoit deux points de la courbe et renvoie un troisième point qui est également sur la courbe.

Multiplier un point de la courbe par une constante

Nous avons vu qu'il est possible d'additionner un point 𝑃 à lui-même, et nous avons noté le point résultant 2𝑃. Si l'on additionne à nouveau le point 𝑃 à ce résultat, on atteint un point noté 3𝑃, et ainsi de suite. De cette manière, il est possible de définir la « multiplication » d'un point par une constante, en additionnant le point à lui-même de manière répétée (de la même manière que la multiplication entre nombres) :

$𝑛𝑃 = 𝑃 + 𝑃 + ⋯ + 𝑃\ \ \ \ \ (n\ times)$

En apparence, pour multiplier un point par un nombre 𝑛, il faut effectuer 𝑛 opérations d'addition entre points. En effet, étant donné un point de départ, il est difficile de savoir à l'avance où tombera le « dernier » point, sans l'atteindre « pas à pas ». Un tel calcul serait très inefficace, car 𝑛 pourrait être très grand.

Pour cela, il existe l'algorithme Double And Add (doubler et additionner), dans lequel on part du point 𝑃, puis pour chaque bit de la représentation binaire de 𝑛, le point courant est multiplié par 2 (c'est-à-dire qu'il est additionné à lui-même), et est ajouté au résultat si la valeur du bit est 1. La complexité temporelle de cet algorithme est 𝑂(log 𝑛), et il permet de multiplier efficacement des points par de très grands nombres.

Une propriété importante de la multiplication de points que nous utiliserons plus tard est que, pour tout point 𝑃 et toute paire de nombres 𝑎, 𝑏, on a :

$𝑏(𝑎𝑃) = (𝑏𝑎)𝑃 = (𝑎𝑏)𝑃 = 𝑎(𝑏𝑃)$

Intuitivement, supposons que l'on parte du point 𝑃, que l'on fasse 𝑎 pas à partir de celui-ci, et que l'on atteigne le point 𝑎𝑃. À partir de ce point, on fait 𝑏 pas de « taille » 𝑎 et on atteint le point 𝑏(𝑎𝑃). Alternativement, dans un autre scénario, on pourrait partir du point 𝑃, faire 𝑏 pas avec celui-ci et atteindre le point 𝑏𝑃. À partir de ce point, faire 𝑎 pas de « taille » 𝑏 et atteindre le point 𝑎(𝑏𝑃).

Dans les deux scénarios, on a effectué au total le même nombre de 𝑎𝑏 pas depuis le point 𝑃, donc dans les deux scénarios, on a atteint le même point final. Mathématiquement, la multiplication d'un point par une constante est associative.

Point générateur

Si l'on part d'un point 𝑃 et qu'on l'additionne à lui-même encore et encore, à chaque étape, on atteindra un nouveau point de la courbe. Comme il y a un nombre fini de points sur la courbe, à un certain stade, nous atteindrons à nouveau des points déjà atteints, et nous serons dans une sorte de boucle, ou de « cercle ». Plus précisément, à un certain stade, nous atteindrons le point -𝑃, à l'étape suivante, nous atteindrons le point 𝒪, et à l'étape d'après, nous atteindrons à nouveau le point 𝑃, d'où nous étions partis.

Le point qui crée un tel « cercle » est appelé un générateur, car tout le « cercle » peut être généré à partir de lui, et il est courant de le noter par la lettre 𝐺. Le nombre de points dans le « cercle » (y compris le point 𝒪) est appelé l'« ordre du générateur 𝐺 », et est généralement noté 𝑛. Chaque point de la courbe forme une sorte de « cercle ». Mathématiquement, l'ensemble des points de ce « cercle » est un groupe cyclique.

Une propriété intéressante qui en résulte est que multiplier un point 𝐺 par son ordre 𝑛 donne le point à l'infini :
𝑛𝐺 = 𝒪

Le problème difficile

« Étant donné des points 𝑃 et 𝑄 tels que 𝑄 = 𝑥𝑃 pour un certain 𝑥, il est difficile de trouver 𝑥. »

En d'autres termes, supposons que quelqu'un parte d'un point de départ, fasse un certain nombre de pas à partir de celui-ci et atteigne un point final. Étant donné le point de départ et le point final, comment savoir combien de pas ont été effectués ?

La réponse à cette question n'est pas si intuitive, car il est difficile de prédire à l'avance, à partir d'un point de départ, quels points seront atteints en faisant des pas à partir de celui-ci. Une solution naïve consisterait à partir nous-mêmes de 𝑃, à avancer pas à pas et à compter les pas effectués, jusqu'à atteindre 𝑄. La complexité de cette solution est 𝑂(𝑥), et elle est irréalisable si l'on sait que 𝑥 est un grand nombre, par exemple si 𝑥 est 256 bit.

Ce problème est appelé problème du logarithme discret sur courbes elliptiques (ECDLP), et c'est un problème difficile. Mais à quel point est-il difficile ?

Dans un contexte cryptographique, il est courant de mesurer la « difficulté des problèmes », ou la « robustesse d'un système cryptographique », avec une métrique appelée niveau de sécurité. Dans cette métrique, on dit qu'un problème a « 𝑛 bits de sécurité » si la meilleure attaque connue résout le problème en $𝑂(2^𝑛)$ étapes.

Actuellement, le meilleur algorithme qui résout le problème ECDLP le fait avec une complexité de $𝑂(\sqrt n)$, où 𝑛 est l'ordre du point 𝑃, et il le fait en utilisant une attaque de type Meet In The Middle. Lorsqu'un point avec un ordre suffisamment grand est choisi, le résoudre est irréalisable, d'où la robustesse du problème.

Par exemple, si l'on choisit 𝑛 de taille 256 bit, on obtient que le problème ECDLP a un niveau de sécurité de 128 bit. Pour comparaison, pour atteindre le même niveau de sécurité de 128 bit dans le chiffrement RSA, qui est basé sur le problème de la factorisation d'entiers, une clé publique de taille 3072 bit est nécessaire. Cela rend l'utilisation des courbes elliptiques relativement plus efficace en termes de calcul.

Les courbes elliptiques dans le contexte de la cryptographie

Après toute cette introduction au monde des courbes elliptiques, nous allons maintenant voir ce que l'on peut en faire dans un contexte cryptographique. Comme nous le savons, les systèmes cryptographiques sont généralement basés sur un « problème difficile » à résoudre. Par exemple, RSA avec le problème de factorisation d'un nombre que nous avons mentionné, ou le protocole Diffie-Hellman avec le problème du logarithme discret. Un système cryptographique basé sur le problème ECDLP dans une courbe elliptique appartient à la famille de la cryptographie à courbes elliptiques, ou plus brièvement ECC.

Première utilisation des courbes elliptiques - Accord sur un secret partagé

Commençons par une histoire. Imaginez que vous êtes à une fête - une pièce pleine de gens, où tout le monde peut parler à tout le monde et où tout le monde entend tout le monde. Dans cette pièce se trouvent également Alice et Bob, qui ne se sont jamais rencontrés auparavant. Alice aime Bob et veut l'inviter à sortir. Alice est un peu timide, alors elle veut dire ce message secret à Bob sans que les autres invités ne l'entendent. Alice et Bob n'ont rien coordonné à l'avance, et tout ce qu'Alice dit à Bob sera entendu par tous les autres invités de la fête. Comment Alice peut-elle transmettre le message à Bob sans que personne d'autre ne l'entende ?

Si vous avez répondu « courbes elliptiques », alors vous avez raison !

Alice choisira une courbe elliptique et un générateur dans celle-ci, et les communiquera à Bob. Plus précisément, Alice transmettra à Bob (et à tous les autres dans la pièce) les deux paramètres de la courbe 𝑎, 𝑏, le module 𝑝, et le générateur 𝐺. De plus, Alice choisira une valeur $𝑑_𝐴$ dans l'intervalle $1 ≤ 𝑑_𝐴 ≤ 𝑛 − 1$ où 𝑛 est l'ordre de 𝐺. Cette valeur $𝑑_𝐴$ est appelée la clé privée d'Alice. Alice calculera le point $𝐴 = 𝑑_𝐴𝐺$, appelé clé publique d'Alice, et le communiquera à Bob. De même, Bob choisira une clé privée $𝑑_𝐵$, calculera le point $𝐵 = 𝑑_𝐵𝐺$, appelé clé publique de Bob, et la communiquera à Alice.

Alice prendra la clé publique de Bob, multipliera ce point par sa clé privée et atteindra un troisième point $𝑃_𝐴 = 𝑑_𝐴𝐵$. De même, Bob prendra la clé publique d'Alice, la multipliera par sa clé privée et atteindra un troisième point qui lui est propre, $𝑃_𝐵 = 𝑑_𝐵𝐴$. Si l'on examine les points qu'Alice et Bob ont atteints séparément, on constate qu'ils ont atteint le même point ! Ce fait provient de la propriété d'associativité de la multiplication d'un point par une constante que nous avons vue précédemment :

$𝑃_𝐴 = 𝑑_𝐴𝐵 = 𝑑_𝐴(𝑑_𝐵𝐺) = 𝑑_𝐵(𝑑_𝐴𝐺) = 𝑑_𝐵𝐴 = 𝑃_𝐵$

À la fin de tout le processus, Alice et Bob sont parvenus à se mettre d'accord sur un point de la courbe, et à aucun moment l'un ou l'autre n'a transmis ce point à l'autre personne. Les informations que tout le monde a entendues sont : 𝑎, 𝑏, 𝑝, 𝐺, 𝐴, 𝐵. Une personne présente dans la pièce qui écoute ces informations ne peut pas trouver le point sur lequel Alice et Bob se sont mis d'accord.

C'est parce que si une autre personne dans la pièce voulait trouver ce point, elle devrait connaître soit la clé privée d'Alice, soit la clé privée de Bob, afin de multiplier 𝐵 ou 𝐴 par celles-ci. Pour trouver la clé privée d'Alice par exemple, elle examinera $𝐴 = 𝑑_𝐴𝐺$, car c'est la seule information qui a été envoyée et qui « contient » la clé privée d'Alice. Étant donné 𝐺 et $𝑑_𝐴𝐺$, trouver $𝑑_𝐴$ équivaut à résoudre le problème du logarithme discret sur les courbes elliptiques, qui est, comme mentionné, un problème difficile.

Ce magnifique protocole s'appelle : Diffie-Hellman sur courbes elliptiques (ECDH).

Utilisation du secret partagé pour une communication ultérieure

Nous n'avons pas terminé notre histoire. Bien qu'Alice et Bob se soient mis d'accord sur un point secret partagé, Alice n'a toujours pas demandé à Bob ce rendez-vous qu'elle souhaitait tant.

Après que les parties se sont mises d'accord sur un point secret partagé, elles peuvent l'utiliser comme clé de chiffrement pour n'importe quelle méthode de chiffrement, par exemple AES, et à partir de ce moment, communiquer de manière sécurisée par chiffrement.

Il est courant de prendre l'une des coordonnées 𝑥 ou 𝑦 du point et de l'utiliser. Pour des raisons de sécurité, il est recommandé de hacher la valeur choisie et d'utiliser uniquement le résultat du hachage comme clé de chiffrement. En pratique, il arrive que la valeur soit trop grande pour être utilisée comme clé de chiffrement. Par exemple, si la fonction de hachage utilisée est SHA-1, sa longueur de sortie est de 160 bit, alors que le chiffrement AES n'en nécessite que 128 bit. Dans ce cas, il est courant de n'utiliser que 128 bits sur les 160 et de jeter le reste.

Quoi qu'il en soit, à ce stade, Alice et Bob se mettent d'accord sur une clé de chiffrement, et ils sont les seuls à la connaître. À partir de ce moment, ils communiquent par chiffrement, et toute personne qui écoute dans la pièce ne peut pas comprendre ce qu'ils disent.

Voici un schéma du protocole :

En utilisant la clé convenue, Alice chiffre le message « Salut Bob, veux-tu sortir prendre un café demain soir ? » et transmet le message chiffré à Bob. Bob déchiffre le message avec la clé qu'il connaît également. Alice espère que Bob dira oui, mais cela ne fait pas partie du protocole.

Les similitudes entre Diffie-Hellman sur courbes elliptiques et Diffie-Hellman

Dans le protocole Diffie-Hellman (DH) connu, les parties transmettent ouvertement un nombre premier 𝑝 et un générateur 𝑔 appartenant au groupe correspondant à la valeur 𝑝. Alice génère aléatoirement une clé privée 𝑎 et diffuse ouvertement sa clé publique $𝐴 = 𝑔^𝑎\ \ \ \ (mod\ 𝑝)$. De même, Bob génère aléatoirement une clé privée 𝑏 et diffuse ouvertement sa clé publique $𝐵 = 𝑔^𝑏\ \ \ \ (mod\ 𝑝)$. Alice prend ensuite la clé publique de Bob et l'élève à la puissance de sa clé privée, calculant ainsi la valeur $𝐾 = 𝐵^𝑎 = (𝑔^𝑏)^𝑎 =𝑔^{𝑎𝑏}\ \ \ \ (mod\ 𝑝)$. De la même manière, Bob calcule la valeur $𝐾 = 𝐴^𝑏 = (𝑔^𝑎)^𝑏 =𝑔^{𝑎𝑏}\ \ \ \ (mod\ 𝑝)$. À la fin du processus, Alice et Bob sont parvenus à se mettre d'accord sur une valeur commune 𝐾, sans la transmettre entre eux.

Un attaquant qui les écoute ne peut pas trouver 𝐾 à partir des valeurs diffusées 𝑝, 𝑔, 𝐴, 𝐵. Pour ce faire, il devra trouver soit la clé privée d'Alice, soit celle de Bob. Pour calculer la clé privée d'Alice par exemple, il devrait trouver 𝑎 à partir de 𝑔 et $𝑔^𝑎\ \ \ \ (mod\ 𝑝)$, ce qui est un problème difficile. Ce problème est appelé problème du logarithme discret (DLP).

Il existe une similitude très nette entre DH, qui repose sur le DLP, et ECDH, qui repose sur l'ECDLP (ils sont fondamentalement les mêmes, avec seulement un préfixe EC). Dans les deux protocoles, deux parties qui se parlent peuvent se mettre d'accord sur une valeur secrète partagée, sans rien coordonner à l'avance. Toute personne qui écoute les messages entre les parties sera exposée aux informations publiques qu'elles échangent, mais ne pourra pas atteindre la valeur secrète partagée entre elles.### Deuxième utilisation des courbes elliptiques - Signer un message Pour continuer notre histoire, disons qu'Alice et Bob sont allés à leur rendez-vous et ont passé une agréable soirée ensemble. Le lendemain, Alice reçoit un message disant « Salut Alice, c'est Bob, j'ai passé un super moment avec toi hier et j'aimerais te revoir ce week-end ». Alice soupçonne que ce n'est pas Bob qui a envoyé le message, car elle sait que Bob s'est tellement amusé avec elle hier qu'il n'attendra pas le week-end pour la revoir, mais voudra la voir demain ! Comment Alice peut-elle vérifier que c'est bien Bob qui a écrit le message ?

Si vous avez répondu « courbes elliptiques », vous avez encore raison !

La difficulté du problème ECDLP peut également être utilisée pour signer des messages. Lors de leur rendez-vous, Alice et Bob se sont mis d'accord sur une courbe elliptique et un générateur 𝐺 de celle-ci. Bob a généré une valeur $𝑑_𝐵$, appelée clé privée de Bob, et a calculé le point $𝑃_𝐵 = 𝑑_𝐵𝐺$, appelé clé publique de Bob. Bob a donné sa clé publique à Alice afin qu'elle puisse l'utiliser plus tard pour vérifier si un message qu'elle reçoit a bien été signé par lui.

Supposons que Bob veuille signer un certain message 𝑚. Il calcule la valeur $z = hash(m)$ à l'aide d'une fonction de hachage sécurisée, et conserve du résultat un nombre de bits égal à la longueur en bits de n, l'ordre du générateur 𝐺. Bob génère ensuite une valeur aléatoire 𝑘 dans l'intervalle $1 ≤ 𝑘 ≤ 𝑛 − 1$. Bob calcule alors le point $𝑘𝐺 = (𝑥_1, 𝑦_1)$, prend sa coordonnée 𝑥, et calcule $𝑟 = 𝑥1\ \ \ \ (mod\ n)$. Enfin, Bob calcule la valeur $𝑠 = 𝑘^{−1}(𝑧 + 𝑟𝑑_𝐵)$.

La signature du message 𝑚 est définie comme la paire de valeurs calculées 𝑟 et 𝑠.

Supposons qu'Alice ait reçu un certain message 𝑚, dont la signature est une paire de valeurs 𝑟 et 𝑠. Alice veut s'assurer que c'est bien Bob qui a signé le message. Alice calcule la valeur $z = hash(m)$ de la même manière que Bob. Alice calcule ensuite les valeurs $𝑢_1 = 𝑧𝑠^{−1}$ et $𝑢_2 = 𝑟𝑠^{−1}$. Enfin, Alice utilise la clé publique de Bob $𝑃_𝐵$ et calcule le point $𝑢_1𝐺 + 𝑢_2𝑃_𝐵 = (𝑥_1, 𝑦_1)$. La signature sera considérée comme valide si l'on a $𝑟 ≡ 𝑥_1\ \ \ \ (mod\ n)$. La raison pour laquelle cela est correct est que l'on a :

$𝑢_1𝐺 + 𝑢_2𝑃_𝐵 = 𝑧𝑠^{−1}𝐺 + 𝑟𝑠^{−1}𝑃_𝐵 = 𝑠^{−1}(𝑧𝐺 + 𝑟𝑃_𝐵) = 𝑠^{−1}(𝑧𝐺 + 𝑟𝑑_𝐵𝐺) = 𝑠^{−1}(𝑧 + 𝑟𝑑_𝐵)𝐺 = 𝑘(𝑧 + 𝑟𝑑_𝐵)^{−1}(𝑧 + 𝑟𝑑_𝐵)𝐺 = 𝑘𝐺$

Si la signature est valide, la coordonnée 𝑥 de ce point devrait bien être 𝑟, comme défini dans la signature du message. Il convient de noter que l'ordre du générateur 𝐺, désigné par la lettre 𝑛, doit être un nombre premier ; cela permet en effet de calculer les inverses dans les algorithmes de signature et de vérification.

On voit que seule la personne qui détient la clé privée $𝑑_𝐵$ peut créer une signature valide pour la clé publique $𝑃_𝐵$. Un attaquant qui ne possède pas la valeur $𝑑_𝐵$ ne peut pas calculer la valeur 𝑠 correspondant à $𝑃_𝐵$ dans la signature. Si l'attaquant veut créer une signature correspondant à un certain message, il devra résoudre le problème ECDLP, c'est-à-dire trouver la clé privée $𝑑_𝐵$ à partir de $𝐺$ et $𝑃_𝐵 = 𝑑_𝐵𝐺$, ce qui est un problème difficile.

Ce protocole de signature est appelé Elliptic Curve Digital Signature Algorithm, ou ECDSA en abrégé. Le protocole garantit que les messages signés n'ont pas été modifiés ou falsifiés, et garantit en outre que la personne qui a signé le message ne peut pas nier en être l'auteur.

Contrairement au protocole ECDH, où les parties n'ont pas besoin de se coordonner à l'avance, dans le protocole ECDSA les parties doivent se mettre d'accord à l'avance sur une clé publique. Ce n'est qu'une fois que chaque partie est certaine que la clé publique qu'elle détient appartient bien à la personne avec laquelle elle veut communiquer que le protocole peut être utilisé. Sinon, vérifier la signature avec la clé publique que chaque partie possède n'a aucun sens.

Revenons à notre histoire. Alice sait avec certitude que la clé publique $𝑃_𝐵$ en sa possession appartient bien à Bob, car Bob la lui a explicitement donnée lors de leur rendez-vous. Alice essaie de vérifier le message avec cette clé et découvre qu'il n'y a pas de correspondance. Bien sûr ! Quelqu'un d'autre a créé le message et l'a signé, comme Alice le soupçonnait.

Voici un schéma du protocole :

Les similitudes entre ECDSA et ElGamal

Dans le protocole ElGamal de signature de messages, les parties se mettent d'accord sur un grand nombre premier 𝑝 et un générateur 𝑔. Le signataire génère une valeur 𝑑 dans l'intervalle $1 ≤ 𝑑 < 𝑝 − 1$, appelée clé privée, calcule la valeur $𝑦 = 𝑔^𝑑\ \ \ \ (mod\ p)$, appelée clé publique, et la publie.

Pour signer un certain message, ils calculent la valeur $z = hash(m)$ et génèrent une valeur aléatoire 𝑘 dans l'intervalle $1 ≤ 𝑘 < 𝑝 − 1$ qui soit première avec $(p-1)$. Ils calculent $𝑟 = 𝑔^𝑘\ \ \ \ (mod\ p)$ et $𝑠 = 𝑘^{−1}(𝑧 − 𝑑𝑟)\ \ \ \ (mod\ (p-1))$. La signature du message m est définie comme la paire de valeurs calculées 𝑟 et 𝑠.

La partie qui a reçu un certain message 𝑚, dont la signature est une paire de valeurs 𝑟 et 𝑠, utilise la clé publique 𝑦 pour vérifier la signature en calculant les valeurs $​𝑢_1 = 𝑟^𝑠𝑦^𝑟$ et $𝑢_2 = 𝑔^𝑧$. La signature sera considérée comme valide si $𝑢_1 = 𝑢_2$. Cela est dû au fait que, selon la définition de 𝑠, on a :
$𝑠 = 𝑘^{−1}(𝑧 − 𝑑𝑟)$, donc $𝑘𝑠 = 𝑧 − 𝑑𝑟$, d'où $𝑧 = 𝑘𝑠 + 𝑑𝑟$. Par conséquent :

$𝑢_2 = 𝑔^𝑧 = 𝑔^{𝑘𝑠+𝑑𝑟} = 𝑔^{𝑘𝑠}𝑔^{𝑑𝑟} = (𝑔^𝑘)^𝑠(𝑔^𝑑)^𝑟 = 𝑟^𝑠𝑦^𝑟 = 𝑢_1$

Un attaquant ne peut pas créer de signature valide pour la clé publique 𝑦 sans connaître la clé privée 𝑑. Pour obtenir la clé privée à partir de la clé publique, l'attaquant devrait résoudre le problème DLP, ce qui est un problème difficile.

Ici aussi, il existe une similitude évidente entre ECDSA, qui repose sur ECDLP, et ElGamal, qui repose sur DLP. Dans les deux cas, les parties doivent se coordonner à l'avance sur une clé publique, et il est nécessaire de générer une valeur aléatoire 𝑘 à chaque fois que l'on veut signer un nouveau message. De plus, dans les deux cas, un attaquant qui écoute les messages échangés entre les parties ne peut pas en déduire d'informations utiles qui lui permettraient de forger des signatures.

Attaques ECC

Nous avons vu comment les courbes elliptiques peuvent être utilisées dans les systèmes cryptographiques pour convenir d'une valeur secrète et pour signer des messages. Comme pour tout dans la vie, lorsqu'il s'agit de mettre quelque chose en pratique, les choses ne se passent pas toujours comme prévu. Dans le reste de l'article, je présenterai différentes façons d'attaquer les systèmes cryptographiques basés sur les courbes elliptiques qui ont été mal utilisés par l'utilisateur, ou implémentés de manière non sécurisée.

Naturellement, je divise cette partie en attaques sur ECDH et attaques sur ECDSA. Dans les deux cas, nous dirons que l'attaque a « réussi » si nous trouvons la clé privée de l'une des parties, et nous nous arrêterons là. Dans le cas d'ECDH, cela suffit car à partir de la clé privée, il est possible d'accéder à la valeur du secret partagé et à toutes les informations chiffrées avec elle par la suite. Dans le cas d'ECDSA, cela suffit car la clé privée peut être utilisée pour signer des messages comme nous le souhaitons.

SageMath

SageMath est un logiciel mathématique gratuit et open source. Il peut être écrit avec une syntaxe presque identique à celle de Python, et peut également être utilisé comme bibliothèque Python. Cette bibliothèque implémente des fonctions utiles relatives aux courbes elliptiques et est donc très pratique pour les calculs que nous devons effectuer dans le cadre de l'ECC. Dans le cadre de cet article, je fournis des extraits de code écrits avec cette bibliothèque. J'ai constaté qu'il est plus simple de l'installer sur le système d'exploitation Ubuntu, plus précisément la version 22.04. Pour l'installer, il suffit d'exécuter la commande : sudo apt install sagemath. Pour exécuter un fichier contenant du code, enregistrez le fichier avec l'extension .sage et exécutez la commande : sage file.sage.

De plus, un interpréteur peut être utilisé, de la même manière que l'interpréteur Python, en exécutant la commande : sage. Il est également possible de créer des fichiers .py dans lesquels la bibliothèque sage.all est importée, et de les exécuter avec la commande python3 file.py. Notez que lorsqu'un fichier est exécuté avec la commande sage, la notation ^ est interprétée comme une puissance, tandis qu'avec python3, cette notation est interprétée comme un xor.

Dans cet article, j'utilise principalement les fonctions suivantes dans SageMath :

• E.gens() - trouver des générateurs dans la courbe E
• G.order() - calculer l'ordre du générateur G
• n*G - multiplication du générateur G par le nombre n
• n.factor() - factoriser le nombre n en ses facteurs - la fonction renvoie une liste de paires (𝑝, 𝑒) telles que 𝑝 est un facteur premier, et 𝑒 son exposant, c'est-à-dire le nombre de fois que 𝑝 apparaît dans la décomposition de n
• crt - résoudre un système d'équations du théorème des restes chinois

Attaques ECDH

L'ordre du générateur est trop petit

L'utilisation incorrecte d'ECDH la plus facile à attaquer est peut-être de choisir un générateur avec un ordre n trop petit. Comme mentionné, il est possible de résoudre le problème ECDLP avec une complexité de $O(\sqrt{n})$. Lorsque 𝑛 est trop petit, par exemple 32 bits, il devient alors possible de résoudre ce problème. Il existe plusieurs algorithmes pour résoudre ce problème, notamment Baby-Step Giant-Step, Pollard's Rho et Pollard's Lambda. Ces algorithmes peuvent être exécutés en boîte noire à l'aide de SageMath, en utilisant la fonction discrete_log :```python import random p = random_prime(2^32) a = random.randrange(p) b = random.randrange(p) E = EllipticCurve(GF(p), [a,b]) G = E.gens()[0] n = G.order() private_key = random.randrange(n) A = private_key * G found_key = G.discrete_log(A) assert found_key * G == A assert private_key == found_key print("success!")

Dans cet extrait de code, nous choisissons aléatoirement les paramètres de la courbe, sous la contrainte que `𝑝` a une longueur de 32 bits. Cette contrainte nous garantit que le nombre de points sur la courbe est $O(2^{32})$ et donc que l'ordre de chaque point de la courbe est au plus $O(2^{32})$ également. Ensuite, nous créons la courbe, choisissons un générateur, générons une clé privée aléatoire et calculons la clé publique. Enfin, à partir du générateur et de la clé publique, nous calculons le logarithme discret pour retrouver la clé privée, et vérifions que la clé trouvée est bien correcte. Ce code ne prend tout au plus que quelques secondes pour trouver la clé privée.

## L'ordre du générateur est un nombre friable
Comme mentionné, l'ordre d'un générateur est défini comme le nombre de points du « cercle » formé lorsque l'on additionne le point générateur à lui-même de manière répétée, et il est noté `𝑛`. Si `𝑛` est un nombre composé qui peut être factorisé en facteurs premiers plus petits, alors il est possible de résoudre efficacement l'ECDLP. Un tel nombre est appelé nombre friable, et dans le cadre de cet article, c'est un nombre qui peut être factorisé en un nombre suffisant de facteurs premiers, chacun étant assez petit pour que notre attaque fonctionne. La définition formelle d'un nombre friable est un peu différente et ne nous concerne pas.

Intuitivement, cela se fait en « attaquant » chacun des facteurs premiers séparément. Étant donné un point générateur `𝐺` qui forme un très grand « cercle », et un point `𝑃` de ce « cercle » tel que `𝑃 = 𝑘𝐺`. Le grand « cercle » peut être décomposé en plusieurs petits « cercles », chacun de la taille d'un facteur premier de `𝑛`. Dans chaque petit « cercle », nous pouvons mapper `G` et `P` vers d'autres points correspondants `G'` et `P'` situés dans le petit « cercle », et qui satisfont `𝑃′ = 𝑘′𝐺′`. Comme le « cercle » est petit, il est relativement facile de résoudre le problème et de trouver `𝑘′`. Enfin, nous pouvons combiner tous les petits `𝑘′` trouvés pour obtenir le `𝑘` recherché dans le « cercle » d'origine.

L'algorithme qui effectue ce que je viens de décrire s'appelle l'algorithme de Pohlig-Hellman. Sa complexité temporelle est $O(\sqrt{p_{max}})$, où $p_{max}$ est le plus grand facteur premier dans la décomposition de `𝑛`. Cela a aussi du sens, car la partie la plus « lourde » de l'algorithme consiste à résoudre le problème ECDLP dans le plus grand « cercle » parmi les plus petits « cercles ». Par exemple, `n` peut être un nombre de 128 bits, et il se décompose en facteurs premiers dont le plus grand est un nombre de 30 bits. L'algorithme réduit la complexité de résolution du problème de $2^{64}$ à $2^{15}$, le faisant ainsi passer d'irréalisable à réalisable.

Heureusement, la fonction `discrete_log` de SageMath implémente cet algorithme. Pour exécuter l'attaque, il suffit d'appeler la fonction:```python
p = 183740305291166889900894879302858411333
a = 13
b = 37
E = EllipticCurve(GF(p), [a,b])
G = E(123764810000715262449972298016641419881,
144640915410606177233842123838934486566)
n = G.order()
print("number of bits in n:", n.nbits())
print("n's factors:", n.factor())
print("number of bits in n's greatest factor:", n.factor()[-1][0].nbits())
import random
private_key = random.randrange(n)
A = private_key * G
print("Calculating discrete_log...")
found_key = G.discrete_log(A)
assert found_key * G == A
assert private_key == found_key
print("success!")

Dans cet extrait de code, on définit une courbe elliptique et un générateur, puis on affiche les facteurs premiers de son ordre. La sortie est :``` number of bits in n: 128 n's factors: 2 * 3 * 13 * 101 * 211 * 21141581 * 38581057 * 60652309 * 2234328781 number of bits in n's greatest factor: 32 Calculating discrete_log... success!

On peut voir que bien que l'ordre du générateur soit de 128 bits, il se décompose en facteurs premiers tels que le plus grand facteur premier est de 32 bits.

Ensuite, comme dans l'attaque précédente — nous choisissons une clé privée aléatoire, calculons une clé publique à partir de celle-ci, puis, étant donnés le générateur et la clé publique, calculons la clé privée et vérifions qu'elle est correcte.

Bien que nous ayons terminé, nous n'avons pas vu comment les « petits » cercles sont définis, comment mapper les points `𝐺` et `𝑃` vers leurs points correspondants `𝐺′` et `𝑃′`, et comment combiner toutes les petites solutions en une grande solution. Je vais essayer de l'expliquer intuitivement ici, car la prochaine attaque repose également sur cette partie.

Supposons que nous ayons un « cercle » d'ordre `3𝑥5𝑥7 = 105`, et que son générateur soit `𝐺`. Nous définissons un point `𝐺′ = (5𝑥7)𝐺 = 35𝐺`, et examinons le « cercle » généré à partir de celui-ci. Si nous partons de `𝐺′` d'un « pas », c'est-à-dire que nous ajoutons `𝐺′` à lui-même, ce sera comme avancer de 35 pas depuis le point `35𝐺` dans le « cercle » d'origine, et nous atteindrons le point `2𝐺′ = 70𝐺`. Si nous avançons d'un « pas » supplémentaire, nous atteindrons le point `3𝐺′ = 105𝐺 = 𝒪`, et si nous avançons encore d'un « pas », nous atteindrons le point `4𝐺′ = 35𝐺 = 𝐺′`, c'est-à-dire de retour au point de départ. Le « cercle » formé par `G′` est d'ordre `3`, et ce n'est pas une coïncidence, car sur un « cercle » d'ordre `105`, il est possible de faire exactement `3` « pas » de taille `35`. De même, nous pourrions créer un « cercle » d'ordre `5` en définissant le point `𝐺′ = (3𝑥7)𝐺 = 21𝐺`, et un cercle d'ordre `5` en définissant `𝐺′ = (3𝑥5)𝐺 = 15𝐺`.

Quand on regarde les choses dans l'autre sens, cela devient plus intéressant. Supposons que dans le « cercle » d'origine, nous ayons fait `𝑛` pas depuis le point `G` et que nous ayons atteint le point `𝑛𝐺`. Si, dans le petit « cercle », nous faisons également `𝑛` pas depuis le point `𝐺′`, nous atteindrions le point `𝑛′𝐺′` tel que `𝑛 ≡ 𝑛′ (𝑚𝑜𝑑 3)`. Et pourquoi est-ce intéressant ? Parce que l'ordre de `𝐺′` est beaucoup plus petit que l'ordre de `𝐺` et, par conséquent, étant donnés `𝐺′` et `𝑛′𝐺′`, nous pouvons trouver `𝑛′` relativement facilement. Si nous le faisons, et si nous le faisons aussi pour les deux autres facteurs premiers de l'ordre du « cercle », qui sont `5` et `7`, nous obtiendrions les valeurs suivantes :

𝑛 ≡ $𝑛'_1$ (𝑚𝑜𝑑 3)\
𝑛 ≡ $𝑛'_2$ (𝑚𝑜𝑑 5)\
𝑛 ≡ $𝑛'_3$ (𝑚𝑜𝑑 7)

À partir de ces trois valeurs, `𝑛` peut être facilement trouvé en utilisant le théorème des restes chinois, et ainsi résoudre le problème d'origine.

## L'ordre du générateur est presque un nombre friable, et la clé privée est petite

Supposons que, comme dans l'attaque précédente, nous obtenions une courbe dans laquelle l'ordre du générateur se décompose en facteurs premiers, mais cette fois, le plus grand facteur premier est trop grand pour qu'il soit pratique de résoudre son ECDLP. Par exemple, si l'ordre du générateur est de `256 bit`, mais que le plus grand facteur premier est de `128 bit`.

L'algorithme de Pohlig-Hellman nécessitera environ $O(2^{64})$ opérations pour trouver la clé privée, ce qui est irréalisable.

Si nous savons que la clé privée utilisée est relativement petite, elle peut encore être trouvée efficacement.

Supposons que la clé privée soit de `64 bit` (au lieu de `256 bit`). Lorsque la clé publique est créée, le générateur est multiplié par la clé privée et vous obtenez un point quelconque dans le « cercle » que le générateur crée. Bien que le « cercle » ait une taille d'environ $2^{256}$ points, ce point « tombera » quelque part dans les $2^{64}$ premiers points. Il n'y a pas d'« interaction » entre la clé privée et les points du « cercle » qui correspondent à des valeurs plus grandes.

Il est possible d'exécuter l'algorithme de Pohlig-Hellman, mais d'« écarter » les « cercles » trop grands, à condition que le produit des ordres des « cercles » restants soit au moins égal à la longueur de la clé privée. Si l'on trouve suffisamment de petits facteurs premiers, dont le produit est d'au moins `64 bit`, alors les « cercles » correspondants seront suffisants pour mener la même attaque que nous avons vue précédemment.

Si précédemment nous avions la vie facile en termes d'écriture de code, cette fois nous devrons implémenter les choses nous-mêmes, car la fonction `discrete_log` de SageMath ne sait pas que nous voulons « écarter » certains des facteurs premiers. L'extrait de code suivant fait ceci :```python
p = 88664572752015126127869404674421545790506871948117527783533589813159111825511
a = 13
b = 37
E = EllipticCurve(GF(p), [a,b])
G = E(19374976316789648652022260955836934561553454311144967863145605756652014623129,
      68630819472054489323664324766002023315775509214344811025345735680440707888471)
n = G.order()

print("Number of bits in n:", n.nbits())
factors = n.factor()
print("n's factors:", factors)

PRIVATE_KEY_BIT_SIZE = 64
import random
private_key = random.randrange(2^PRIVATE_KEY_BIT_SIZE)
P = private_key * G

print("We know that the private key is", PRIVATE_KEY_BIT_SIZE, "bits long")
print("Lets find which of the factors of G's order are relevant for finding the private key")
# find factors needed such that the order is greater than the secret key size
count_factors_needed = 0
new_order = 1
for p, e in factors:
    new_order *= p^e
    count_factors_needed += 1
    if new_order.nbits() >= PRIVATE_KEY_BIT_SIZE:
        print("Found enough factors! The rest are not needed")
        break
factors = factors[:count_factors_needed]
print("Considering these factors:", factors)

print("Calculating discrete log for each quotient group...")
subsolutions = []
subgroup = []
for p, e in factors:
    quotient_n = (n // p ^ e)
    G0 = quotient_n * G # G0's order is p^e
    P0 = quotient_n * P
    k = G0.discrete_log(P0)
    subsolutions.append(k)
    subgroup.append(p ^ e) # k the order of G0

print("Running CRT...")
found_key = crt(subsolutions, subgroup)
assert found_key * G == P
assert private_key == found_key
print("success!")

Dans cet extrait de code, nous définissons une courbe elliptique et un générateur dans celle-ci, et affichons les facteurs premiers de son ordre. La sortie est :``` Number of bits in n: 256 n's factors: 2 * 3 * 29 * 2699 * 28751 * 831913766251 * 92996710252298530263979 * 84878782522781478604307230464271

L'ordre du générateur est de `256 bit`, et il se décompose en plusieurs facteurs premiers, de sorte que les deux plus grands  sont de `77 bit` et `107 bit`. Ils sont suffisamment grands pour qu'il soit irréaliste de résoudre l'ECDLP. Ensuite, une clé privée de `64 bit` est générée aléatoirement, et une clé publique est calculée. À l'étape suivante, nous « collectons » suffisamment de facteurs premiers jusqu'à obtenir un ordre d'une longueur d'au moins `64 bit`. Le résultat est :```
We know that the private key is 64 bits long
Lets find which of the factors of G's order are relevant for finding the private key
Found enough factors! The rest are not needed
Considering these factors: [(2, 1), (3, 1), (29, 1), (2699, 1), (28751, 1), (831913766251, 1)]

On peut voir que les deux plus grands facteurs sont redondants, et le plus grand facteur qui nous reste est 40 bit. À l'étape suivante, pour chacun des facteurs restants, nous calculons les points 𝐺′ et 𝑃′ comme je l'ai expliqué précédemment, et pour chacun d'eux nous résolvons l'ECDLP. Les résultats et les facteurs premiers sont conservés respectivement dans les listes subsolutions et subgroups. Enfin, tous les résultats sont combinés à l'aide du théorème des restes chinois pour obtenir la clé privée, et nous vérifions qu'elle est bien correcte.

Ne pas vérifier qu'un point est sur la courbe

En examinant la définition de l'addition de points sur les courbes elliptiques, on remarque une propriété intéressante : dans l'addition de points, la valeur 𝑏 n'est pas utilisée, mais seulement les valeurs 𝑎 et 𝑝. Cela signifie que l'addition de points situés sur une courbe peut également avoir un sens pour une autre courbe, qui ne diffère de la première que par cette valeur 𝑏. Cela est bien sûr également vrai pour la multiplication d'un point par un nombre. Si l'utilisateur ne vérifie pas que le point qu'il reçoit de l'autre partie comme clé publique se trouve bien sur sa courbe, il s'expose alors à une attaque par courbe invalide.

Supposons que deux parties se soient mises d'accord sur une courbe elliptique $E_1$. Un attaquant peut créer une courbe malveillante $𝐸_2$, qui a les mêmes valeurs 𝑎 et 𝑝 que $𝐸_1$ mais une valeur 𝑏 différente. Sur la courbe $𝐸_2$, l'attaquant choisira un point 𝑃 dont l'ordre est petit, par exemple 3. Bien sûr, le point 𝑃 ne se trouvera pas sur $𝐸_1$, car il satisfait une équation avec une valeur 𝑏 différente de celle de $𝐸_1$. L'attaquant enverra le point 𝑃 comme clé publique à l'utilisateur. Disons que l'utilisateur ne prend pas la peine de vérifier que le point qu'il reçoit se trouve bien sur la courbe $𝐸_1$ convenue par les parties. L'utilisateur prendra la clé publique reçue de l'attaquant, la multipliera par sa clé privée, et obtiendra un point qui devrait être le point secret partagé, comme nous l'avons vu dans la définition du protocole ECDH. Du point de vue de l'utilisateur, il calculera l'opération de multiplication sur la courbe $𝐸_1$. Mais comme le point 𝑃 ne s'y trouve pas du tout, mais sur $𝐸_2$, l'utilisateur calculera en réalité l'opération de multiplication sur la courbe $𝐸_2$. Ensuite, l'utilisateur utilisera le point secret partagé pour continuer la communication avec l'attaquant. Supposons que les parties utilisent la coordonnée 𝑥 du point comme clé de chiffrement AES. Dans ce cas, l'utilisateur chiffrera un message et l'enverra à l'attaquant.

Puisque l'ordre de 𝑃 est 3, il n'y a que 3 possibilités pour le point partagé que l'utilisateur peut calculer. L'attaquant parcourra ces points possibles et trouvera lequel correspond à la clé qui déchiffre avec succès le message chiffré envoyé par l'utilisateur. Étant donné ce point et le point de départ 𝑃, l'attaquant peut déduire le reste de la division de la clé privée de l'utilisateur par le nombre 3. L'attaquant peut envoyer à l'utilisateur d'autres points 𝑃 malveillants, avec des ordres croissants, par exemple 5, 7, et ainsi de suite. De cette façon, l'attaquant peut collecter suffisamment de valeurs représentant les restes des divisions de la clé privée de l'utilisateur par de petits nombres. Enfin, l'attaquant peut utiliser le théorème des restes chinois pour calculer la clé privée de l'utilisateur, de la même manière que dans l'attaque précédente.

Voici une explication plus intuitive : un attaquant peut fournir à l'utilisateur un point sur un très petit « cercle », par exemple de longueur 2. L'utilisateur avancera sur ce « cercle » d'un certain nombre de pas et atteindra le point de destination. L'attaquant connaît le point de destination de l'utilisateur, qui peut être l'une des 2 possibilités. L'attaquant peut donc déterminer si l'utilisateur a effectué un nombre pair ou impair de pas sur le cercle. L'attaquant peut fournir à l'utilisateur d'autres points sur des « cercles » de longueurs 3, 5, 7, et ainsi de suite. Jusqu'à ce que l'attaquant ait suffisamment de tels facteurs, chacun contenant un peu d'information sur le nombre de pas effectués par l'utilisateur. Enfin, l'attaquant peut combiner toutes ces valeurs pour obtenir le nombre exact de pas effectués par l'utilisateur, c'est-à-dire sa clé privée.

Le code suivant illustre l'attaque :```python from ecdsa.ecdsa import generator_128r1, curve_128r1 from Crypto.Util.number import long_to_bytes from Crypto.Util.Padding import pad, unpad from Crypto.Cipher import AES import random

Select a curve and generator

curve = curve_128r1 G = generator_128r1 n = G.order() p = curve.p() a = curve.a()

This is the private key of the other side, we don't know it and don't use it!

private_key = random.randrange(n)

Both sides encrypt and decrypt data the same way

key is the shared point's x coordinate, IV is point's y coordinate

def encrypt_data(shared_point, message): if shared_point.is_zero(): x, y = 0, 0 else: x, y = shared_point.xy() key = long_to_bytes(int(x)).rjust(16, b"\x00") iv = long_to_bytes(int(y)).rjust(16, b"\x00") cipher = AES.new(key, AES.MODE_CBC, iv)

message = pad(message.encode(), 16)
return cipher.encrypt(message)

def decrypt_data(shared_point, enc_message): if shared_point.is_zero(): x, y = 0, 0 else: x, y = shared_point.xy() key = long_to_bytes(int(x)).rjust(16, b"\x00") iv = long_to_bytes(int(y)).rjust(16, b"\x00") cipher = AES.new(key, AES.MODE_CBC, iv)

decrypted = cipher.decrypt(enc_message)
return unpad(decrypted, 16)

def ECDH(A): # Send our public key to the other side # Have them reach the shared point and # Send us an encrypted message using the shared point as key

# This part takes place remotely and is unknown to the attacker
shared_point = private_key * A
message = "Inconceivable!"
return encrypt_data(shared_point, message)

def brute_force_encrypted_message(A, encrypted_message, max_order): # Returns n such that n*A matches the key used to encrypt the message for i in range(1, max_order): shared_point = i * A try: # If both padding is correct and all characters are ascii # Then it is probably the correct encryption key decrypted = decrypt_data(shared_point, encrypted_message) decrypted = decrypted.decode() return i except: continue raise Exception("Did not find a value for one of the encrypted messages")

def find_curves_with_small_subgroup(p, a, max_order): # Yield tuples of (order, point) such that the point is # on a curve with the same a & p values, but different b # and the point's order is <= max_order orders_found = set() b = 0 while True: b += 1 if b == p: # Ran out of b values break if (4a^3 + 27b^2) % p == 0: # Curve is singular continue

    E = EllipticCurve(GF(p), [a, b])
    for _ in range(100):
        R = E.random_point()
        n = R.order()
        for f, e in n.factor():
            if f in orders_found:
                continue
            if f > max_order:
                break

            # Create a point with order f
            orders_found.add(f)
            P = (n // f) * R
            assert P.order() == f
            yield (f, P)

subsolutions = [] subgroup = [] max_order = 10000 upto = 1 for order, A in find_curves_with_small_subgroup(p, a, max_order): upto *= order print("Found point with order", order, "so now can find keys of size up to", upto)

# Send this point as our public key and get an encrypted message from other side
encrypted_message = ECDH(A)

# Find the value n such that: private_key = n (mod order)
key_mod_order = brute_force_encrypted_message(A, encrypted_message, max_order)

# Save result to be used in CRT later
subsolutions.append(key_mod_order)
subgroup.append(order)

# Found enough values to calculate private key
if upto >= n:
    break

print("Found enough values! Running CRT...") found_key = crt(subsolutions, subgroup) print("Found private key", found_key) assert private_key == found_key print("success!")

In this code snippet, a curve and a generator are selected, the user randomly generates a private key and uses it for all uses of the ECDH protocol. The function `find_curves_with_small_subgroup` finds pairs of points and orders, such that the order of each point is relatively small, and the point is on some curve that is different from the original curve only by the value of `𝑏`. The code generates such pairs until enough pairs are found. For each pair, the public key is sent to the user and an encrypted message is received from them.

Brute force is performed on the encrypted message in order to find the value of the user's private key, modulo the current order. All of these results are saved, and finally we use the Chinese Remainder Theorem to calculate the user's private key and verify it is correct. In this case the parties agreed that the communication will be done in AES, with the encryption key that is the `x` coordinate of the shared secret point, and IV which is its `𝑦` coordinate.

The complexity of the attack is $𝑂(𝑛_{𝑚𝑎𝑥})$ where $𝑛_{𝑚𝑎𝑥}$ is the largest order among the orders of the malicious points. This is because the "heaviest" part of the attack is the brute force on the largest "circle" among the small "circles", and luckily for the attacker, they can control this value almost completely. Therefore this attack is relatively efficient in terms of complexity. As mentioned, the root of the problem in this case is that the user does not check that the point they received is even on the curve they are working with. In addition, the user uses the same private key in every new use of ECDH, which is not so safe.


## La courbe est singulière
L'une des propriétés importantes qu'une courbe elliptique doit posséder pour être cryptographiquement sûre est qu'elle soit non singulière. Une courbe non singulière est une courbe dont une certaine valeur, appelée le « discriminant » de la courbe, est non nulle. Cela est vérifié lorsque ses paramètres `𝑎` et `𝑏` satisfont l'inégalité :

$4a^3 + 27b^2 ≠ 0$

Une courbe qui ne satisfait pas cette inégalité possède un point « problématique » appelé `singular point`. Il existe deux types de tels points : le nœud et le point de rebroussement. Un point de type nœud existe sur une courbe qui présente une sorte de boucle qui se croise au point singulier, et deux tangentes différentes à la courbe peuvent être tracées en ce point.
Un point de rebroussement est un point où la courbe est « pointue », comme si deux lignes en sortaient, mais il n'y a qu'une seule tangente à la courbe en ce point.


<img src="https://assets.kitploit.com/production/public/readmes/48932/a40d8ce67ecb97eeabe85b52937a8935bc917b622e02168d9047200ed54feafc.png" alt="Singular Elliptic Curves"  width="500">

Dans un point de type nœud, il y a une racine double, donc l'équation de la courbe peut s'écrire :

$y^2 = (x-x_0)^2(x-x_1)\ \ \ \ (mod\ p)$

La courbe peut être « déplacée » vers la gauche en remplaçant la variable $x$ par la variable $(𝑥 + 𝑥_0)$ et atteindre la forme :

$y^2 = x^2(x+x_0-x_1)\ \ \ \ (mod\ p)$

Ainsi, maintenant le point singulier est à l'origine des axes. La valeur numérique de $t = (x_0-x_1)$ peut être utilisée pour créer une application des points de la courbe vers les entiers, de sorte que l'opération d'addition entre les points de la courbe soit équivalente à l'opération de multiplication entre les nombres. Pour chaque point `(𝑥, 𝑦)`, nous associerons le nombre
$\frac{y+\sqrt{t}x}{y-\sqrt{t}x}$. En particulier, à une paire de points `𝐺` et `𝑄` telle que `𝑄 = 𝑛𝐺`, nous pouvons faire correspondre des nombres `𝑔` et `𝑞` tels que $𝑞 ≡ 𝑔^𝑛\ \ \ \ (mod\ p)$, et c'est un problème DLP « normal ». Pour illustrer ce processus, j'ai ajouté un lien vers un exemple avec de petits nombres dans les références à la fin de l'article. Dans l'application que nous avons faite, nous avons utilisé l'équation des droites $y+\sqrt{t}x$ et $y-\sqrt{t}x$, et ce sont les droites qui correspondent aux deux tangentes qui peuvent être tracées au point singulier (après avoir « déplacé » la courbe), ce qui explique essentiellement pourquoi cette attaque peut être utilisée.

Un tel problème DLP peut être résolu efficacement à l'aide de l'algorithme de Pohlig-Hellman, que nous avons déjà vu auparavant, car il peut également être utilisé sur des entiers au lieu de points sur la courbe. Dans le contexte des points, nous avons vu que l'algorithme est utile lorsque l'ordre du générateur est un nombre lisse. Contrairement à un « cercle » de points sur une courbe, qui peut avoir n'importe quel ordre, dans le corps des entiers modulo un nombre premier `𝑝`, l'ordre est `𝑝 − 1`. Si `𝑝 − 1` est un nombre lisse, alors l'algorithme résoudra le problème DLP efficacement, trouvant ainsi la clé privée `n`.

L'extrait de code suivant fait cela :```python
p = 102360775616927576983385464260307534406913988994641083488371841417601237589487
a = -3
b = 2
assert (4*a^3 + 27*b^2) % p == 0

Gx = 1777671135698746847568710125129424132255529153914112337834835240247819869964
Gy = 6786424314307625790108882554225666781375821855884993473586521771737454762217
Qx = 45541468695354471317248123146376609839909398850045396377931300808635064950836
Qy = 42191909885728105279718027025083923092282618497451601162405594991792376530066

x = GF(p)["x"].gen()
f = x^3 + a*x + b
roots = f.roots()

assert len(roots) == 2 # two roots, so one must be double
if roots[0][1] == 2:
    double_root = roots[0][0]
    single_root = roots[1][0]
else:
    double_root = roots[1][0]
    single_root = roots[0][0]

print("double root:", double_root)
print("single root:", single_root)

# map G and Q to the new "shifted" curve
Gx = (Gx - double_root)
Qx = (Qx - double_root)

# Transform G and Q into numbers g and q, such that q=g^n
t = double_root - single_root
t_sqrt = t.square_root()

def transform(x, y, t_sqrt):
    return (y + t_sqrt * x) / (y - t_sqrt * x)

g = transform(Gx, Gy, t_sqrt)
q = transform(Qx, Qy, t_sqrt)
print("g:", g)
print("q:", q)

# Find the private key n
print("Factors of p-1:", factor(p-1))
print("Calculating discrete log for g and q...")
found_key = discrete_log(q, g)
print("Found private key:", found_key)

from Crypto.Util.number import long_to_bytes
print("The secret is:", long_to_bytes(found_key).decode())

Dans cet extrait de code, nous définissons les paramètres d'une courbe elliptique et vérifions qu'elle est bien singulière. Nous trouvons les racines du polynôme correspondant à la courbe et identifions laquelle d'entre elles est la racine double. Nous utilisons la racine double pour « déplacer » la courbe et atteindre les points « déplacés » 𝐺 et 𝑄. Ensuite, nous calculons $\sqrt{t}$ à partir des racines trouvées et l'utilisons pour mapper les points 𝐺 et 𝑄 aux nombres 𝑔 et 𝑞. Nous affichons la décomposition de 𝑝 − 1 en ses facteurs premiers (pour vérifier que le DLP peut effectivement être résolu efficacement). Enfin, nous calculons le DLP et interprétons le résultat comme une chaîne de caractères.

La sortie est : ``` double root: 1 single root: 102360775616927576983385464260307534406913988994641083488371841417601237589485 g: 79308184675041981395063385790064051127319168083579208141274962436724168376607 q: 72551144069373709737718398534799929820619379063890479978458954196900267190559 Factors of p-1: 2 * 41 * 2422091127107 * 3224683479179 * 3224849279789 * 3269304069319

• 3792634171577 * 3997021218613 Calculating discrete log for g and q... Found private key: 30943506368388267314266516224984737426569114488424608324579076903023329506337 The secret is: Digital Whisper is pretty great!

Cette fois, j'ai caché un message dans la clé privée elle-même. Il faut noter que, comme il s'agit d'une courbe singulière, il n'est pas possible dans SageMath de la créer de manière normale, d'y définir des points et d'effectuer des opérations avec eux comme nous l'avons fait précédemment. Dans ce code, j'ai défini les coordonnées des points comme des variables constantes. Pour calculer le point `𝑄`, j'ai moi-même multiplié la clé privée par le générateur en utilisant ma propre implémentation de l'algorithme Double And Add.


## La courbe est supersingulière
Étant donné une courbe elliptique modulo `𝑝`, et un générateur dont l'ordre est `𝑛`, le degré de plongement de la courbe par rapport au générateur est défini comme le plus petit nombre `k` satisfaisant l'équation $p^k ≡ 1\ \ \ \ (mod\ 𝑛)$. Grâce à certaines transformations, le problème ECDLP peut être réduit à un problème DLP dans un corps d'ordre $𝑝^𝑘$. La valeur `𝑘` est généralement un très grand nombre (environ de la même taille que `𝑝` lui-même), mais lorsqu'elle est relativement petite (disons, inférieure à `6`), la courbe est appelée `supersingulière` et il devient possible de résoudre ce problème DLP efficacement. Cette attaque est appelée attaque MOV, du nom de ses trois inventeurs (Menezes-Okamoto-Vanstone).

Les transformations que j'ai mentionnées sont des fonctions qui prennent deux points et renvoient un nombre dans le corps des nombres complexes. Les transformations utilisables sont l'appariement de Weil ou l'appariement de Tate, et nous les utiliserons comme une boîte noire. Une telle transformation `𝑇` satisfait la propriété suivante pour toute paire de points `𝑃`, `𝑄` :

$T(mP, nQ)=T(P,Q)^{mn}$


Par conséquent, étant donné deux points `𝐺` et `𝑄 = 𝑚𝐺`, nous pouvons sélectionner aléatoirement un troisième point `𝑅` et calculer les deux valeurs : \
$g = T(G, R)$ \
$q = T(Q, R)=T(mG,R)=T(G,R)^m=g^m$
À partir de là, nous pouvons résoudre le problème DLP pour `𝑔` et `𝑞` dans un corps d'ordre $p^k$, trouvant ainsi la clé privée `𝑚`. J'ai inclus un lien vers une explication plus détaillée des mathématiques derrière cette attaque, dans les références à la fin de l'article.

L'extrait de code suivant effectue cette attaque :```python
p = 682209701131405092329016993551
a = -35
b = 98
E = EllipticCurve(GF(p), [a, b])
G = E(516365702870683577608927237052, 
     524474557735717484100814381066)

# Find embedding degree k
Gn = G.order()
k = 1
while p^k % Gn != 1:
   k += 1
print("Found k:", k)

# Select private key, and calculate public key Q
private_key = 5072587499125503347
Q = private_key * G

# Define new curve mod p^k and the points on it
Ek = EllipticCurve(GF(p ^ k), [a, b])
Gk = Ek(G)
Qk = Ek(Q)
Rk = Ek.random_point()

# Find a point T with order d such that d divides G's order
m = Rk.order()
d = gcd(m, Gn)
Tk = (m // d) * Rk
assert Tk.order() == d
assert (Gn*Tk).is_zero() # Point INFINITY

# Using T, pair G and Q to integers g and q such that q=g^n (mod p^k)
g = Gk.weil_pairing(Tk, Gn)
q = Qk.weil_pairing(Tk, Gn)
# Alternatively:
#g = Gk.tate_pairing(Tk, Gn, k)
#q = Qk.tate_pairing(Tk, Gn, k)

# Make sure the pairing did not break anything
assert g ^ private_key == q

print("Calculating private key...")
found_key = q.log(g)
assert found_key == private_key
print("success!")

from Crypto.Util.number import long_to_bytes
print("The private key is:", long_to_bytes(found_key).decode())

Dans cet extrait de code, nous définissons une courbe et son générateur, et calculons sa valeur de degré de plongement, qui est 2 dans ce cas, il est donc pratique d'effectuer l'attaque. Nous définissons une courbe identique à la courbe d'origine, sauf que les calculs sont effectués modulo $𝑝^𝑘$ au lieu de modulo $𝑝$. Les deux points 𝐺 et 𝑄 sont également sur la nouvelle courbe. Ensuite, nous trouvons un troisième point dont l'ordre divise 𝑛.

En utilisant le troisième point, nous mappons les points 𝐺 et 𝑄 vers les nombres 𝑔 et 𝑞 et calculons le logarithme discret pour ceux-ci. Enfin, nous vérifions que le résultat obtenu est bien correct.

La sortie est :``` Found k: 2 Calculating private key... success! The private key is: Festivus

D'un point de vue computationnel, il existe aujourd'hui des algorithmes de calcul d'indice capables de résoudre le problème DLP de manière relativement efficace, et ce avec une complexité de $e^{O((log\ p^k)^{1/3}(log\ log\ p^k)^{2/3})}$. Cette expression peut sembler effrayante, mais comparée aux algorithmes ECDLP dont la complexité est $O(\sqrt{p})=e^{O(log\ p)}$, on peut voir qu'il est plus facile de résoudre le problème DLP, en supposant que le degré de plongement (noté `𝑘`) est effectivement petit.



## La courbe est anormale
Si une certaine courbe a la propriété que l'ordre de la courbe (le nombre de points sur celle-ci) est exactement égal au modulus `𝑝`, alors elle est appelée une `courbe anormale` et est vulnérable à une attaque appelée attaque de Smart. Cette attaque utilise les `nombres 𝑝-adiques`. Un tel nombre peut être représenté comme une somme de puissances de `p` (positives et négatives) avec des coefficients. Formellement, un tel nombre `s` est une série de la forme :

$s=\sum_{i = -k}^{\infty} a_{i}p^i = a_{-k}p^{-k} + \cdots + a_0 + a_1p + a_2p^2 + \cdots$

Lorsque les coefficients sont des entiers dans l'intervalle $0 ≤ 𝑎_𝑖 < 𝑝$, la somme peut être infinie dans le sens des puissances positives de `𝑝`. Dans de tels nombres, on « regarde » les chiffres de droite à gauche au lieu de gauche à droite, et donc une telle série peut converger vers une certaine valeur. De tels nombres appartiennent à un système numérique différent de celui auquel nous sommes habitués, et se comportent très différemment des règles mathématiques « normales ». Un article entier pourrait être écrit uniquement sur ce sujet, et pour ceux que cela intéresse, j'ai inclus dans les références à la fin de l'article un lien vers une vidéo qui le présente de manière relativement claire.

Dans tous les cas, dans cette attaque, une nouvelle courbe est créée à partir de la courbe donnée, définie sur les nombres p-adiques. Étant donné deux points `𝐺` et `𝑄 = 𝑚𝐺` sur la courbe d'origine, on les associe à des points correspondants sur la nouvelle courbe. À partir des coordonnées des points obtenus, il est facile de calculer `𝑚`.

Le code suivant exécute l'attaque :```python
def lift(P, E, p):
    # lift point P from old curve to a new curve
    Px, Py = map(ZZ, P.xy())
    for point in E.lift_x(Px, all=True):
         # take the matching one of the 2 points corresponding to this x on the p-adic curve
        _, y = map(ZZ, point.xy())
        if y % p == Py:
            return point


p = 82880337306360052550952380657384418102169134986290141696988204552000561657747
a = 26413685284385555604181540288021678971301314378522544469879270355650843743231
b = 10017655579196313780863100027113686719855502076415017585743221280232958057095
E = EllipticCurve(GF(p), [a, b])
G = E(37991937053350834320678619330546903567320901767090609881924528835279022654346,
      28947208718252880061735762506756351277969075978732800286053352115837132331595)
assert E.order() == p

private_key = 28153370716511608040616395150859085058202177279382452583684367923334520519740
P = private_key * G

# Lift the points to some new curve over p-adic numbers
E_adic = EllipticCurve(Qp(p), [a+p*13, b+p*37]) 
G = p * lift(G, E_adic, p)
P = p * lift(P, E_adic, p)

# Calculate discrete log
Gx, Gy = G.xy()
Px, Py = P.xy()
found_key = int(GF(p)((Px / Py) / (Gx / Gy)))
assert found_key == private_key
print("success!")

from Crypto.Util.number import long_to_bytes
print("The private key is:", long_to_bytes(found_key).decode())

Dans cet extrait de code, une fonction lift est définie, qui reçoit un point de la courbe originale et lui fait correspondre un point sur la nouvelle courbe. Ensuite, nous définissons une courbe elliptique et un générateur sur celle-ci, et vérifions que l'ordre de la courbe est bien p. Nous choisissons une clé privée et calculons la clé publique correspondante, puis effectuons l'attaque. Nous définissons une nouvelle courbe sur les nombres 𝑝-adiques, et mappons les points d'origine 𝐺 et 𝑃 vers les points correspondants de la nouvelle courbe à l'aide de la fonction lift et en les multipliant par 𝑝.

Pour chaque nouveau point, nous calculons le rapport entre sa coordonnée 𝑥 et sa coordonnée 𝑦. Le quotient de ces deux valeurs est la solution ECDLP des points d'origine.

La sortie est :``` success! The private key is: >>>>> Extraordinarily Nice <<<<<

La raison pour laquelle ce calcul fonctionne est liée au fait que le nombre de points sur la courbe est exactement `𝑝`. Cette propriété nous permet d'effectuer plusieurs applications, dont la dernière fait correspondre des points sur une courbe sur les nombres 𝑝-adiques à des nombres modulo $p^2$. Cette application a la propriété que le rapport entre la paire de nombres correspondant aux deux points d'origine est exactement le résultat du logarithme des deux points. Nous laisserons toutes ces applications comme une boîte noire, mais à la fin de l'article j'ai ajouté des références aux explications mathématiques pertinentes.


# Attaques ECDSA
## Ne pas hacher le message avant de le signer
Nous avons vu que dans le processus de signature d'un message, le hachage du message est d'abord calculé, et les bits de poids fort du hachage sont utilisés dans le calcul de la signature. Supposons que dans certaines implémentations de signature et de vérification, cette étape de hachage soit ignorée, et qu'au lieu de prendre les bits de poids fort du hachage, les bits soient pris directement dans le message tel quel. Dans une telle implémentation, la seule partie du message qui affecte sa signature est le début du message. En d'autres termes, si nous avons un message et sa signature, nous pouvons conserver le début du message et modifier le reste, et la signature restera valide. C'est une attaque vraiment simple.


Supposons, par exemple, que vous écriviez le message suivant à votre banque et que vous le signiez sans le hacher :```
"Please transfer 1,000$ from my account to GitHub so that they can continue hosting awesome repositories"

La banque vérifiera avec succès ce message et effectuera l'action. Un ... attaquant ... pourrait créer le message suivant :``` "Please transfer 1,000$ from my account to GitHub and 1,000,000$ to Eli Kaski"

Et utilisez la signature que vous venez de créer. La signature sera également valable pour ce message, et la banque effectuera l'action. Pas bien (enfin, ça dépend pour qui).

Le code suivant illustre l'attaque :```python
from ecdsa import SigningKey, NIST256p

signing_key = SigningKey.generate(NIST256p)
verifying_key = signing_key.verifying_key

class MyHash:
    def __init__(self, data):
        self.data = data

    def digest(self):
        return self.data

# Sign the message and verify the signature
message = "Please transfer 1,000$ to GitHub"
signature = signing_key.sign(message.encode(), hashfunc=MyHash)
assert verifying_key.verify(signature, message.encode(), hashfunc=MyHash)

# Construct an evil message and verify the original message's signature is valid for it as well
evil_message = "Please transfer 1,000$ to GitHub and 1,000,000$ to Eli Kaski"
assert verifying_key.verify(signature, evil_message.encode(), hashfunc=MyHash)
print("success!")

Dans cet extrait de code, la bibliothèque ecdsa est utilisée, ainsi qu'une courbe connue. Nous définissons une classe qui devrait implémenter une fonction de hachage mais ne le fait pas, et laisse plutôt le message tel quel. Par conséquent, lors de la signature d'un message, seuls les premiers bits du message d'origine sont utilisés, au lieu de ceux de son hachage. Ensuite, le message est signé et vérifié avec succès. Un message malveillant est alors créé, et le code vérifie que la signature du message d'origine correspond également au message malveillant.

Dans un tel scénario, nous n'avons peut-être pas obtenu la clé privée pour générer nos propres nouvelles signatures, mais étant donné une signature, nous pouvons signer autant de messages que nous le souhaitons, à condition qu'ils commencent par le même préfixe.

Réutilisation de la même valeur de k dans différentes signatures

Dans le cadre du processus de signature de messages, l'utilisateur doit générer aléatoirement une valeur 𝑘 et l'utiliser pour signer le message. Il est très important d'utiliser des valeurs 𝑘 différentes pour des signatures différentes. Sinon - étant donné deux messages signés où l'utilisateur a utilisé la même valeur 𝑘 au lieu de la régénérer, un attaquant pourrait calculer la clé privée de l'utilisateur.

Comme mentionné, lors de la signature de messages, l'utilisateur envoie publiquement $r=x_1\ \ \ \ (mod\ p)$ et $s=k^{-1}(z+rd_A)$. En supposant que l'utilisateur ait signé deux messages différents correspondant à $𝑧_1$ et $𝑧_2$, et ait envoyé publiquement deux paires de valeurs $𝑟, 𝑠_1$ et $𝑟, 𝑠_2$, c'est-à-dire qu'il a utilisé la même valeur 𝑘 dans ces deux signatures. Nous notons que :

$s_1-s_2=k^{-1}(z_1+rd_A)-k^{-1}(z_2+rd_A)=k^{-1}(z_1+rd_A-z_2-rd_A)=k^{-1}(z_1-z_2)$

À partir de cela, l'attaquant peut trouver la valeur de 𝑘 en calculant :

$\displaystyle k=\frac {z_1-z_2}{s_1-s_2}$

Après avoir trouvé 𝑘, l'attaquant peut calculer la clé privée de l'utilisateur à partir d'une des signatures. Notons que :

$r^{-1}(ks-z)=r^{-1}(kk^{-1}(z+rd_A)-z)=r^{-1}(z+rd_A-z)=r^{-1}rd_A=d_A$

Étant donné les valeurs de 𝑟, 𝑠 et 𝑧 d'un message et de sa signature, et la valeur de 𝑘 que l'attaquant a trouvée, l'attaquant peut calculer $d_A=r^{-1}(ks-z)$. À partir de ce point, l'attaquant peut signer n'importe quel message, au nom de l'utilisateur dont il a obtenu la clé privée.

L'extrait de code suivant effectue cette attaque :```python from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key from Crypto.Util.number import bytes_to_long, long_to_bytes from hashlib import sha256 import random

Select a curve and generator

curve = curve_256 generator = generator_256 n = generator.order()

Create private key and public keys

secret_key = 6743529130774090927928101169617481154782309 public_key = Public_key(generator, generator * secret_key) private_key = Private_key(public_key, secret_key)

Sign 2 messages using the same k

k = random.randrange(curve.p()) message1 = "Life is like a box of chocolates." message2 = "You never know what you're gonna get." z1 = bytes_to_long(sha256(message1.encode()).digest()) z2 = bytes_to_long(sha256(message2.encode()).digest())

signature1 = private_key.sign(z1, k) signature2 = private_key.sign(z2, k)

Given the two messages and their signatures, find k

found_k = (z1 - z2) * inverse_mod(signature1.s - signature2.s, n) % n assert k == found_k

Given k and one of the messages, find the private key

found_key = inverse_mod(signature1.r, n) * (found_k * signature1.s - z1) % n assert found_key == secret_key print("success!") print("The secret is:", long_to_bytes(found_key).decode())

Dans cet extrait de code, la bibliothèque ecdsa est utilisée, avec une courbe connue. Nous définissons une clé privée et l'utilisons pour signer deux messages. La valeur de `𝑘` est générée aléatoirement, mais elle reste la même pour les deux signatures. Étant donné les deux messages et leurs signatures, le code effectue le calcul que nous avons vu pour trouver `𝑘`. Enfin, nous utilisons la valeur de `𝑘` que nous avons trouvée pour calculer la clé privée comme nous l'avons vu. La sortie est :```
Success!
The secret is: Mistakes were made

Il est intéressant de noter que cette attaque a été réellement utilisée en 2010, lorsque Sony a implémenté de manière non sécurisée son mécanisme de signature sur le logiciel de la console PlayStation. Sony utilisait une valeur statique de 𝑘 pour ses signatures, ce qui a permis aux attaquants d’obtenir la clé privée de Sony grâce au calcul décrit ci-dessus. Cela a conduit à la capacité de signer n’importe quel code et de faire accepter à la PlayStation de l’exécuter. Par la suite, cette capacité a été utilisée pour installer des jeux pirates et non officiels sur la console.

Générer des valeurs k de manière non sécurisée

Si l’utilisateur choisit 𝑘 d’une manière insuffisamment aléatoire, la clé privée peut être retrouvée. Par exemple, si l’attaquant sait que 𝑘 se trouve dans une plage de valeurs très restreinte, ou si certains octets de 𝑘 sont connus de l’attaquant, il est alors possible, par une simple force brute, de retrouver la clé privée de l’utilisateur à partir d’un seul message signé. L’attaquant exécutera le calcul vu dans l’attaque précédente pour les différentes valeurs de 𝑘, jusqu’à atteindre la bonne valeur et en déduire la clé privée.

Pour contourner ce problème, les utilisateurs génèrent parfois une valeur aléatoire, calculent son empreinte avec une fonction de hachage, puis utilisent le résultat comme 𝑘. Cette méthode peut poser problème. Supposons, par exemple, que l’ordre du générateur 𝑛 soit de 256 bit et que la fonction de hachage choisie soit SHA-1. La sortie de cette fonction est un nombre de 160 bit. Dans les calculs modulo 𝑛, on sait que la valeur de 𝑘 contient 96 zéros au début, ce qui signifie que 𝑘 est un nombre relativement petit. Dans une telle situation, on dit que les valeurs de 𝑘 sont biaisées, et à partir de plusieurs messages signés avec la même clé privée, il est possible de retrouver cette clé privée.

L’attaque repose sur une structure algébrique appelée « Lattice » (réseau). De manière informelle, un réseau peut être considéré comme un ensemble de vecteurs dans un espace à 𝑚 dimensions, pouvant être exprimés comme combinaison linéaire de vecteurs « de base » à coefficients entiers. Mathématiquement, si $\{b_1,\dots,b_d\}$ sont les vecteurs de base sur $ℝ^𝑚$, alors le réseau correspondant est $L=$ $\{\sum_{i=1}^d a_ib_i\mid a_i \in Z\}$. Dans cette structure, il existe un problème bien connu : étant donné la base d’un réseau, trouver le plus court vecteur présent dans ce réseau. Dans ce contexte, de manière informelle, un « vecteur court » est un vecteur dont les éléments sont aussi proches de zéro que possible. Ce problème est appelé « problème du plus court vecteur » (Shortest Vector Problem, SVP) et est considéré comme NP-difficile. Il existe des algorithmes qui résolvent un problème similaire mais plus facile : trouver un vecteur court, c’est-à-dire un vecteur relativement « proche » du plus court vecteur du réseau. Ce problème est appelé « problème du vecteur le plus proche » (Closest Vector Problem, CVP), et l’un des algorithmes qui le résout est appelé algorithme de Lenstra-Lenstra-Lovász (LLL). Dans cette attaque, nous utiliserons cet algorithme comme une boîte noire.

Étant donné 𝑑 messages signés, il est possible de construire un réseau qui contient le vecteur $(𝑘_1, \dots , 𝑘_𝑑)$, où chaque élément du vecteur est une valeur de 𝑘 correspondant à une signature. L’algorithme LLL trouvera une approximation du plus court vecteur dans ce réseau. Comme on sait que les valeurs de 𝑘 sont petites, il y a une forte probabilité que le vecteur court trouvé par l’algorithme contienne au moins un élément k correct. Une fois qu’un 𝑘 correct est trouvé, la clé privée peut être calculée comme nous l’avons vu dans l’attaque précédente.

Pour construire ce réseau, il est nécessaire de définir ses vecteurs de base. J’ai inclus dans les références à la fin de l’article un lien vers un article qui explique comment ces vecteurs de base sont définis. Techniquement, les vecteurs de base du réseau peuvent être représentés sous la forme d’une matrice, où chaque ligne est constituée des éléments d’un vecteur de base. Pour améliorer la précision de l’algorithme LLL, il est recommandé d’ajouter à cette matrice deux colonnes qui contiennent des informations sur la taille attendue des valeurs de 𝑘 et sur le rapport entre 𝑘 et 𝑛. Cette amélioration est également expliquée dans la référence que j’ai jointe. L’extrait de code suivant illustre cette attaque :```python from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key from Crypto.Util.number import bytes_to_long, long_to_bytes from hashlib import sha1 import random

def build_matrix(signatures, bias, q): # M matrix should be: """ [ B 0 m'1 m'2 m'2 ... m'n 0 B/q r'1 r'2 r'3 ... r'n 0 0 0 0 q * I 0 0 ] where: m' = s^-1 * m r' = s^-1 * r """

# Construct the first 2 rows of M:
row1 = [bias, 0]
row2 = [0, bias / q]
for m, r, s in signatures:
    row1.append((inverse_mod(s, q) * m) % q)
    row2.append((inverse_mod(s, q) * r) % q)
top_rows = Matrix(QQ, [row1, row2])

# Construct the q*I block along with 2 columns of zeros
zero_cols = zero_matrix(QQ, len(signatures), 2)
qI = q * identity_matrix(QQ, len(signatures))
bottom_rows = block_matrix([[zero_cols, qI]])

# Combine all rows into one matrix
M = top_rows.stack(bottom_rows)
return M

def find_private_key(L, signatures, public_key): # Check if any valid k was found in L generator = public_key.generator q = generator.order() for row in L.rows(): for i in range(len(signatures)): m,r,s = signatures[i] # Skip the first two vector components we used to improve LLL possible_k = row[i+2] # LLL might have swapped the sign of the found short vectors for k in [possible_k, -possible_k]: d = inverse_mod(r,q)(ks-m) % q if d*generator == public_key.point: return d

Select a curve and generator

curve = curve_256 generator = generator_256 q = int(generator_256.order())

Create private key and public key

secret_key = 1793056234309773077862125006843383726029262764680727851636 public_key = Public_key(generator, generator * secret_key) private_key = Private_key(public_key, secret_key)

Sign some messages

messages_to_sign = [ "And then I go and spoil it all", "By saying somethin' stupid like", "I love you" ]

signatures = [] for message in messages_to_sign: message_hash = bytes_to_long(sha1(message.encode()).digest()) k = bytes_to_long(sha1(long_to_bytes(random.randrange(q))).digest()) signature = private_key.sign(message_hash, k) signatures.append((message_hash, signature.r, signature.s))

Given the messages and their signatures, retrieve the private key

Build the matrix out of the signatures

We know that k < 2^160 because it is the result of sha1

bias = 2^160 M = build_matrix(signatures, bias, q)

Calculate the closest short vector

L = M.LLL()

Find the private key!

found_key = find_private_key(L, signatures, public_key) assert found_key == secret_key print("success!") print("The secret is:", long_to_bytes(found_key).decode())

Dans cet extrait de code, une courbe standard est utilisée, une clé privée est sélectionnée et la clé publique correspondante est calculée à partir de celle-ci. 3 messages sont créés et signés avec 3 valeurs aléatoires `k` issues de la fonction de hachage SHA-1. Ensuite, nous créons la matrice correspondant à la base du réseau comme expliqué dans l'article, puis nous exécutons l'algorithme LLL sur celle-ci. Ensuite, nous parcourons les lignes de la matrice résultante et vérifions si une valeur correcte d'un `𝑘` quelconque s'y trouve.

La vérification est effectuée en calculant la clé privée à partir du `𝑘` potentiel, comme nous l'avons vu dans l'attaque précédente, et en vérifiant si la clé obtenue est bien correcte. Enfin, nous nous assurons que la clé privée trouvée est bien correcte. La sortie est :```
success!
The secret is: I am Jack's broken heart

La complexité de cette attaque est la même que celle de l'algorithme LLL, qui est $O(d^6\ \log^3B)$, où 𝐵 indique la longueur du biais de 𝑘 ($2^{160}$ dans notre cas), et 𝑑 indique le nombre de messages signés (3 dans notre cas). La question se pose de savoir quel est le nombre minimum de messages signés que nous sommes tenus d'utiliser pour pouvoir exécuter l'attaque. La réponse est $\displaystyle d=O(\frac {\log n}{\log n-\log B})$ où 𝑛 est l'ordre du générateur et 𝐵 est le biais. Une explication de ceci apparaît dans le deuxième lien des références que j'ai jointes à ce sujet à la fin de l'article.

En pratique, une variante de cette attaque peut également être exécutée dans les cas où les bits de poids fort de 𝑘 sont connus, ou simplement n'importe quels bits de 𝑘. L'attaque peut être exécutée même si la valeur d'un seul bit est connue, ou même si la valeur d'un seul bit est connue avec une probabilité supérieure à 50%! Mais bien sûr, dans ces cas, beaucoup plus de messages signés sont nécessaires pour mener à bien l'attaque.

Ne pas vérifier que le générateur est valide

Nous avons vu que, dans le processus de vérification de signature, le signataire envoie la paire de valeurs ​𝑟 et 𝑠 au vérificateur. Dans les navigateurs qui implémentent le protocole HTTPS, par exemple, il est courant d'envoyer cette paire de valeurs ​​dans un certificat, qui peut également contenir des données sur la courbe utilisée par le signataire. Le vérificateur doit s'assurer que les données de courbe trouvées dans le certificat correspondent bien à la courbe préalablement convenue. Si ce n'est pas le cas, cela peut poser problème.

Supposons que sur une certaine courbe Alice possède une clé privée $d_A$ et une clé publique $𝑃_𝐴$ qui lui correspond, ce qui signifie que $𝑃_𝐴 = 𝑑_𝐴𝐺$ pour le générateur 𝐺 de cette courbe. Avec la clé privée $𝑑_𝐴$, Alice peut signer ses messages comme nous l'avons vu dans la définition du protocole ECDSA. Supposons que la partie qui vérifie la signature reçoive également le générateur 𝐺 de l'utilisateur, et ne vérifie pas que le générateur reçu de l'utilisateur est bien le générateur convenu. Un attaquant peut envoyer comme générateur le point qui est la clé publique d'Alice, $𝐺^′ = 𝑃_𝐴$. L'attaquant choisira comme clé privée "factice" la valeur $𝑑_𝐴^′ = 1$, et il est donc clair que $𝑃_𝐴 = 𝑑_𝐴^′𝐺^′$. Cela signifie que l'attaquant peut "prouver" qu'il possède la clé privée correspondant à la clé publique d'Alice. Ainsi un attaquant peut créer n'importe quel message qu'il veut, et calculer pour celui-ci une paire de valeurs ​𝑟 et 𝑠 de la manière habituelle avec $𝑑_𝐴^′$, et la signature résultante sera vérifiée avec succès.

Intuitivement, dans le processus de vérification de signature, le signataire prouve qu'il est bien le "propriétaire" de la clé publique, qui est en réalité un point "destination" sur la courbe. Cela tient au fait que seul le signataire sait combien de pas effectuer depuis le point de départ pour atteindre le point de destination. Si le vérificateur ne vérifie pas que le point de départ reçu de l'utilisateur est bien le véritable point de départ, alors un attaquant peut décider que le point de départ est le point de destination, et que le nombre de pas à effectuer depuis ce point est zéro. Toutes les autres parties de la vérification de signature restent les mêmes, et la signature sera vérifiée avec succès. Cette attaque est appelée Curveball.

Cette attaque peut être généralisée avec des valeurs supplémentaires. L'attaquant choisira une valeur 𝑥 et calculera $𝐺^′ = 𝑥𝑃_𝐴$. La fausse clé privée sera $𝑑'_𝐴 = 𝑥^{−1}\ \ \ \ (mod\ n)$. Alors, il est clair que $𝑑'_𝐴𝐺^′ = 𝑥^{−1}𝑥𝑃_𝐴 = 𝑃_𝐴$.

Le code suivant illustre l'attaque :```python from ecdsa.ecdsa import generator_256 from Crypto.Util.number import bytes_to_long from hashlib import sha256 import random

def hash_message(message): return bytes_to_long(sha256(message.encode()).digest())

def verify(public_key, G, message, r, s): n = G.order() if r < 1 or r > n - 1 or s < 1 or s > n-1: return False hash = hash_message(message) u1 = (hash * inverse_mod(s, n)) % n u2 = (r * inverse_mod(s, n)) % n P = u1 * G + u2 * public_key return P.x() % n == r

def sign(private_key, G, message): n = G.order() k = random.randrange(n) hash = hash_message(message)

r = (k * G).x() % n
s = inverse_mod(k, n) * (hash + r * private_key) % n
return r, s

Create private and public keys

G = generator_256 n = G.order() private_key = random.randrange(n) public_key = private_key * G

Sign a message and verify it

message = "Let me be the one that shines with you" r, s = sign(private_key, G, message) assert verify(public_key, G, message, r, s)

Create a fake private key and generator that match the original public key

x = random.randrange(n) fake_G = x * public_key fake_private_key = inverse_mod(x, n) assert fake_private_key != private_key assert fake_G != G

Sign an evil message and verify it using the same public key

evil_message = "Where did I go wrong?" r, s = sign(fake_private_key, fake_G, evil_message) assert verify(public_key, fake_G, evil_message, r, s)

Dans cet extrait de code, nous choisissons un générateur connu, une clé privée et une clé publique. Nous signons un message et nous nous assurons qu'il est vérifié avec succès. Ensuite, nous créons une fausse clé privée et un faux générateur tels que les deux correspondent à la clé publique d'origine. Un message malveillant est signé avec la fausse clé, et enfin la fausse signature est vérifiée avec succès avec la clé publique d'origine. Le problème avec ce code est que l'algorithme de vérification ne vérifie pas que le générateur `𝐺` correspond à la clé publique. Bien que, dans cette attaque, nous n'ayons pas trouvé la clé privée de l'utilisateur, un attaquant peut exploiter l'implémentation incorrecte de la vérification de signature et créer une signature qui est vérifiée avec succès. Cependant, l'attaquant ne peut pas créer de « vraies » signatures qui seront effectivement vérifiées avec succès dans une implémentation correcte de la vérification de signature.

Il est intéressant de noter qu'il s'agit d'une vulnérabilité réelle qui existait dans l'architecture Windows CryptoAPI. Dans la fonction chargée de vérifier la signature d'un certificat, la vérification des paramètres de la courbe était insuffisante, dans les cas où ceux-ci étaient inclus dans le certificat lui-même. En particulier, rien ne vérifiait que le générateur était bien celui qui correspond à la clé publique. Un attaquant pouvait créer de faux certificats considérés comme fiables parce qu'ils semblaient avoir été signés par une autorité de certification de confiance. Cela était fait en ajoutant des champs de courbe malveillants au certificat et en choisissant le générateur de la manière que j'ai décrite. La vulnérabilité a été découverte par la NSA, corrigée en 2020 et a reçu le numéro CVE-2020-0601.

# Conclusion
## Aperçu des attaques ECDH
| Type de problème | Le problème | L'attaque | Comment fonctionne l'attaque | Complexité de l'attaque |
| ------------- | ------------- | ------------- | ------------- | ------------- |
| Choix d'une courbe avec un générateur non sûr | L'ordre du générateur `n` est trop petit | Baby-Step Giant-Step | Meet In The Middle | $𝑂(\sqrt n)$ |
| Choix d'une courbe avec un générateur non sûr | L'ordre du générateur `n` est un nombre lisse | Pohlig-Hellman | Décomposer `𝑛` en facteurs premiers, attaquer chacun d'eux séparément, puis combiner les résultats à l'aide du théorème des restes chinois | $O(\sqrt{p_{max}})$ où $p_{max}$ est le plus grand facteur premier dans la décomposition de `𝑛` |
| Choix d'une courbe avec un générateur non sûr + choix d'une clé privée non sécurisée | L'ordre du générateur `n` est presque un nombre lisse, et la clé privée est petite | Pohlig-Hellman amélioré | Décomposer `𝑛` en facteurs premiers, écarter les facteurs trop grands, attaquer chacun d'eux séparément, puis combiner les résultats à l'aide du théorème des restes chinois | $O(\sqrt{p_{max}})$ où $p_{max}$ est le plus grand facteur premier dans la décomposition de `𝑛` |
| Implémentation incorrecte d'ECDH | Ne pas vérifier qu'un point est sur la courbe | Attaque par courbe invalide | Envoyer comme clé publique des points de petits ordres sur des courbes malveillantes, attaquer chacun d'eux séparément, puis combiner les résultats à l'aide du théorème des restes chinois | $𝑂(𝑛_{𝑚𝑎𝑥})$ où $𝑛_{𝑚𝑎𝑥}$ est le plus grand ordre parmi les ordres des points malveillants |
| Sélection de paramètres de courbe non sécurisés | La courbe est singulière | Réduction de l'ECDLP au DLP | Mapper les points vers des nombres d'une manière qui transforme l'addition de points en multiplication d'entiers | $O(\sqrt{p_{max}})$ où $p_{max}$ est le plus grand facteur premier dans la décomposition de $(p-1)$ |
| Sélection de paramètres de courbe non sécurisés | La courbe est supersingulière | Réduction de l'ECDLP au DLP | Mapper les points vers des nombres d'une manière qui transforme l'addition de points en multiplication d'entiers | $e^{O((log\ p^k)^{1/3}(log\ log\ p^k)^{2/3})}$ où `k` est le degré de plongement par rapport au générateur |
| Sélection de paramètres de courbe non sécurisés | La courbe est anormale | Attaque de Smart | Une série d'applications entre des points d'une courbe et des points d'une courbe sur les nombres `p-adic`, puis de retour vers des entiers | $O(1)$ |


## Aperçu des attaques ECDSA
| Type de problème | Le problème | L'attaque | Comment fonctionne l'attaque | Complexité de l'attaque |
| ------------- | ------------- | ------------- | ------------- | ------------- |
| Implémentation incorrecte de la signature et de la vérification  | Ne pas hacher le message avant de le signer | Étant donné un message signé, forger des messages supplémentaires correspondant à la même signature | Conserver le préfixe du message tel quel et modifier le reste | $O(1)$ |
| Utilisation incorrecte de l'algorithme de signature | Réutiliser la même valeur de `k` dans différentes signatures | Trouver la clé privée de l'utilisateur | Trouver la valeur de `k`, puis calculer la clé privée de l'utilisateur à partir de celle-ci | $O(1)$ |
| Utilisation incorrecte de l'algorithme de signature | Générer des valeurs de `k` de manière non sécurisée | Étant donné plusieurs messages signés, trouver la clé privée de l'utilisateur | Réduire le problème à la recherche d'un vecteur court dans un réseau, trouver la valeur de `k`, puis calculer la clé privée de l'utilisateur à partir de celle-ci |  $O(d^6\ \log^3B)$ où `B` est le biais de `k`, et `d` est le nombre de messages signés |
| Implémentation incorrecte de la vérification | Ne pas vérifier que le générateur est valide | Forger des signatures qui sont vérifiées avec succès (Curveball) | Choisir un faux générateur et une fausse clé privée correspondant à la clé publique d'un autre utilisateur | $O(1)$ |


## Protection contre ces attaques
Il convient de noter que dans ECDH, les deux parties doivent se mettre d'accord sur la courbe au début du protocole. Si un utilisateur communique avec un attaquant et que c'est l'attaquant qui fournit les paramètres de la courbe, alors l'attaquant peut fournir des paramètres non sûrs. Par conséquent, l'attaquant peut obtenir la clé privée de l'utilisateur. Si l'utilisateur utilise toujours la même clé privée, l'attaquant peut alors déchiffrer toutes les conversations entre cet utilisateur et tout autre utilisateur. C'est pourquoi il est très important de ne pas autoriser des utilisateurs inconnus à fournir les paramètres de la courbe s'ils ne sont pas dignes de confiance. De plus, vous devez vous assurer que chaque point reçu d'un utilisateur étranger se trouve bien sur la courbe convenue. Et bien sûr, vous devez vous assurer que la courbe sélectionnée elle-même n'est pas vulnérable à l'une des attaques connues que nous avons vues. De plus, il est préférable d'utiliser une nouvelle clé privée à chaque fois que vous utilisez le protocole ECDH.

De même, dans ECDSA, il faut veiller à implémenter correctement les algorithmes de signature et de vérification. Ne négligez pas le hachage du message, ni la génération aléatoire et sûre de la valeur `𝑘` à chaque fois que le protocole est utilisé, et, bien sûr, lors de la vérification de la signature, si le générateur est reçu de l'utilisateur, assurez-vous qu'il s'agit bien de celui qui a été convenu précédemment.

## Références
- Dans cet article, j'ai utilisé des graphiques du livre Understanding Cryptography de Christof Paar:\
https://gnanavelrec.wordpress.com/wp-content/uploads/2019/06/2.understanding-cryptography-by-christof-paar-.pdf

- Un site qui illustre à quoi ressemblent les courbes elliptiques cryptographiques:\
https://graui.de/code/elliptic2/

- Explication détaillée des opérations d'addition et de multiplication sur les courbes elliptiques:\
https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication

- Cours d'introduction aux courbes elliptiques et à l'addition de points - par Christof Paar:\
https://www.youtube.com/watch?v=vnpZXJL6QCQ

- Cours sur les générateurs, l'ECDLP, la difficulté des problèmes, l'ECDH, Double And Add - par Christof Paar:\
https://www.youtube.com/watch?v=zTt4gvuQ6sY

- Explication du niveau de sécurité de différents algorithmes de chiffrement:\
https://en.wikipedia.org/wiki/Security_level

- Explication d'ECDH:\
https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93Hellman

- Explication d'ECDSA:\
https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm

- Explication des signatures avec ElGamal:\
https://en.wikipedia.org/wiki/ElGamal_signature_scheme

- Explication du théorème des restes chinois:\
https://en.wikipedia.org/wiki/Chinese_remainder_theorem

- Explication de la relation entre le discriminant d'une courbe singulière et le fait qu'elle ait une racine double:\
https://www.quora.com/For-an-elliptic-curve-in-the-form-Y-2-X-3+AX+B-why-is-4A-3+27B-2-neq-0-the-condition-for-non-singularity

- Un exemple avec de petits nombres de l'application entre les points et les nombres dans les courbes singulières:\
https://crypto.stackexchange.com/questions/61302/how-to-solve-this-ecdlp/61434#61434

- Explications des nombres 𝑝-adiques:\
https://en.wikipedia.org/wiki/P-adic_number \
https://www.youtube.com/watch?v=3gyHKCDq1YA

- Explication des mathématiques derrière l'attaque MOV:\
https://risencrypto.github.io/WeilMOV/

- Explications des mathématiques derrière l'attaque de Smart (c'est assez compliqué, vous êtes prévenus):\
https://wstein.org/edu/2010/414/projects/novotney.pdf \
http://www.monnerat.info/publications/anomalous.pdf

- Explication de l'attaque par réseau et de l'algorithme LLL:\
https://forum.vac.dev/t/lattice-attacks-on-ecdsa/136 \
\
L'attaque est basée sur la partie 4 d'un article de Joachim Breitner et Nadia Heninger:\
https://eprint.iacr.org/2019/023.pdf

- Explication du problème CVP:\
https://en.wikipedia.org/wiki/Lattice_problem#Closest_vector_problem_(CVP)

- Explication de l'algorithme LLL:\
https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm