Cryptographie!

Chiffrer à l'aide des courbes elliptiques


Avant d'aborder cette lecture, il faut avoir lu cette page.

  Les courbes elliptiques sont bien adaptées à la cryptographie à clé publique. Elles permettent de remplacer les calculs sur des entiers, ou dans les groupes $\mathbb Z/n\mathbb Z$, par des calculs dans les groupes associés à une courbe elliptique.
Echange de clés par courbes elliptiques :

  Il s'agit d'un échange de clés à la manière de Diffie et Hellman, c'est-à-dire sans se les communiquer directement. Alice et Bob se mettent d'accord ensemble et publiquement sur une courbe elliptique $E(a,b,\mathbb K)$, c'est-à-dire qu'ils choisissent un corps fini $\mathbb K$ (par exemple, $\mathbb Z/p\mathbb Z$) et une courbe elliptique $y^2=x^3+ax^2+b$. Ils choisissent aussi ensemble, et toujours publiquement, un point $P$ situé sur la courbe.

  Ensuite, chacun de leur côté, et secrètement, Alice choisit un entier $k_A$ et Bob choisit un entier $k_B$. Alice envoie à Bob le point de la courbe elliptique $k_AP$, et Bob envoie à Alice le point $k_BP$. Chacun de leur côté, ils sont capables de calculer $k_A(k_B P)=k_B(k_A P)=(k_Ak_B)P$. Ce point de la courbe elliptique constitue leur clé secrète.

Alice Bob
Étape 1 :   Alice et Bob choisissent ensemble une courbe elliptique $E(a,b,\mathbb K)$ et un point $P$ sur la courbe. Cet échange n'a pas besoin d'être sécurisé.
Étape 2 :  

Alice choisit secrètement $k_A$ et envoie $k_AP$ à Bob. Cet échange n'a pas besoin d'être sécurisé.

Bob choisit secrètement $k_B$ et envoie $k_B P$ à Alice. Cet échange n'a pas besoin d'être sécurisé.

Étape 3 :  

Alice calcule $k_A(k_B P)=(k_Ak_B)P$.

Bob calcule $k_B(k_A P)=(k_Ak_B)P$.

  Si quelqu'un a espionné leurs échanges, il connait $E(a,b,K)$, $P$, $k_A P$ et $k_b P$. Pour pouvoir retrouver la clé $k_Ak_B P$, il faut pouvoir calculer $k_A$ connaissant $P$ et $k_A P$. C'est ce que l'on appelle résoudre le logarithme discret sur la courbe elliptique (c'est le même type de problème, avec des notations additives, que de retrouver $n$ dans une équation $y\equiv x^n\ [p]$, avec $x,y$ et $p$ connus). Le logarithme discret est déjà difficile à résoudre dans les groupes bien connus comme $\mathbb Z/p\mathbb Z$. Pour les groupes plus compliqués, et très différents les uns des autres, des courbes elliptiques, c'est encore plus difficile!

Transmission de messages :

  On suppose cette fois qu'Alice veut envoyer à Bob un message en utilisant un algorithme de chiffrement par courbes elliptiques. Bob commence par fabriquer une clé publique de la façon suivante. Il choisit une courbe elliptique $E(a,b,\mathbb K)$, un point $P$ de la courbe, et un entier $k_B$. Sa clé publique est constituée par la courbe elliptique $E(a,b,K)$ et par les points $P$ et $k_B P$ de cette courbe elliptique. Sa clé privée est l'entier $k_B$, qu'on ne peut pas retrouver même connaissant $P$ et $k_B P$, par la difficulté de résoudre le problème du logarithme discret sur une courbe elliptique.

  Lorsqu'Alice veut envoyer de façon secrète un point $M$ de la courbe elliptique à Bob, voici l'échange qui se passe :

Alice Bob
Étape 1 :   Alice prend connaissance de la clé publique $(E,a,b,\mathbb K)$, $P$ et $k_B P$ de Bob.

Étape 2 :  

Alice choisit secrètement et aléatoirement un entier $n$.

Étape 3 :  

Alice calcule $nP$ et $M+nk_B P$ et envoie ces deux points à Bob.

Étape 4 :   Avec sa clé secrète $k_B$, Bob calcule $nk_B P$ à partir de $nP$, puis il calcule $(M+nk_B P)-nk_B P$.
Il retrouve ainsi $M$.

Si quelqu'un espionne les échanges, on ne connait pas de chemin plus facile que de calculer $k_B$ pour retrouver $M$ : c'est encore une fois le problème du logarithme discret à résoudre.

  Nous avons passé sous silence une difficulté majeure : si on veut s'échanger un texte, il faut pouvoir le tranformer en une suite de points de la courbe elliptique. Ceci est loint d'être trivial, car il n'est pas toujours facile de trouver des points sur une courbe elliptique. Les personnes intéressées peuvent consulter le livre de Neil Koblitz, A course in number theory and cryptography.

Avantages et inconvénients :

  Ce qui fait la différence des algorithmes de chiffrement à base de courbes elliptiques par rapport aux algorithmes basés sur les entiers comme RSA ou El-Gamal est que, pour les vaincre, il faut résoudre le logarithme discret sur le groupe de la courbe elliptique, et non un problème analogue sur les entiers. Ces groupes sont plus difficiles à manipuler, ils peuvent différer beaucoup les uns des autres si on change les paramètres. Ainsi, résoudre un problème de logarithme discret sur une courbe elliptique est réputé être un problème plus difficile que le problème similaire dans les entiers modulo $n$. C'est pourquoi on estime qu'une clé de 200 bits (qui mesure, pour une courbe elliptique, la taille du corps fini $\mathbb K$ de cette courbe) pour les chiffres basés sur les courbes elliptiques est plus sûre qu'une clé de 1024 bits pour le RSA. Comme les calculs sur les courbes elliptiques ne sont pas bien compliqués à réaliser, c'est un gros avantage pour les cartes à puces où on dispose de peu de puissance, et où la taille de la clé influe beaucoup sur les performances.

  Les inconvénients sont de deux ordres. D'une part, la théorie des fonctions elliptiques est complexe, et encore relativement récente. Il n'est pas exclu que des trappes permettent de contourner le problème du logarithme discret. D'autre part, la technologie de cryptographie par courbe elliptique a fait l'objet du dépot de nombreux brevets à travers le monde. Cela peut rendre son utilisation très coûteuse!
Consulter aussi