Algorithmes et Implémentations Optimisées de Calculs Cryptographiques sur les Courbes Elliptiques Binaires

Les calculs cryptographiques necessitent d’effectuer des operations sur des corps finis avec les regles arithmetiques correspondantes. Le developpement de la cryptographie sur les courbes elliptiques (ECC, Elliptic Curve Cryptography), et plus particulierement celles definies sur les corps binaires (F 2 m ), implique d’implementer ces operations a l’aide d’algorithmes de plus en plus performants, et de tirer parti des plates-formes disposant des processeurs ayant un jeu d’instruction etendu a l’arithmetique des polynomes de ces corps binaires. Apres avoir rappele les fondements de l’arithmetique sur les courbes elliptiques ainsi que pour les operations sur les corps binaires, nous parlerons ensuite d’optimisations du code exploitant les specificites du processeur Intel Core I7, en particulier la multiplication sans retenue (carry-less multiplier ), ainsi que l’utilisation des registres MMX (MultiMedia eXtension). Ces deux optimisations impliquent une refonte profonde de la facon de coder les algorithmes, de par le caractere SIMD du jeu d’instruction correspondant. Nous montrerons combien les algorithmes doivent etre adaptes a de tels types de variables. Ces implementations permettent d’atteindre les meilleures performances publiees et d’etre au niveau de l’etat de l’art. Peut-on aller plus loin ? Certaines combinaisons d’operations sur le corps binaire (F 2 m ), lorsque des operandes sont communes ou donnent lieu a des simplifications, peuvent-elles apporter un gain supplementaire ? L’examen d’optimisations prenant en compte des operations combinees de type AB, AC et AB + CD, (A, B, C, D ∈ F 2 m ) fait l’objet d’experimentations. La combinatoire des cas (taille des corps binaires finis et type des variables manipulees par les implementations) est partiellement exploree. Des gains sont observes sous certaines conditions. Les experimentations menees laissent encore la question ouverte, mais tracent la voie a des developpements ulterieurs.