La cryptographie basée sur la théorie des nombres est menacée par l’avènement de l’ordinateur quantique. Il devient alors urgent d’imaginer de nouvelles techniques pour nous protéger contre cette menace. Certains cryptosystèmes prétendent resister à des attaques quantiques, notamment en basant leur sécurité sur la difficulté du problème de décodage. Dans ce projet, nous tentons de mieux comprendre ce problème et d’en mesurer sa complexité avec précision pour ainsi mieux calibrer les cryptosystèmes de demain.
La cryptographie basée sur la théorie des nombres est menacée par l’avènement de l’ordinateur quantique. Il devient alors urgent d’imaginer de nouvelles techniques pour nous protéger contre cette menace. Certains cryptosystèmes prétendent resister à des attaques quantiques, notamment en basant leur sécurité sur la difficulté du problème de décodage. Dans ce projet, nous tentons de mieux comprendre ce problème et d’en mesurer sa complexité avec précision pour ainsi mieux calibrer les cryptosystèmes de demain.
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.
Cryptanalyse quantique des réseaux et codes L'émergence de l'ordinateur quantique impose protéger nos systèmes informatiques face à ces nouvelles attaques quantiques. De nombreux schémas cryptographiques post-quantiques reposent sur la difficulté de résoudre des problèmes provenant des théories des réseaux euclidiens et de codes. Dans cette thèse, nous étudions la complexité du problème de trouver un vecteur court (SVP) dans un réseau. Nous améliorons l'attaque quantique contre SVP grâce à un nouvel algorithme de crible utilisant des marches quantiques et des techniques de filtrage. Nous proposons aussi des algorithmes de k-crible atteignant de meilleurs compromis temps-mémoire en introduisant une nouvelle technique de filtrage adaptée au k-crible. Nous nous intéressons aussi à la complexité du problème de décodage, sur lequel repose notamment la signature électronique Wave. Nous décrivons une attaque quantique pour contrefaire des signatures, et estimons sa sécurité face aux meilleurs attaques classiques et quantiques connues.
Sécurité étendue de la cryptographie fondée sur les réseaux Euclidiens La cryptographie fondée sur les réseaux euclidiens représente une alternative prometteuse à la cryptographie asymétrique utilisée actuellement, en raison de sa résistance présumée à un ordinateur quantique universel. Cette nouvelle famille de schémas asymétriques dispose de plusieurs atouts parmi lesquels de fortes garanties théoriques de sécurité, un large choix de primitives et, pour certains de ses représentants, des performances comparables aux standards actuels. Une campagne de standardisation post-quantique organisée par le NIST est en cours et plusieurs schémas utilisant des réseaux euclidiens font partie des favoris. La communauté scientifique a été encouragée à les analyser car ils pourraient à l'avenir être implantés dans tous nos systèmes. L'objectif de cette thèse est de contribuer à cet effort. Nous étudions la sécurité de ces nouveaux cryptosystèmes non seulement au sens de leur résistance à la cryptanalyse en ''boîte noire'' à l'aide de moyens de calcul classiques, mais aussi selon un spectre plus large de modèles de sécurité, comme les attaques quantiques, les attaques supposant des failles d'utilisation, ou encore les attaques par canaux auxiliaires. Ces différents types d’attaques ont déjà été largement formalisés et étudiés par le passé pour des schémas asymétriques et symétriques pré-quantiques. Dans ce mémoire, nous analysons leur application aux nouvelles structures induites par les réseaux euclidiens. Notre travail est divisé en deux parties complémentaires : les contremesures et les attaques. La première partie regroupe nos contributions à l'effort actuel de conception de nouvelles protections algorithmiques afin de répondre aux nombreuses publications récentes d’attaques par canaux auxiliaires. Les travaux réalisés en équipe auxquels nous avons pris part on abouti à l'introduction de nouveaux outils mathématiques pour construire des contre-mesures algorithmiques, appuyées sur des preuves formelles, qui permettent de prévenir systématiquement les attaques physiques et par analyse de temps d'exécution. Nous avons ainsi participé à la protection de plusieurs schémas de signature fondés sur les réseaux euclidiens comme GLP, BLISS, qTesla ou encore Falcon. Dans une seconde partie consacrée à la cryptanalyse, nous étudions dans un premier temps de nouvelles attaques qui tirent parti du fait que certains schémas de chiffrement à clé publique ou d'établissement de clé peuvent échouer avec une faible probabilité. Ces échecs sont effectivement faiblement corrélés au secret. Notre travail a permis d’exhiber des attaques dites « par échec de déchiffrement » dans des modèles de failles d'utilisation ou des modèles quantiques. Nous avons d'autre part introduit un outil algorithmique de cryptanalyse permettant d’estimer la sécurité du problème mathématique sous-jacent lorsqu’une information partielle sur le secret est donnée. Cet outil s’est avéré utile pour automatiser et améliorer plusieurs attaques connues comme des attaques par échec de déchiffrement, des attaques classiques ou encore des attaques par canaux auxiliaires.
La cryptographie classique, aujourd’hui basée sur la complexité, doit faire face à la menace à moyen terme des ordinateurs quantiques. Une technologie prometteuse est la distribution quantique de clé qui assure une sécurité absolue basée sur les lois de la Physique Quantique. L’objectif premier de cet article est d’expliquer les fondements et les enjeux de la distribution quantique de clé en des termes simples et compréhensibles par tous. L’article présente les protocoles les plus connus et discute leur mise en place pratique dans différents milieux, ainsi que les enjeux sous-jacents.
Quelque soit l’environnement dans lequel se deroule une communication, la securite reste un pilier necessaire pour le bon deroulement de cette communication. Afin d’assurer un certain niveau de securite, la confidentialite est un element essentiel a assurer. Ce sont les techniques de cryptographie qui l’assurent. La pierre angulaire des techniques cryptographiques est la gestion de cle. Plusieurs protocoles ont ete proposes pour assurer une bonne gestion de cle dans un groupe, mais leur securite se base sur la complexite computationnelle. La distribution de cle quantique, par abus dite cryptographie quantique, est une primitive cryptographique basee sur les lois de la mecanique quantique, permettant d’etablir une cle secrete commune entre les traditionnels correspondants Alice et Bob. Dans cette these, nous nous interessons a la problematique de la distribution de cle dans groupe. Nous proposons pour cela une solution basee sur la distribution de cle quantique, ce qui permet d’exploiter cette meme solution dans le contexte de groupe. Nous avancons par la suite la preuve formelle de la solution proposee en utilisant le verificateur formel PRISM
Sécurité des protocoles cryptographiques fondés sur la théorie des codes correcteurs d'erreurs 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.