Cryptographie à base de courbe elliptique et implémentation

Abstract

Cette thèse porte principalement sur la contribution au domaine de cryptographie à courbe elliptique afin de réaliser le protocole d'accord Diffie-Hellmann (ECDH). Celle-ci, a permis le développement d'une nouvelle boîte à outils Matlab appelée ECC-NIST qui est une extension à la bibliothèque Matlab déjà existante, qui peut gérer de champs Galois du type GF (2 m) sur les courbes elliptiques. Les corps binaires GF (2 m) présentent l'avantage de faciliter l'implémentation sur nos ordinateurs pour d'évidentes raisons de cohérence et de compatibilité entre leur représentation binaire et la technologie informatique. L'opération principale du protocole d'accord ECDH est la multiplication scalaire qui consiste à additionner et à doubler un certain nombre de fois un point de courbe elliptique avec lui-même. Donc optimiser cette opération, faire un bon choix de paramètres de la courbe ainsi que le choix des coordonnées sont des critères cruciales. Nous avons choisi la méthode de la réduction de Montgomery, qui est une méthode de réduction permettant d'éviter l'utilisation de divisions coûteuses en les remplaçant par des opérations très efficaces comme des décalages. Pour pouvoir utiliser ces décalages, la contrainte est d'autoriser la sortie à être un peu supérieure à p pour une réduction modulo p, et ainsi une optimisation au niveau du multiplieur modulaire qui est basé sur l'algorithme de Karatsuba-Ofman pour l?accélération de l'opération la plus lourde et la plus complexe, car le produit de polynômes et d?entiers est une opération élémentaire, qui intervient dans le calcul de KP . L?efficacité de cet algorithme repose donc sur celle du produit. Pour multiplier deux polynômes de degré n à coefficients dans un anneau A, la méthode classique requiert O (n 2) opérations dans A. De même, l'algorithme scalaire de multiplication de deux entiers à n chiffres nécessite un nombre d?opérations binaires en O (n 2) par contre l?algorithme de Karatsuba, réduit la complexité à O (n 1,59). Il existe de nombreuses références dans l'état de l'art qui présentent des algorithmes d'inversion modulaire d'un opérande. Pour notre protocole d'échange, nous avons utilisé l'algorithme inverse de Itoh-Tsujii multiplicatif sur le champ GF (2 m). Ainsi on réduit le nombre au minimum d'opération car elle est très coûteuse vis à vis des autres opérations comme la multiplication et la règle de la chaîne d'addition sur les courbes elliptiques est donnée par NIST.