Le problème du logarithme discret est une brique fondamentale de nombreux protocoles de communication sécurisée. Son instantiation sur les courbes elliptiques a permis, grâce à la petite taille des opérandes considérées, le déploiement de primitives asymétriques efficaces sur des systèmes embarqués. De nos jours, les cryptosystèmes utilisant des courbes elliptiques, aussi appelées courbes de genre 1, sont déjà intensément utilisés: il est donc impératif de savoir estimer précisément la robustesse de ces systèmes. L'existence d'attaques mathématiques permettant de transférer un problème de logarithme discret elliptique dans un autre type de courbe algébrique, et la nouvelle compétitivité des courbes de genre 2 imposent de ne pas se restreindre à la seule compréhension du problème sur les courbes elliptiques.Dans cette optique, le sujet de cette thèse se concentre sur les attaques algébriques sur les courbes de genre supérieur à 1. Les algorithmes de type calcul d'indice sont en général préférés pour ce genre d'attaque. Ces algorithmes se déroulent en deux phases: la première, appelée phase de récolte, dispose de nombreuses modélisations algébriques dépendant de la courbe ciblée. Le problème sous-jacent revient à savoir décomposer efficacement des points dans la variété Jacobienne de la courbe en somme d'autres points.On propose dans un premier temps une approche par crible pour la phase de récolte, s'adaptant à tous les types de courbes de genre plus grand que 1, et qui est expérimentalement plus efficaces que les méthodes de l'état de l'art. Cette méthode a l'avantage de proposer une implémentation immédiate, et évite les problèmes usuels de gestion des relations obtenues.Ensuite, on se concentre les variantes de calcul d'indice appelées attaques par décomposition, et ciblant les courbes définies sur des extensions de corps. Dans cette situation, la phase de récolte est effectuée par résolution de nombreux systèmes polynomiaux multivariés. On propose une nouvelle approche de modélisation de ces systèmes, en généralisant la notion de polynômes de sommation elliptique à tout les types de courbes algébriques. Pour cela on fait appel à la théorie de l'élimination, tandis que l'aspect pratique est gérée par des méthodes de bases de Gröbner.Enfin, on fournit des algorithmes d'amélioration du processus de résolution des systèmes lorsque la caractéristique du corps de base est paire. Par le biais d'une présentation théorique générale et en utilisant des méthodes de bases de Gröbner, on propose une analyse fine de l'impact de ces améliorations sur la complexité de la résolution. Cette analyse fine, ainsi qu'une implémentation dédiée, nous permettent d'attaquer une courbe de genre 2 satisfaisant des bornes de sécurité réaliste en pratique. / The discrete logarithm problem is a fundamental brick for several protocols for secured communications. Its instantiation over elliptic curves allows the deployment of efficient asymmetric primitives in embedded systems, because of the small size of the parameters considered. Nowadays, elliptic curves cryptosystems are already widely used: it is therefore crucial to precisely understand the hardness of such systems. Because of the existence of mathematical attacks enabling the transfer from an elliptic curve discrete logarithm problem to another algebraic curve, and the upcoming competitivity of genus 2 curves, it is mandatory to study the problem not only for elliptic curves, but for the other curves as well.In this way, this thesis focuses on the algebraic attacks over curves with genus greater than 1. The index calculus family of algorithms is in general preferred for this kind of attacks. Those algorithms run in two phases: the first, called harvesting phase, can be modelled by different algebraic approaches, depending in the targetted curve. The underlying problem amounts to knowing how to decompose efficiently points in the Jacobian variety of the curve into sums of other points.First, we propose a sieving approach to the harvesting, that can be adated to any type of curves with genus greater than 1, and which turns to be experimentally more efficient than state-of-the-art's methods. Moreover, our method allows a close-to-immediate implementation, and avoid complications coming from relations management.Our second focus is on a variant of index calculus called decomposition attack, targetting curves defined over field extensions. In this situation, harvesting is done by solving numerous multivariate polynomial systems. We propose a new approach to this modelling by generalizing the notion of elliptic summation polynomias to any type of algebraic curves. This uses elimination theory, and the computational aspect is handled by Gröbner bases methods.Third, we give algorithms to improve the solving process of the systems arising from a decomposition attacks when the characteristic of the base field is even. By mean of a general theoretical presentation, and using Gröbner bases methods, we give a sharp analysis of the impact of such improvement on the complexity of the resolution process. This sharp analysis together with a dedicated implementation allows us to attack a genus 2 curve satisfying realistic security parameters.

La cryptographie à base de codes correcteurs, introduite par Robert McEliece en 1978, est un candidat potentiel au remplacement des primitives asymétriques vulnérables à l'émergence d'un ordinateur quantique. Elle possède de plus une sécurité classique éprouvée depuis plus de trente ans, et permet des fonctions de chiffrement très rapides. Son défaut majeur réside dans la taille des clefs publiques. Pour cette raison, plusieurs variantes du schéma de McEliece pour lesquelles les clefs sont plus aisées à stocker ont été proposées ces dernières années. Dans cette thèse, nous nous intéressons aux variantes utilisant soit des codes alternants avec symétrie, soit des codes de Goppa sauvages. Nous étudions leur résistance aux attaques algébriques et exhibons des faiblesses parfois fatales. Dans chaque cas, nous révélons l'existence de structures algébriques cachées qui nous permettent de décrire la clef secrète par un système non-linéaire d'équations en un nombre de variables très inférieur aux modélisations antérieures. Sa résolution par base de Gröbner nous permet de trouver la clef secrète pour de nombreuses instances hors de portée jusqu'à présent et proposés pour un usage à des fins cryptographiques. Dans le cas des codes alternants avec symétrie, nous montrons une vulnérabilité plus fondamentale du processus de réduction de taille de la clef.Pour un déploiement à l'échelle industrielle de la cryptographie à base de codes correcteurs, il est nécessaire d'en évaluer la résistance aux attaques physiques, qui visent le matériel exécutant les primitives. Nous décrivons dans cette optique un algorithme de déchiffrement McEliece plus résistant que l'état de l'art. / Code-based cryptography, introduced by Robert McEliece in 1978, is a potential candidate to replace the asymetric primitives which are threatened by quantum computers. More generral, it has been considered secure for more than thirty years, and allow very vast encryption primitives. Its major drawback lies in the size of the public keys. For this reason, several variants of the original McEliece scheme with keys easier to store were proposed in the last years.In this thesis, we are interested in variants using alternant codes with symmetries and wild Goppa codes. We study their resistance to algebraic attacks, and reveal sometimes fatal weaknesses. In each case, we show the existence of hidden algebraic structures allowing to describe the secret key with non-linear systems of multivariate equations containing fewer variables then in the previous modellings. Their resolutions with Gröbner bases allow to find the secret keys for numerous instances out of reach until now and proposed for cryptographic purposes. For the alternant codes with symmetries, we show a more fondamental vulnerability of the key size reduction process. Prior to an industrial deployment, it is necessary to evaluate the resistance to physical attacks, which target device executing a primitive. To this purpose, we describe a decryption algorithm of McEliece more resistant than the state-of-the-art.Code-based cryptography, introduced by Robert McEliece in 1978, is a potential candidate to replace the asymetric primitives which are threatened by quantum computers. More generral, it has been considered secure for more than thirty years, and allow very vast encryption primitives. Its major drawback lies in the size of the public keys. For this reason, several variants of the original McEliece scheme with keys easier to store were proposed in the last years.In this thesis, we are interested in variants using alternant codes with symmetries and wild Goppa codes. We study their resistance to algebraic attacks, and reveal sometimes fatal weaknesses. In each case, we show the existence of hidden algebraic structures allowing to describe the secret key with non-linear systems of multivariate equations containing fewer variables then in the previous modellings. Their resolutions with Gröbner bases allow to find the secret keys for numerous instances out of reach until now and proposed for cryptographic purposes. For the alternant codes with symmetries, we show a more fondamental vulnerability of the key size reduction process. Prior to an industrial deployment, it is necessary to evaluate the resistance to physical attacks, which target device executing a primitive. To this purpose, we describe a decryption algorithm of McEliece more resistant than the state-of-the-art.

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.