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

Jean-Marc Robert 1, 2
2 DALI - Digits, Architectures et Logiciels Informatiques
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, UPVD - Université de Perpignan Via Domitia
Résumé : Les calculs cryptographiques nécessitent d’effectuer des opérations sur des corps finis avec les règles arithmétiques correspondantes. Le développement de la cryptographie sur les courbes elliptiques (ECC, Elliptic Curve Cryptography), et plus particulièrement celles définies sur les corps binaires (F 2 m ), implique d’implémenter ces opérations à l’aide d’algorithmes de plus en plus performants, et de tirer parti des plates-formes disposant des processeurs ayant un jeu d’instruction étendu à l’arithmétique des polynômes de ces corps binaires. Après avoir rappelé les fondements de l’arithmétique sur les courbes elliptiques ainsi que pour les opérations sur les corps binaires, nous parlerons ensuite d’optimisations du code exploitant les spécificités 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 façon de coder les algorithmes, de par le caractère SIMD du jeu d’instruction correspondant. Nous montrerons combien les algorithmes doivent être adaptés à de tels types de variables. Ces implémentations permettent d’atteindre les meilleures performances publiées et d’être au niveau de l’état de l’art. Peut-on aller plus loin ? Certaines combinaisons d’opérations sur le corps binaire (F 2 m ), lorsque des opérandes sont communes ou donnent lieu à des simplifications, peuvent-elles apporter un gain supplémentaire ? L’examen d’optimisations prenant en compte des opérations combinées de type AB, AC et AB + CD, (A, B, C, D ∈ F 2 m ) fait l’objet d’expérimentations. La combinatoire des cas (taille des corps binaires finis et type des variables manipulées par les implémentations) est partiellement explorée. Des gains sont observés sous certaines conditions. Les expérimentations menées laissent encore la question ouverte, mais tracent la voie à des développements ultérieurs.
Type de document :
Communication dans un congrès
C2: Journées Codage et Cryptographie, Oct 2012, Dinard, France. 2012
Liste complète des métadonnées

Littérature citée [1 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01121958
Contributeur : Jean-Marc Robert <>
Soumis le : vendredi 24 avril 2015 - 01:03:38
Dernière modification le : mardi 10 octobre 2017 - 11:07:50
Document(s) archivé(s) le : mardi 18 avril 2017 - 19:43:55

Fichier

C2-111012.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-01121958, version 1

Collections

Citation

Jean-Marc Robert. Algorithmes et Implémentations Optimisées de Calculs Cryptographiques sur les Courbes Elliptiques Binaires. C2: Journées Codage et Cryptographie, Oct 2012, Dinard, France. 2012. 〈lirmm-01121958〉

Partager

Métriques

Consultations de
la notice

136

Téléchargements du document

148