Implementation of elliptic and hyperelliptic curve cryptographic algorithms has been the focus of a great deal of recent research directed at increasing efficiency. Elliptic curve cryptography (ECC) was introduced independently by Koblitz and Miller in the 1980s. Hyperelliptic curve cryptography (HECC), a generalization of the elliptic curve case, allows a decreasing field size as the genus increases. The work presented in this thesis examines the problems created by limited area, power, and computation time when elliptic and hyperelliptic curves are integrated into constrained devices such as wireless sensor network (WSN) and smart cards. The lack of a battery in wireless sensor network limits the processing power of these devices, but they still require security. It was widely believed that devices with such constrained resources cannot incorporate a strong HECC processor for performing cryptographic operations such as elliptic curve scalar multiplication (ECSM) or hyperelliptic curve divisor multiplication (HCDM). However, the work presented in this thesis has demonstrated the feasibility of integrating an HECC processor into such devices through the use of the proposed architecture synthesis and optimization techniques for several inversion-free algorithms. The goal of this work is to develop a hardware implementation of binary elliptic and hyperelliptic curves. The focus is on the modeling of three factors: register allocation, operation scheduling, and storage binding. These factors were then integrated into architecture synthesis and optimization techniques in order to determine the best overall implementation suitable for constrained devices. The main purpose of the optimization is to reduce the area and power. Through analysis of the architecture optimization techniques for both datapath and control unit synthesis, the number of registers was reduced by an average of 30%. The use of the proposed efficient explicit formula for the different algorithms also enabled a reduction in the number of read/write operations from/to the register file, which reduces the processing power consumption. As a result, an overall HECC processor requires from 1843 to 3595 slices for a Xilinix XC4VLX200 and the total computation time is limited to between 10.08 ms to 15.82 ms at a maximum frequency of 50 MHz for a varity of inversion-free coordinate systems in hyperelliptic curves. The value of the new model has been demonstrated with respect to its implementation in elliptic and hyperelliptic curve crypogrpahic algorithms, through both synthesis and simulations. In summary, a framework has been provided for consideration of interactions with synthesis and optimization through architecture modeling for constrained enviroments. Insights have also been presented with respect to improving the design process for cryptogrpahic algorithms through datapath and control unit analysis.

Implementation of elliptic and hyperelliptic curve cryptographic algorithms has been the focus of a great deal of recent research directed at increasing efficiency. Elliptic curve cryptography (ECC) was introduced independently by Koblitz and Miller in the 1980s. Hyperelliptic curve cryptography (HECC), a generalization of the elliptic curve case, allows a decreasing field size as the genus increases. The work presented in this thesis examines the problems created by limited area, power, and computation time when elliptic and hyperelliptic curves are integrated into constrained devices such as wireless sensor network (WSN) and smart cards. The lack of a battery in wireless sensor network limits the processing power of these devices, but they still require security. It was widely believed that devices with such constrained resources cannot incorporate a strong HECC processor for performing cryptographic operations such as elliptic curve scalar multiplication (ECSM) or hyperelliptic curve divisor multiplication (HCDM). However, the work presented in this thesis has demonstrated the feasibility of integrating an HECC processor into such devices through the use of the proposed architecture synthesis and optimization techniques for several inversion-free algorithms. The goal of this work is to develop a hardware implementation of binary elliptic and hyperelliptic curves. The focus is on the modeling of three factors: register allocation, operation scheduling, and storage binding. These factors were then integrated into architecture synthesis and optimization techniques in order to determine the best overall implementation suitable for constrained devices. The main purpose of the optimization is to reduce the area and power. Through analysis of the architecture optimization techniques for both datapath and control unit synthesis, the number of registers was reduced by an average of 30%. The use of the proposed efficient explicit formula for the different algorithms also enabled a reduction in the number of read/write operations from/to the register file, which reduces the processing power consumption. As a result, an overall HECC processor requires from 1843 to 3595 slices for a Xilinix XC4VLX200 and the total computation time is limited to between 10.08 ms to 15.82 ms at a maximum frequency of 50 MHz for a varity of inversion-free coordinate systems in hyperelliptic curves. The value of the new model has been demonstrated with respect to its implementation in elliptic and hyperelliptic curve crypogrpahic algorithms, through both synthesis and simulations. In summary, a framework has been provided for consideration of interactions with synthesis and optimization through architecture modeling for constrained enviroments. Insights have also been presented with respect to improving the design process for cryptogrpahic algorithms through datapath and control unit analysis.

Cette thèse est consacrée à l'étude des fibres de l'application moment du système de Mumford (pair ou impair) d'ordre g>0. Ces fibres sont paramétrées par des courbes hyperelliptiques de genre g. Comme l'a démontré Mumford, la fibre au-dessus d'une telle courbe lisse est la jacobienne de la courbe, moins son diviseur thêta. Nous décrivons les fibres au-dessus d'une courbe singulière, à la fois de manière algébrique et géométrique. Pour ce faire, nous utilisons de façon essentielle les g champs de vecteurs du système de Mumford, qui définissent une stratification de chaque fibre, où chaque strate est isomorphe à une strate particulière (dite maximale) d'une fibre d'un système de Mumford d'ordre inférieur. Sur cette strate, tous les champs de vecteurs du système de Mumford sont linéairement indépendants en tout point. Nous décrivons cette strate comme un ouvert de la jacobienne généralisée d'une courbe hyperelliptique singulière. Nous montrons également que sur la jacobienne généralisée, les champs de Mumford sont des champs invariants par translation. / This thesis is dedicated to the study and to the description of the fibres of the momentum map of the (even or odd) Mumford system of degree g>0. These fibres are parameterized by hyperelliptic curves. Mumford proved that each fiber over a smooth curve is isomorphic to the Jacobian of the curve, minus its theta divisor. We give a geometrical as well as an algebraic description of the fibers over any singular curve. The geometrical description uses in an essential way the g vector field of the Mumford system. They define a stratification of each fiber where each stratum is isomorphic to a particular stratum, called the maximal stratum, of a fiber of a Mumford system of degree at most g. The algebraic description uses the theory of subresultants, which is applied to the polynomials which parametrize the points of phase space. We show that every stratum is isomorphic with an affine part of the generalized Jacobian of a singular hyperelliptic curve. We also prove that the Mumford vector fields are translation invariant on these generalized Jacobians.

In present work we study the algorithms for point counting on elliptic and hy- perelliptic curves. At the beginning we describe a few simple and ineffective al- gorithms. Then we introduce more complex and effective ways to determine the point count. These algorithms(especially the Schoof's algorithm) are important for the cryptography based on discrete logarithm in the group of points of an el- liptic or hyperelliptic curve. The point count is important to avoid the undesirable cases where the cryptosystem is easy to attack. 1

Secure communication is critical to many applications. To this end, various security goals can be achieved using elliptic/hyperelliptic curve and pairing based cryptography. Polynomial multiplication is used in the underlying operations of these protocols. Therefore, as part of this thesis different recursive algorithms are studied; these algorithms include Karatsuba, Toom, and Bernstein. In this thesis, we investigate algorithms and implementation techniques to improve the performance of the cryptographic protocols. Common factors present in explicit formulae in elliptic curves operations are utilized such that two multiplications are replaced by a single multiplication in a higher field. Moreover, we utilize the idea based on common factor used in elliptic curves and generate new explicit formulae for hyperelliptic curves and pairing. In the case of hyperelliptic curves, the common factor method is applied to the fastest known even characteristic hyperelliptic curve operations, i.e. divisor addition and divisor doubling. Similarly, in pairing we observe the presence of common factors inside the Miller loop of Eta pairing and the theoretical results show significant improvement when applying the idea based on common factor method. This has a great advantage for applications that require higher speed.

Cette thèse traite de plusieurs aspects algorithmiques des courbes algébriques. La première partie décrit et implémente en Magma un algorithme de calcul des tordues pour les courbes sur les corps finis et en étudie la complexité. Dans le cas hyperellitptique, il s’agit du premier algorithme complet pour faire cela en tout genre. La deuxième partie construit des familles représentatives pour les courbes non hyperelliptiques de genre 3 afin de permettre leur énumération efficace en lien avec le problème de l’obstruction de Serre. Cette partie a fait l’objet d’une publication dans ANTS et une annexe de la thèse est constituée d’un préprint étudiant un modèle statistique pour l’interprétation des données obtenues. La dernière partie de la thèse étudie les invariants et covariants des formes binaires en lien avec la description de l’espace de modules des courbes de genre 2. On y décrit en particulier une nouvelle opération pour engendrer des covariants en petite caractéristique. On étudie aussi l’application d’une nouvelle stratégie (dite de Geyer-Sturmfels) pour obtenir les algèbres de séparants et on l’applique au cas du degré 4 et du degré 6. Enfin, un dernier chapitre montre la validité d’un algorithme de reconstruction pour les courbes de genre 2 à partir de leurs invariants en toute caractéristique différente de 2 et l’implémente en SAGE. / This thesis addresses several algorithmic aspects of algebraic curves.The first part describe and plug in Magma a computational algorithm of twists for the curves over finite fields and study it's complexity. In the hyperelliptic case, it is the first complete algorithm to do this in all genus. The second part builts representatives family for the non hyperelliptic curves of genus 3 to enable them effective enumeration in connection with the Serre obstruction problem. This part has been published in ANTS and an annex of this thesis is made up of a preprint studing a statistic model for interpreting the data obtained.The last part of the thesis studies the invariants and covariants of binary forms in connexion with the description of the moduli space of curves of genus 2. A new operation in particular is described to generate covariants in small characteristic. We study to the implementation of a new strategy (called Geyer-Sturmfels) to get the algebras of separants and we apply it of the case of degree 4 ans 6. Finally, the last chapter shows the validity of a reconstruction algorithm for genus 2 curves from their invariants in all characteristic diferent from 2 and implements it in SAGE .

Cílem této práce je zpracovat úvod do problematiky hypereliptických křivek s důrazem na konečná pole. T práci je dále popsán úvod do teorie divizorů na hypereliptických křivkách, jejich reprezentace, aritmetika nad divizory a jejich využití v kryptografii. Teorie je hojně demonstrována příklady a výpočty v systému Mathematica.

No description available.

De nombreux systèmes numériques nécessitent des primitives de cryptographie asymétrique de plus en plus performantes mais aussi robustes aux attaques et peu coûteuses pour les applications embarquées. Dans cette optique, la cryptographie sur courbe hyperelliptique (HECC) a été proposée comme une alternative intéressante aux techniques actuelles du fait de corps finis plus petits. Nous avons étudié des cryptoprocesseurs HECC matériels performants, flexibles et robustes contre certaines attaques physiques. Tout d’abord, nous avons proposé une nouvelle architecture d’opérateurs exécutant, en parallèle, plusieurs multiplications modulaires (A × B) mod P, où P est un premier générique de quelques centaines de bits et configurable dynamiquement. Elle permet le calcul de la grande majorité des opérations nécessaires pour HECC. Nous avons développé un générateur d’opérateurs, distribué en logiciel libre, pour l'exploration de nombreuses variantes de notre architecture. Nos meilleurs opérateurs sont jusqu'à 2 fois plus petits et 2 fois plus rapids que les meilleures solutions de l'état de l'art. Ils sont aussi flexibles quant au choix de P et atteignent les fréquences maximales du FPGA. Dans un second temps, nous avons développé des outils de modélisation et de simulation pour explorer, évaluer et valider différentes architectures matérielles pour la multiplication scalaire dans HECC sur les surfaces de Kummer. Nous avons implanté, validé et évalué les meilleures architectures sur différents FPGA. Elles atteignent des vitesses similaires aux meilleures solutions comparables de l’état de l’art, mais pour des surfaces réduites de moitié. La flexibilité obtenue permet de modifier lors de l'exécution les paramètres des courbes utilisées. / Many digital systems require primitives for asymmetric cryptography that are more and more efficient but also robust to attacks and inexpensive for embedded applications. In this perspective, and thanks to smaller finite fields, hyperelliptic curve cryptography (HECC) has been proposed as an interesting alternative to current techniques. We have studied efficient and flexible hardware HECC cryptoprocessors that are also robust against certain physical attacks. First, we proposed a new operator architecture able to compute, in parallel, several modular multiplications (A × B) mod P, where P is a generic prime of a few hundred bits and configurable at run time. It allows the computation of the vast majority of operations required for HECC. We have developed an operator generator, distributed in free software, for the exploration of many variants of our architecture. Our best operators are up to 2 times smaller and twice as fast as the best state-of-the-art solutions. They are also flexible in the choice of P and reach the maximum frequencies of the FPGA. In a second step, we developed modeling and simulation tools to explore, evaluate and validate different hardware architectures for scalar multiplication in HECC on Kummer surfaces. We have implemented, validated and evaluated the best architectures on various FPGA. They reach speeds similar to the best comparable solutions of the state of the art, but for halved surfaces. The flexibility obtained makes it possible to modify the parameters of the curves used during execution.