Arithmetic for Cryptography based on Elliptic Curves

In this thesis, we are interested in the problem of implementing point multiplication by a scalar on elliptic curves defined over prime fields. We address this problem both at the level of point multiplication algorithms and at the level of the arithmetic of the curve or the underlying body. The originality of the work presented here is that it does not deal with each aspect separately. Indeed we have always tried to develop the arithmetic at a given level keeping in mind its link with the lower or higher levels.The present thesis consists of three parts. The first part is devoted to the state of the art concerning the arithmetic of elliptic curves. Chapter 1 is an overview of the main properties of elliptic curves and of the different formulas for adding points according to the chosen coordinate system. In chapter 2, we present the main methods of point multiplication by a scalar, both for curves defined on prime fields and for curves defined on binary fields.The second part deals with the study of new point addition formulas on curves and the new point multiplication algorithms that can be derived from them. Chapter 3 details the new point addition formulas, as well as the so-called "Fibonacci" algorithm and addition. In chapter 4 we present a type of addition chains, the differential addition chains, naturally adapted to the formulas introduced in the previous chapter, then we propose a construction of particular chains, in order to deduce the most efficient point multiplication algorithm possible.The third part deals with the RNS representation and its adaptation to the arithmetic of elliptic curves. In chapter 5 we recall the main properties of the RNS representation. In chapter 6, we propose particular RNS bases allowing to improve the efficiency of the calculations. Then, in chapter 7, we propose a modular inversion algorithm in RNS. Finally, chapter 8 is devoted to the study of the complexity of the sums of modular products according to the chosen representation system, and then to the development of the formulas of addition of points on the curves in order to take advantage of the specificity of RNS.Dans cette thèse, nous nous intéressons au problème de l'implantation de la multiplication de point par un scalaire sur les courbes elliptiques définies sur des corps premiers. Nous abordons ce problème aussi bien au niveau des algorithmes de multiplication de points, que de l'arithmétique de la courbe ou du corps sous-jacent. L'originalité des travaux présentés ici est qu'ils ne traitent pas de chaque aspects séparément. En effet nous avons toujours cherché à développer l'arithmétique à un niveau donné en gardant à l'esprit son lien avec les niveaux inférieurs ou supérieurs.La présente thèse compose de trois parties. La première partie est consacré à l'état de l'art concernant l'arithmétique des courbeselliptiques. Le chapitre 1 est un tour d'horizon des principales propriétés des courbes elliptiques et des différentes formules d'addition de points selon le système de coordonnées choisi. Dans le chapitre 2, nous présentons les principales méthodes de multiplication de points par un scalaire, aussi bien pour les courbes définies sur des corps premiers que pour les courbes définies sur des corps binaires.La deuxième partie a pour objet l'étude de nouvelles formules d'addition de points sur les courbes et les nouveaux algorithmes de multiplication de points que l'on peut en déduire. Le chapitre 3 détaille les nouvelles formules d'addition de points, ainsi que l'algorithme dit de "Fibonacci" et addition. Dans le chapitre 4 nous présentons un type de chaînes d'additions, les chaînes d'additions différentielles, naturellement adaptées auxformules introduites dans le chapitre précédent, puis, nous proposons une construction de chaînes particulières, afin d'en déduire un algorithme de multiplication de point le plus efficace possible.La troisième partie traite de la représentation RNS et de son adaptation à l'arithmétique des courbes elliptiques. Dans le chapitre 5 nous faisons un rappel des propriétés principale de la représentation RNS. Nous proposons, dans le chapitre 6, des bases RNS particulières permettant d'améliorer l'efficacité des calculs. Ensuite, dans le chapitre 7, nous proposons un algorithme d'inversion modulaire en RNS. Enfin, le chapitre 8 est consacré à l'étude de la complexité des sommes de produits modulaires en fonction du système de représentation choisi, puis à l'aménagement des formules d'additions de points sur les courbes afin de tirer avantages des spécificité du RNS