Dissertations / Theses on the topic 'Algorithmes symétriques'

L’objectif de cette thèse est de proposer de nouvelles pistes de recherche dans l’état de l’art afin de sécuriser les algorithmes cryptographiques au sein d’un circuit électronique. Notre axe d’étude principal s’articule autour de la contre-mesure des implémentations à seuil, résistante contre les attaques par observations en présence de glitches. Ces derniers phénomènes apparaissent dans un circuit électronique de manière aléatoire et sont à l’origine de nombreuses attaques en cryptanalyse. Nous étudions l’application des implémentations à seuil sur la cryptographie symétrique. Dans un premier temps, nous contribuons à la littérature cryptographique par la conception de nouvelles implémentations à seuil applicables sur un grand nombre d’algorithmes symétriques. Les travaux réalisés sont appuyés par des preuves mathématiques formelles et permettent de contrer les attaques physiques par observations en présence de glitches. Par ailleurs, nos recherches ont également débouché à la proposition de deux brevets au sein de l’entreprise STMicroelectronics, participant ainsi au processus d’innovation industriel. Dans un second temps, nous nous intéressons à l’étude de l’algorithme symétrique SM4 et sa résistance face à la cryptanalyse actuelle. Les travaux obtenus permettent de centraliser les différentes implémentations du SM4 sécurisées contre les attaques par observations proposées dans l’état de l’art et d’offrir une visibilité sur les performances de ces constructions. Nous contribuons également à la recherche académique par la première proposition d’une implémentation à seuil du SM4, mathématiquement résistante contre les attaques par observations en présence de glitches
The goal of this thesis is to contribute to the state-of-the-art by proposing new areas of research in order to secure cryptographic algorithms within an embedded device.Our main focal axis is organized around the countermeasure called threshold implementations which is known to be resistant against side-channel analysis attacks in the presence of glitches.These latter phenomenon occur randomly within an electronic circuit and lead to numerous attacks in cryptanalysis. We study the application of threshold implementations on symmetric-key cryptography.In a first phase, we participate to the cryptographic litterature by designing new threshold implementations easily applicable on a large variety of symmetric-key algorithms. Our countermeasures are provable mathematically secured against side-channel analysis attacks in the presence of glitches. In comparison with the recent publications of the state-of-the-art, we adress new issues and we assure similar or better performances. Therefore, our research has resulted in two patents within STMicroelectronics, thereby contributing to the industrial innovation process.In a second phase, we are interested in the study of the symmetric-key algorithm SM4 and its resistance against side-channel analysis attacks. The works obtained allow to centralize the proposed SM4 countermeasures against side-channel analysis attacks of the state-of-the-art and offer a visibility on the software performances of these constructions. We finally introduce the first threshold implementation of the SM4 algorithm. Our construction is provably mathematically resistant against side-channel analysis attacks in the presence of glitches

Cette these se divise en deux parties independantes. La premiere partie concerne la resolution de systemes lineaires de grande taille sur des systemes a memoire distribuee. L'algorithme utilise la factorisation lu et la resolution des deux systemes triangulaires. Nous donnons une description detaillee de cet algorithme, et discutons les choix qui ont ete realises lors de son implantation. Nous montrons aussi que cet algorithme est numeriquement stable, et permet de preserver le caractere creux de la matrice. Au cours de son execution, les taches sont equitablement reparties entre les differents processeurs. Pour montrer les performances de l'algorithme, nous resolvons plusieurs problemes issus de la physique sur diverses machines cibles a memoire distribuee. Nous illustrons l'influence de certains parametres de l'algorithme sur la qualite de la solution et sur la vitesse de convergence. Dans la seconde partie, nous nous interessons a une categorie d'algorithmes de reordonnancement pour des matrices non symetriques. Le but initial du reordonnancement est d'amener les pivots de plus large module sur la diagonale de la matrice, pour ameliorer la qualite numerique des solutions. Nous presentons en detail diverses variantes de ces algorithmes. Nous envisageons aussi la possibilite d'utiliser en plus du reordonnancement, des techniques de scaling. Enfin nous presentons des experimentations numeriques qui permettent de comparer les algorithmes de reordonnancement. Nous montrerons l'impact de ces techniques lorsqu'elles sont utilisees un amont d'algorithmes directs ou iteratifs de resolution de systemes lineaires.

Les travaux de cette thèse portent sur les critères de sécurité des
algorithmes de chiffrement à clé secrète et ont été menés suivant deux
axes. Le premier concerne la sécurité des chiffrements symétriques
itératifs par blocs contre les attaques par distingueur sur le dernier
tour. Les résultats portent en particulier sur la généralisation d'une
attaque différentielle d'ordre supérieur menée sur l'algorithme
MISTY1. L'origine de cette attaque ainsi que de sa généralisation a pu
être expliquée grâce aux propriétés du spectre de Walsh des fonctions
de non-linéarité maximale utilisées. Ainsi il a été possible
d'élaborer une attaque générique sur tous les chiffrements de Feistel
à cinq tours utilisant des fonctions dont le spectre de Walsh est
divisible par une grande puissance de 2 car cette propriété permet
d'obtenir une borne supérieure sur le degré de la composition de
telles fonctions, nettement plus faible que la borne
triviale. Cette attaque suggère ainsi un nouveau critère de sécurité
qui porte sur la divisibilité du spectre de Walsh des fonctions de
tour utilisées dans les chiffrements itératifs par blocs. La deuxième
partie de la thèse porte sur l'étude des fonctions booléennes
symétriques, et en particulier sur l'existence éventuelle de
propriétés cryptographiques. À partir d'une propriété structurelle de
périodicité d'une représentation d'une fonction booléenne symétrique,
les propriétés de degré algébrique, d'équilibre, de résilience, de
critère de propagation et de non-linéarité ont été étudiées, ce qui a
permis d'améliorer les résultats existants. Par ailleurs, le calcul
explicite du spectre de Walsh des fonctions booléennes symétriques de
degré 2 et 3 a été réalisé, ainsi que la détermination de toutes les
fonctions symétriques équilibrées de degré inférieur ou égal à 7,
indépendamment du nombre de variables.

Dans de nombreux domaines scientifiques il est necessaire de compter des objets ou de realiser de longs calculs pour valider des modeles ou tester des conjectures. L'informatique theorique produit a cette fin de nombreux algorithmes et methodes ayant pour vocation d'aider a resoudre ces problemes. Il n'est pas surprenant que la combinatoire algebrique joue ici un grand role en offrant des moyens de compter des objets ou d'etablir des relations sur ces objets. Aussi, les liens entre combinatoire algebrique, fonctions symetriques et theorie des groupes conduisent a examiner l'application de ses methodes en physique theorique ou il est necessaire de produire des calculs de grande envergure sur les representations des groupes non compacts. La grande complexite de ces algorithmes requiert le developpement de nouvelles methodes pour calculer plus facilement la decomposition de certaines classes de produit tensoriels et plethysmes. Ceci permet alors la construction de nouveaux algorithmes plus efficaces utilises pour des calculs sur les modeles physiques. Cette these presente apres des rappels theoriques des techniques utilisees pour les calculs sur les representations de dimension infinie de certains groupes non compacts, parmi lesquels le groupe symplectique reel. Pour ce groupe nous donnons deux exemples d'illustration. Plus generalement sont presentes des exemples de calcul realises avec schur, programme augmente des resultats presentes. Pour certains cas on donne des exemples de programme maple montrant la simplicite des nouvelles methodes de calculs. De nouveaux resultats sont aussi presentes pour les representations irreductibles des groupes non compacts so*(2n), sp(2n, r) et u(p,q) et pour les sous-groupes finis du groupe exceptionnel g 2

Les travaux de la thèse se focalisent sur la protection des réseaux de distribution HTA en présence des générateurs distribués (éoliennes, fermes solaires,...). Dans un premier temps, un état de l’art a été réalisé sur les comportements des générateurs en creux de tension, leurs impacts sur le système de protection et les pistes de solution proposées pour y remédier. L’étape suivante est la mise au point d’algorithmes directionnels de détection de défauts, sans mesure de tension. Ces algorithmes s’appuient sur la décomposition en composantes symétriques des courants mesurés. Ces relais doivent empêcher le déclenchement intempestif de protections de surintensité dû au courant de défaut provenant des générateurs distribués. Ils sont moins coûteux par rapport à ceux traditionnels car les capteurs de tension, qui sont indispensables pour ces derniers, peuvent être enlevés. Après détection d’un défaut sur critère de seuil simple (max de I ou max de I résiduel), la direction est évaluée à l’aide d’un algorithme en delta basé sur les rapports courants inverse-homopolaire ou inverse-direct, selon le type de défaut (monophasé ou biphasé). En se basant sur ces rapports, un classifieur SVM (Support Vector Machines), entrainé préalablement à partir des simulations, donne ensuite l’estimation de la direction du défaut (amont ou aval par rapport au relais). La bonne performance de ces algorithmes a été montrée dans la thèse pour différents paramètres du réseau et en présence de différents types de générateurs. Le développement de tels algorithmes favorise la mise en œuvre des protections en réseau, qui pourraient être installées dans les futurs Smart Grids
This research focuses on the protection of MV distribution networks with Distributed Generators (DGs), such as wind farms or photovoltaic farms, etc. First, the state of art is carried out on fault behaviour of DGs, their impacts on protection system and the mitigation solutions. Next, algorithms are developed for directional relays without voltage sensors. Based on the symmetrical component method, these algorithms help the overcurrent protections to avoid the false tripping issue due to fault contribution of DGs. With the suppression of voltage sensors, such directional relays become cheaper in comparison with the traditional ones. Following the fault detection (the phase or residual current reaches the pick-up value) and depending on fault type (line-to-ground or line-to-line fault), the ratios between the variation (before and during fault) of negative-zero sequence or negative-positive sequence currents are calculated. From these ratios, a SVM (Support Vector Machines) classifier estimates the fault direction (upstream or downstream the detector). The classifier is trained beforehand from transient simulations. This survey shows good performances of the directional algorithms with different network parameters and different kinds of DGs. Such algorithms could be implemented in protections along the feeders in the future smart grids

Les réseaux de distribution moyenne tension sont victimes de défauts qui doivent être détectés et éliminés le plus rapidement possible, puis localisés plus précisément afin de permettre l'intervention d'équipes de réparation. Ce travail de recherche porte sur l'utilisation des composantes symétriques (homopolaires, directes et inverses) et harmoniques par des algorithmes de protection et de localisation de défauts. Une première partie théorique a permis de mettre en évidence les propriétés de la décomposition symétrique et harmonique des signaux tension et courant, et de calculer les composantes des courants issus des différents défauts considérés. Les algorithmes de protection directionnels développés par la suite ont comme principal avantage de pouvoir se passer de capteurs de tension dans la plupart des configurations. L'information harmonique, lorsqu'elle est disponible, amène à une amélioration des performances de ces algorithmes, sans pour autant être réellement indispensable. Les algorithmes de localisation mis au point ne requièrent pour fonctionner que la connaissance topologique du réseau et non pas celle des caractéristiques électriques de chaque tronçon. Ils aboutissent eux aussi à une diminution du nombre de capteurs nécessaires. Leur généralisation nous conduit à un système global de localisation applicable quels que soient le nombre et l'emplacement des capteurs. Tous ces algorithmes ont été testés et validés par simulation sur un grand nombre de configurations et de cas. Nous avons ainsi clairement identifié leurs limites et leurs performances. Deux régimes de neutre ont été pris en compte: neutre résistif et neutre compensé, ainsi que deux types de défaut: monophasé et biphasé
The medium voltage distribution networks are victims of faults which must be detected and eliminated as soon as possible, then more precisely localised in order to allow repairing staff to operate. This research work relates to the use of the symmetrical (homopolar, positive and onegative sequence) and harmonic components by protection and localization algorithms. A first theoretical part made it possible to highlight the properties of the symmetrical and harmonic decomposition of the voltage and current signals, and to calculate the components of the currents resulting from the various faults considered. The directional protection algorithms developed thereafter have as principal advantage of being able to work without voltage sensors in most configurations. Harmonic information, when it is available, leads to an improvement of the performances of these algorithms, without being really essential. The algorithms of localization developed require to function only the topological knowledge of the network and not that of the electric characteristics of each section. They also lead to a reduction in the number of sensors necessary. Their generalization leads us to a total system of applicable localization whatever the number and situation of the sensors. All these algorithms were tested and validated by simulation on a great number of configurations and cases. We thus clearly identified their limits and their performances. Two kind of neutral grounding were taken into account: resistive neutral and compensated neutral, like two types of fault : single-phase current and two-phase

L'objet de cette thèse concerne les propriétés du groupe symétrique à travers deux problèmes. Le premier consiste à étudier l'action du groupe symétrique sur la fraction (...). En appliquant certaines opérations sur les graphes et les cartes, nous donnons des algorithmes et des formules combinatoires pour déterminer complètement la fraction réduite suivante : (...). L'auteur C. Greene a introduit cette fraction rationnelle pour généraliser des identités liées a la règle de Murnaghan-Nakayama. Nous utilisons (...) pour établir un nouvel algorithme de décomposition en éléments simples à l'aide des graphes. Dans la seconde partie, nous cherchons a développer les puissances paires du Vandermonde au moyen de fonctions symétriques. En particulier, nous proposons une écriture hyperdéterminantale des coefficients du développement des puissances paires du Vandermonde dans la base des fonctions de Schur. Nous obtenons plusieurs identités reliant les puissances paires du Vandermonde et les polynômes de Jack. Puis nous introduisons une q-déformation des puissances paires du Vandermonde que nous exprimons grâce aux polynômes de Macdonald

La sécurité des transmissions et du stockage des données est devenue un enjeu majeur de ces dernières années et la cryptologie, qui traite de la protection algorithmique de l'information, est un sujet de recherche extrêmement actif. Elle englobe la conception d'algorithmes cryptographiques, appelée cryptographie, et l'analyse de leur sécurité, appelée cryptanalyse.Dans cette thèse, nous nous concentrons uniquement sur la cryptanalyse, et en particulier celle des algorithmes de chiffrement symétrique, qui reposent sur le partage d'un même secret entre l'entité qui chiffre l'information et celle qui la déchiffre. Dans ce manuscrit, trois attaques contre des algorithmes de chiffrement symétriques sont présentées. Les deux premières portent sur deux candidats de l'actuelle compétition cryptographique CAESAR, les algorithmes AEZ et NORX, tandis que la dernière porte sur l'algorithme Kravatte, une instance de la construction Farfalle qui utilise la permutation de la fonction de hachage décrite dans le standard SHA-3. Les trois algorithmes étudiés présentent une stratégie de conception similaire, qui consiste à intégrer dans une construction nouvelle une primitive, i.e. une fonction cryptographique élémentaire, déjà existante ou directement inspirée de travaux précédents.La compétition CAESAR, qui a débuté en 2015, a pour but de définir un portefeuille d'algorithmes recommandés pour le chiffrement authentifié. Les deux candidats étudiés, AEZ et NORX, sont deux algorithmes qui ont atteint le troisième tour de cette compétition. Les deux attaques présentées ici ont contribué à l'effort de cryptanalyse nécessaire dans une telle compétition. Cet effort n'a, en l'occurrence, pas permis d'établir une confiance suffisante pour justifier la présence des algorithmes AEZ et NORX parmi les finalistes.AEZ est une construction reposant sur la primitive AES, dont l'un des principaux objectifs est d'offrir une résistance optimale à des scénarios d'attaque plus permissifs que ceux généralement considérés pour les algorithmes de chiffrement authentifié. Nous montrons ici que dans de tels scénarios il est possible, avec une probabilité anormalement élevée, de retrouver l'ensemble des secrets utilisés dans l'algorithme.NORX est un algorithme de chiffrement authentifié qui repose sur une variante de la construction dite en éponge employée par exemple dans la fonction de hachage Keccak. Sa permutation interne est inspirée de celles utilisées dans BLAKE et ChaCha. Nous montrons qu'il est possible d'exploiter une propriété structurelle de cette permutation afin de récupérer la clé secrète utilisée. Pour cela, nous tirons parti du choix des concepteurs de réduire les marges de sécurité dans le dimensionnement de la construction en éponge.Enfin, la dernière cryptanalyse remet en cause la robustesse de l'algorithme Kravatte, une fonction pseudo-aléatoire qui autorise des entrées et sorties de taille variable. Dérivée de la permutation Keccak-p de SHA-3 au moyen de la construction Farfalle, Kravatte est efficace et parallélisable. Ici, nous exploitons le faible degré algébrique de la permutation interne pour mettre au jour trois attaques par recouvrement de clé : une attaque différentielle d'ordre supérieur, une attaque algébrique "par le milieu" et une attaque inspirée de la cryptanalyse de certains algorithmes de chiffrement à flot
Nowadays, cryptology is heavily used to protect stored and transmitted data against malicious attacks, by means of security algorithms. Cryptology comprises cryptography, the design of these algorithms, and cryptanalysis, the analysis of their security.In this thesis, we focus on the cryptanalysis of symmetric encryption algorithms, that is cryptographic algorithms that rely on a secret value shared beforehand between two parties to ensure both encryption and decryption. We present three attacks against symmetric encryption algorithms. The first two cryptanalyses target two high profile candidates of the CAESAR cryptographic competition, the AEZ and NORX algorithms, while the last one targets the Kravatte algorithm, an instance of the Farfalle construction based on the Keccak permutation. Farfalle is multipurpose a pseudo-random function (PRF) developed by the same designers' team as the permutation Keccak used in the SHA-3 hash function.The CAESAR competition, that began in 2015, aims at selecting a portfolio of algorithms recommended for authenticated encryption. The two candidates analysed, AEZ and NORX, reached the third round of the CAESAR competition but were not selected to be part of the finalists. These two results contributed to the cryptanalysis effort required in such a competition. This effort did not establish enough confidence to justify that AEZ and NORX accede to the final round of the competition.AEZ is a construction based on the AES primitive, that aims at offering an optimal resistance against more permissive attack scenarios than those usually considered for authenticated encryption algorithms. We show here that one can recover all the secret material used in AEZ with an abnormal success probability.NORX is an authenticated encryption algorithm based on a variant of the so-called sponge construction used for instance in the SHA-3 hash function. The internal permutation is inspired from the one of BLAKE and ChaCha. We show that one can leverage a strong structural property of this permutation to recover the secret key, thanks to the designers' non-conservative choice of reducing the security margin in the sponge construction.Finally, the last cryptanalysis reconsiders the robustness of the Kravatte algorithm. Kravatte is an efficient and parallelizable PRF with input and output of variable length. In this analysis, we exploit the low algebraic degree of the permutation Keccak used in Kravatte to mount three key-recovery attacks targeting different parts of the construction: a higher order differential attack, an algebraic meet-in-the-middle attack and an attack based on a linear recurrence distinguisher

Cette thèse se situe dans le domaine de la combinatoire algébrique et porte sur la construction de plusieurs structures combinatoires et algébriques sur différentes espèces d'arbres. Après avoir défini un analogue du monoïde plaxique dont les classes d'équivalence sont indexées par les couples d'arbres binaires jumeaux, nous proposons un analogue de la correspondance de Robinson-Schensted dans ce contexte. À partir de ce monoïde, nous construisons une sous-algèbre de Hopf de l'algèbre de Hopf des fonctions quasi-symétriques libres dont les bases sont indexées par les couples d'arbres binaires jumeaux. Ensuite, nous proposons un foncteur combinatoire de la catégorie des monoïdes vers la catégorie des opérades ensemblistes. En utilisant ce foncteur, nous construisons plusieurs opérades qui mettent en jeu divers objets combinatoires. Par le biais d'une construction qui à une opérade associe une algèbre de Hopf non commutative, nous obtenons à partir de l'une des opérades obtenue par notre construction, une algèbre de Hopf basée sur les forêts ordonnées d'arbres plans enracinés. Nous proposons une réalisation polynomiale de cette dernière. Finalement, nous établissons certaines propriétés vérifiées par les arbres binaires équilibrés dans le treillis de Tamari. Nous montrons que l'ensemble des arbres binaires équilibrés y est clos par intervalle et que les intervalles d'arbres binaires équilibrés ont la forme d'hypercubes. Dans l'objectif de dénombrer ces intervalles, nous introduisons une nouvelle sorte de grammaires d'arbres, les grammaires synchrones. Celles-ci permettent d'obtenir une équation fonctionnelle de point fixe pour la série génératrice des arbres qu'elles engendrent

Nous étudions les propriétés cryptographiques des fonctions booléennes telles que la résilience, le critère de propagation (PC) et le degré algébrique. Nous introduisons également un algorithme permettant d'augmenter la robustesse des systèmes de chiffrement symétrique en renforçant la confusion de ces systèmes. Nous présentons tout d'abord un état de l'art des bornes inférieures et supérieures sur le nombre de fonctions booléennes m-résilientes à n variables, que nous enrichissons de quelques compléments. Nous proposons ensuite une nouvelle borne supérieure sur le nombre de ces fonctions qui améliore significativement les bornes supérieures connues pour des ordres m compris entre n/2 et 3n/4. Puis, nous nous intéressons à la construction de fonctions booléennes équilibrées satisfaisant PC(l) et nous recherchons le plus haut degré algébrique atteint par ces fonctions. Nous étudions les fonctions de Maiorana-MacFarland dans ce contexte et construisons des fonctions booléennes équilibrées ayant un degré algébrique élevé et satisfaisant PC(l) pour des valeurs de l pour lesquelles de telles fonctions n'étaient pas connues auparavant. Nous étudions ensuite les fonctions booléennes symétriques. Nous montrons que celles qui vérifient PC(l) pour tout l fixé avec l>=2 sont les fonctions symétriques quadratiques. Ce résultat dont la preuve est très simple, implique en particulier comme corollaire immédiat un résultat connu : les seules fonctions symétriques courbes sont les fonctions symétriques quadratiques. Enfin, nous proposons une nouvelle brique de confusion pour le chiffrement symétrique.

La simulation numérique de la mise en forme est un outil indispensable pour réduire les coûts de conception dans l'industrie. Le logiciel d'analyse éléments finis FORGE3® fut créé dans ce but et il est capable de résoudre des problèmes thermomécaniques des grandes déformations complexes, en prenant en comptes des lois de comportement non-linéaires et plusieurs corps déformables. Dans la première partie de cette thèse on présente les travaux effectuées pour prendre en compte les symétries cycliques de répétition afin de réduire le temps CPU pour la simulation thermomécanique du forgeage des engrenages hélicoïdaux. Ce type de symétrie est traité comme une condition de contact bilatéral collant particulière entre deux faces de symétrie appartenant au même corps, à travers d'un algorithme maître-esclave. Ensuite une technique similaire est utilisée pour traiter le contact entre la pièce et les outils déformables tout en gardant un domaine réduit sur lequel on effectue les calculs. Une première série des tests montre la fiabilité de la méthode. La deuxième partie se focalise sur l'amélioration du traitement du contact entre les corps déformables, dont les maillages sont non coïncidents. On utilise une formulation nodale, quasi-symétrique pénalisée de la condition de contact. Cette approche nous permet d'appliquer des conditions aux limites sur tous les nœuds des interfaces sans surcontraindre le problème. Une deuxième série d'exemples académiques et industriels montre les avantages en terme de précision et de vitesse de convergence de la nouvelle méthode, d'une part, et la robustesse du code pour résoudre des problèmes industriels d'autre part.

Ce travail se divise en deux parties. Dans la première partie, nous généralisons le travail de Khuri-Makdisi qui décrit des algorithmes pour l'arithmétique des diviseurs sur une courbe sur un corps. Nous montrons que les analogues naturelles de ses résultats se vérifient pour les diviseurs de Cartier relatifs effectifs sur un schéma projectif, lisse et de dimension relative un sur un schéma affine noetherien quelconque, et que les analogues naturelles de ses algorithmes se vérifient pour une certaine classe d'anneaux de base. Nous présentons un formalisme pour tels anneaux qui sont caractérisés par l'existence d'un certain sous-ensemble des opérations standards de l'algèbre linéaire pour les modules projectifs sur ces anneaux.Dans la deuxième partie de ce travail, nous considérons un type de problème de Riemann-Roch pour les diviseurs sur certaines surfaces algébriques. Plus précisément, nous analysons les surfaces algébriques qui émanent d'un produit ou d'un produit symétrique d'une courbe hyperelliptique de genre supérieur à un sur un corps (presque) arbitraire. Les résultats principaux sont une décomposition des espaces de sections globales de certains diviseurs sur telles surfaces et des formules explicites qui décrivent les dimensions des espaces de sections de ces diviseurs. Dans le dernier chapitre, nous présentons un algorithme qui produit une base pour l'espace de sections globales d'un tel diviseur
The contribution of this thesis is divided naturally into two parts. In Part I we generalise the work of Khuri-Makdisi (2004) on algorithms for divisor arithmetic on curves over fields to more general bases. We prove that the natural analogues of the results of Khuri-Makdisi continue to hold for relative effective Cartier divisors on projective schemes which are smooth of relative dimension one over an arbitrary affine Noetherian base scheme and that natural analogues of the algorithms remain valid in this context for a certain class of base rings. We introduce a formalism for such rings,which are characterised by the existence of a certain subset of the usual linear algebra operations for projective modules over these rings.Part II of this thesis is concerned with a type of Riemann-Roch problem for divisors on certain algebraic surfaces. Specifically we consider algebraic surfaces arising as the square or the symmetric square of a hyperelliptic curve of genus at least two over an (almost) arbitrary field. The main results are a decomposition of the spaces of global sections of certain divisors on such surfaces and explicit formulæ for the dimensions of the spaces of sections of these divisors. In the final chapter we present an algorithm which generates a basis for the space of global sections of such a divisor

Les travaux exposés dans ce document portent essentiellement sur l'étude des cryptanalyses statistiques des chiffrements par blocs. Certains des résultats présentés sont cependant suffisamment généraux pour pouvoir être utilisés dans d'autres contextes comme les chiffrements à flot, les attaques par canaux cachés, ... Après avoir donné quelques notions de base nécessaires à la compréhension du document, l'on s'intéresse aux deux grandes familles de cryptanalyses statistiques : les cryptanalyses linéaires et cryptanalyses différentielles. Un état de l'art est effectué afin de pouvoir appréhender les différentes problématiques liées à ces cryptanalyses. Dans un second temps, le document présente les travaux effectués durant ces trois années de thèse. Ceux-ci portent en majorité sur l'analyse de la complexité en données et de la probabilité de succès des cryptanalyses statistiques. Est aussi présenté un algorithme de décodage des codes linéaires qui peut être utilisé pour retrouver la clef lors d'une cryptanalyse linéaire. Notons que deux attaques sont proposées sur des schémas de chiffrement reconnus. Une cryptanalyse linéaire multiple sur la totalité du DES et une cryptanalyse différentielle multiple sur 18 tours du chiffrement PRESENT. Ces deux attaques sont, à ce jour, les meilleures attaques connues de leur catégorie sur ces chiffrements. Enfin, un appendice contient tous les détails techniques et preuves calculatoires permettant d'obtenir les résultats importants de ce document.

Depuis 1980, l'idée d'utiliser des systèmes chaotiques pour la conception d'algorithmes de chiffrement/déchiffrement attire de plus en plus l'attention des chercheurs. La riche dynamique des systèmes chaotiques, telle que la sensibilité aux conditions initiales et aux paramètres de contrôle, l'imprédictibilité à long terme et à large spectre, permet d'avoir de fortes propriétés telles que la "confusion" et la "diffusion". La découverte de la possibilité d'une synchronisation du chaos en 1990, a ouvert les portes d'investigation aux chiffrements chaotiques. Par ailleurs, deux approches possibles coexistes pour la conception des cryptosystèmes basés chaos : les approches analogique et numérique. Les techniques de chiffrement analogiques sont basées principalement sur la recherche d'une synchronisation des signaux chaotiques générés analogiquement. Tandis que, les techniques numériques de chiffrement chaotique ne dépendent pas d'une synchronisation chaotique et peuvent être mis en ?uvre soit sous forme logicielle ou matérielle. Plusieurs contributions ont été proposées pour la réalisation de cryptosystèmes numériques. Cependant, la plupart d'entre elles sont vulnérables et cryptanalysées. Afin de concevoir des chiffrements numériques chaotiques plus robustes et répondant aux besoins de sécurité dans les systèmes embarqués, des mécanismes originaux doivent soigneusement être considérés au cours d'une conception. Toutefois, le problème de la dégradation dynamique d'une numérisation lors de la conception des systèmes chaotiques n'a pas été sérieusement considéré par la plupart des concepteurs d'algorithmes de chiffrements numériques. D'autre part, la quasi-totalité des cryptosystèmes numériques basés chaos proposés ne traitent l'aspect pas sécurité-embarquabilité. Cette thèse se concentre sur la conception et l'implantation numérique d'un nouveau cryptosystème basé chaos, dédié aux applications embarquées temps réel. Parmi les tâches développées au cours de ces travam de thèse, on trouve les solutions adaptées et performantes de résolution de ces deux principaux inconvénients, notamment pour les applications embarquées sécurisées. Nos principales contributions sont, premièrement la conception et l'implantation sur FPGA de nouveaux générateurs de clés pseudo-aléatoires basés sur des systèmes chaotiques (continus et discrets). Deuxièmement, l'analyse statistique détaillée de la sécurité de ces générateurs. Troisièmement, la conception d'un nouveau générateur de clés de chiffrement adéquat par comparaison et son intégration dans un cryptosystème symétrique par flot, tout en y incluant la résolution du problème de la synchronisation entre un émetteur et un récepteur. Quatrièmement, la mise en ?uvre matérielle du cryptosystème proposé pour des applications réelles de cryptage/décryptage. Plus précisément, le chiffrement/déchiffrement en temps réel de données audio, image et vidéo. De plus, une évaluation des performances et une comparaison avec d'autres algorithmes basés chaos sont réalisées afin d'extraire les points faibles et forts de l'approche proposée et dont le but d'en tirer des perspectives de travaux futurs
Since 1980, the idea of using dynamic systems with chaotic behaviour for the design of encryption/decryption algorithms has attracted increasing: attention from researchers. The strong dynamics of chaotic systems such as sensitivity to initial conditions and control parameters, the unpredictability in the long term and broad-spectrum can provide important properties such as confusion and diffusion usually meet in standard cryptography. In addition, there are two possible approaches for designing chaos-based cryptosystems: analog and digital. Analog encryption techniques are primarily based on chaos-synchronization, while the chaotic digital encryption approaches do not depend on the chaos-synchronization and can be implemented either in software or hardware. This thesis focuses on the digital design and implementation of a new cryptosystem based on chaos-synchronization. The discovery of the possibility of chaos synchronization in 1990 opens the door to investigation digital chaos-based encryption. Indeed, many contributions are made for many promising achievements of digital cryptosystems. However, a number of recently proposed digital chaotic ciphers have been shown that they are not secure enough and they are cryptanalyzed. In addition, in order to design more secure digital chaotic ciphers and meet the security requirements in embedded systems, rules and new mechanisms must be carefully considered to make up the flaws in the design flow. However, the problem of the degradation dynamics of chaotic systems has not been seriously considered by most designers of digital chaotic ciphers. Furthermore, most all the digital chaos-based cryptosystems proposed in the literature does not address the issue of real-time embedded applications. Consequently, the tasks of these thesis works focus on the design solutions providing the real secure suitable for embedded applications. Our contributions in this thesis are, firstly the design and hardware implementation on reconfigurable FPGA technology of a pseudo-random key generator based on chaotic systems (continuous and discrete). Secondly, the statistical analysis detailed security of the proposed generators. Thirdly, the development, the conception and the integration of a new chaotic generator in a symmetric stream cipher, includes the resolution problem of the chaos synchronization between the transmitter (encryption) and receiver (decryption). Fourthly, the hardware implementation of the proposed cryptosystem on real encryption applications. i.e. the encryption/decryption of real-time audio, image and video data. In addition, a performance evaluation and comparisons with previous conventional and chaos-based ciphers is performed in order to extract these weaknesses and strengths and define future work prospects

L'évolution des architectures de systèmes d'information n'a de cesse depuis l'avènement des télécommunications. Pour s'adapter aux nouvelles dimensions en nombre d'utilisateurs et taille des données, les systèmes d'information modernes sont répartis et hétérogènes. Ce constat ouvre de nouveaux enjeux de sûreté de fonctionnement pour les systèmes d'information, il s'agit de garantir disponibilité, fiabilité, innocuité, confidentialité, intégrité et maintenabilité tout au long du cycle de vie du système. C'est dans ce contexte que cette thèse a été conduite, les fruits des travaux de recherche gravitent autour de plusieurs notions de la sûreté de fonctionnement : – La confidentialité et l'intégrité avec le design, l'implémentation et l'étude de robustesse des chiffres symétriques par bloc. Les chiffres DES, AES et CS-Cipher ont été étudiés dans un spectre large rassemblant les implémentations logicielles et matérielles et leurs performances, la maléabilité des structures de diffusion, la cryptographie conventionnelle et les attaques par canaux auxiliaires. – La fiabilité avec le développement d'algorithmes auto-tolérants aux fautes et la certification de résultats. Cette étude est dédiée aux systèmes distribués de calcul tels que les clusters, les grilles ou encore les réseaux pair-à-pairs utilisés pour des calculs d'algèbre linéaires.

La cryptographie moderne est fondée sur la notion de sécurité computationnelle. Les niveaux de sécurité attendus des cryptosystèmes sont exprimés en nombre d'opérations ; une attaque est un algorithme d'une complexité inférieure à la borne attendue. Mais ces niveaux de sécurité doivent aujourd'hui prendre en compte une nouvelle notion d'algorithme : le paradigme du calcul quantique. Dans le même temps,la délégation grandissante du chiffrement à des puces RFID, objets connectés ou matériels embarqués pose de nouvelles contraintes de coût.Dans cette thèse, nous étudions la sécurité des cryptosystèmes à clé secrète face à un adversaire quantique.Nous introduisons tout d'abord de nouveaux algorithmes quantiques pour les problèmes génériques de k-listes (k-XOR ou k-SUM), construits en composant des procédures de recherche exhaustive.Nous présentons ensuite des résultats de cryptanalyse dédiée, en commençant par un nouvel outil de cryptanalyse quantique, l'algorithme de Simon hors-ligne. Nous décrivons de nouvelles attaques contre les algorithmes Spook et Gimli et nous effectuons la première étude de sécurité quantique du chiffrement AES. Dans un troisième temps, nous spécifions Saturnin, une famille de cryptosystèmes à bas coût orientés vers la sécurité post-quantique. La structure de Saturnin est proche de celle de l'AES et sa sécurité en tire largement parti
Modern cryptography relies on the notion of computational security. The level of security given by a cryptosystem is expressed as an amount of computational resources required to break it. The goal of cryptanalysis is to find attacks, that is, algorithms with lower complexities than the conjectural bounds.With the advent of quantum computing devices, these levels of security have to be updated to take a whole new notion of algorithms into account. At the same time, cryptography is becoming widely used in small devices (smart cards, sensors), with new cost constraints.In this thesis, we study the security of secret-key cryptosystems against quantum adversaries.We first build new quantum algorithms for k-list (k-XOR or k-SUM) problems, by composing exhaustive search procedures. Next, we present dedicated cryptanalysis results, starting with a new quantum cryptanalysis tool, the offline Simon's algorithm. We describe new attacks against the lightweight algorithms Spook and Gimli and we perform the first quantum security analysis of the standard cipher AES.Finally, we specify Saturnin, a family of lightweight cryptosystems oriented towards post-quantum security. Thanks to a very similar structure, its security relies largely on the analysis of AES

Nous étudions la sécurité de systèmes cryptographiques face à un adversaire muni d'un ordinateur quantique. En algorithmique quantique, nous avons étudié les problèmes de période et de décalage cachés, qui sont les seuls connus à ce jour ayant des applications en cryptographie et pour lesquels le meilleur algorithme quantique connu est plus que polynomialement plus rapide que le meilleur algorithme classique. Nous avons proposé des améliorations, de nouveaux compromis entre temps et mémoire classiques et quantiques, et étendu leur champ d'applications à des cas où seul un oracle classique est accessible. En cryptanalyse, en cryptographie symétrique, nous avons proposé des attaques de constructions symétriques utilisant des décalages cachés, et généralisé moult attaques exploitant des périodes cachées aux cas où l'accès à la construction est classique. Nous avons proposé une cryptanalyse quantique des différentes versions du chiffrement authentifié AEZ ainsi que des versions quantiques de multiples slide attacks, qui sont une famille classique d'attaques. Cette reformulation d'attaques dans le formalisme des périodes cachées nous ont permis de proposer de nouvelles attaques classiques sur différentes variantes du chiffrement MiMC. En cryptographie asymétrique, nous avons proposé une étude concrète et asymptotique de la sécurité quantique de schémas d'échange de clé à base d'isogénies. Enfin, nous avons étudié la sécurité dans des cadres où ces problèmes de structures cachées ne s'appliquent pas, avec la première analyse de sécurité quantique d'AES, le chiffrement symétrique le plus utilisé à l'heure actuelle
In this thesis, we study the security of cryptographic systems against an adversary who has access to a quantum computer. In quantum computing, we studied the hidden period and hidden shift problems, which are among the few known problems that have some applications in cryptogaphy and for which the best known quantum algorithm is more than polynomially faster than the best known classical algorithm. We proposed some improvements, new tradeoffs between classical and quantum time and memory, and extended their scope of applications to cases where only a classical oracle is available. In cryptanalysis, in symmetric cryptography, we proposed some attacks against symmetric constructions based on hidden shifts, and generalized many attacks using hidden periods to cases where the construction is only accessible classically. We proposed a quantum cryptanalysis of the different versions of the authenticated cipher AEZ and some quantum versions of multiple slide attacks, which are a classical family of cryptanalyses. This rewriting of attacks in the formalism of hidden periods has allowed us to propose a new classical attack against multiple variants of the cipher MiMC. In asymmetric cryptography, we proposed a concrete and asymptotic quantum security analysis of some isogeny-based key exchanges. Finally, we studied quantum security in some cases where these hidden structure problems do not apply, with in particular the first quantum security analysis of AES, the most used symmetric cipher to date

Un outil numérique destiné à la simulation instationnaire d'écoulements incompressibles visqueux partiellement confinés dans le cadre d'une approximation bi-dimensionnelle plane est présenté. Basé sur une méthode de Random Vortex hybride, il exploite l'équation de transport de la vorticité par une discrétisation adaptative sur des éléments lagrangiens à supports compacts. Des algorithmes destinés à améliorer la performance de calcul et la flexibilité sont également introduits. Une étude bibliographique raisonnée relative aux écoulements au travers d'expansions symétriques brusques est menée. Les paramètres déterminants sont dégagés. Différents régimes sont distingués : les transitions rencontrées à nombre de Reynolds croissant conduisent d'un écoulement recirculant symétrique stationnaire à des configurations asymétriques puis à l'apparition d'instabilités. Certaines justifications phénoménologiques sont proposées et les mécanismes mal cernés sont soulignés. La méthode numérique décrite est appliquée à la simulation de ces écoulements et les résultats obtenus comparés aux données expérimentales et numériques disponibles. Les prédictions effectuées sont en excellent accord dans le cas du régime symétrique stationnaire. A un nombre de Reynolds plus élevé, les calculs conduisent à des régimes asymétriques dont seule la nature est conforme aux résultats expérimentaux. Le déclenchement d'instabilités apparaît à une valeur de Reynolds plus faible qu'expérimentalement. Le rôle de la méthode numérique dans ces désaccords est suggéré, ainsi que d'éventuels palliatifs

Cette thèse est constituée de deux parties. La première traite de la méthode QR pour le calcul de valeurs propres de matrices quelconques, de tailles modérées. Les contributions originales à ce sujet sont a) une preuve rigoureuse de sa stabilité inverse, b) un nouveau critère d'arrêt justifié par une analyse mathématique. La seconde partie traite de la méthode de Yau et Lu pour le calcul de valeurs propres de matrices symétriques réelles de grandes tailles. Les contributions dans ce travail à ce sujet sont a) une compréhension mathématique accrue de la méthode, b) sa validation numérique, c) une proposition de parallélisation

Les travaux de recherche de cette thèse concernent l'encadrement de la constante de Markov Bernstein pour la norme L2 associée aux mesures de Jacobi et Gegenbauer généralisée. Ce travail est composé de deux parties : dans la première partie, nous avons développé une généralisation de l'algorithme qd pour les matrices symétriques définies positives à largeur de bande $\ell$ et nous avons construit l'algorithme qd pour les matrices de Jacobi par blocs. Ensuite, nous l'avons généralisé aux cas des matrices par bloc à largeur de bande $\ell$. Ces algorithmes nous permettent de trouver un majorant de la constante. Enfin, nous avons développé le déterminant caractéristique d'une matrice symétrique définie positive pentadiagonale, ce qui nous permet d'obtenir un minorant de la constante en utilisant la méthode de Newton. La deuxième partie est consacrée à l'application de tous les outils développés à l'encadrement de la constante de Markov Bernstein pour la norme L2 associée à la mesure de Gegenbauer généralisée.

Les algorithmes de chiffrement par blocs paramétrables constituent une généralisation des algorithmes de chiffrement par blocs classiques qui, en plus d'une clé et d'un message à chiffrer ou déchiffrer, admettent un paramètre additionnel, nommé tweak en anglais. Le rôle de ce paramètre additionnel est d'apporter une variabilité à l'algorithme de chiffrement, sans qu'il soit nécessaire de changer la clé ou de garder le tweak secret. Ce dernier doit également pouvoir être contrôlé par l'adversaire sans dégradation de la sécurité. Dans cette thèse nous nous intéressons à une classe particulière d'algorithmes de chiffrement par blocs, les algorithmes de chiffrement par blocs à clé alternée. Plusprécisément, nous étudions la sécurité du schéma d'Even-Mansour, qui constitue une abstraction de la structure de ces algorithmes dans le modèle de la permutation aléatoire, et cherchons à rendre ce schéma paramétrable tout en conservant de fortes garanties de sécurité. À cette fin, nous introduisons une nouvelle construction générique, baptiséeTEM, qui remplace les clés de tours de la construction d'Even-Mansour par une valeur qui dépend de la clé et du tweak, et en étudions la sécurité dans deux cas : lorsque le mixage de la clé et du tweak est linéaire ou lorsqu'il est très non-linéaire. Nos preuves de sécurité utilisent la technique des coefficients H, introduite par Jacques Patarin danssa thèse de doctorat, qui permet de transformer des problèmes cryptographiques en problèmes combinatoires sur des groupes finis
Tweakable block ciphers are a generalization of classical block ciphers which, in addition to a key and a plaintext or a ciphertext, take an additionnal parameter called a tweak. The goal of this new parameter is to bring variability to the block cipher without needing to change the key or to keep the tweak secret. The tweak should also be adversariallycontrollable without sacrificing security. In this thesis we study a particular class of block ciphers, namely key-alternating ciphers. More precisely, we study the security of the Even-Mansour scheme, which is an abstraction of these ciphers in the random permutation model, and seek to bring tweakability to this scheme while keeping strong security guarantees. To this end, we introduce a new generic construction, dubbed TEM, which replaces the round keys from the Even-Mansour construction by a value depending on both the key and the tweak, and study its security in two cases: when the tweak and key mixing is linear or highly non-linear. Our security proofs rely on the H-coefficients technique, a technique introduced by Jacques Patarin in his PhD thesis which transforms cryptographic problems into combinatorial problems in finite groups

Cette thèse présente de nouvelles méthodes markoviennes pour la séparation aveugle de mélanges linéaires instantanés des signaux unidimensionnels et des images. Dans la première partie, nous avons proposé plusieurs améliorations pour une méthode existante de séparation de signaux temporels. La nouvelle méthode exploite simultanément la non-gaussianité, l'autocorrélation et la nonstationnarité des sources. D'excellentes performances ont été obtenues pour la séparation de mélanges artificiels de signaux de parole, et nous avons réussi à séparer des mélanges réels de spectres astrophysiques. Une extension à la séparation des images a été ensuite proposée. La dépendance entre pixels a été modélisée par un champ de Markov à demi-plan non-symétrique. De très bonnes performances ont été obtenues pour la séparation de mélanges artificiels d'images naturelles et d'observations non-bruitées du satellite Planck. Les résultats pour un faible bruit sont acceptables
This thesis presents new Markovian methods for blind separation of instantaneous linear mixtures of one-dimensional signals and images. In the first part, we propose several improvements to an existent method for separating temporal signals. The new method exploits simultaneously non-Gaussianity, autocorrelation and non-stationarity of the sources. Excellent performance is obtained for the separation of artificial mixtures of speech signals, and we succeed to separate real mixtures of astrophysical spectra. An extension to image separation is then proposed. The dependence within the image pixels is modelled by non-symetrical half-plane Markov random fields. Very good performance is obtained for the separation of artificial mixtures of natural images and noiseless observations of the Planck satellite. The results obtained with a low level noise are acceptable