Littérature scientifique sur le sujet « Sécurité post-quantique »

Avec la possibilité de l’existence d’un ordinateur quantique, les primitives cryptographiques basées sur la théorie des nombres risquent de devenir caduques. Il devient donc important de concevoir des schémas résistants à ce nouveau type de menaces. Les réseaux euclidiens et les codes correcteurs d’erreurs sont deux outils mathématiques permettant de construire des problèmes d’algèbre linéaire, pour lesquels il n’existe aujourd’hui pas d’algorithme quantique permettant d’accélérer significativement leur résolution. Dans cette thèse, nous proposons quatre primitives cryptographiques de ce type : deux schémas de signatures (dont une signature traçable) basés sur les réseaux, un protocole de délégation de signature utilisant du chiffrement complètement homomorphe, et une nouvelle approche permettant de construire des cryptosystèmes très efficaces en pratique basés sur les codes. Ces contributions sont accompagnées de paramètres concrets permettant de jauger les coûts calculatoires des primitives cryptographique dans un monde post-quantique
In the likely event where a quantum computer sees the light, number theoretic based cryptographic primitives being actually in use might become deciduous. This results in an important need to design schemes that could face off this new threat. Lattices and Error Correcting Codes are mathematical tools allowing to build algebraic problems, for which – up to-date – no quantum algorithm significantly speeding up their resolution is known. In this thesis, we propose four such kind cryptographic primitives: two signatures schemes (among those a traceable one) based on lattices, a signature delegation protocol using fully homomorphic encryption, and a new framework for building very efficient and practical code-based cryptosystems. These contributions are fed with concrete parameters allowing to gauge the concrete costs of security in a post-quantum world

Ces dernières années la cryptographie a été chamboulée par l'arrivée des ordinateurs quantiques. En effet ceux-ci possèdent un très fort avantage pour casser les schémas cryptographique utilisés actuellement dans la quasi-totalité des communications sécurisées. Nous proposons dans cette thèse plusieurs constructions cryptographiques basées sur des outils mathématiques résistants à ces ordinateurs quantique, que sont les réseaux euclidiens. Tout d'abord nous construisons une signature de groupe, permettant à chaque membre composant un groupe donné de signer au nom du groupe tout en conservant son anonymat. Nous rajoutons une propriété supplémentaire qui est la "forward secrecy" qui sépare le temps en périodes durant lesquelles les clés secrètes des utilisateurs sont mises à jour. Nous proposons également un schéma de signature aveugle qui permet à un utilisateur de générer une signature sur un message de son choix de manière interactive avec un signeur qui possède la clé de signature. Nous améliorons l'état-de-l'art en proposant un schéma sans abandon et avec une sécurité plus efficace. Enfin, comme cas d'usage de la signature aveugle nous construisons un schéma de vote électronique à partir de cette primitive
The past few years have seen the rising of the quantum computers, that are a serious threat to nearly all the actual cryptographic schemes used in practice. In this thesis we propose some new constructions to prevent this obsolescence by building our schemes on the mathematical tool of lattices that is assumed post-quantum resistant. We firstly develop a group signature scheme, allowing each member composing the group to anonymously sign on the behalf of the group. We add a supplementary property, which is the froward secrecy. This property cut the time in periods, such that each secret key is updated when entering a new period. We also propose a blind signature scheme, which is an interactive protocol between an user, who wants to sign a message, with a signer who possesses the signing secret key. We improve the state-of-the art by proposing a constructions without any restart and with a more efficient security. Finally as a use case of the blind signature, we develop an evoting protocol that take as a basis the construction described above

Contrairement aux protocoles cryptographiques fondés sur la théorie des nombres, les systèmes de chiffrement basés sur les codes correcteurs d’erreurs semblent résister à l’émergence des ordinateurs quantiques. Un autre avantage de ces systèmes est que le chiffrement et le déchiffrement sont très rapides, environ cinq fois plus rapide pour le chiffrement, et 10 à 100 fois plus rapide pour le déchiffrement par rapport à RSA. De nos jours, l’intérêt de la communauté scientifique pour la cryptographie basée sur les codes est fortement motivé par la dernière annonce de la “National Institute of Standards and Technology" (NIST), qui a récemment initié le projet intitulé “Post-Quantum cryptography Project". Ce projet vise à définir de nouveaux standards pour les cryptosystèmes résistants aux attaques quantiques et la date limite pour la soumission des cryptosystèmes à clé publique est fixée pour novembre 2017. Une telle annonce motive certainement à proposer de nouveaux protocoles cryptographiques basés sur les codes, mais aussi à étudier profondément la sécurité des protocoles existants afin d’écarter toute surprise en matière de sécurité. Cette thèse suit cet ordre d’idée en étudiant la sécurité de plusieurs protocoles cryptographiques fondés sur la théorie des codes correcteurs d’erreurs. Nous avons commencé par l’étude de la sécurité d’une version modifiée du cryptosystème de Sidelnikov, proposée par Gueye et Mboup [GM13] et basée sur les codes de Reed-Muller. Cette modification consiste à insérer des colonnes aléatoires dans la matrice génératrice (ou de parité) secrète. La cryptanalyse repose sur le calcul de carrés du code public. La nature particulière des codes de Reed-Muller qui sont définis au moyen de polynômes multivariés binaires, permet de prédire les valeurs des dimensions des codes carrés calculés, puis permet de récupérer complètement en temps polynomial les positions secrètes des colonnes aléatoires. Notre travail montre que l’insertion de colonnes aléatoires dans le schéma de Sidelnikov n’apporte aucune amélioration en matière de sécurité. Le résultat suivant est une cryptanalyse améliorée de plusieurs variantes du cryptosystème GPT qui est un schéma de chiffrement en métrique rang utilisant les codes de Gabidulin. Nous montrons qu’en utilisant le Frobenius de façon appropriée sur le code public, il est possible d’en extraire un code de Gabidulin ayant la même dimension que le code de Gabidulin secret mais avec une longueur inférieure. Le code obtenu corrige ainsi moins d’erreurs que le code secret, mais sa capacité de correction d’erreurs dépasse le nombre d’erreurs ajoutées par l’expéditeur et par conséquent, un attaquant est capable de déchiffrer tout texte chiffré, à l’aide de ce code de Gabidulin dégradé. Nos résultats montrent qu’en fin de compte, toutes les techniques existantes visant à cacher la structure algébrique des codes de Gabidulin ont échoué. Enfin, nous avons étudié la sécurité du système de chiffrement de Faure-Loidreau [FL05] qui est également basé sur les codes de Gabidulin. Inspiré par les travaux précédents et, bien que la structure de ce schéma diffère considérablement du cadre classique du cryptosystème GPT, nous avons pu montrer que ce schéma est également vulnérable à une attaque polynomiale qui récupère la clé privée en appliquant l’attaque d’Overbeck sur un code public approprié. Comme exemple, nous arrivons en quelques secondes à casser les paramètres qui ont été proposés comme ayant un niveau de sécurité de 80 bits
Contrary to the cryptosystems based on number theory, the security of cryptosystems based on error correcting codes appears to be resistant to the emergence of quantum computers. Another advantage of these systems is that the encryption and decryption are very fast, about five times faster for encryption, and 10 to 100 times faster for decryption compared to RSA cryptosystem. Nowadays, the interest of scientific community in code-based cryptography is highly motivated by the latest announcement of the National Institute of Standards and Technology (NIST). They initiated the Post-Quantum cryptography Project which aims to define new standards for quantum resistant cryptography and fixed the deadline for public key cryptographic algorithm submissions for November 2017. This announcement motivates to study the security of existing schemes in order to find out whether they are secure. This thesis thus presents several attacks which dismantle several code-based encryption schemes. We started by a cryptanalysis of a modified version of the Sidelnikov cryptosystem proposed by Gueye and Mboup [GM13] which is based on Reed-Muller codes. This modified scheme consists in inserting random columns in the secret generating matrix or parity check matrix. The cryptanalysis relies on the computation of the square of the public code. The particular nature of Reed-Muller which are defined by means of multivariate binary polynomials, permits to predict the values of the dimensions of the square codes and then to fully recover in polynomial time the secret positions of the random columns. Our work shows that the insertion of random columns in the Sidelnikov scheme does not bring any security improvement. The second result is an improved cryptanalysis of several variants of the GPT cryptosystem which is a rank-metric scheme based on Gabidulin codes. We prove that any variant of the GPT cryptosystem which uses a right column scrambler over the extension field as advocated by the works of Gabidulin et al. [Gab08, GRH09, RGH11] with the goal to resist Overbeck’s structural attack [Ove08], are actually still vulnerable to that attack. We show that by applying the Frobeniusoperator appropriately on the public key, it is possible to build a Gabidulin code having the same dimension as the original secret Gabidulin code, but with a lower length. In particular, the code obtained by this way corrects less errors than thesecret one but its error correction capabilities are beyond the number of errors added by a sender, and consequently an attacker is able to decrypt any ciphertext with this degraded Gabidulin code. We also considered the case where an isometrictransformation is applied in conjunction with a right column scrambler which has its entries in the extension field. We proved that this protection is useless both in terms of performance and security. Consequently, our results show that all the existingtechniques aiming to hide the inherent algebraic structure of Gabidulin codes have failed. To finish, we studied the security of the Faure-Loidreau encryption scheme [FL05] which is also a rank-metric scheme based on Gabidulin codes. Inspired by our precedent work and, although the structure of the scheme differs considerably from the classical setting of the GPT cryptosystem, we show that for a range of parameters, this scheme is also vulnerable to a polynomial-time attack that recovers the private key by applying Overbeck’s attack on an appropriate public code. As an example we break in a few seconds parameters with 80-bit security claim

Craig Gentry a proposé en 2009 le premier schéma de chiffrement complétement homomorphe. Depuis, un effort conséquent a été, et est toujours, fourni par la communauté scientifique pour rendre utilisable ce nouveau type de cryptographie. Son côté révolutionnaire tient au fait qu'il permet d'effectuer des traitements directement sur des données chiffrées (sans que l’entité réalisant les traitements ait besoin de les déchiffrer). Plusieurs pistes se sont développées en parallèle, explorant d'un côté des schémas complétement homomorphes, plus flexibles entermes d'applications mais plus contraignants en termes de taille de données ou en coût de calcul, et de l'autre côté des schémas quelque peu homomorphes, moins flexibles mais aussi moins coûteux. Cette thèse, réalisée au sein de la chaire de cyberdéfense des systèmes navals, s’inscrit dans cette dynamique. Nous avons endossé divers rôles. Tout d’abord un rôle d'attaquant pour éprouver la sécurité des hypothèses sous-jacentes aux propositions. Ensuite, nous avons effectué un état de l’art comparatif des schémas quelque peu homomorphes les plus prometteurs afin d'identifier le(s) meilleur(s) selon les cas d’usages, et de donner des conseils dans le choix des paramètres influant sur leur niveau de sécurité, la taille des données chiffrées et le coût algorithmique des calculs. Enfin, nous avons endossé le rôle du concepteur en proposant un nouveau schéma complétement homomorphe performant, ainsi que son implémentation mise à disposition sur github
Craig Gentry presented in 2009 the first fully homomorphic encryption scheme. Since then, a tremendous effort has been, and still is, dedicated by the cryptographic community to make practical this new kind of cryptography. It is revolutionnary because it enables direct computation on encrypted data (without the need for the computing entity to decrypt them). Several trends have been developed in parallel, exploring on one side fully homomorphic encryption schemes, more versatile for applications but more costly in terms of time and memory. On the other side, the somewhat homomorphic encryption schemes are less flexible but more efficient. This thesis, achieved within the Chair of Naval Cyber Defence, contributes to these trends. We have endorsed different roles. First, an attacker position to assess the hardness of the security assumptions of the proposals. Then, we conducted a state-of-the-art of the most promising schemes in order to identify the best(s) depending on the use-cases and to give precise advice to appropriately set the parameters that drive security level, ciphertext sizes and computation costs. Last, we endorsed a designer role. We proposed a new powerful fully homomorphic encryption scheme together with its open-source implementation, available on github

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

Dans cette thèse nous nous intéressons à la cryptographie utilisant des codes correcteurs. Cette proposition, née du système de chiffrement à clef publique de McEliece, est à ce jour considérée comme post-quantique, ie : pouvant être utilisée sur ordinateur classique et résistante face à un adversaire muni d'un ordinateur quantique. Nous avons élaboré des attaques contre le schéma de signature RankSign, qui faisait partie des soumissions au processus de standardisation post-quantique du NIST, ainsi que contre le premier chiffrement fondée sur l'identité utilisant des codes. Nous proposons une nouvelle signature utilisant des codes : Wave. Nous avons introduit une nouvelle trappe, les codes (U,U+V)-généralisés. Nous montrons comment les utiliser pour décoder en des distances où le décodage est génériquement difficile. Nous montrons ensuite que pour ces codes la stratégie de Gentry Peikert et Vaikuntanathan, fructueuse en cryptographie utilisant des réseaux, peut être suivie. Cela est en partie dû à une méthode de rejet qui évite toute fuite d’information. Notre système repose sur le décodage générique à grande distance. Nous avons alors étudié la complexité de résolution de ce problème et proposé le meilleur algorithme connu à ce jour pour le résoudre. Nous étudions une des rares alternatives du décodage par ensemble d'information : le décodage statistique. Nous améliorons les techniques pour trouver des équations de parité de modéré puis nous donnons la première étude asymptotique de ce décodeur grâce à de nouveaux sur les polynômes de Krawtchouk. Nous montrons alors que le décodage statistique n'est pas compétitif avec les décodeurs par ensemble d'information
In this thesis we study code-based cryptography. By this term we mean the crypto-systems whose security relies on the generic decoding problem. The first of those systems is a public key encryption scheme proposed by McEliece in 1978. Four decades later, no attack is known to present a serious threat on the system, even on a quantum computer. This makes code-based cryptography a credible candidate for post-quantum cryptography. First we give attacks against the code-based signature scheme RankSign, which was proposed to the post-quantum standardization of the NIST, and against the first code-based Identity-Based-Encryption scheme. On the other hand we propose a new code-based signature scheme: Wave. For this design we introduced a new trapdoor, the family of generalized (U,U+V)-codes. We show how to decode them for weights such that the generic decoding problem is hard. Then we show how to follow the Gentry-Peikert and Vaikuntanathan strategy which has proved to be fruitful in lattice-based cryptography. This was done by avoiding any information leakage of signatures thanks to an efficient rejection sampling. Furthermore, for the first time we propose a crypto-system whose security relies on the generic decoding problem for high distances. We give in this thesis the best known algorithm to solve this problem. At last, we study one of the few alternatives to information set decoding: the statistical decoding. First we improve algorithms to compute parity-check equations of small or moderate weight and we make the first asymptotic study of its complexity. We show that statistical decoding is not competitive with information set decoding contrary to what was claimed. This study relies on new results about Krawtchouk polynomials

L'algorithme quantique de Shor peut être utilisé pour résoudre le problème de factorisation de grands entiers et le logarithme discret dans certains groupes. La sécurité des protocols cryptographiques à clé publique les plus répandus dépend de l'hypothèse que ces problèmes mathématiques soient difficiles à résoudre. Un ordinateur quantique suffisamment puissant pourrait donc constituer une menace pour la confidentialité et l'authenticité de la communication numérique sécurisée. La cryptographie post-quantique est basée sur des problèmes mathématiques qui sont difficile à résoudre même pour les ordinateurs quantiques, tels que Learning with Errors (LWE) et ses variants RLWE et MLWE. Dans cette thèse, nous présentons et comparons des implantations sur FPGA des algorithmes de chiffrement à clé publique. Nous discutons des compromis entre la sécurité, le temps de calcul et le coût en surface. Les implantations sont parallélisées afin d'obtenir une accélération plus importante. En outre, nous discutons de la sécurité matérielle des implantations, et proposons des protections contre des attaques par canaux auxilliares. Nous considerons des contremesures de l'état de l'art, telles que le masquage et le blindage, et proposons des améliorations à ces algorithmes. Nous proposons également de nouvelles protections basées sur la représentation redondante des nombres et sur des permutations aléatoires des opérations de calcul. Toutes ces protections sont implantées sur FPGA dans le but de comparer leur coût en surface et le surcoût en temps de calcul
Shor's quantum algorithm can be used to efficiently solve the integer factorisation problem and the discrete logarithm in certain groups. The security of the most commonly used public key cryptographic protocols relies on the conjectured hardness of exactly these mathematical problems. A sufficiently large quantum computer could therefore pose a threat to the confidentiality and authenticity of secure digital communication. Post quantum cryptography relies on mathematical problems that are computationally hard for quantum computers, such as Learning with Errors (LWE) and its variants RLWE and MLWE. In this thesis, we present and compare FPGA implementations of LWE, RLWE and MLWE based public key encryption algorithms. We discuss various trade-offs between security, computation time and hardware cost. The implementations are parallelized in order to obtain maximal speed-up. We show that MLWE has the best performance in terms of computation time and area utilization, and can be parallelized more efficiently than RLWE. We also discuss hardware security and propose countermeasures against side channel attacks for RLWE. We consider countermeasures from the state of the art, such as masking and blinding, and propose improvements to these algorithms. Moreover, we propose new countermeasures based on redundant number representation and the random shuffling of operations. All countermeasures are implemented on FPGA to compare their cost and computation time overhead. Our proposed protection based on redundant number representation is particularly flexible, in the sens that it can be implemented for various degrees of protection at various costs

La cryptographie basée sur les codes n'est pas largement déployée dans la pratique. Principalement à cause de son inconvénient majeur: des tailles de clés énormes. Dans cette thèse, nous proposons deux approches différentes pour résoudre ce problème. Le premier utilise des codes algébriques, présentant un moyen de construire des codes de Goppa qui admettent une représentation compacte. Ce sont les Codes de Goppa p-adiques. Nous montrons comment construire ces codes pour instancier des systèmes de chiffrement à clé publique, comment étendre cette approche pour instancier un schéma de signature et, enfin, comment généraliser cet approche pour définir des codes de caractéristique plus grande au égale à deux. En résumé, nous avons réussi à produire des clés très compact basé sur la renommée famille de codes de Goppa. Bien qu'efficace, codes de Goppa p-adiques ont une propriété non souhaitable: une forte structure algébrique. Cela nous amène à notre deuxième approche, en utilisant des codes LDPC avec densité augmentée, ou tout simplement des codes MDPC. Ce sont des codes basés sur des graphes, qui sont libres de structure algébrique. Il est très raisonnable de supposer que les codes MDPC sont distinguable seulement en trouvant des mots de code de poids faible dans son dual. Ceci constitue un avantage important non seulement par rapport à tous les autres variantes du système de McEliece à clés compactes, mais aussi en ce qui concerne la version classique basée sur les codes de Goppa binaires. Ici, les clés compactes sont obtenus en utilisant une structure quasi-cyclique.

La cryptographie à base de codes correcteurs, introduite par Robert McEliece en 1978, est un candidat potentiel au remplacement des primitives asymétriques vulnérables à l'émergence d'un ordinateur quantique. Elle possède de plus une sécurité classique éprouvée depuis plus de trente ans, et permet des fonctions de chiffrement très rapides. Son défaut majeur réside dans la taille des clefs publiques. Pour cette raison, plusieurs variantes du schéma de McEliece pour lesquelles les clefs sont plus aisées à stocker ont été proposées ces dernières années. Dans cette thèse, nous nous intéressons aux variantes utilisant soit des codes alternants avec symétrie, soit des codes de Goppa sauvages. Nous étudions leur résistance aux attaques algébriques et exhibons des faiblesses parfois fatales. Dans chaque cas, nous révélons l'existence de structures algébriques cachées qui nous permettent de décrire la clef secrète par un système non-linéaire d'équations en un nombre de variables très inférieur aux modélisations antérieures. Sa résolution par base de Gröbner nous permet de trouver la clef secrète pour de nombreuses instances hors de portée jusqu'à présent et proposés pour un usage à des fins cryptographiques. Dans le cas des codes alternants avec symétrie, nous montrons une vulnérabilité plus fondamentale du processus de réduction de taille de la clef.Pour un déploiement à l'échelle industrielle de la cryptographie à base de codes correcteurs, il est nécessaire d'en évaluer la résistance aux attaques physiques, qui visent le matériel exécutant les primitives. Nous décrivons dans cette optique un algorithme de déchiffrement McEliece plus résistant que l'état de l'art
Code-based cryptography, introduced by Robert McEliece in 1978, is a potential candidate to replace the asymetric primitives which are threatened by quantum computers. More generral, it has been considered secure for more than thirty years, and allow very vast encryption primitives. Its major drawback lies in the size of the public keys. For this reason, several variants of the original McEliece scheme with keys easier to store were proposed in the last years.In this thesis, we are interested in variants using alternant codes with symmetries and wild Goppa codes. We study their resistance to algebraic attacks, and reveal sometimes fatal weaknesses. In each case, we show the existence of hidden algebraic structures allowing to describe the secret key with non-linear systems of multivariate equations containing fewer variables then in the previous modellings. Their resolutions with Gröbner bases allow to find the secret keys for numerous instances out of reach until now and proposed for cryptographic purposes. For the alternant codes with symmetries, we show a more fondamental vulnerability of the key size reduction process. Prior to an industrial deployment, it is necessary to evaluate the resistance to physical attacks, which target device executing a primitive. To this purpose, we describe a decryption algorithm of McEliece more resistant than the state-of-the-art.Code-based cryptography, introduced by Robert McEliece in 1978, is a potential candidate to replace the asymetric primitives which are threatened by quantum computers. More generral, it has been considered secure for more than thirty years, and allow very vast encryption primitives. Its major drawback lies in the size of the public keys. For this reason, several variants of the original McEliece scheme with keys easier to store were proposed in the last years.In this thesis, we are interested in variants using alternant codes with symmetries and wild Goppa codes. We study their resistance to algebraic attacks, and reveal sometimes fatal weaknesses. In each case, we show the existence of hidden algebraic structures allowing to describe the secret key with non-linear systems of multivariate equations containing fewer variables then in the previous modellings. Their resolutions with Gröbner bases allow to find the secret keys for numerous instances out of reach until now and proposed for cryptographic purposes. For the alternant codes with symmetries, we show a more fondamental vulnerability of the key size reduction process. Prior to an industrial deployment, it is necessary to evaluate the resistance to physical attacks, which target device executing a primitive. To this purpose, we describe a decryption algorithm of McEliece more resistant than the state-of-the-art

Le premier protocole cryptographique basé sur les codes correcteurs d'erreurs a été proposé en 1978 par Robert McEliece. La cryptographie basée sur les codes est dite post-quantique car il n'existe pas à l'heure actuelle d'algorithme capable d'attaquer ce type de protocoles en temps polynomial, même en utilisant un ordinateur quantique, contrairement aux protocoles basés sur des problèmes de théorie des nombres. Toutefois, la sécurité du cryptosystème de McEliece ne repose pas uniquement sur des problèmes mathématiques. L'implantation, logicielle ou matérielle, a également un rôle très important pour sa sécurité et l'étude de celle-ci face aux attaques par canaux auxiliaires/cachés n'a débuté qu'en 2008. Des améliorations sont encore possibles. Dans cette thèse, nous proposons de nouvelles attaques sur le déchiffrement du cryptosystème de McEliece, utilisé avec les codes de Goppa classiques, ainsi que des contre-mesures correspondantes. Les attaques proposées sont des analyses de temps d'exécution ou de consommation d'énergie. Les contre-mesures associées reposent sur des propriétés mathématiques et algorithmiques. Nous montrons qu'il est essentiel de sécuriser l'algorithme de déchiffrement en le considérant dans son ensemble et non pas seulement étape par étape
The first cryptographic protocol based on error-correcting codes was proposed in 1978 by Robert McEliece. Cryptography based on codes is called post-quantum because until now, no algorithm able to attack this kind of protocols in polynomial time, even using a quantum computer, has been proposed. This is in contrast with protocols based on number theory problems like factorization of large numbers, for which efficient Shor's algorithm can be used on quantum computers. Nevertheless, the McEliece cryptosystem security is based not only on mathematical problems. Implementation (in software or hardware) is also very important for its security. Study of side-channel attacks against the McEliece cryptosystem have begun in 2008. Improvements can still be done. In this thesis, we propose new attacks against decryption in the McEliece cryptosystem, used with classical Goppa codes, including corresponding countermeasures. Proposed attacks are based on evaluation of execution time of the algorithm or its power consumption analysis. Associate countermeasures are based on mathematical and algorithmic properties of the underlying algorithm. We show that it is necessary to secure the decryption algorithm by considering it as a whole and not only step by step