Nous avons développé un cryptosystème à clé symétrique hautement sécuritaire qui est basé sur un réseau de substitutions et de permutations. Il possède deux particularités importantes. Tout d'abord, il utilise de très grandes S-Boxes incompressibles dont la taille peut varier entre 256 Kb et 32 Gb bits d'entrée et qui sont générées aléatoirement. De plus, la phase de permutation est effectuée par un ensemble de fonctions linéaires choisies aléatoirement parmi toutes les fonctions linéaires possibles. Chaque fonction linéaire est appliquée sur tous les bits du bloc de message. Notre protocole possède donc une structure simple qui garantit l'absence de portes dérobées. Nous allons expliquer que notre cryptosystème résiste aux attaques actuellement connues telles que la cryptanalyse linéaire et la cryptanalyse différentielle. Il est également résistant à toute forme d'attaque basée sur un biais en faveur d'une fonction simple des S-Boxes. / We developed a new symmetric-key algorithm that is highly secure. Our algorithm is SPN-like but with two main particularities. First of all, we use very large random incompressible s-boxes. The input size of our s-boxes vary between 256 Kb and 32 Gb.Secondly, for the permutation part of the algorithm, we use a set of random linear functions chosen uniformly and randomly between every possible fonctions. The input of these functions is all the bits of the block of messages to encode. Our system has a very simple structure that guarantees that there are no trap doors in it. We will explain how our algorithm is resistant to the known attacks, such as linear and differential cryptanalysis. It is also resistant to any attack based on a bias of the s-boxes to a simple function.

Les fonctions de F_q dans lui-même sont des objets étudiés dans de divers domaines tels que la cryptographie, la théorie des codes correcteurs d'erreurs, la géométrie finie ainsi que la géométrie algébrique. Il est bien connu que ces fonctions sont en correspondance exacte avec les polynômes en une variable à coefficients dans F_q. Nous étudierons trois classes de polynômes particulières: les polynômes Presque Parfaitement Non linéaires (Almost Perfect Nonlinear (APN)), les polynômes planaires ou parfaitement non linéaire (PN) et les o-polynômes.Les fonctions APN sont principalement étudiées pour leurs applications en cryptographie. En effet, ces fonctions sont celles qui offre la meilleure résistance contre la cryptanalyse différentielle.Les polynômes PN et les o-polynômes sont eux liés à des problèmes célèbres de géométrie finie. Les premiers décrivent des plans projectifs et les seconds sont en correspondance directe avec les ovales et hyperovales de P^2(F_q). Néanmoins, leurs champ d'application a été récemment étendu à la cryptographie symétrique et à la théorie des codes correcteurs d'erreurs.L'un des moyens utilisé pour compléter la classification est de considérer les polynômes présentant l'une des propriétés recherchées sur une infinité d'extension de F_q. Ces fonctions sont appelées fonction APN (respectivement PN ou o-polynômes) exceptionnelles.Nous étendrons la classification des polynômes APN et PN exceptionnels et nous donneront une description complète des o-polynômes exceptionnels. Les techniques employées sont basées principalement sur la borne de Lang-Weil et sur des méthodes élémentaires. / Functions from F_q to itself are interesting objects arising in various domains such as cryptography, coding theory, finite geometry or algebraic geometry. It is well known that these functions admit a univariate polynomial representation. There exists many interesting classes of such polynomials with plenty of applications in pure or applied maths. We are interested in three of them: Almost Perfect Nonlinear (APN) polynomials, Planar (PN) polynomials and o-polynomials. APN polynomials are mostly used in cryptography to provide S-boxes with the best resistance to differential cryptanalysis and in coding theory to construct double error-correcting codes. PN polynomials and o-polynomials first appeared in finite geometry. They give rise respectively to projective planes and ovals in P^2(F_q). Also, their field of applications was recently extended to symmetric cryptography and error-correcting codes.A complete classification of APN, PN and o-polynomials is an interesting open problem that has been widely studied by many authors. A first approach toward the classification was to consider only power functions and the studies were recently extended to polynomial functions.One way to face the problem of the classification is to consider the polynomials that are APN, PN or o-polynomials over infinitely many extensions of F_q, namely, the exceptional APN, PN or o-polynomials.We improve the partial classification of exceptional APN and PN polynomials and give a full classification of exceptional o-polynomials. The proof technique is based on the Lang-Weil bound for the number of rational points in algebraic varieties together with elementary methods.

Un code correcteur d'erreur ajoute de la redondance à un message afin de pouvoir corriger celui-ci lorsque des erreurs se sont introduites pendant la transmission. Les codes convolutifs sont des codes performants, et par conséquent, souvent utilisés. Le principe d'un code convolutif consiste à se fixer une fonction de transfert définie sur le groupe des entiers relatifs et à effectuer la convolution d'un message avec cette fonction de transfert. Ces codes ne protègent pas le message d'une interception par une tierce personne. C'est pourquoi nous proposons dans cette thèse, des codes convolutifs avec des propriétés cryptographiques, définis sur des groupes non-commutatifs. Nous avons tout d'abord étudié les codes définis sur le groupe diédral infini, qui, malgré de bonnes performances, n'ont pas les propriétés cryptographiques recherchées. Nous avons donc étudié ensuite des codes convolutifs en bloc sur des groupes finis, avec un encodage variable dans le temps. Nous avons encodé chaque message sur un sous-ensemble du groupe différent à chaque encodage. Ces sous-ensembles sont générés de façon chaotique à partir d'un état initial, qui est la clé du cryptosystème symétrique induit par le code. Nous avons étudié plusieurs groupes et plusieurs méthodes pour définir ces sous-ensembles chaotiques. Nous avons étudié la distance minimale des codes que nous avons conçus et montré qu'elle est légèrement plus petite que la distance minimale des codes en blocs linéaires. Cependant, nous avons, en plus, un cryptosystème symétrique associé à ces codes. Ces codes convolutifs non-commutatifs sont donc un compromis entre correction d'erreur et sécurité. / An error correcting code adds redundancy to a message in order to correct it when errors occur during transmission.Convolutional codes are powerful ones, and therefore, often used. The principle of a convolutional code is to perform a convolution product between a message and a transfer function, both defined over the group of integers. These codes do not protect the message if it is intercepted by a third party. That is why we propose in this thesis, convolutional codes with cryptographic properties defined over non-commutative groups. We first studied codes over the infinite dihedral group, which despite good performance, do not have the desired cryptographic properties. Consequently, we studied convolutional block codes over finite groups with a time-varying encoding. Every time a message needs to be encoded, the process uses a different subset of the group. These subsets are chaotically generated from an initial state. This initial state is considered as the symmetric key of the code-induced cryptosystem. We studied many groups and many methods to define these chaotic subsets. We examined the minimum distance of the codes we conceived and we showed that it is slightly smaller than the minimum distance of the linear block codes. Nevertheless, our codes have, in addition, cryptographic properties that the others do not have. These non-commutative convolutional codes are then a compromise between error correction and security.

Cette thèse se situe dans la cryptanalyse physique des algorithmes de chiffrement par blocs. Un algorithme cryptographique est conçu pour être mathématiquement robuste. Cependant, une fois implémenté dans un circuit, il est possible d'attaquer les failles de ce dernier. Par opposition à la cryptanalyse classique, on parle alors d'attaques physiques. Celles-ci ne permettent pas d'attaquer l'algorithme en soi, mais son implémentation matérielle. Il existe deux grandes familles d'attaques physiques différentes : les attaques par observation du circuit durant le chiffrement, et les attaques par injections de fautes, qui analysent l'effet d'une perturbation intentionnelle sur le fonctionnement du circuit. Les attaques physiques ont deux types d'objectifs : rechercher la clé ou faire de la rétro-conception (retrouver une partie d'un algorithme de chiffrement privé, ex : s-boxes modifiées). Bien que leurs principes semblent distincts, cette thèse présente un formalisme qui permet d'unifier toutes ces attaques. L'idée est de décrire les attaques physiques de façon similaire, afin de pouvoir les comparer. De plus, ce formalisme a permis de mettre en évidence de nouvelles attaques. Des travaux novateurs ayant pour objet de retrouver la clé de chiffrement d'un AES, uniquement avec la consommation de courant ont été menés. Une nouvelle attaque de type FIRE (Fault Injection for Reverse Engineering) pour retrouver les s-boxes d'un pseudo DES est également présentée dans la thèse. Ce travail a abouti sur une réflexion plus générale, sur les attaques par injections de fautes dans les schémas de Feistel classiques et généralisés. / The main subject of this work is the physical cryptanalysis of blocks ciphers. Even if cryptographic algorithms are properly designed mathematically, they may be vulnerable to physical attacks. Physical attacks are mainly divided in two families: the side channel attacks which are based on the observation of the circuit behaviour during the computation, and the fault injection attacks which consist in disturbing the computation in order to alter the correct progress of the algorithm. These attacks are used to target the cipher key or to reverse engineer the algorithm. A formalism is proposed in order to describe the two families in a unified way. Unifying the different attacks under a same formalism allows to deal with them with common mathematical tools. Additionally, it allows a comparison between different attacks. Using this framework, a generic method to assess the vulnerabilities of generalized Feistel networks to differential fault analysis is presented. This work is furthermore extended to improve a FIRE attack on DES-like cryptosystems with customized s-boxes.

Cette thèse aborde la conception et les contremesures permettant d'améliorer le calcul cryptographique matériel léger. Parce que la cryptographie (et la cryptanalyse) sont de nos jours de plus en plus omniprésentes dans notre vie quotidienne, il est crucial que les nouveaux systèmes développés soient suffisamment robustes pour faire face à la quantité croissante de données de traitement sans compromettre la sécurité globale. Ce travail aborde de nombreux sujets liés aux implémentations cryptographiques légères. Les principales contributions de cette thèse sont : - Un nouveau système d'accélération matérielle cryptographique appliqué aux codes BCH ; - Réduction de la consommation des systèmes embarqués et SoCs ; - Contre-mesures légères des attaques par canal auxiliaire applicables à l'algorithme de chiffrement reconfigurable AES ;- CSAC : Un pare-feu sécurisé sur la puce cryptographique ; - Attaques par analyse fréquentielle ; - Un nouveau protocole à divulgation nulle de connaissance appliquée aux réseaux de capteurs sans fil ; - OMD : Un nouveau schéma de chiffrement authentifié. / This thesis addresses lightweight hardware design and countermeasures to improve cryptographic computation. Because cryptography (and cryptanalysis) is nowadays becoming more and more ubiquitous in our daily lives, it is crucial that newly developed systems are robust enough to deal with the increasing amount of processing data without compromising the overall security. This work addresses many different topics related to lightweight cryptographic implementations. The main contributions of this thesis are: - A new cryptographic hardware acceleration scheme applied to BCH codes; - Hardware power minimization applied to SoCs and embedded devices; - Timing and DPA lightweight countermeasures applied to the reconfigurable AES block cipher; - CSAC: A cryptographically secure on-chip firewall; - Frequency analysis attack experiments; - A new zero-knowledge zero-knowledge protocol applied to wireless sensor networks; - OMD: A new authenticated encryption scheme.

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.