Le problème du logarithme discret sur courbes elliptiques est à la base de nombreux protocoles cryptographiques, dans la mesure où on ne connaît jusqu'à présent aucun algorithme permettant de l'attaquer efficacement. Du point de vue de la cryptanalyse, certaines approches basées sur des méthodes de calcul d'indices, et s'appuyant sur la résolution de systèmes pour la recherche de relations, sont toutefois prometteuses. La première partie de cette thèse est consacrée aux techniques de calcul de bases de Gröbner appliquées à la résolution de systèmes polynomiaux. Après une description détaillée des algorithmes F4 et F5 de Faugère considérés comme les plus performants actuellement, on présente et analyse une variante de l'algorithme F4, particulièrement utile pour la résolution de nombreux systèmes "similaires". Plusieurs exemples d'applications de ce nouvel algorithme sont donnés à la fois au domaine du calcul formel et de la cryptographie, montrant que pour certaines attaques algébriques, cette variante est plus efficace que F4 et F5. Etant munis de ces nouveaux outils, on étudie dans la seconde partie le problème du logarithme discret sur courbes algébriques. Après une présentation rapide des attaques existantes sur ce type de courbes dans un contexte général, on s'intéresse plus particulièrement aux courbes elliptiques définies sur des extensions de corps finis. On donne ainsi une description complète des techniques GHS, puis des méthodes d'attaques par décomposition introduites par Gaudry et Diem. On présente notamment des variantes de ces méthodes de décompositions permettant, grâce aux outils introduits en première partie de cette thèse, de fragiliser le DLP (et des problèmes reliés) sur courbes elliptiques sur une gamme plus large d'extensions de corps finis. Enfin, une nouvelle approche combinant les attaques par recouvrement ainsi que les méthodes de décompositions est proposée : cette attaque permet entre autres de calculer complètement le logarithme discret sur des courbes elliptiques définies sur des extensions sextiques de taille jamais atteinte auparavant.

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 aux systèmes cryptographiques précédemment employés tels que RSA (Rivest-Shamir-Adleman). Les travaux qui suivent décrivent dans un premier temps l'implantation efficace et sécurisée de la cryptographie à base de courbes elliptiques sur des composants embarqués, en particulier 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 à observer le comportement d'un composant pendant qu'il manipule une valeur secrète pour en déduire de l'information sur celle-ci, et les analyses par faute dans lesquelles un attaquant peut perturber un composant dans le même but.Dans la seconde partie de ce mémoire de thèse, nous étudions ces attaques et leurs implications 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 en particulier proposées. Une étude spécifique de certaines attaques appliquées à l'algorithme de chiffrement par bloc AES est également présentée. / Elliptic curve based cryptosystems are nowadays increasingly used in protocols involving public-key cryptography. This is particularly true in the context of embedded devices which is subject to strong cost, resources, and efficiency constraints, since elliptic curve cryptography requires significantly smaller key sizes compared to other commonly used cryptosystems such as RSA.The following study focuses in a first time on secure and efficient implementation of elliptic curve cryptography in embedded devices, especially smart cards. Designing secure implementations requires to take into account physical attacks which can target embedded devices. These attacks include in particular side-channel analysis which may infer information on a secret key manipulated by a component by monitoring how it interacts with its environment, and fault analysis in which an adversary can disturb the normal functioning of a device in the same goal.In the second part of this thesis, we study these attacks and their impact on the implementation of the most used public-key cryptosystems. In particular, we propose new analysis techniques and new countermeasures for these cryptosystems, together with specific attacks on the AES block cipher.

Les protocoles de cryptographie asymétrique nécessitent des calculs arithmétiques dans différentes structures mathématiques de grandes tailles. Pour garantir une sécurité suffisante, ces tailles varient de plusieurs centaines à plusieurs milliers de bits et rendent les opérations arithmétiques coûteuses en temps de calcul. D'autre part, 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. Dans cette thèse, nous étudions la parallélisation d'opérateurs à différents niveaux arithmétique. Nous nous intéressons plus particulièrement à la multiplication entre entiers multiprécision ; à la multiplication modulaire ; et enfin à la multiplication scalaire sur les courbes elliptiques.Dans chacun des cas, nous étudions différents ordonnancements des calculs permettant d'obtenir les meilleures performances. Nous proposons également une bibliothèque permettant la parallélisation sur processeur graphique d'instances d'opérations modulaires et d'opérations sur les courbes elliptiques. Enfin, nous proposons une méthode d'optimisation automatique de la multiplication scalaire sur les courbes elliptiques pour de petits scalaires permettant l'élimination des sous-expressions communes apparaissant dans la formule et l'application systématique de transformations arithmétiques. / Asymmetric cryptography requires some computations in large size finite mathematical structures. To insure the required security, these sizes range from several hundred to several thousand of bits. Mathematical operations are thus expansive in terms of computation time. Otherwise, current architectures have several computing units, which are distribued over the processors and GPU and easily implementable using dedicated languages as OpenMP or CUDA. In this dissertation, we investigate the parallelization of some operators for different arithmetical levels.In particular, our research focuse on parallel multiprecision and modular multiplications, and the parallelization of scalar multiplication over elliptic curves. We also propose a library to parallelize modular operations and elliptic curves operations. Finally, we present a method which allow to optimize scalar elliptic curve multiplication for small scalars.

Cette thèse se concentre sur les problèmes liés à l’authentification dans la technologie RFID. Cette technologie est l’une des technologies les plus prometteuses dans le domaine de l’informatique ubiquitaire, elle est souvent désignée comme la prochaine révolution après Internet. Cependant, à cause des ressources très limitées en termes de calcul, mémoire et énergie sur les étiquettes RFID, les algorithmes classiques de sécurité ne peuvent pas être implémentés sur les étiquettes à bas coût rendant ainsi la sécurité et la vie privée un important sujet de recherche aujourd’hui. Dans un premier temps, nous étudions le passage à l’échelle dans les systèmes RFID à bas coût en développant un module pour ns-3 qui simule le standard EPC Class 1 Generation 2 pour établir un cadre stricte pour l’identification sécurisée des RFID à bas coût, ce qui nous conduit à l’utilisation de la cryptographie à clés publiques. Ensuite, nous proposons un protocole d’authentification basé sur une adaptation que nous avons introduit sur le célèbre cryptosystème NTRU. Ce protocole est spécialement conçu pour les RFID à bas coût comme les étiquettes n’implémentent que des opérations simples (xor, décalages, addition) et il garantit le passage à l’échelle. Enfin, nous considérons l’identification à divulgation nulle de connaissance, ce type d’approches est très utile dans de nombreuses applications RFID. Nous proposons deux protocoles à divulgation nulle de connaissance basés sur cryptoGPS et cryptoGPS randomisé. Ces approches consistent à stocker sur le serveur des coupons pré-calculés, ainsi la sécurité et la vie privée sont mieux supportées que dans les autres approches de ce type / This thesis focuses on issues related to authentication in low-cost radio frequency identification technology, more commonly referred to as RFID. This technology it is often referred to as the next technological revolution after the Internet. However, due to the very limited resources in terms of computation, memory and energy on RFID tags, conventional security algorithms cannot be implemented on low-cost RFID tags making security and privacy an important research subject today. First of all, we investigate the scalability in low-cost RFID systems by developing a ns-3 module to simulate the universal low-cost RFID standard EPC Class-1 Generation-2 in order to establish a strict framework for secure identification in low-cost RFID systems. We show that, the symmetrical key cryptography is excluded from being used in any scalable low-cost RFID standard. Then, we propose a scalable authentification protocol based on our adaptation of the famous public key cryptosystem NTRU. This protocol is specially designed for low-cost RFID systems, it can be efficiently implemented into low-cost tags. Finally, we consider the zero-knowledge identification i.e. when the no secret sharing between the tag and the reader is needed. Such identification approaches are very helpful in many RFID applications when the tag changes constantly the field of administration. We propose two lightweight zero-knowledge identification approaches based on GPS and randomized GPS schemes. The proposed approaches consist in storing in the back-end precomputed values in the form of coupons. So, the GPS-based variant can be private and the number of coupons can be much higher than in other approaches thus leading to higher resistance to denial of service attacks for cheaper tags

L'application d'Abel-Jacobi fait le lien entre la forme de Weierstrass d'une courbe elliptique définie sur C et le tore complexe qui lui est associé. Il est possible de la calculer en un nombre d'opérations quasi-linéaire en la précision voulue, c'est à dire en temps O(M(P) log P). Son inverse est donné par la fonction p de Weierstrass, qui s'exprime en fonction de thêta, une fonction importante en théorie des nombres. L'algorithme naturel d'évaluation de thêta nécessite O(M(P) sqrt(P)) opérations, mais certaines valeurs (les thêta-constantes) peuvent être calculées en O(M(P) log P) opérations en exploitant les liens avec la moyenne arithmético-géométrique (AGM). Dans ce manuscrit, nous généralisons cet algorithme afin de calculer thêta en O(M(P) log P). Nous exhibons une fonction F qui a des propriétés similaires à l'AGM. D'une façon similaire à l'algorithme pour les thêta-constantes, nous pouvons alors utiliser la méthode de Newton pour calculer la valeur de thêta. Nous avons implanté cet algorithme, qui est plus rapide que la méthode naïve pour des précisions supérieures à 300 000 chiffres décimaux. Nous montrons comment généraliser cet algorithme en genre supérieur, et en particulier comment généraliser la fonction F. En genre 2, nous sommes parvenus à prouver que la même méthode mène à un algorithme qui évalue thêta en O(M(P) log P) opérations ; la même complexité s'applique aussi à l'application d'Abel-Jacobi. Cet algorithme est plus rapide que la méthode naïve pour des précisions plus faibles qu'en genre 1, de l'ordre de 3 000 chiffres décimaux. Nous esquissons également des pistes pour obtenir la même complexité en genre quelconque. Enfin, nous exhibons un nouvel algorithme permettant de calculer une isogénie de courbes elliptiques de noyau donné. Cet algorithme utilise l'application d'Abel-Jacobi, car il est facile d'évaluer l'isogénie sur le tore ; il est sans doute possible de le généraliser au genre supérieur / The Abel-Jacobi map links the short Weierstrass form of a complex elliptic curve to the complex torus associated to it. One can compute it with a number of operations which is quasi-linear in the target precision, i.e. in time O(M(P) log P). Its inverse is given by Weierstrass's p-function, which can be written as a function of theta, an important function in number theory. The natural algorithm for evaluating theta requires O(M(P) sqrt(P)) operations, but some values (the theta-constants) can be computed in O(M(P) log P) operations by exploiting the links with the arithmetico-geometric mean (AGM). In this manuscript, we generalize this algorithm in order to compute theta in O(M(P) log P). We give a function F which has similar properties to the AGM. As with the algorithm for theta-constants, we can then use Newton's method to compute the value of theta. We implemented this algorithm, which is faster than the naive method for precisions larger than 300,000 decimal digits. We then study the generalization of this algorithm in higher genus, and in particular how to generalize the F function. In genus 2, we managed to prove that the same method leads to a O(M(P) log P) algorithm for theta; the same complexity applies to the Abel-Jacobi map. This algorithm is faster than the naive method for precisions smaller than in genus 1, of about 3,000 decimal digits. We also outline a way one could reach the same complexity in any genus. Finally, we study a new algorithm which computes an isogeny of elliptic curves with given kernel. This algorithm uses the Abel-Jacobi map because it is easy to evaluate the isogeny on the complex torus; this algorithm may be generalizable to higher genera

L'objet de cette thèse est l'étude de diverses primitives cryptographiques utiles dans des protocoles Diffie-Hellman. Nous étudions tout d'abord les protocoles Diffie-Helmman sur des structures commutatives ou non. Nous en proposons une formulation unifiée et mettons en évidence les différents problèmes difficiles associés dans les deux contextes. La première partie est consacrée à l'étude de pseudo-paramétrisations de courbes algébriques en temps constant déterministe, avec application aux fonctions de hachage vers les courbes. Les propriétés des courbes algébriques en font une structure de choix pour l'instanciation de protocoles reposant sur le problème Diffie-Hellman. En particulier, ces protocoles utilisent des fonctions qui hachent directement un message vers la courbe. Nous proposons de nouvelles fonctions d'encodage vers les courbes elliptiques et pour de larges classes de fonctions hyperelliptiques. Nous montrons ensuite comment l'étude de la géométrie des tangentes aux points d'inflexion des courbes elliptiques permet d'unifier les fonctions proposées tant dans la littérature que dans cette thèse. Dans la troisième partie, nous nous intéressons à une nouvelle instanciation de l'échange Diffie-Hellman. Elle repose sur la difficulté de résoudre un problème de factorisation dans un anneau de polynômes non-commutatifs. Nous montrons comment un problème de décomposition Diffie-Hellman sur un groupe non-commutatif peut se ramener à un simple problème d'algèbre linéaire pourvu que les éléments du groupe admettent une représentation par des matrices. Bien qu'elle ne soit pas applicable directement au cas des polynômes tordus puisqu'ils n'ont pas d'inverse, nous profitons de l'existence d'une notion de divisibilité pour contourner cette difficulté. Finalement, nous montrons qu'il est possible de résoudre le problème Diffie-Hellman sur les polynômes tordus avec complexité polynomiale. / In this thesis, we study several cryptographic primitives of use in Diffie-Hellman like protocols. We first study Diffie-Hellman protocols on commutative or noncommutative structures. We propose an unified wording of such protocols and bring out on which supposedly hard problem both constructions rely on. The first part is devoted to the study of pseudo-parameterization of algebraic curves in deterministic constant time, with application to hash function into curves. Algebraic curves are indeed particularly interesting for Diffie-Hellman like protocols. These protocols often use hash functions which directly hash into the curve. We propose new encoding functions toward elliptic curves and toward large classes of hyperelliptic curves. We then show how the study of the geometry of flex tangent of elliptic curves unifies the encoding functions as proposed in the litterature and in this thesis. In the third part, we are interested in a new instantiation of the Diffie-Hellman key exchange. It relies on the difficulty of factoring in a non-commutative polynomial ring. We show how to reduce a Diffie-Hellman decomposition problem over a noncommutative group to a simple linear algebra problem, provided that group elements can be represented by matrices. Although this is not directly relevant to the skew polynomial ring because they have no inverse, we use the divisibility to circumvent this difficulty. Finally, we show it's possible to solve the Diffie-Hellman problem on skew polynomials with polynomial complexity.

No description available.

No description available.

Cette thèse porte sur des questions liées à la conjecture de parité. On démontre la conjecture de p-parité pour un certain twist d'une courbe elliptique sur un corps local. On en déduit des résultats globaux d'invariance de la conjecture de p-parité (pour une courbe elliptique) par certaines extensions. Avec l'objectif de généraliser les résultats précédents, on démontre une formule pour les signes locaux des représentations essentiellement symplectiques et modérément ramifiées du groupe de Weil. Cette formule généralise celle, déjà connue, pour les courbes elliptiques ayant potentiellement bonne réduction. Finalement, on fait un premier pas vers la généralisation escomptée en comparant les nombres de Tamagawa et les constantes de régulation pour certains prémotifs.

La cryptographie basée sur les courbes elliptiques (ECC) est de plus en plus utilisée dans les cryptosystèmes à clé publique, notamment parce qu'à niveau de sécurité équivalent, la taille nécessaire des clés ECC est nettement inférieure à ce que son prédécesseur, le RSA, requiert. L'ECC conduit donc à implanter des circuits plus compacts que pour le RSA, ce qui indique qu'elle est plus adaptée aux circuits fortement contraints (cartes à puce, etc.). L'ECC a d'ailleurs bénéficié de l'amélioration continue de l'arithmétique (des ordinateurs et des courbes) ces dernières années, ce qui lui permet de se positionner comme un remplaçant crédible au RSA dans le monde industriel. Il est vrai qu'un concepteur de circuits cryptographiques doit chercher à améliorer les performances de son cryptosystème, mais il doit également protéger ce dernier contre des attaques physiques pouvant compromettre sa sécurité. En effet, des attaques efficaces dites "par observation" et "par perturbation" ont été mises en évidence. Le concepteur de circuits cryptographiques doit donc implanter des parades à ces attaques, également appelées contre-mesures. Cependant, l'ajout de ces contre-mesures ne doit pas d'une part ajouter de nouvelles vulnérabilités au cryptosystème, et d'autre part diminuer drastiquement ses performances. Ces travaux de thése proposent une nouvelle architecture d'unité arithmétique pour l'ECC. Il se trouve que les performances de cette derniére sont meilleures que la plupart de celles présentes dans la littérature. Ceci est essentiellement dû à l'utilisation d'une représentation redondante des nombres, appelée repréesentation à retenues signées. Le second r'ésultat principal de ces travaux provient de la protection de cette unité contre les attaques par observation à l'aide de l'état de l'art : ce faisant, nous proposons là encore la solution la plus performante de la littérature. Enfin, nous avons exploré la possibilié de protéger notre circuit contre les attaques par perturbation à l'aide du principe de la préservation de la parité. Cette dernière contribution amène des réesultats encourageants