Université de Rennes 1 Analyse de nouvelles primitives cryptographiques pour les schémas Diffie-Hellman Analysis of new cryptographic primitives for Diffie-Hellman schemes cryptographiecryptanalysepolynôme torducourbes elliptiquescubiquescourbes algébriquescourbes hyperelliptiqueshachageencodage cryptographic primitivesDiffie-Hellman protocolsalgebraic curves -toward elliptic -elliptic curvesalgebra problemskew polynomialspolynomial complexity Cryptographie Thèses et écrits académiques Courbes algébriques Thèses et écrits académiques 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. Electronic Thesis or DissertationText fr application/pdf1 : 1086 Kohttp://ecm.univ-rennes1.fr/nuxeo/site/esupversions/cc7c2565-d23c-470d-8713-dd7cdf107677 Kammerer Jean-Gabriel 1986-04-05 FR 171112385 10041919 jean-gabriel.kammerer@m4x.org 2013REN1S035 http://www.theses.fr/2013REN1S035 2013-05-23 Mathématiques fondamentales et applications Université de Rennes 1thesis.degree.grantor_1 02778715X Université européenne de Bretagnethesis.degree.grantor_2 139075119 Doctorat non ouiLercierReynaldintervenant_111637974X Mathématiques, informatique, signal, électronique et télécommunicationsecoleDoctorale_1 139007164 IRMARpartenaireRecherche_1 028233107 ddc:510 LercierReynaldUniversité de Rennes 1Sciences et technologie, médecine, pharmacie, odontologie, droit, économie, gestion, philosophieUniversité européenne de BretagnePôle de recherche et d'enseignement supérieur de BretagneMathématiques, informatique, signal, électronique et télécommunicationsÉcole doctorale Mathématiques, informatique, signal, électronique et télécommunications (Rennes)IRMAR ASCII PDF 1112562