Cette thèse est dédiée à la cryptanalyse de l'AES (Advanced Encryption Standard) qui est l'un des systèmes de chiffrement par bloc les plus répandu dans le monde. Nous y présentons une nouvelle technique pour résoudre un type particulier d'équations spécialement conçu pour attaquer l'AES. Cette technique est basée sur l'algèbre linéaire ainsi que sur la technique de la " Rencontre par le Milieu " et offre pour un système donné, plusieurs algorithmes de résolution de complexités différentes mais prédictibles. Ainsi nous avons conçu un programme pour trouver l'algorithme le plus rapide. Dans un premier temps nous l'avons appliqué directement aux systèmes d'équations décrivant un nombre réduit de tours d'AES et avons trouvé de nouvelles attaques lorsque la quantité de couples clair/chiffré est très limitée, améliorant celles trouvées manuellement par d'autres chercheurs. La technique étant générale nous avons pu utiliser le programme pour étudier d'autres modèles comme celui des attaques par fautes et celui des attaques à clé choisie ainsi que d'autres primitives cryptographiques comme la fonction d'authentification Pelican-MAC et le système de chiffrement par flot LEX. Enfin nous présentons une généralisation des attaques de Demirci et Selçuk publiées à la conférence FSE2008 ainsi qu'un algorithme qui nous a permis de trouver les meilleures attaques de cette classe, avec certaines parmi les meilleures connues à ce jour. Cet algorithme repose sur l'utilisation du précédent programme afin de déterminer le nombre de valeurs prises par des sous-ensembles d'octets de clé ou des états internes ainsi que la complexité de les énumérer.

Les travaux exposés dans cette thèse se situent à l’interface des mathématiques discrètes, des corps finis et de la cryptographie symétrique.Les 'boîtes-S’ sont des fonctions non-linéaires de petites tailles qui constituent souvent la partie de confusion, indispensable, des chiffrements par blocs ou des fonctions de hachages.Dans la première partie de cette thèse, nous nous intéressons à la construction de boîtes-S bijectives résistantes aux attaques différentielle. Nous étudions l’inverse pour la composition des monômes de permutations optimaux vis-à-vis du critère différentiel. Nous explorons ensuite des classes spécifiques de polynômes creux. Enfin, nous construisons des boîtes-S à partir de leurs dérivées discrètes.Dans la deuxième partie, nous portons notre attention sur la cryptanalyse différentielle impossible. Cette cryptanalyse à clairs choisis très performante pour attaquer des chiffrements par blocs itératifs, exploite la connaissance d’une différentielle de probabilité zéro pour écarter les clés candidates. Elle est très technique, et de nombreuses erreurs ont été repérées dans des travaux passés, invalidant certaines attaques. Le but de ces travaux est de formaliser et d’automatiser l’évaluation des complexités d’une telle attaque afin d’unifier et d’optimiser les résultats obtenus. Nous proposons aussi de nouvelles techniques réduisant les complexités cette cryptanalyse. Nous démontrons enfin l’efficacité de notre approche en fournissant les meilleures cryptanalyses différentielles impossibles contre les chiffrements CLEFIA, Camellia, LBlock et Simon. / The work I have carried out in this thesis lie between discrete mathematics, finite fields theory and symmetric cryptography. In block ciphers, as well as in hash functions, SBoxes are small non-linear and necessary functions working as confusion layer.In the first part of this document, we are interesting in the design of bijective SBoxes that have the best resistance to differential attacks. We study the compositional inverse of the so-called Almost Perfect Nonlinear power functions. Then, we extensively study a class of sparse permutation polynomials with low differential uniformity. Finally, we build functions, over finite fields, from their discrete derivatives.In the second part, we realize an automatic study of a certain class of differential attacks: impossible differential cryptanalysis. This known plaintexts attack has been shown to be very efficient against iterative block ciphers. It exploits the knowledge of a differential with probability zero to occur. However this cryptanalysis is very technical and many flaws have been discovered, thus invalidating many attacks realized in the past. Our goal is to formalize, to improve and to automatize the complexity evaluation in order to optimize the results one can obtain. We also propose new techniques that aims at reducing necessary data and time complexities. We finally prove the efficiency of our method by providing some of the best impossible differential cryptanalysis against Feistel oriented block ciphers CLEFIA, Camellia, LBlock and Simon.

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.

Ces travaux traitent des problèmes de sécurité et de flexibilité dans le domaine des circuits sécurisés. Dans ce manuscrit, après la présentation de notions cryptographiques, nous étudions deux problématiques distinctes. La première concerne les attaques par clonage et retro-ingénierie. Dans ce sens, nous proposons une solution basée sur l'utilisation de logique reconfigurable répartie, et traitons aussi du protocole de reconfiguration associé. La seconde problématique étudiée dans ce manuscrit vise à éviter les attaques par analyse des canaux cachés. Nous suggérons alors une contre-mesure, basée sur la reconfiguration dynamique des chemins de données du circuit intégré. Cette contre-mesure est présentée selon différentes variantes et évaluée selon différents placements et niveaux d'abstraction.

Le travail porte sur la synthèse et la cryptanalyse des schémas de chiffrement basés sur le chaos. Ces schémas utilisent, côté émetteur, des systèmes dynamiques non linéaires exhibant un comportement chaotique. La séquence complexe ainsi produite est utilisée pour masquer une information. Plusieurs modes de chiffrement sont étudiés : la modulation chaotique, la modulation paramétrique et le chiffrement par inclusion, principalement dans le cas des systèmes chaotiques à temps discret. Pour ces schémas, la reconstruction de l'information nécessite la synchronisation de l'émetteur et du récepteur. Un observateur joue le rôle du récepteur.<br /><br />Tout d'abord, le lien entre le chiffrement par le chaos et le chiffrement usuel est établi. <br /><br />Concernant la modulation chaotique, nous proposons, pour le déchiffrement, une méthode systématique de synthèse d'observateur polytopique, tenant compte de la spécificité du problème liée au chaos. Dans la modulation paramétrique, côté émetteur, l'information claire module les paramètres d'un système chaotique. Pour réaliser la synchronisation, un observateur adaptatif polytopique assurant la reconstruction simultanée état/paramètre est proposé.<br /><br />Enfin, la cryptanalyse du chiffrement par inclusion est effectuée. Nous considérons des systèmes présentant uniquement des non linéarités polynomiales qui englobent un grand nombre de systèmes chaotiques usuels. La sécurité de ce schéma repose sur les paramètres du système chaotique, supposés jouer le rôle de clé secrète. Un formalisme général, basé sur le concept de l'identifiabilité, est élaboré pour tester la reconstructibilité de ces paramètres. Les différentes définitions de l'identifiabilité sont récapitulées et des approches permettant de tester l'identifiabilité sont présentées. Ce formalisme est appliqué sur des schémas usuels de chiffrement par inclusion afin de tester leur sécurité.

Ce travail de thèse concerne la sécurisation des circuits électroniques contre les attaques (dites SCA) qui visent leur implémentation. Les algorithmes cryptographiques ont été traditionnellement étudiés pour résister aux attaques théoriques. Néanmoins, dès lors que ces algorithmes sont mis en oeuvre sur des dispositifs concrets, de nouvelles attaques deviennent possibles. Effectivement, de l'information peut être extraite passivement (par observation). Cette information complémentaire, communément appelée "canal caché", apporte un pouvoir supplémentaire aux attaquants. Les canaux cachés les plus populaires sont la consommation électrique et le rayonnement électromagnétique. Nous montrons tout d'abord que les attaques sur les canaux cachés sont structurelles, c'est-à-dire inhérentes au traitement de l'information. Il se trouve par ailleurs que les algorithmes cryptographiques sont spécialement sensibles aux SCA, à cause des propriétés constitutives des fonctions booléennes utilisées. Le talon d'Achille principal est l'architecture RTL de l'opérateur cryptographique. Effectivement, les transferts de registres rendent possible une attaque dite en distance de Hamming. Nous continuons en recherchant des moyens permettant de ne fuir pratiquement aucune information exploitable par un attaquant. Des portes logiques sécurisées sont conçues de sorte à minimiser les violations de symétrie. Une stratégie de routage équilibré obéi aux mêmes critères. La conservation de la symétrie est traitée avec un soin tout particulier, aboutissant à la méthode générique de "backend duplication".

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.

Dans ce travail de thèse, nous développons des méthodes de synchronisation des systèmes chaotiques pour les applications de transmission d'informations. La première méthode de synchronisation que nous proposons est basée sur les observateurs adaptatifs à entrées inconnues pour une classe des systèmes chaotiques présentant des incertitudes paramétriques et des perturbations dans leurs dynamiques et du bruit dans les signaux de sortie (bruit dans le canal de communication). La méthode développée repose sur les techniques adaptatives pour la compensation des non-linéarités et des incertitudes paramétriques et pour la restauration des messages transmis. Elle se base également sur les méthodes de synthèse d'observateurs à entrées inconnues pour supprimer l'influence des perturbations et du bruit. Ensuite, nous développons une deuxième méthode de synchronisation utilisant un observateur adaptatif à ''modes glissants" pour une classe des systèmes chaotiques présentant des entrées inconnues et dont les signaux de sortie sont bruités. La synthèse de l'observateur s'appuie sur la théorie des modes glissants, les techniques de synthèse d'observateurs singuliers et les techniques adaptatives dans le but d'estimer conjointement l'état et les entrées inconnues malgré la présence du bruit dans les équations de sortie. Cette approche de synchronisation est ensuite employée dans un nouveau schéma de communication chaotique sécurisée dont l'objectif est d'augmenter le nombre et l'amplitude des messages transmis, améliorer le niveau de sécurité ainsi que la robustesse aux bruits présents dans le canal de communication. En outre, le scénario de présence des retards de transmission est étudié en élaborant une troisième approche de synchronisation à base d'observateurs adaptatifs pour une classe des systèmes chaotiques de Lur'e avec des non-linéarités à pente restreinte et des signaux de sortie retardés. En se basant sur la théorie de Lyapunov-Krasovskii et en utilisant une hypothèse d'excitation persistante, l'observateur adaptatif proposé garantit la synchronisation maitre-esclave et la restauration des informations transmises malgré l'existence des retards de transmission. Les résultats théoriques obtenus dans ce travail de thèse sont vérifiés à travers des applications de transmission d'informations utilisant différents modèles des systèmes chaotiques tout en étudiant les différents scénarios et cas de figure pouvant se présenter en pratique et en analysant les aspects de sécurité de ces systèmes.

De façon générale, cette thèse porte sur l'estimation de l'état et des entrées inconnues pour une classe de systèmes non linéaires. De façon plus particulière, le problème est abordé sous l'angle de la conception d'un système de transmission sécurisée d'informations exploitant les propriétés des systèmes chaotiques et leur capacité de synchronisation. Les travaux présentés traitent trois points principaux, à savoir le choix de l'émetteur, le développement du récepteur, et la mise au point du processus de transmission de l'information ou du message. <br />L'émetteur retenu est un système non linéaire chaotique dont la dynamique comporte un retard, ce qui lui confère un comportement particulièrement complexe. La conception du récepteur repose sur la synthèse d'un observateur non linéaire, dont la stabilité et la convergence garantissent la synchronisation avec l'émetteur. L'insertion du message est réalisée par modulation de la phase d'un signal porteur chaotique. Le décryptage de l'information s'apparente à une restauration d'entrée inconnue au niveau du récepteur.<br />Une étude de la sécurité du processus de cryptage/décryptage a été menée, reposant sur des techniques standard de cryptanalyse. Des multimodèles chaotiques ont été proposés pour renforcer la sécurité du processus de synchronisation.

Au début des années 90, l'apparition de nouvelles méthodes de cryptanalyse a bouleversé la sécurité des dispositifs cryptographiques. Ces attaques se basent sur l'analyse de consommation en courant lorsque le microprocesseur d'une carte est en train de dérouler l'algorithme cryptographique. Dans cette thèse nous explorons, principalement, les attaques template, et y apportons quelques améliorations pratiques notamment par l'utilisation de différentes techniques de traitement du signal. Nous commençons par étudier l'efficacité de ces attaques sur des mises en oeuvre matérielles non protégées, et explorons au fur et à mesure quelque modèles de fuite d'information. Après cela, nous examinons la pertinence du cadre théorique sur les attaques par profilage présenté par F.-X. Standaert et al. à Eurocrypt 2009. Ces analyses consistent en des études de cas basées sur des mesures de courant acquises expérimentalement à partir d'un accélérateur cryptographique. À l'égard de précédentes analyses formelles effectuées sur des mesures par " simulations ", les investigations que nous décrivons sont plus complexes, en raison des différentes architectures et de la grande quantité de bruit algorithmique. Dans ce contexte, nous explorons la pertinence des différents choix pour les variables sensibles, et montrons qu'un attaquant conscient des transferts survenus pendant les opérations cryptographiques peut sélectionner les distingueurs les plus adéquats, et augmenter ainsi son taux de succès. Pour réduire la quantité de données, et représenter les modèles en deux dimensions, nous utilisons l'analyse en composantes principales (ACP) et donnons une interprétation physique des valeurs propres et vecteurs propres. Nous introduisons une méthode basée sur le seuillage de la fuite de données pour accélérer le profilage ainsi que l'attaque. Cette méthode permet de renforcer un attaquant qui peut avec un minimum de traces, améliorer 5 fois sa vitesse dans la phase en ligne de l'attaque. Aussi, il a été souligné que les différents modèles utilisés, ainsi que les échantillons recueillis durant la même acquisition peuvent transporter des informations complémentaires. Dans ce contexte, nous avons eu l'occasion d'étudier comment combiner au mieux différentes attaques en se basant sur différentes fuites. Cela nous a permis d'apporter des réponses concrètes au problème de la combinaison des attaques. Nous nous sommes concentrés également sur l'identification des problèmes qui surgissent quand il y a une divergence entre les templates et les traces attaquées. En effet, nous montrons que deux phénomènes peuvent entraver la réussite des attaques lorsque les templates sont obsolètes, à savoir, la désynchronisation des traces, et le redimensionnement des traces en amplitudes. Nous suggérons deux remèdes pour contourner ce type de problèmes : le réajustement des signaux et la normalisation des campagnes d'acquisitions. Finalement, nous proposons quelques méthodes du traitement du signal dans le contexte des attaques physiques. Nous montrons que lorsque les analyses sont effectuées en multi-résolution, il y a un gain considérable en nombre de traces nécessaires pour récupérer la clé secrète, par rapport à une attaque ordinaire.