Etude de l'implémentaiton matérielle de l'arithmétique pour la cryptolographie
Institution:
Paris 8Disciplines:
Directors:
Abstract EN:
In this thesis, we propose to study and discuss the problem of the hardware implementation of arithmetic for the cryptography based on elliptic curves. We study the mathematical tools necessary for the execution of the different protocols for elliptic curves, by discussing theoretical and hardware aspects, by treating in detail their complexity as well as various possible optimizations for the execution of these protocols (basic field, coordinate systems, algorithm of addition and duplication,…, etc. ). This subject is at the interface of mathematics, data processing and electronics. After a first bibliographical study on the subject; by studying the notion of cryptography and arithmetic of the finite fields, we make a state of the art of cryptography and we introduce the mathematical general tools which we will use (the arithmetic in the field Fqn), we present in detail the concept of elliptic curves; we then present the various methods of scalar multiplication on the curves. Then we give the various coordinate systems to represent the curves, as well as the formulas of additions, of doublings relationaly to these coordinates. We introduce another family of curves which are the curves of Edwards, and we make a comparison between this curves and the standards elliptic curves. We study the reconfigurable circuits for a hardware implementation; we present the reconfigurable circuits mainly FPGAs. In the last part, we develop the hardware implementations of elliptic curves arithmetic and some architectures of the scalar multiplication; we are interested in arithmetic of elliptic curves: this part gathers various works which we carried out concerning the establishment of arithmetic in finite fields and the study of implementation of hash functions, which are required for protocols of digital signature. We devoted more efforts to the development of the theoretical part in this thesis, by developing a number of various concepts, methods of computation and algorithms, considering that it was necessary to acquire a solid knowledge of embedded arithmetic for public key cryptography, on the FPGAs devices. Therefore, it was necessary to have a good control on theoretical aspects as well.
Abstract FR:
Dans ce travail de thèse, nous nous proposons d’étudier et de discuter la problématique de l’implémentation matérielle de l’arithmétique pour la cryptographie basée sur les courbes elliptiques. Nous étudions les outils mathématiques nécessaires pour l’exécution des différentes protocoles pour les courbes elliptiques, en discutant les aspects théoriques et matériels, en traitant en détail leurs complexité ainsi que les différentes optimisations possibles pour l’exécution de ces protocoles (corps de base, coordonnées, algorithme d’addition et de duplication,…, etc. ). Ce travail se situe à l’interface des mathématiques, de l’informatique et de l’électronique. Après une première étape bibliographique sur le sujet, en étudiant la notion de cryptographie et de l’arithmétique des corps finis; nous faisons un état de l’art de la cryptographie et nous introduisons les outils généraux mathématiques que nous utiliserons (l’arithmétique dans les corps Fqn): nous présentons en détail la notion de courbes elliptiques, nous rappellerons d’abord les différentes méthodes de multiplication scalaire sur les courbes. Ensuite nous donnons les différents systèmes de coordonnées pour représenter les courbes, ainsi que les formules d’additions, de doublements, dans ces coordonnées. Nous présenterons une autre famille de courbes qui sont les courbes d’Edwards et nous faisons une comparaison avec les courbes elliptiques standards. Nous exposons ensuite les circuits reconfigurables en vue d’une implémentation matérielle, nous présentons principalement les FPGAs. En dernier nous développons les implémentations matérielles de l’arithmétique des courbes elliptiques et les différentes architectures de la multiplication scalaire. Nous nous intéressons également à l’arithmétique sur les courbes elliptiques; cette partie regroupe les divers travaux que nous avons effectués concernant l’implantation de l’arithmétique dans les corps finis et l’étude de l’implémentation matérielle des fonctions de hachage qui sont requises dans les protocoles de signature numérique. Nous avons consacré plus d’efforts au développement théorique dans le travail de cette thèse, en développant au maximum les différentes notions, méthodes de calcul et algorithmes traités dans ce travail: il a fallu d’abord acquérir de solides connaissances en arithmétique embarquée pour la cryptographie à clé publique implantée sur FPGA, et que pour se lancer dans cet axe de recherche, il fallait bien arriver à maîtriser les aspects théoriques en la matière.