|
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,K), c'est-à-dire qu'ils choisissent un corps fini K (ex : Z/pZ), et une courbe elliptique y2=x3+ax2+b. Ils se mettent aussi d'accord sur un point P situé sur la courbe. Secrètement, Alice choisit un entier kA, et Bob un entier kB. Alice envoie à Bob le point kAP, et Bob envoie à Alice kBP. Chacun de leur côté, ils sont capables de calculer kA(kBP)=kB(kAP)=(kAkB)P, qui est un point de la courbe, et constitue leur clé secrète. Si quelqu'un a espionné leurs échanges, il connait E(a,b,K), P, kAP et kBP. Pour pouvoir calculer kAkBP, il faut pouvoir calculer kA connaissant P et kAP. C'est ce que l'on appelle résoudre le logarithme discret sur la courbe elliptique (c'est le même type de problèmes, avec des notations additives, que de retrouver n dans une équation y=xn dans Z/pZ, y et x connus). Le logarithme discret est déjà difficile à résoudre dans les groupes bien connus (Z/pZ)*. Pour les groupes plus compliqués, et très différents les uns des autres, des courbes elliptiques, c'est encore plus difficile!
On suppose qu'Alice et Bob ont suivi le protocole d'échange de clés expliqué ci-dessus. Alice veut envoyer à Bob un message: ils se sont mis d'accord sur la façon de transformer un texte en suite de points de la courbe elliptique. Alice doit donc transmettre, de façon secrète, un point M de la courbe E(a,b,K). Elle choisit (secrètement) un nombre l, et envoie à Bob le couple (lP,M+lkBP). Bob, lui, multiplie lP par kB (sa clé secrète), puis retranche lkBP à M+lkBP : il retrouve M. Si quelqu'un espionne les échanges, il lui faut absolument connaitre kB pour retrouver M : c'est encore une fois le problème du logarithme discret à résoudre. Nous avons passé sous silence une des difficultés majeures : l'algorithme pour transformer un texte en points de la courbe elliptique est loin d'être trivial; il n'est pas toujours facile de trouver un point sur la courbe elliptique. Les personnes intéressées peuvent consulter le livre de Neil Koblitz A course in number theory and cryptography.
Ce qui fait la sûreté de l'algorithme à base de courbes elliptiques par rapport au RSA est que, pour le vaincre, il faut résoudre le logarithme discret sur le groupe de la courbe elliptique, et non plus sur (Z/pZ)*. Mais ces groupes sont beaucoup moins bien connus que ce dernier, et ils diffèrent d'une courbe à l'autre. Les algorithmes dont on dispose pour résoudre le logarithme discret sur les courbes elliptiques sont donc moins efficaces. C'est pourquoi on estime qu'une clé (=taille du corps de base) de 200 bits pour 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!Et encore, dans la cryptographie expliquée...
|