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.

L'avènement de l'informatique quantique permet de réétudier les primitives cryptographiques avec une sécurité inconditionnelle, c'est à dire sécurisé même contre des adversaires tout puissants. En 1984, Bennett et Brassard ont construit un protocole quantique de distribution de clé. Dans ce protocole, deux joueurs Alice et Bob coopèrent pour partager une clé secrète inconnue d'une tierce personne Eve. Ce protocole a une sécurité inconditionnelle et n'a pasd'équivalent classique.Dans ma thèse, j'ai étudié les primitives cryptographiques à deux joueurs où ces joueurs ne se font pas confiance. J'étudie principalement le pile ou face quantique et la mise-en-gage quantique de bit. En informatique classique, ces primitivessont réalisables uniquement avec des hypothèses calculatoires, c'est-à-dire en supposant la difficulté d'un problème donné. Des protocoles quantiques ont été construits pour ces primitives où un adversaire peut tricher avec une probabilité constante strictement inférieure à 1, ce qui reste impossible classiquement. Néanmoins, Lo et Chau ont montré l'impossibilité de créer ces primitives parfaitement même en utilisant l'informatique quantique. Il reste donc à déterminer quelles sont les limites physiques de ces primitives.Dans une première partie, je construis un protocole quantique de pile ou face où chaque joueur peut tricher avec probabilité au plus 1/racine(2) + eps pour tout eps > 0. Ce résultat complète un résultat de Kitaev qui dit que dans un jeu de pile ou face quantique, un joueur peut toujours tricher avec probabilité au moins 1/racine(2). J'ai également construit un protocole de mise-en-gage de bit quantique optimal où un joueur peut tricher avec probabilité au plus 0,739 + eps pour tout eps > 0 puis ai montré que ce protocole est en fait optimal. Finalement, j'ai dérivé des bornes inférieures et supérieures pour une autre primitive: la transmission inconsciente, qui est une primitive universelle.Dans une deuxième partie, j'intègre certains aspects pratiques dans ces protocoles. Parfois les appareils de mesure ne donnent aucun résultat, ce sont les pertes dans la mesure. Je construis un protocole de lancer de pièce quantique tolérant aux pertes avec une probabilité de tricher de 0,859. Ensuite, j'étudie le modèle dispositif-indépendant où on ne suppose plus rien sur les appareils de mesure et de création d'état quantique.Finalement, dans une troisième partie, j'étudie ces primitives cryptographiques avec un sécurité computationnelle. En particulier, je fais le lien entre la mise en gage de bit quantique et les protocoles zero-knowledge quantiques.

Les réseaux Euclidiens sont un riche objet algébrique qui apparaît dans des contextes variés en mathématiques et en informatique. Cette thèse considère plusieurs aspects algorithmiques des réseaux. Le concept de réduction d'une base d'un réseau est étudié minutieusement : nous couvrons en particulier le spectre complet des compromis qualité-temps des algorithmes de réduction. D'une part, nous présentons et analysons des algorithmes rapides pour trouver une base assez courte (base LLL-réduite) d'un réseau donné arbitraire. D'autre part, nous proposons de nouvelles analyses pour des algorithmes (plus lents) permettant de calculer des bases très courtes (bases HKZ et BKZ-réduites). Cette étude des algorithmes de résolution efficace de problèmes portant sur les réseaux est complétée par une application constructive exploitant leur difficulté apparente. Nous proposons et analysons des schémas cryptographiques, dont la fonction de chiffrement NTRU, et les prouvons au moins aussi difficiles à casser que de résoudre des problèmes pires-cas bien spécifiés portant sur les réseaux.

Dans la cryptographie à clé privée l'arithmétique joue un rôle important. En particulier, l'arithmétique des corps finis doit être très rapide étant donnée la quantité de calculs effectués en nécessitant des ressources limitées (surface de circuit, taille mémoire, consommation d'énergie) mais aussi tout en offrant un bon niveau de robustesse vis à vis des attaques physiques. L'objectif de cette thèse etait d'étudier, comparer, concevoir en matériel et enfin de valider expérimentalement et théoriquement des opérateurs arithmétiques matériels pour la cryptographie sur courbes elliptiques (ECC) sur des extensions du corps fini binaire (GF(2m)) à la fois performants, peu gourmands en énergie et robustes d'un point de sécurité contre les attaques physiques par canaux cachés (p.ex. mesure de la consommation d'énergie). Des travaux effectues aboutissent à la proposition d'opérateurs de multiplication performants (rapides, surface de circuit limitée) dans une architecture modulaire (pouvant être adaptée à des besoins spécifiques sans perte de performance). Les calculs requis par ces opérateurs sont complexes car les éléments du corps sont grands (160-580 bits) et la multiplication s'effectue modulo un polynôme irréductible. En plus la thèse presente des modification et l'optimisation des opérateurs pour les rendre plus robustes à certaines attaques par canaux cachés (de type mesure de consommation) sans perte de performance. Sécurisation d'opérateurs arithmétiques pour ECC au niveau des calculs sur le corps fini est particulièrement intéressant car c'est la première proposition de ce type. Ce travail complète un état de l'art en protections aux niveaux supérieurs (courbes, protocoles).

Les systèmes embarqués actuels (téléphone portable, assistant personnel...) ne sont pas considérés<br />comme des hôtes de confiance car toute personne y ayant accès, sont des attaquants potentiels. Les données<br />contenues dans ces systèmes peuvent être sensibles (données privées du propriétaire, mot de passe, code d'un<br />logiciel...) et sont généralement échangées en clair entre le Système sur Puces (SoC – System on Chip) et la<br />mémoire dans laquelle elles sont stockées. Le bus qui relie ces deux entités constitue donc un point faible : un<br />attaquant peut observer ce bus et récupérer le contenu de la mémoire, ou bien a la possibilité d'insérer du code<br />afin d'altérer le fonctionnement d'une application s'exécutant sur le système. Afin de prévenir ce type d'attaque,<br />des mécanismes matériels doivent être mis en place afin d'assurer la confidentialité et l'intégrité des données.<br />L'approche conventionnelle pour atteindre cet objectif est de concevoir un mécanisme matériel pour chaque<br />service de sécurité (confidentialité et intégrité). Cette approche peut être implantée de manière sécurisée mais<br />empêche toute parallélisation des calculs sous-jacents.<br />Les travaux menés au cours de cette thèse ont dans un premier temps, consisté à faire une étude des<br />techniques existantes permettant d'assurer la confidentialité et l'intégrité des données. Dans un deuxième temps,<br />nous avons proposé deux mécanismes matériels destinés à la sécurisation des transactions entre un processeur et<br />sa mémoire. Un moteur de chiffrement et de contrôle d'intégrité parallélisé, PE-ICE (Parallelized Encryption and<br />Integrity Checking Engine) a été conçu. PE-ICE permet une parallélisation totale des opérations relatives à la<br />sécurité aussi bien en écriture qu'en lecture de données en mémoire. Par ailleurs, une technique basée sur une<br />structure d'arbre (PRV-Tree – PE-ICE protected Reference Values) comportant la même propriété de<br />parallélisation totale, a été spécifiée afin de réduire le surcoût en mémoire interne impliqué par les mécanismes de sécurité

Dans cette thèse nous abordons le problème de la conception de passerelle IPsec très haut débit pour la sécurisation des communications entre réseaux locaux. Pour cela, nous proposons deux architectures : une passerelle purement logicielle sur un unique serveur, dite intégrée, et une passerelle utilisant plusieurs serveurs et un module matériel cryptographique, dite en rupture. La première partie de nos travaux étudie l'aspect performance des deux architectures proposées. Nous commençons par montrer qu'un serveur générique est limité par sa puissance de calcul pour atteindre l'objectif de chiffrement et communication à 10 Gb/s. De plus, les nouvelles cartes graphiques, bien que prometteuses en terme de puissance, ne sont pas adaptées au problème du chiffrement de paquets réseau (à cause de leur faible taille). Nous mettons alors en place une pile réseau répartie sur plusieurs machines et procédons à sa parallélisation dans le cadre de l'architecture en rupture. Dans un second temps, nous analysons l'intégration d'une passerelle dans un réseau, notamment l'interaction du protocole de contrôle ICMP avec IPsec. ICMP est particulièrement important pour atteindre le haut débit par son implication dans le mécanisme d'optimisation de la taille des paquets. Pour cela, nous avons développé IBTrack, un logiciel d'étude du comportement des routeurs, par rapport à ICMP, le long d'un chemin. Nous montrons ensuite qu'ICMP est un vecteur d'attaque contre IPsec en exploitant un défaut fondamental des normes IP et IPsec : le surcoût des paquets IP créé par le mode tunnel entre en conflit avec le minimum de la taille maximale prévue par IP.

Les systèmes de cryptographie à base de courbe elliptique (ECC) ont été adoptés comme des systèmes standardisés de cryptographie à clé publique (PKC) par l'IEEE, ANSI, NIST, SEC et WTLS. En comparaison avec la PKC traditionnelle, comme RSA et ElGamal, l'ECC offre le même niveau de sécurité avec des clés de plus petites tailles. Cela signifie des calculs plus rapides et une consommation d'énergie plus faible ainsi que des économies de mémoire et de bande passante. Par conséquent, ECC est devenue une technologie indispensable, plus populaire et considérée comme particulièrement adaptée à l'implémentation sur les dispositifs à ressources restreintes tels que les réseaux de capteurs sans fil (WSN). Le problème majeur avec les noeuds de capteurs chez les WSN, dès qu'il s'agit d'opérations cryptographiques, est les limitations de leurs ressources en termes de puissance, d'espace et de temps de réponse, ce qui limite la capacité du capteur à gérer les calculs supplémentaires nécessaires aux opérations cryptographiques. En outre, les mises en oeuvre actuelles de l'ECC sur WSN sont particulièrement vulnérables aux attaques par canaux auxiliaires (SCA), en particulier aux attaques par analyse de consommation (PAA), en raison de l'absence de la sécurité physique par blindage, leur déploiement dans les régions éloignées et le fait qu'elles soient laissées sans surveillance. Ainsi, les concepteurs de crypto-processeurs ECC sur WSN s'efforcent d'introduire des algorithmes et des architectures qui ne sont pas seulement résistants PAA, mais également efficaces sans aucun supplément en termes de temps, puissance et espace. Cette thèse présente plusieurs contributions dans le domaine des cryptoprocesseurs ECC conscientisés aux PAA, pour les dispositifs à ressources limitées comme le WSN. Premièrement, nous proposons deux architectures robustes et efficaces pour les ECC conscientisées au PAA. Ces architectures sont basées sur des algorithmes innovants qui assurent le fonctionnement de base des ECC et qui prévoient une sécurisation de l'ECC contre les PAA simples (SPA) sur les dispositifs à ressources limitées tels que les WSN. Deuxièmement, nous proposons deux architectures additionnelles qui prévoient une sécurisation des ECC contre les PAA différentiels (DPA). Troisièmement, un total de huit architectures qui incluent, en plus des quatre architectures citées ci-dessus pour SPA et DPA, deux autres architectures dérivées de l'architecture DPA conscientisée, ainsi que deux architectures PAA conscientisées. Les huit architectures proposées sont synthétisées en utilisant la technologie des réseaux de portes programmables in situ (FPGA). Quatrièmement, les huit architectures sont analysées et évaluées, et leurs performances comparées. En plus, une comparaison plus avancée effectuée sur le niveau de la complexité du coût (temps, puissance, et espace), fournit un cadre pour les concepteurs d'architecture pour sélectionner la conception la plus appropriée. Nos résultats montrent un avantage significatif de nos architectures proposées par rapport à la complexité du coût, en comparaison à d'autres solutions proposées récemment dans le domaine de la recherche.

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

L'objectif central de cette thèse est d'exploiter les propriétés quantiques du champ électromagnétique pour développer de nouveaux dispositifs de communication. L'étude porte sur les composantes de quadrature (variables quantiques continues) d'un mode impulsionnel du champ lumineux. Une démonstration expérimentale de cryptographie quantique avec des états cohérents a été réalisée. Le dispositif se base sur des impulsions modulées en amplitude et en phase et comportant en moyenne une centaine de photons. Pour chaque impulsion lumineuse, une détection homodyne résolue en temps permet de mesurer une composante de quadrature particulière avec une forte efficacité. Une clé secrète a ainsi été transmise à un débit de 1.7 Mbits/s en l'absence de pertes et 75 kbits/s pour une transmission présentant des pertes de 3.1 dB, ce qui ouvre la voie pour des applications de cryptographie quantique à hauts débits. Afin d'étudier l'utilisation de spécificités quantiques, nous avons développé une source impulsionnelle d'états comprimés et d'états intriqués. Cette source utilise des conversions non-linéaires d'impulsions ultrabrèves intervenant dans un cristal mince de niobate de potassium. Suivant la configuration, la réduction du bruit en quadrature est de 2.7 dB sous le niveau de bruit quantique standard, ou les corrélations entre les quadratures des faisceaux intriqués sont de 2.5 dB. Grâce à ce dispositif, nous avons mis en oeuvre la première expérience de "dégaussification", pour transformer des impulsions de vide comprimé en des états non-gaussiens. Ce protocole est directement lié à la distillation de l'intrication de variables continues, qui permet d'améliorer la portée des dispositifs de cryptographie. Enfin, des schémas sont étudiés pour réaliser des tests complets des inégalités de Bell avec des variables continues mesurées par des détections homodynes.

Cette thèse porte sur la distribution quantique de clés, qui est une primitive cryptographique permettant à deux correspondants éloignés, Alice et Bob, d'établir une clé secrète commune malgré la présence potentielle d'un espion. On s'intéresse notamment aux protocoles " à variables continues " où Alice et Bob encodent l'information dans l'espace des phases. L'intérêt majeur de ces protocoles est qu'ils sont faciles à mettre en œuvre car ils ne requièrent que des composants télécom standards. La sécurité de ces protocoles repose sur les lois de la physique quantique : acquérir de l'information sur les données échangées par Alice et Bob induit nécessairement un bruit qui révèle la présence de l'espion. Une étape particulièrement délicate pour les protocoles à variables continues est la " réconciliation " durant laquelle Alice et Bob utilisent leurs résultats de mesure classiques pour se mettre d'accord sur une chaîne de bits identiques. Nous proposons d'abord un algorithme de réconciliation optimal pour le protocole initial, puis introduisons un nouveau protocole qui résout automatiquement le problème de la réconciliation grâce à l'emploi d'une modulation discrète. Parce que les protocoles à variables continues sont formellement décrits dans un espace de Hilbert de dimension infinie, prouver leur sécurité pose des problèmes mathématiques originaux. Nous nous intéressons d'abord à des symétries spécifiques de ces protocoles dans l'espace des phases. Ces symétries permettent de simplifier considérablement l'analyse de sécurité. Enfin, nous étudions l'influence des effets de tailles finies, tels que l'estimation du canal quantique, sur les performances des protocoles.