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.

Ce travail se divise en deux parties. Dans la première partie, nous généralisons le travail de Khuri-Makdisi qui décrit des algorithmes pour l'arithmétique des diviseurs sur une courbe sur un corps. Nous montrons que les analogues naturelles de ses résultats se vérifient pour les diviseurs de Cartier relatifs effectifs sur un schéma projectif, lisse et de dimension relative un sur un schéma affine noetherien quelconque, et que les analogues naturelles de ses algorithmes se vérifient pour une certaine classe d'anneaux de base. Nous présentons un formalisme pour tels anneaux qui sont caractérisés par l'existence d'un certain sous-ensemble des opérations standards de l'algèbre linéaire pour les modules projectifs sur ces anneaux.Dans la deuxième partie de ce travail, nous considérons un type de problème de Riemann-Roch pour les diviseurs sur certaines surfaces algébriques. Plus précisément, nous analysons les surfaces algébriques qui émanent d'un produit ou d'un produit symétrique d'une courbe hyperelliptique de genre supérieur à un sur un corps (presque) arbitraire. Les résultats principaux sont une décomposition des espaces de sections globales de certains diviseurs sur telles surfaces et des formules explicites qui décrivent les dimensions des espaces de sections de ces diviseurs. Dans le dernier chapitre, nous présentons un algorithme qui produit une base pour l'espace de sections globales d'un tel diviseur. / The contribution of this thesis is divided naturally into two parts. In Part I we generalise the work of Khuri-Makdisi (2004) on algorithms for divisor arithmetic on curves over fields to more general bases. We prove that the natural analogues of the results of Khuri-Makdisi continue to hold for relative effective Cartier divisors on projective schemes which are smooth of relative dimension one over an arbitrary affine Noetherian base scheme and that natural analogues of the algorithms remain valid in this context for a certain class of base rings. We introduce a formalism for such rings,which are characterised by the existence of a certain subset of the usual linear algebra operations for projective modules over these rings.Part II of this thesis is concerned with a type of Riemann-Roch problem for divisors on certain algebraic surfaces. Specifically we consider algebraic surfaces arising as the square or the symmetric square of a hyperelliptic curve of genus at least two over an (almost) arbitrary field. The main results are a decomposition of the spaces of global sections of certain divisors on such surfaces and explicit formulæ for the dimensions of the spaces of sections of these divisors. In the final chapter we present an algorithm which generates a basis for the space of global sections of such a divisor.

Dans cette thèse, j'étudie deux aspects distincts de la cryptographie basée sur les courbes elliptiques et hyperelliptiques. Dans une première partie, je confronte deux méthodes de calcul de couplages, originales car ne reposant pas sur le traditionnel algorithme de Miller. Ainsi, dans [42], K. Stange calcula le couplage de Tate sur une courbe elliptique à partir d'un nouvel outil, les elliptic nets. Y. Uchida et S. Uchiyama généralisèrent ces objets au cas hyperelliptique ([47]), mais ne donnèrent un algorithme pour le calcul de couplages que dans le cas des courbes de genre 2. Mon premier travail dans cette thèse fut de donner cet algorithme pour le cas général. De leur côté, D. Lubicz et D. Robert donnèrent dans [28] une autre méthode de calcul de couplage, basée sur les fonctions thêta. Le second résultat de ma thèse est de réunifier ces deux méthodes : je montre que la formule de récurrence à la base des nets est une conséquence des formules d'addition des fonctions thêta utilisées dans l'algorithme de Lubicz et Robert. Dans la seconde partie de ma thèse, je me suis intéressé à l'algorithme de calcul d'index attaquant le problème du logarithme discret sur les courbes elliptiques et hyperelliptiques. Dans le cas elliptique, une des étapes principales de cette attaque repose sur les polynômes de Semaev. Je donne une nouvelle construction ces polynômes en utilisant la fonction sigma de Weierstrass, pour pouvoir ensuite les généraliser pour la première fois au cas hyperelliptique. / In this thesis, I study two different aspects of elliptic and hyperelliptic curves based cryptography.In the first part, I confront two methods of pairings computation, whose original feature is that they are not based the traditional Miller algorithm. Therefore, in [42], K. Stange computed Tate pairings on elliptic curves using a new tool, the elliptic nets. Y. Uchida and S. Uchiyama generalized these objects to hyperelliptic case ([47]), but they gave an algorithm for pairing computation only for the genus 2 case. My first work in this thesis was to give this algorithm for the general case. Meanwhile, D. Lubicz and D. Robert gave in [28] an other pairing computation method, based on theta functions. The second result of my thesis is the reunification of these two methods : I show that the recurrence equation which is the basis of nets theory is a consequence of the addition law of theta functions used in the Lubicz and Robert’s algorithm. In the second part, I study the index calculus algorithm attacking the elliptic and hyperelliptic curve discrete logarithm problem. In the elliptic case, one of the main steps of this attack requires the Semaev polynomials. I reconstruct these polynomials using Weierstrass sigma function, with the purpose of giving their first hyperelliptic generalization.

Le logarithme discret sur les courbes elliptiques fournit la panoplie standard de la cryptographie à clé publique: chiffrement asymétrique, signature, authentification. Son extension à des courbes hyperelliptiques de genre supérieur se heurte à la difficulté de construire de telles courbes qui soient sécurisées. Dans cette thèse nous utilisons la théorie des fonctions thêta développée par Mumford pour construire des algorithmes efficaces pour manipuler les variétés abéliennes. En particulier nous donnons une généralisation complète des formules de Vélu sur les courbes elliptiques pour le calcul d'isogénie sur des variétés abéliennes. Nous donnons également un nouvel algorithme pour le calcul efficace de couplage sur les variétés abéliennes en utilisant les coordonnées thêta. Enfin, nous présentons une méthode de compression des coordonnées pour améliorer l'arithmétique sur les coordonnées thêta de grand niveau. Ces applications découlent d'une analyse fine des formules d'addition sur les fonctions thêta. Si les résultats de cette thèse sont valables pour toute variété abélienne, pour les applications nous nous concentrons surtout sur les jacobienne de courbes hyperelliptiques de genre~$2$, qui est le cas le plus significatif cryptographiquement. / The discrete logarithm on elliptic curves give the standard protocols in public key cryptography: asymmetric encryption, signatures, ero-knowledge authentification. To extends the discrete logarithm to hyperelliptic curves of higher genus we need efficient methods to generate secure curves. The aim of this thesis is to give new algorithms to compute with abelian varieties. For this we use the theory of algebraic theta functions in the framework of Mumford. In particular, we give a full generalization of Vélu's formulas for the computation of isogenies on abelian varieties. We also give a new algorithm for the computation of pairings using theta coordinates. Finally we present a point compression method to manipulate These applications follow from the analysis of Riemann relations on theta functions for the addition law. If the results of this thesis are valid for any abelian variety, for the applications a special emphasis is given to Jacobians of hyperelliptic genus~$2$ curves, since they are the most significantly relevant case in cryptography.

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

Dans cette thèse nous étudions la filtration par le poids sur la cohomologie de De Rham d’une courbe hyperelliptique C définie sur une extension finie de Qp et à réduction semi-stable. L’objectif est de fournir des algorithmes calculant explicitement, étant donné une équation de C, les bases des crans de la filtration par le poids ainsi que la matrice de l’accouplement de Poincaré. Dans le premier chapitre, nous mettons en place des outils relatifs à la cohomologie de De Rham algébrique de la courbe hyperelliptique. Nous construisons une base adaptée de la cohomologie de De Rham de C, nous établissons une formule explicite pour le cup-produit et la trace, et enfin nous proposons un algorithme calculant la matrice de l’accouplement de Poincaré. Le deuxième chapitre est consacré à la description explicite de la flèche induite par l’inclusion du tube d’un point double sur les espaces de cohomologie. C’est l’ingrédient essentiel pour pouvoir décrire la filtration par le poids sur la cohomologie de De Rham de C. À cette fin nous nous plaçons dans le cadre de la géométrie analytique à la Berkovich et nous introduisons puis développons les notions de point résiduellement singulier standard et de forme apparente de l’équation de la courbe. Dans le troisième et dernier chapitre, nous faisons la synthèse des résultats obtenus et achevons la description de la filtration par le poids. Enfin, nous donnons les algorithmes calculant les bases de Fil0 et Fil1. Pour les algorithmes obtenus dans la thèse nous proposons une implémentation en sage, ainsi que des exemples concrets sur des courbes de genre un et deux. / In this thesis we study the weight filtration on the De Rham cohomology of an hyperelliptic curve C defined over a finite extension of Qp and with semi-stable reduction. The goal is to provide algorithms computing explicitly, given an equation of C, the basis of the weight filtration’s spaces as well as the matrix of the Poincaré pairing. In the first chapter we introduce tools related to the algebraic De Rham cohomology of the hyperelliptic curve. We build a suitable basis of the De Rham cohomology of C, we establish explicit formulae for the cup-product and the trace, and we give an algorithm computing the matrix of the Poincaré pairing. The second chapter is dedicated to the explicit description of the morphism induced by the inclusion of the tube of a double point on the cohomology spaces. It is the main ingredient that allows us to describe the weight filtration on the De Rham cohomology of C. To achieve that, we use the framework of the Berkovitch analytical geometry. We introduce and then we develop the notion of standard residually singular points and the notion of apparent form of the curve’s equation. In the third and last chapter, we synthesize all the results and we complete the description of the weight filtration. Finally, we give the algorithms that compute the basis of Fil0 and Fil1. For each of our algorithm, we propose a sage implementation and concrete examples on genus one and two curves.

Disertaciją sudaro darbai, autoriaus atlikti 2006-2013 metais. Šiuos darbus jungianti tema yra algebrinių kreivių, apibrėžtų virš racionaliųjų skaičių, šeimos, einančios per taškus, kurių koordinatės priklauso duotam skaičių kūnui ar jo sveikųjų skaičių žiedui. Pirmoje disertacijos dalyje yra gaunama vidutinio mažo aukščio racionaliųjų taškų kiekio ant fiksuoto žanro hiperelipsinių kreivių asimptotika. Antroje dalyje šis rezultatas išplečiamas, apibūdinant vidutinį homogeninių daugianarių reikšmių taškuose, kurių koordinatės yra mažo aukščio tarpusavyje pirminiai skaičiai, sutampančių su duoto vieno kintamojo daugianario reikšmėmis sveikuosiuose taškuose, skaičių. Trečioje dalyje sukonstruojamos nedidelės kreivių, apibrėžtų virš racionaliųjų skaičių ir išvengiančių taškų, kurių koordinatės priklauso duotam skaičių kūnui, šeimos. Ketvirtoje dalyje nagrinėjamos kongruenčių skaičių kreivės. Įrodoma, kad bent pusė pirminių skaičių p, kurie lieka inertiški cikliniame skaičių kūne K, atitinka kreives 16p^2 = x^4 - y^2, neturinčias netrivialių taškų su koordinatėmis to kūno sveikųjų skaičių žiede. Paskutinėje dalyje iliustruojamas Gauso sveikųjų skaičių skaidymosi daugikliais vienatinumo taikymas įrodant, kad konkreti hiperelipsinė kreivė neturi taškų su sveikosiomis koordinatėmis. / In this document, the author collected his work that ranges through the years 2006-2013. The common theme that occurs in its five separate parts is that of families of algebraic curves defined over the rational numbers with points over a number field or over its ring of integers. In the first part, average number of rational points of small height on hyperelliptic curves of fixed genus is described. In the second part, this result is extended to describing how often, on average, values of homogeneous polynomials at pairs of small coprime integers are values of a given univariate polynomial with integer coefficients. Further, small families of curves that are defined over the rational numbers and do not have points over a given number field are constructed. In the subsequent part, congruent number curves are investigated. It is shown that, given a cyclic number field K, at least half of the prime numbers p that remain inert in K correspond to curves 16p^2 = x^4 - y^2 that do not have nontrivial points over the ring of integers of K. In the last part, a short exposition to a classical technique of showing that a particular curve does not have integral points is given.

In this document, the author collected his work that ranges through the years 2006 - 2013. The common theme that occurs in its five parts is that of families of algebraic curves defined over the rational numbers with points over a number field or over its ring of integers. In the first part, average number of rational points of small height on hyperelliptic curves of fixed genus is described. In the second part, this result is extended to describing how often, on average, values of homogeneous polynomials at pairs of small coprime integers are values of a given univariate polynomial with integer coefficients. Further, small families of curves that are defined over the rational numbers and do not have points over a given number field are constructed. In the subsequent part, congruent number curves are investigated. It is shown that, given a cyclic number field K, at least half of the prime numbers p that remain inert in K correspond to curves 16p^2 = x^4 - y^2 that do not have nontrivial points over the ring of integers of K. In the last part, a short exposition to a classical technique of showing that a particular curve does not have integral points is given. / Disertaciją sudaro darbai, autoriaus atlikti 2006-2013 metais. Šiuos darbus jungianti tema yra algebrinių kreivių, apibrėžtų virš racionaliųjų skaičių, šeimos, einančios per taškus, kurių koordinatės priklauso duotam skaičių kūnui ar jo sveikųjų skaičių žiedui. Pirmoje disertacijos dalyje yra gaunama vidutinio mažo aukščio racionaliųjų taškų kiekio ant fiksuoto žanro hiperelipsinių kreivių asimptotika. Antroje dalyje šis rezultatas išplečiamas, apibūdinant vidutinį homogeninių daugianarių reikšmių taškuose, kurių koordinatės yra mažo aukščio tarpusavyje pirminiai skaičiai, sutampančių su duoto vieno kintamojo daugianario reikšmėmis sveikuosiuose taškuose, skaičių. Trečioje dalyje sukonstruojamos nedidelės kreivių, apibrėžtų virš racionaliųjų skaičių ir išvengiančių taškų, kurių koordinatės priklauso duotam skaičių kūnui, šeimos. Ketvirtoje dalyje nagrinėjamos kongruenčių skaičių kreivės. Įrodoma, kad bent pusė pirminių skaičių p, kurie lieka inertiški cikliniame skaičių kūne K, atitinka kreives 16p^2 = x^4 - y^2, neturinčias netrivialių taškų su koordinatėmis to kūno sveikųjų skaičių žiede. Paskutinėje dalyje iliustruojamas Gauso sveikųjų skaičių skaidymosi daugikliais vienatinumo taikymas įrodant, kad konkreti hiperelipsinė kreivė neturi taškų su sveikosiomis koordinatėmis.