Dans cette thèse, je propose des architectures de coprocesseurs haute performance pour implémenter les primitives de cryptographie asymétrique, comme le RSA, les courbes elliptiques ou le couplage. Les coprocesseurs décrits dans cette thèse ont été implémentés dans des FPGA, et présentent des performances jamais égalées auparavant dans la littérature publique sur ce type de technologie. La particularité de ces architectures est l'utilisation du Residue Number System, un mode de représentation alternatif qui utilise les restes chinois pour calculer efficacement les opérations arithmétiques sur les grands nombres. Ces travaux permettent de confirmer expérimentalement les avantages théoriques de ce mode de représentation pour l'arithmétique modulaire, issus de [14, 13, 43]. Au bénéfice théorique que le RNS apporte s'ajoute une forte capacité de parallélisation qui permet d'obtenir des designs réguliers et pipelinés, proposant une fréquence maximale importante tout en réalisant les opérations modulaires dans un nombre très faible de cycles, et ce quelle que soit la taille des nombres. A titre d'exemple, une multiplication scalaire sur une courbe de 160 bits s'effectue en 0.57 ms sur un Altera Stratix, et en 4 ms pour une courbe de 512 bits, là ou les techniques de représentation classiques réalisent la même opération en le double de temps, à technologie équivalente (excepté pour des courbes particulières). Dans le cas du couplage, le gain est encore plus intéressant, puisqu'il a permis une division par 4 de latence de la meilleure implémentation sur corps de grande caractéristique au moment de la publication de [35], et la première implémentation d'un couplage à 128 bits de sécurité sur corps de grande caractéristique à descendre en dessous de la milliseconde. Enfin, je démontre la capacité du RNS à sécuriser une implémentation haute performance, en proposant 2 contre-mesures contre les canaux auxiliaires et les fautes s'adaptant efficacement sur les coprocesseurs et pouvant être utilisées pour toutes les primitives cryptographiques basées sur l'arithmétique modulaire de grands nombres.

Depuis ces dix dernières années, les attaques sur le logarithme discret sur les courbes elliptiques (ECDLP) mettant en jeu la résolution de systèmes polynomiaux connaissent un large succès. C'est dans ce contexte que s'inscrit cette thèse dont les contributions sont doubles. D'une part, nous présentons de nouveaux outils de résolution de systèmes polynomiaux par bases de Gröbner. Nous montrons que la résolution de systèmes avec symétries est étroitement liée à la résolution de systèmes quasi-homogènes. Nous proposons ainsi de nouveaux résultats de complexité pour la résolution de tels systèmes. Nous nous intéressons également à l'étape bloquante de la résolution de systèmes : le changement d'ordre pour bases de Gröbner. La complexité classique de cette étape est cubique en le nombre de solutions et domine la complexité totale de la résolution. Nous proposons pour la première fois des algorithmes de changement d'ordre de complexité sous-cubique en le nombre de solutions. D'autre part, nous nous intéressons à l'attaque du logarithme discret sur les courbes elliptiques par calcul d'indice proposée par Gaudry. Nous mettons en évidence des familles de courbes elliptiques possédant des symétries particulières. Ces symétries impliquent un gain exponentiel sur la complexité de la résolution du ECDLP. Nous obtenons ainsi de nouveaux paramètres de sécurité pour certaines instances du ECDLP. Une des étapes principales de cette attaque nécessite le calcul de polynômes de sommation introduits par Semaev. Les symétries des courbes elliptiques binaires nous permettent d'élaborer un nouvel algorithme par évaluation-interpolation pour le calcul des polynômes de sommation. Munis de cet algorithme nous établissons un nouveau record pour le calcul de ces polynômes.

<p>Les systèmes cryptographiques à base de courbes elliptiques sont aujourd'hui de plus en plus employés dans les protocoles utilisant la cryptographie à clef publique. Ceci est particulièrement vrai dans le monde de l'embarqué qui est soumis à de fortes contraintes de coût, de ressources et d'efficacité, car la cryptographie à base de courbes elliptiques permet de réduire significativement la taille des clefs utilisées par rapport à d'autres systèmes cryptographiques tels que RSA.</p> <p>Les travaux qui suivent décrivent dans un premier temps 'implantation efficace et sécurisée de la cryptographie à base de courbes elliptiques sur des composants embarqués, en particulier sur des cartes à puce. La sécurisation de ces implantations nécessite de prendre en compte les attaques physiques dont un composant embarqué peut être la cible. Ces attaques incluent notamment les analyses par canaux auxiliaires qui consistent à étudier le comportement d'un composant qui manipule une clef secrête pour en déduire de l'information sur celle-ci, et les analyses par faute dans lesquelles un attaquant peut perturber le fonctionnement d'un composant dans le même but.</p> <p>Dans la seconde partie de ce mémoire de thèse, nous étudions ces attaques et leurs conséquences concernant l'implantation des systèmes cryptographiques à clef publique les plus répandus. De nouvelles méthodes d'analyse et de nouvelles contre-mesures sont proposées pour ces systèmes cryptographiques, ainsi que des attaques spécifiques à l'algorithme de chiffirement par bloc AES.</p>

La protection des mécanismes cryptographiques constitue un enjeu important lors du développement d'un système d'information car ils permettent d'assurer la sécurisation des données traitées. Les supports utilisés étant à la fois logiciels et matériels, les techniques de protection doivent s'adapter aux différents contextes.Dans le cadre d'une cible logicielle, des moyens légaux peuvent être mis en oeuvre afin de limiter l'exploitation ou les usages. Cependant, il est généralement difficile de faire valoir ses droits et de prouver qu'un acte illicite a été commis. Une alternative consiste à utiliser des moyens techniques, comme l'obscurcissement de code, qui permettent de complexifier les stratégies de rétro-conception en modifiant directement les parties à protéger.Concernant les implantations matérielles, on peut faire face à des attaques passives (observation de propriétés physiques) ou actives, ces dernières étant destructives. Il est possible de mettre en place des contre-mesures mathématiques ou matérielles permettant de réduire la fuite d'information pendant l'exécution de l'algorithme, et ainsi protéger le module face à certaines attaques par canaux cachés.Les travaux présentés dans ce mémoire proposent nos contributions sur ces sujets tes travaux. Nous étudions et présentons les implantations logicielle et matérielle réalisées pour le support de courbes elliptiques sous forme quartique de Jacobi étendue. Ensuite, nous discutons des problématiques liées à la génération de courbes utilisables en cryptographie et nous proposons une adaptation à la forme quartique de Jacobi étendue ainsi que son implantation. Dans une seconde partie, nous abordons la notion d'obscurcissement de code source. Nous détaillons les techniques que nous avons implantées afin de compléter un outil existant ainsi que le module de calcul de complexité qui a été développé. / The protection of cryptographic mechanisms is an important challenge while developing a system of information because they allow to ensure the security of processed data. Since both hardware and software supports are used, the protection techniques have to be adapted depending on the context.For a software target, legal means can be used to limit the exploitation or the use. Nevertheless, it is in general difficult to assert the rights of the owner and prove that an unlawful act had occurred. Another alternative consists in using technical means, such as code obfuscation, which make the reverse engineering strategies more complex, modifying directly the parts that need to be protected.Concerning hardware implementations, the attacks can be passive (observation of physical properties) or active (which are destructive). It is possible to implement mathematical or hardware countermeasures in order to reduce the information leakage during the execution of the code, and thus protect the module against some side channel attacks.In this thesis, we present our contributions on theses subjects. We study and present the software and hardware implementations realised for supporting elliptic curves given in Jacobi Quartic form. Then, we discuss issues linked to the generation of curves which can be used in cryptography, and we propose an adaptation to the Jacobi Quartic form and its implementation. In a second part, we address the notion of code obfuscation. We detail the techniques that we have implemented in order to complete an existing tool, and the complexity module which has been developed.

Dans cette thèse, on étudie les représentations 2-dimensionnelles continues du groupe de Galois absolu d'une clôture algébrique fixée de Q sur les corps finis qui sont modulaires et leurs images. Ce manuscrit se compose de deux parties.Dans la première partie, on étudie un problème local-global pour les courbes elliptiques sur les corps de nombres. Soit E une courbe elliptique sur un corps de nombres K, et soit l un nombre premier. Si E admet une l-isogénie localement sur un ensemble de nombres premiers de densité 1 alors est-ce que E admet une l-isogénie sur K ? L'étude de la repréesentation galoisienne associéee à la l-torsion de E est l'ingrédient essentiel utilisé pour résoudre ce problème. On caractérise complètement les cas où le principe local-global n'est pas vérifié, et on obtient une borne supérieure pour les valeurs possibles de l pour lesquelles ce cas peut se produire.La deuxième partie a un but algorithmique : donner un algorithme pour calculer les images des représentations galoisiennes 2-dimensionnelles sur les corps finis attachées aux formes modulaires. L'un des résultats principaux est que l'algorithme n'utilise que des opérateurs de Hecke jusqu'à la borne de Sturm au niveau donné n dans presque tous les cas. En outre, presque tous les calculs sont effectués en caractéristique positive. On étudie la description locale de la représentation aux nombres premiers divisant le niveau et la caractéristique. En particulier, on obtient une caractérisation précise des formes propres dans l'espace des formes anciennes en caractéristique positive.On étudie aussi le conducteur de la tordue d'une représentation par un caractère et les coefficients de la forme de niveau et poids minimaux associée. L'algorithme est conçu à partir des résultats de Dickson, Khare-Wintenberger et Faber sur la classification, à conjugaison près, des sous-groupes finis de $\PGL_2(\overline{\F}_\ell)$. On caractérise chaque cas en donnant une description et des algorithmes pour le vérifier. En particulier, on donne une nouvelle approche pour les représentations irréductibles avec image projective isomorphe soit au groupe symétrique sur 4 éléments ou au groupe alterné sur 4 ou 5 éléments. / In this thesis we investigate $2$-dimensional, continuous, odd, residual Galois representations and their images. This manuscript consists of two parts.In the first part of this thesis we analyse a local-global problem for elliptic curves over number fields. Let $E$ be an elliptic curve over a number field $K$, and let $\ell$ be a prime number. If $E$ admits an $\ell$-isogeny locally at a set of primes with density one then does $E$ admit an $\ell$-isogeny over $K$? The study of the Galois representation associated to the $\ell$-torsion subgroup of $E$ is the crucial ingredient used to solve the problem. We characterize completely the cases where the local-global principle fails, obtaining an upper bound for the possible values of $\ell$ for which this can happen.In the second part of this thesis, we outline an algorithm for computing the image of a residual modular $2$-dimensional semi-simple Galois representation. This algorithm determines the image as a finite subgroup of $\GL_2(\overline{\F}_\ell)$, up to conjugation, as well as certain local properties of the representation and tabulate the result in a database. In this part of the thesis we show that, in almost all cases, in order to compute the image of such a representation it is sufficient to know the images of the Hecke operators up to the Sturm bound at the given level $n$. In addition, almost all the computations are performed in positive characteristic.In order to obtain such an algorithm, we study the local description of the representation at primes dividing the level and the characteristic: this leads to a complete description of the eigenforms in the old-space. Moreover, we investigate the conductor of the twist of a representation by characters and the coefficients of the form of minimal level and weight associated to it in order to optimize the computation of the projective image.The algorithm is designed using results of Dickson, Khare-Wintenberger and Faber on the classification, up to conjugation, of the finite subgroups of $\PGL_2(\overline{\F}_\ell)$. We characterize each possible case giving a precise description and algorithms to deal with it. In particular, we give a new approach and a construction to deal with irreducible representations with projective image isomorphic to either the symmetric group on $4$ elements or the alternating group on $4$ or $5$ elements.

Un nombre naturel n est dit congruent si il est l’aire d’un triangle rectangle dont tous les cotés sont de longueur rationnelle. Le problème des nombres congruents consiste à déterminer quels nombres sont congruents. Cette question, connue depuis plus de 1000 ans, est toujours ouverte. Elle est liée à la théorie des courbes elliptiques, car le naturel n est congruent si et seulement si la courbe elliptique y²=x³-n²x possède un point rationnel d’ordre infini. Ce lien entre les nombres congruents et les courbes elliptiques permet d’accéder à des techniques venant de la géométrie algébrique. Une de ces méthodes est le concept des matrices de Monsky qui peuvent être utilisées pour calculer la taille du groupe de 2-Selmer de la courbe elliptique y²=x³-n²x. On peut utiliser ces matrices afin de trouver de nouvelles familles infinies de nombres non-congruents. Cette relation introduit aussi des généralisations possibles au problème des nombres congruents. Par exemple, nous pouvons considérer le problème des nombres θ-congruent qui étudie des triangles avec un avec un angle fixé de taille θ au lieu de seulement des triangles rectangles. Ce problème est aussi lié aux courbes elliptiques et le concept des matrices de Monsky peut être étendu à ce cas. En fait, les matrices de Monsky peuvent être généralisées à n’importe quelle courbe elliptique qui possède une forme de Legendre sur les rationnels. Le but de ce mémoire est de construire une telle généralisation puis de l’appliquer à des problèmes de géométrie arithmétique afin de reprouver efficacement de vieux résultats ainsi que d’en trouver de nouveaux. / A positive integer n is said to be congruent if it is the area of a right triangle whose sides are all of rational length. The task of finding which integers are congruent is an old and famous yet still open question in arithmetic geometry called the congruent number problem. It is linked to the theory of elliptic curves as the integer n is congruent if and only if the elliptic curve y²=x³-n²x has a rational point of infinite order. The link between congruent numbers and elliptic curves enables the application of techniques from algebraic geometry to study the problem. One of these methods is the concept of Monsky matrices that can be used to calculate the size of the 2-Selmer group of the elliptic curve y²=x³-n²x. One can use these matrices in order to find new infinite families of non-congruent numbers. The connection to elliptic curves also introduces generalizations to the congruent number problem. For example, one may consider the θ-congruent number problem which studies triangles with a fixed angle of θ instead of only right triangles. This problem is also related to elliptic curves and the concept of Monsky matrices can be generalized to it. In fact, Monsky matrices can be generalized to any elliptic curve that has a Legendre form over the rationals. The goal of this thesis is to construct such a generalization and then to apply it to relevant problems in arithmetic geometry to efficiently reprove old results and find new ones.

Le présent mémoire traite une variation de la mesure de Mahler où l'intégrale de définition est réalisée sur un tore plus général. Notre travail est basé sur une famille de polynômes tempérée originellement étudiée par Boyd, P_k (x, y) = x + 1/x + y + 1/y + k avec k ∈ R_{>4}. Pour le k = 4 cas, nous utilisons des valeurs spéciales du dilogarithme de Bloch-Wigner pour obtenir la mesure de Mahler de P_4 sur un tore arbitraire (T_ {a, b})^2 = {(x, y) ∈ C* X C* : | x | = a, | y | = b } avec a, b ∈ R_{> 0}. Ensuite, nous établissons une relation entre la mesure de Mahler de P_8 sur un tore (T_ {a, √a} )^2 et sa mesure de Mahler standard. La combinaison de cette relation avec des résultats de Lalin, Rogers et Zudilin conduit à une formule impliquant les mesures de Mahler généralisées de ce polynôme données en termes de L' (E, 0). Au final, nous proposons une stratégie pour prouver des résultats similaires dans le cas général k> 4 sur (T_ {a, b})^2 avec certaines restrictions sur a, b. / In this thesis we consider a variation of the Mahler measure where the defining integral is performed over a more general torus. Our work is based on a tempered family of polynomials originally studied by Boyd, Boyd P_k (x, y) = x + 1/x + y + 1/y + k with k ∈ R_{>4}. For the k = 4 case we use special values of the Bloch-Wigner dilogarithm to obtain the Mahler measure of P_4 over an arbitrary torus (T_ {a, b})^2 = {(x, y) ∈ C* X C* : | x | = a, | y | = b } with a, b ∈ R_{> 0}. Next we establish a relation between the Mahler measure of P_8 over a torus(T_ {a, √a} )^2 and its standard Mahler measure. The combination of this relation with results due to Lalin, Rogers, and Zudilin leads to a formula involving the generalized Mahler measure of this polynomial given in terms of L'(E, 0). In the end, we propose a strategy to prove some similar results for the general case k > 4 over (T_ {a, b})^2 with some restrictions on a, b.

Les protocoles de cryptographie asymétrique nécessitent des calculs arithmétiques dans différentes structures mathématiques. Un grand nombre de ces protocoles requièrent en particulier des calculs dans des structures finies, rendant indispensable une arithmétique modulaire efficace. Ces opérations modulaires sont composées d'opérations multiprécision entre opérandes de tailles suffisamment grandes pour garantir le niveau de sécurité requis (de plusieurs centaines à plusieurs milliers de bits). Enfin, certains protocoles nécessitent des opérations arithmétiques dans le groupe des points d'une courbe elliptique, opérations elles-mêmes composées d'opérations dans le corps de définition de la courbe. Les tailles de clés utilisées par les protocoles rendent ainsi les opérations arithmétiques coûteuses en temps de calcul. Par ailleurs, les architectures grand public actuelles embarquent plusieurs unités de calcul, réparties sur les processeurs et éventuellement sur les cartes graphiques. Ces ressources sont aujourd'hui facilement exploitables grâce à des interfaces de programmation parallèle comme OpenMP ou CUDA. Cette thèse s'articule autour de la définition d'opérateurs arithmétiques parallèles permettant de tirer parti de l'ensemble des ressources de calcul, en particulier sur des architectures multicœur à mémoire partagée. La parallélisation au niveau arithmétique le plus bas permet des gains modérés en termes temps de calcul, car les tailles des opérandes ne sont pas suffisamment importantes pour que l'intensité arithmétique des calculs masque les latences dues au parallélisme. Nous proposons donc des algorithmes permettant une parallélisation aux niveaux arithmétiques supérieurs : algorithmes parallèles pour la multiplication modulaire et pour la multiplication scalaire sur les courbes elliptiques. Pour la multiplication modulaire, nous étudions en particulier plusieurs ordonnancements des calculs au niveau de l'arithmétique modulaire et proposons également une parallélisation à deux niveaux : modulaire et multiprécision. Ce parallélisme à plus gros grain permet en pratique des gains plus conséquents en temps de calcul. Nous proposons également une parallélisation sur processeur graphique d'opérations modulaires et d'opérations dans le groupe des points d'une courbe elliptique. Enfin, nous présentons une méthode pour optimiser la multiplication scalaire sur les courbes elliptiques pour de petits scalaires.

Cette thèse porte sur l'étude des points entiers et rationnels de certaines courbes et variétés modulaires. Après une brève introduction décrivant les motivations et le cadre de ce genre d'études ainsi que les résultats principaux de la thèse, le manuscrit se divise en trois parties. Le premier chapitre s'intéresse aux Q-courbes, et aux morphismes Gal(Q/Q) -> PGL2(Fp) qu'on peut leur associer pour tout p premier. Nous montrons que sous de bonnes hypothèses, pour p assez grand par rapport au discriminant du corps de définition de la Q-courbe, ce morphisme est surjectif, ce qui résout un cas particulier du problème d'uniformité de Serre (toujours ouvert en général). Les outils principaux du chapitre sont la méthode de Mazur (basée ici sur des résultats d'Ellenberg), la méthode de Runge et des théorèmes d'isogénie, suivant la structure de preuve de Bilu et Parent. Le second chapitre consiste en des estimations analytiques de sommes pondérées de valeurs de fonctions L de formes modulaires, dans l'esprit de techniques développées par Duke et Ellenberg. La motivation de départ d'un tel résultat est l'application de la méthode de Mazur dans le premier chapitre. Le troisième chapitre est consacré à la recherche de généralisations de la méthode de Runge pour des variétés de dimension supérieure. Nous y redémontrons un résultat de Levin inspiré de cette méthode, avant d'en prouver une forme assouplie dite "de Runge tubulaire", plus largement applicable. Dans l'optique de recherche de points entiers de variétés modulaires, nous en donnons enfin un exemple d'utilisation à la réduction d'une surface abélienne en produit de courbes elliptiques. / This thesis concerns the study of integral and rational points on some modular curves and varieties. After a brief introduction which describes the motivation and the setting of this topic as well as the main results of this thesis, the manuscript follows a threefold development. The first chapter focuses on Q-curves, and on the morphisms Gal(Q/Q) -> PGL2(Fp) that we can build with a Q-curve for every prime p. We prove that, under good hypotheses, for p large enough with respect to the discriminant of the definition field of the Q-curve, such a morphism is surjective, which solves a particular case of Serre's uniformity problem (still open in general). The main tools of the chapter are Mazur's method (based here on results of Ellenberg), Runge's method, and isogeny theorems, following the strategy of Bilu and Parent. The second chapter covers analytic estimates of weighted sums of L-function values of modular forms, in the fashion of techniques designed by Duke and Ellenberg. The initial goal of such a result is the application of Mazur's method in the first chapter. The third chapter is devoted to the search for generalisations of Runge's method for higherdimensional varieties. Here we prove anew a result of Levin inspired by this method, before proving an enhanced version called "tubular Runge", more generally applicable. In the perspective of studying integral points of modular varieties, we finally give an example of application of this theorem to the reduction of an abelian surface in a product of elliptic curves.

Cette thèse étudie le problème de minoration de la hauteur canonique sur les courbeselliptiques. Son résultat diophantien principal utilise des méthodes d’intersectionarithmétique pour retrouver un résultat de Laurent, qui démontrait la conjecturede Lehmer pour les courbes elliptiques à multiplications complexes à un exposant" près, tout en explicitant complètement sa dépendance en divers paramètres liésà la courbe elliptique ; une telle démarche peut être motivée par la conjecture deLang, qui présage une minoration possible de la hauteur canonique proportionnelle,essentiellement, à la hauteur de Faltings de la courbe.Notre dissertation commence toutefois par une partie dédiée à l’explicitation duthéorème de densité de Chebotarev, qui reprend les grandes lignes d’un travail deLagarias et Odlyzko, et s’avère être cruciale dans notre approche du problème deLehmer elliptique. On obtient également des majorations des zéros de Siegel et de lanorme du plus petit idéal premier entrant en jeu dans le théorème de Chebotarev. / In this thesis we consider the problem of lower bounds for the canonical height onelliptic curves, aiming for the conjecture of Lehmer. Our main diophantine result isan explicit version of a theorem of Laurent (who proved this conjecture for ellipticcurves with CM up to a " exponent) using arithmetic intersection, enlightening thedependence with parameters linked to the elliptic curve ; such a result can be motivatedby the conjecture of Lang, hoping for a lower bound proportional to, roughly,the Faltings height of the curve.Nevertheless, our dissertation begins with a part dedicated to a completely explicitversion of the density theorem of Chebotarev, along the lines of a previous workdue to Lagarias and Odlyzko, which will be crucial to investigate the elliptic Lehmerproblem. We also obtain upper bounds for Siegel zeros, and for the smallest primeideal whose Frobenius is in a fixed conjugacy class.