La cryptographie et la problématique de la sécurité informatique deviennent des sujets de plus en plus prépondérants dans un monde hyper connecté et souvent embarqué. La cryptographie est un domaine dont l'objectif principal est de ''protéger'' l'information, de la rendre inintelligible à ceux ou à celles à qui elle n'est pas destinée. La cryptographie repose sur des algorithmes solides qui s'appuient eux-mêmes sur des problèmes mathématiques réputés difficiles (logarithme discret, factorisation des grands nombres etc). Bien qu'il soit complexe, sur papier, d'attaquer ces systèmes de protection, l'implantation matérielle ou logicielle, si elle est négligée (non protégée contre les attaques physiques), peut apporter à des entités malveillantes des renseignements complémentaires (temps d’exécution, consommation d'énergie etc) : on parle de canaux cachés ou de canaux auxiliaires. Nous avons, dans cette thèse, étudié deux aspects. Le premier est l'apport de nouvelles idées algorithmiques pour le calcul dans les corps finis binaires GF(2^m) utilisés dans le cadre de la cryptographie sur courbes elliptiques. Nous avons proposé deux nouvelles représentations des éléments du corps : la base normale permutée et le Phi-RNS. Ces deux nouveautés algorithmiques ont fait l'objet d'implémentations matérielles en FPGA dans laquelle nous montrons que ces premières, sous certaines conditions, apportent un meilleur compromis temps-surface. Le deuxième aspect est la protection d'un crypto-processeur face à une attaque par canaux cachés (dite attaque par «templates»). Nous avons implémenté, en VHDL, un crypto-processeur complet et nous y avons exécuté, en parallèle, des algorithmes de «double-and-add» et «halve-and-add» afin d'accélérer le calcul de la multiplication scalaire et de rendre, de par ce même parallélisme, notre crypto-processeur moins vulnérable face à certaines attaques par canaux auxiliaires. Nous montrons que le parallélisme seul des calculs ne suffira pas et qu'il faudra marier le parallélisme à des méthodes plus conventionnelles pour assurer, à l'implémentation, une sécurité raisonnable. / Cryptography and security market is growing up at an annual rate of 17 % according to some recent studies. Cryptography is known to be the science of secret. It is based on mathematical hard problems as integers factorization, the well-known discrete logarithm problem. Although those problems are trusted, software or hardware implementations of cryptographic algorithms can suffer from inherent weaknesses. Execution time, power consumption (...) can differ depending on secret informations such as the secret key. Because of that, some malicious attacks could be used to exploit these weak points and therefore can be used to break the whole crypto-system. In this thesis, we are interested in protecting our physical device from the so called side channel attacks as well as interested in proposing new GF(2^m) multiplication algorithms used over elliptic curves cryptography. As a protection, we first thought that parallel scalar multiplication (using halve-and-add and double-and-add algorithms both executed at the same time) would be a great countermeasure against template attacks. We showed that it was not the case and that parallelism could not be used as protection by itself : it had to be combined with more conventional countermeasures. We also proposed two new GF(2^m) representations we respectively named permuted normal basis (PNB) and Phi-RNS. Those two representations, under some requirements, can offer a great time-area trade-off on FPGAs.

Cette thèse est composée de deux parties indépendantes. Dans la première, on s'intéresse à la résolution de certaines équations diophantiennes par la méthode modulaire. On traite plus particulièrement le cas des équations de Fermat de type (5,5,p) ainsi que celui des équations de la forme F(x,y)=z^p où p est un nombre premier et F une cubique rationnelle. La deuxième partie est consacrée à l'arithmétique des courbes elliptiques. Dans le cas d'une courbe définie sur une extension finie de Q_2 ayant mauvaise réduction additive avec potentiellement bonne réduction, on s'intéresse à la détermination de son défaut de semi-stabilité. On énonce un résultat partiel valable pour toute extension finie de Q_2. Dans le cas des extensions quadratiques ramifiées de Q_2, on obtient un résultat complet. Par ailleurs, si E est une courbe elliptique définie sur un corps de nombres K, on s'intéresse, dans le dernier chapitre, à l'ensemble des nombres premiers p pour lesquels l'action du groupe de Galois absolu de K sur le sous-groupe des points de p-torsion de E est réductible. Lorsque cet ensemble est fini, on obtient un critère permettant en pratique de le déterminer explicitement.

Nombres d'intersection arithmétiques et opérateurs de Hecke sur les courbes modulaires<br /><br />Cette thèse s'inscrit dans l'étude des opérateurs de Hecke en tant que correspondances sur les courbes modulaires X_0(N). D'une part, nous étudions la relation entre l'algèbre de Hecke et la théorie d'Arakelov; d'autre part, nous entreprenons un début d'étude de la dynamique de l'action des opérateurs de Hecke sur l'ensemble des courbes elliptiques supersingulières. <br /><br />On considère la courbe modulaire X_0(N) munie de la métrique de Poincaré (métrique hyperbolique). Cette métrique présente des singularités aux points elliptiques et pointes. On suppose que N est sans facteurs carrés. On note XN le modèle entier de cette courbe donné par l'interprétation modulaire étudiée par Deligne et Rapoport. On définit un groupe de Chow arihmétique généralisé CH(N) tel que ses éléments sont représentés par des couples (D,g) avec D un diviseur de Weil sur XN et g un courant de Green admissible pour la métrique de Poincaré. J.-B. Bost et U. Kühn ont développé, de manière indépendante, des généralisations de la théorie d'intersection arithmétique d'Arakelov qui fournissent une forme bilinéaire à valeurs réelles sur CH(N) x CH(N) dans ce cadre où la métrique est singulière. On étudie aussi une version à coefficients réels et à équivalence numérique près de CH(N), que l'on note CH(N)*.<br /><br />Nous montrons dans cette thèse que les correspondances de Hecke agissent sur CH(N) et que cette action est autoadjointe par rapport à la forme bilinéaire de Bost-Kühn. Ceci permet de diagonaliser cette action sur CH(N)* et de définir ses sous-espaces propres. Ensuite nous étudions le faisceau dualisant relatif, considéré comme un élément de CH(N)*, ainsi que sa décomposition selon les sous-espaces propres. Nous calculons l'auto-intersection de la composante propre correspondante à la pointe à l'infini en utilisant des résultats d'Ulf Kühn.<br /><br /> L'action des opérateurs de Hecke sur les fibres spéciales de XN définit une dynamique qui preserve les points supersinguliers. Nous nous intéressons à étudier cette action sur les points supersinguliers des fibres de bonne réduction et nous calculons, à l'aide des résultats de Deuring et Eichler, la fréquence asymptotique avec laquelle un point supersingulier donné visite un autre point du même type.

Cette thèse donne un aperçu des différentes attaques que doivent contrer les implémentations et propose quelques solutions en distinguant trois niveaux, le niveau hardware, le niveau mathématique et le niveau algorithmique. L'état de l'art fait au chapitre 2 montre bien que les possibilités données à l'attaquant sont multiples et variées. Au niveau hardware, les résultats obtenus dans le projet ESPASS-IS ont motivé la définition de nouveaux projets entre le laboratoire TIMA, le LIRMM et STMicroelectronics . Au niveau mathématique, la mise en ÷uvre de LRA et la collaboration initiée avec le LIRMM a ouvert la voie à de nombreux sujets de recherches vers des arithmétiques à la fois rapides et compactes mais prenant en compte un nouvel élément d'optimisation : la robustesse aux injections de fautes et la minimisation des fuites au travers des canaux cachés. Au niveau algorithmique particulièrement, l'article publié à CHES'00 a fait parti de la toute première vague de travaux de sécurisation des implémentations des courbes elliptiques et constitue une publication très citée dans le domaine.

Le but de cette thèse est d'étudier la structure galoisienne de torseurs sous des schémas en groupes finis (ou quasi-finis) et plats. Pour cela, nous utilisons (et généralisons) un homomorphisme défini par W. Waterhouse, ainsi que le << class invariant homomorphism >> défini par M. J. Taylor.<br /><br />Dans le chapitre I, nous étudions les propriétés fonctorielles de ces homomorphismes. Nous en déduisons une généralisation de résultats de Taylor, Srivastav, Agboola et Pappas concernant le noyau du class invariant homomorphism pour les variétés abéliennes ayant partout bonne réduction qui sont isogènes à un produit de courbes elliptiques.<br /><br />Dans le chapitre II, nous donnons une lecture du class invariant homomorphism dans le langage des 1-motifs.<br /><br />Dans le chapitre III, nous généralisons la construction du class invariant homomorphism pour un sous-groupe fini et plat d'un schéma en groupes semi-stable (sur un schéma de base intègre, normal et noethérien) dont la fibre générique est une variété abélienne. Nous étendons également les résultats de Taylor, Srivastav, Agboola et Pappas à cette situation.<br /><br />Dans le chapitre IV, nous généralisons la construction du chapitre III en considérant un sous-groupe fermé, quasi-fini et plat du modèle de Néron d'une variété abélienne (la base étant un schéma de Dedekind). Ceci nous permet de généraliser un résultat arakélovien du à Agboola et Pappas.

La notion de modules de Drinfeld est le centre de cette thèse, cette notion fut introduite par Drinfeld en 1973, comme étant des " modules elliptiques" appelés de nos jours modules de Drinfeld. Ceux sont des objets algèbriques analogues aux courbes elliptiques sur les corps des nombres et sur les corps finis, obtenus par la réduction modulo une place non-archimédiennene. Une étude de l'arithmétique de tels objet devient légitime, motivée par l'arithmétique des courbes définies sur un corps fini initiée par Artin, Hasse et Weil. Dans cette direction on pousse cette analogie, pour un module de Drinfeld de rang 2, à la majorité de points étudiés pour des courbes elliptiques sur un corps fini. On donne plus précisement un analogue du théorème de Weil, théorème de Deuring-Waterhouse, et un analogue du travail de S. Vladut sur la cyclicité de tel structure algébrique.

Cette thèse est consacrée aux problèmes de minorations de hauteur normalisée des points et des sous-variétés non de torsion. Le chapitre 1 est un chapitre de rappels, les autres sont originaux. On prouve au chapitre 2 un résultat de densité de petits points. Ceci nous permet d'obtenir, pour les sous-variétés de variétés abéliennes de type C.M., une minoration en fonction du degré de la sous-variété, optimale aux puissances de log du degré près. On montre en toute généralité qu'une ``bonne minoration'' de la hauteur des points entraîne une minoration analogue de la hauteur des sous-variétés. Ceci nous permet en particulier de prouver que, sur les variétés abéliennes, le problème de Lehmer pour les points est équivalent au problème de Lehmer pour les sous-variétés. Le chapitre 3 est un raffinement du précédent dans le cas des hypersurfaces. La preuve, qui passe par l'introduction d'une fonction auxiliaire, suit le schéma classique des preuves de transcendance. En utilisant l'inégalité des pentes, due à Bost, on retrouve ensuite au chapitre 4 le célèbre résultat de Dobrowolski concernant le problème originel de Lehmer sur la minoration de la hauteur des entiers algébriques. Le chapitre 5 étend un résultat de Amoroso et Zannier au cas des courbes elliptiques C.M. : on obtient une minoration du type Lehmer, mais où le degré de l'extension engendrée par le point P sur K est remplacé par le degré de l'extension engendrée par le point P sur la clôture abélienne de K. Ceci nous permet de simplifier la preuve d'un résultat de Viada. Enfin au chapitre 6, on fait le lien entre diverses conjectures relatives au problème de Lehmer sur les variétés abéliennes.

Cette thèse s'intéresse à la recherche de points rationnels sur les courbes elliptiques. Darmon et Logan ont proposé une construction conjecturale de points rationnels sur des courbes elliptiques modulaires définies sur un corps de nombres totalement réel. Cette construction va au delà de la construction classique des points de Heegner. C'est sur la généralisation de ces travaux que porte cette thèse. Après un premier chapitre de rappels concernant essentiellement les variétés de Shimura, on construit, dans le chapitre deux une forme différentielle dont l'ensemble des périodes est, sous une conjecture due à Yoshida, un réseau. On y définit aussi un ensemble de cycles dont la classe d'homologie est de torsion. A l'aide de ces données, on énonce au chapitre suivant une conjecture généralisant celle de Darmon et Logan. On s'interesse aussi aux propriétés de ces nouveaux points, principalement en lien avec les théorèmes "classiques" de Gross-Zagier et Gross-Kohnen-Zagier. Le chapitre 4 tente de rendre holomorphes les opérations du chapitre 2, et le chapitre 5 de les rendre plus explicites. Cette thèse comporte une annexe concernant les vérifications informatiques de la conjecture de Darmon.

Un principal résultat de la thèse est une preuve conceptionnelle du fait que le nombre pondéré de courbes tropicales de degré et genre donnés qui passent par le bon nombre de points en position générale dans $\RR^2$ (resp., qui passent par le bon nombre de points en position générale dans $ \RR^r $ et représentent un point fixé dans l'espace de modules de courbes tropicales abstraites de genre g ) ne dépend pas du choix de points. Un autre principal résultat est un nouveau théorème de correspondance entre les cycles tropicaux plans et les courbes algébriques elliptiques planes.

Cette thèse propose des améliorations aux problèmes de la multiplication et de la factorisation d'entier. <p> L'algorithme de Schönhage-Strassen pour la multiplication d'entier, publié en 1971, fut le premier à atteindre une complexité de O(n log (n) log(log(n))) pour multiplier deux entiers de n bits, et reste parmi les plus rapides en pratique. Il réduit la multiplication d'entier à celle de polynôme sur un anneau fini, en utilisant la transformée de Fourier rapide pour calculer le produit de convolution. Dans un travail commun avec Gaudry et Zimmermann, nous décrivons une implantation efficace de cet algorithme, basée sur la bibliothèque GNU MP; par rapport aux travaux antérieurs, nous améliorons l'utilisation de la mémoire cache, la sélection des paramètres et la longueur de convolution, ce qui donne un gain d'un facteur 2 environ. <p> Les algorithmes P-1 et P+1 trouvent un facteur p d'un entier composé rapidement si p-1, respectivement p+1, ne contient pas de grand facteur premier. Ces algorithmes comportent deux phases: la première phase calcule une grande puissance g₁ d'un élément g₀ d'un groupe fini défini sur F_p, respectivement F_p^2, la seconde phase cherche une collision entre puissances de g₁, qui est trouvée de manière efficace par évaluation-interpolation de polynômes. Dans un travail avec Peter Lawrence Montgomery, nous proposons une amélioration de la seconde phase de ces algorithmes, avec une construction plus rapide des polynômes requis, et une consommation mémoire optimale, ce qui permet d'augmenter la limite pratique pour le plus grand facteur premier de p-1, resp. p+1, d'un facteur 100 environ par rapport aux implantations antérieures. <p> Le crible algébrique (NFS) est le meilleur algorithme connu pour factoriser des entiers dont les facteurs n'ont aucune propriété permettant de les trouver rapidement. En particulier, le module du système RSA de chiffrement est choisi de telle sorte, et sa factorisation casse le système. De nombreux efforts ont ainsi été consentis pour améliorer NFS, de façon à établir précisément la sécurité de RSA. Nous donnons un bref aperçu de NFS et de son historique. Lors de la phase de crible de NFS, de nombreux petits entiers doivent être factorisés. Nous présentons en détail une implantation de P-1, P+1, et de la méthode ECM basée sur les courbes elliptiques, qui est optimisée pour de tels petits entiers. Finalement, nous montrons comment les paramétres de ces algorithmes peuvent étre choisis finement, en tenant compte de la distribution des facteurs premiers dans les entiers produits par NFS, et de la probabilité de trouver des facteurs premiers d'une taille donnée.