Dans la vie, on peut avoir besoin de communiquer avec des parties auxquelles on ne fait pas confiance, d'où l'importance de systèmes capables de contrôler ce type de communications. Des systèmes peuvent garantir, par exemple, un ballottage secret, des ventes aux enchères secrètes, des levées d'impôt tout en conservant l'intimité, l'authentification à distance à un ordinateur, l'aide anonyme de la police dans leurs enquêtes, etc. La cryptographie peut aider, au moins, dans quelques cas parmi ceux-ci, par la régularisation du flux d'information de telle manière qu'on n'aura plus besoin de faire confiance à l'autre partie. On fera confiance, seulement, aux systèmes cryptographiques utilisés. Une primitive, appelée mise en gage, est d'une importance suprême dans la cryptographie bipartite, où deux parties qui ne se font pas confiance essayent tout de même d'accomplir un calcul commun sur des données privées (calculer une fonction publique de leurs données secrètes). Cette primitive va être l'objet de ce mémoire. On va expliquer jusqu'à quel point on peut accomplir des taches cryptographiques de façon inconditionnellement sécuritaire, sous la seule hypothèse que la mécanique quantique et la relativité restreinte sont valides. Ce mémoire est largement basé sur les travaux de Mayers [52,53,54,55], Lo et Chau [49,50], Brassard, Crépeau, Mayers et Salvail [15], Spekkens et Rudolph [73], Hardy et Kent [35], Ishizaka [39] et Kent [43,44]. Il fait à la fois une présentation de la cryptographie quantique et une synthèse des travaux essentiels concernant les protocoles de mise en gage quantiques et relativistes. Nous allons donc commencer par une introduction sur l'histoire de la cryptographie classique et son prolongement naturel à ses homologues, quantique et relativiste, qui permettent d'obtenir de meilleurs résultats. Ensuite, nous introduirons un certain nombre d'outils mathématiques utiles à la description de la cryptographie quantique. Nous y présenterons également les preuves de plusieurs résultats à la base de la cryptographie quantique, tels que la décomposition de Schmidt, la purification, le théorème GHJW, le théorème d'Ulmann, le théorème de non-clonage, le théorème de la représentation de Kraus, etc. Nous discuterons aussi des concepts de base de l'informatique quantique, comme la mesure projective et généralisée, l'évolution des systèmes quantiques non isolés, la trace partielle, l'opérateur de densité, etc. Nous aborderons le protocole de la mise en gage proprement dit en exposant en détail la preuve du théorème de l'impossibilité de Mayers, Lo et Chau. Nous y présentons également le travail de Rudolph et Spekkens qui ont calculé les degrés optimaux de lien et de camouflage qui peuvent être obtenus simultanément dans tout protocole de mise en gage quantique non relativiste. Il s'agit-là d'une caractéristique qu'aucun protocole classique non relativiste ne peut assurer. Un autre type de sécurité pour ce protocole est étudié aussi, c'est celui de la mise en gage sensible à la tricherie "cheat sensitive" pour lequel on croyait que le protocole quantique de Hardy et Kent fonctionnait alors que lshizaka a démontré récemment que ce n'est pas le cas. Pire, il a même remis en question toute possibilité de réaliser ce type de sécurité en ce basant sur l'utilisation du protocole du tir à pile ou face comme sous-protocole. La cryptographie relativiste fera l'objet de notre dernier chapitre. Nous commencerons par montrer comment la théorie de la relativité restreinte, et donc l'impossibilité qu'un signal puisse se déplacer à une vitesse supérieur à celle de la lumière, peut être exploitée pour construire un protocole de mise en gage temporairement sécuritaire, c'est celui de Brassard, Crépeau, Mayers et Salvail. Nous présenterons ensuite le premier protocole relativiste d'une mise en gage continuellement sécuritaire, celui de Kent, et la preuve de sa sécurité. Ce protocole ne peut malheureusement pas être implémenté, même s'il est théoriquement sûr. Nous terminerons cette étude par une description d'un deuxième protocole relativiste du même auteur, qui va remédier aux problèmes liés à l'impossibilité pratique du premier protocole. Les preuves de la sécurité de ce dernier contre les attaques classiques et quantiques du type Mayers, Lo et Chau vont être abordées. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Informatique quantique, Mise en gage quantique, Mise en gage quantique sensible à la tricherie, Mise en gage relativiste.

Identification schemes are public-key cryptographic primitives that allow an entity (called the prover) to prove his or her identity to another entity. An identification scheme is secure if no attacker can impersonate the prover. Digital signature schemes allow an entity to produce a signature on a message; given the message and the signature, another entity can check the identity of the signer and verify that the message was not modified. A secure digital signature scheme is such that an attacker can not produce a forgery, i.e. a false signature. There has been a lot of work aiming at establishing, in a provable manner, the security of such schemes. Given a cryptographic scheme and a security property, one should be able to demonstrate whether the scheme satisfies it or not. The approach is usually the following: when the security property is not satisfied, show it with an efficient attack; when it is satisfied, use a security proof. But even when they are provably secure, cryptographic schemes can be attacked: it can be at the implementation level, or because of a flaw in the proof. The goal of this thesis is to apply these approaches to study the security of several public-key cryptographic schemes. We study the GPS identification scheme and show how some implementations can be broken by an efficient attack. We show how to securely sign long messages with RSA. We break a fair exchange signature scheme based on GPS and RSA. We consider a new problem called fair identification and propose a fair identification scheme.

Les couplages sont des algorithmes cryptographiques qui permettent de nouveaux protocoles de cryptographie à clé publique. Après une décennie de recherches sur des implémentations efficaces, ce qui permet maintenant d’exécuter un couplage en un temps raisonnable, nous nous sommes concentrés sur la sécurité de ces mêmes implémentations.Pour cela nous avons évalué la résistance des algorithmes de couplage contre les attaques en faute. Nous avons envoyé des impulsions électromagnétiques sur la puce calculant le couplage à des moments choisis. Cela nous a permis de remonter au secret cryptographique qu’est censé protéger l’algorithme de couplage. Cette étude fut à la fois théorique et pratique avec la mise en œuvre d’attaques en faute. Finalement, des contremesures ont été proposées pour pouvoir protéger l’algorithme dans le futur / Pairings are cryptographic algorithms allowing new protocols for public-key cryptography. After a decade of research which led to a dramatic improvement of the computation speed of pairings, we focused on the security of pairing implementations.For that purpose, we evaluated the resistance to fault attacks. We have sent electromagnetic pulses in the chip computing a pairing at a precise instant. It allowed us to recover the cryptographic secret which should be protected in the computation. Our study was both theoretical and practical; we did implement actual fault attacks. Finally, we proposed countermeasures in order to protect the algorithm in the future

Reproduction de : Thèse de doctorat : Mathématiques appliquées : Grenoble 1 : 1990. / Titre provenant de l'écran-titre. Bibliogr. p. 210-208.

Dans cette thèse, nous nous intéressons à la sécurité de quelques primitives cryptographiques récentes, d’abord symétriques puis asymétriques, en passant par le modèle en boîte blanche, qui est à certains égards intermédiaire. Dans un premier temps, nous montrons l’existence de fonctions linéaires non triviales commutant avec la fonction de tour de certains chiffrements par bloc, dont découlent des attaques par auto-similarité et sous-espace invariant. Nous nous intéressons ensuite à la cryptanalyse de la structure ASASA, où deux couches non linéaires S sont imbriquées dans des couches affines A. Notre cryptanalyse structurelle permet de casser des instances de chiffrement symétrique, multivarié et en boîte blanche. En nous concentrant sur le modèle d’incompressibilité en boîte blanche, nous montrons ensuite comment réaliser un chiffrement par bloc et un générateur de clef efficaces dont la sécurité est prouvable. Finalement, du côté purement asymétrique, nous décrivons une attaque polynomiale contre une construction récente d’application multilinéaire. / In this thesis, we study the security of some recent cryptographic primitives, both symmetric and asymmetric. Along the way we also consider white-box primitives, which may be regarded as a middle ground between symmetric and asymmetric cryptography. We begin by showing the existence of non-trivial linear maps commuting with the round function of some recent block cipher designs, which give rise to self-similarity and invariant subspace attacks. We then move on to the structural cryptanalysis of ASASA schemes, where nonlinear layers S alternate with affine layers A. Our structural cryptanalysis applies to symmetric, multivariate, as well as white-box instances. Focusing on the white-box model of incompressibility, we then build an efficient block cipher and key generator that offer provable security guarantees. Finally, on the purely asymmetric side, we describe a polynomial attack against a recent multilinear map proposal.

Le concept d’un réseau personnel sans fil (Wireless Personal Area Network (WPAN)) est généralement limité aux couples d'appareils (un téléphone, un casque, un appareil photo) et fortement liés à un utilisateur unique. Néanmoins, nous pensons que le concept évoluera dans un proche avenir afin de créer un réseau de communication distribué tout autour de l’utilisateur avec beaucoup plus de dispositifs. Un tel réseau distribué est appelé un réseau personnel (Personal Network (PN)). La prochaine étape après la création de réseaux distribués est de les interconnecter avec certaines restrictions. Etant donné que le WPAN est généralement un espace privé, il est préférable de ne pas exposer toutes ou certaines de nos ressources à des utilisateurs externes, ou plutôt que ces derniers aient un accès limité à certaines ressources. De même, nous préférons nous connecter avec des amis et peut-être utiliser leurs propres ressources avec des conditions équivalentes. Pour réaliser tout cela, nous nous trouvons en face de quelques restrictions. Vue que les dispositifs utilisés dans les réseaux personnels sont, dans certains cas, considérés comme dispositifs à faible débit, la mise en œuvre des protocoles existants et connus de sécurité semble être inefficace. En effet, ces dispositifs nécessitent une implémentation minimale de sécurité à faible coût qui ne peut être prévue par les protocoles connus. En outre, un aperçu vertical de la pile de communication donne un aperçu sur les difficultés d'application de ces protocoles. Nous proposons d’implémenter un mécanisme de chiffrement au niveau de la couche physique juste après le processus de codage correcteur d’erreur. L'architecture proposée repose sur l'utilisation du « Output Feedback Mode (OFB) » en utilisant l'algorithme AES comme algorithme de chiffrement (Cipher). La contribution suivante vise l'élaboration d'un accord (partage) de clé entre plusieurs parties d’une façon hiérarchique. Cette solution permet de sécuriser les communications entre plusieurs groupes de dispositifs (Cluster) liés à un seul propriétaire. Un pas après avoir obtenu une architecture intra-réseau personnel est d'assurer le partage des ressources entre plusieurs PNs. Les ressources ne sont pas nécessairement dans le même domaine d’authentification et le serveur qui les organise s'appelle une fédération. Notre contribution dans ce contexte est basée sur deux composantes: un protocole de signalisation et un protocole qui assure une gestion de clé de groupe. Nous achevons notre travail en proposant une solution de sécurité qui vise l'intégration des réseaux PNs au sein de l'internet du futur, plus précisément, l’internet d'information. Dans l'Internet du futur, tout est mobile et connecté pratiquement à tout d’où l'objet prend une significative importance. En revanche, les réseaux personnels évoluent de façon à créer des Intelligent réseaux personnels (Smart personal networks) autour de l'utilisateur. Dans le concept des réseaux orientés sur l'objet et orientés utilisateur, l’accès à l'information devient plus facile mais l'instauration d'une bonne sécurité devient plus difficile. La difficulté n'est pas de trouver de nouveaux algorithmes de sécurité, mais plutôt d'adapter et d'améliorer les solutions existantes pour répondre aux exigences de sécurité souhaitable. Dans cette contribution, nous proposons une nouvelle solution qui fusionne la cryptographie basé sur l'identité et les systèmes de chiffrement cryptographique « Certificateless afin de garder leurs avantages et résoudre leurs problèmes. / Wireless Personal Area Network (WPAN) communications concept is generally restricted to couples of devices (a phone, a headset, a camera) and strongly related to a user and communicating very periodically (exchanges of differentBtypes). Nonetheless, we believe that the concept will evolve in the near future to create a distributed communication network all around users with more devices. Such a distributed network is called a Personal Network (PN). The next step after the distributed network creation is to interconnect them with certain restrictions. Since the WPAN is generally a private area, we do not like to expose all the resources to external users but still we would like to let them have restricted access to certain facilities. Similarly, we would like to peer friends to let us use their own resources with equivalent conditions. As devices involved in the Personal Networks, in some cases, have a LowData Rate nature, implementing legacy security protocols seems to be inefficient.In fact, such devices require a minimal implementation of security solutions withlow cost which can not be provided by known protocols. Moreover, a verticaloverview of the communication stack gives insight on the difficulties of applyingthese protocols. We propose an efficient physical layer encryption to be implementedafter the error coding process. The proposed architecture relies on the use of the well proven secure Output Feedback Mode OFB using AES algorithm as a Cipher. The next contribution is targeting the development of a hierarchical key agreement between multi-parties to secure communication between many clusters related to only one owner. One step after securing the Intra-Personal Network is to secure resource sharing between many PNs. Resources are not necessarily in the same authentication domain and the group that uses them is called a federation. Our contribution is based on two components: A signaling protocol and a group key management system. We close our work by providing a security solution that targets the integration of the PN within the future internet, more precisely, the network of information. In the future internet, everything is mobile and virtually connected to everything where the object takes the cornerstone. In the other hand, Personal net works are evolving to create Smart personal networks around the user. In the object-centric and user-centric concepts, information access becomes easier but establishing good security becomes harder. The difficulty is not finding new secure algorithms but rather that of adapting and enhancing existing solutions to meet the security requirements desirable for the interaction between these networks. In this contribution, we propose a new solution that merges Identity-Based cryptography and the Certificateless Cryptography cryptographic systems into only one in order to keep their advantages and to resolve their problems.

Les systèmes de chiffrement à flot (stream ciphers) sont couramment utilisés puisqu'ils permettent un chiffrement rapide des données tout en consommant peu d'énergie. Leur principe de fonctionnement est relativement simple: un générateur de pseudo-aléa produit une séquence binaire qui est X-orée au message clair, engendrant ainsi le message chiffré (cryptogramme). Le destinataire, muni d'un générateur identique, déchiffre le message reçu en lui appliquant la même opération. La sécurité de ce système repose entièrement sur la difficulté de produire la séquence pseudo-aléatoire: toute personne en mesure de la générer pourra en effet déchiffrer le cryptogramme qu'elle aura intercepté. L'objet de cette thèse était de proposer de nouvelles attaques sur de tels systèmes. Plus précisément, nous nous sommes intéressés à la cryptanalyse à clair connu des registres filtrés: le générateur de pseudo-aléa est, dans ce cas, constitué d'un unique registre à décalage linéaire (LFSR) filtré par une fonction booléenne. La structure de ces deux composantes est supposée entièrement connue du cryptanalyste, lequel dispose, par ailleurs, de quelques bits de la séquence pseudo-aléatoire. Seule l'initialisation du registre à décalage est secrète et conditionne entièrement la sortie du générateur: elle constitue donc la clé secrète du système de chiffrement et notre objet sera précisément de la déterminer. Le document sera organisé de la façon suivante: dans un premier chapitre, nous décrivons la structure du système de chiffrement qu'est le registre filtré, et nous intéressons aux théories auxquelles ses différentes constituantes renvoient naturellement. Nous proposons, dans un second chapitre, un état de l'art des attaques non-algébriques du registre filtré. Suit un chapitre qui présente les fondements du décodage itératif et quelques résultats de simulation permettant d'évaluer l'impact de différents paramètres du système, celui du canal booléen notamment. Nous décrivons ensuite une nouvelle attaque dont le principe s'inspire de celui du décodage itératif, qui utilise non plus des contraintes linéaires mais celles de la fonction booléenne. Le quatrième chapitre est dédié aux attaques par treillis: nous présentons en premier lieu une attaque déterministe, qui, lorsque les conditions d'application sont réunies, permet de cryptanalyser le registre filtré très efficacement, et sans aucune probabilité d'erreur. Les conditions d'application de cet algorithme étant assez restrictives, nous avons étendu son principe à des systèmes moins spécifiques, perdant de ce fait le caractère déterministe de l'attaque originelle. Enfin, dans un dernier chapitre, nous avons développé deux algorithmes: le "SOJA" et le "Probability-Matching". Tous deux exploitent conjointement la structure de la fonction booléenne et l'existence d'équations vectorielles, le SOJA afin de générer des probabilités a posteriori sur les bits de la séquence d'entrée, le Probability-Matching afin d'identifier des vecteurs d'entrée de la fonction présentant des propriétés remarquables.

Thèse doctorat : Informatique : Villeurbanne, INSA : 2007. / Titre provenant de l'écran-titre. Bibliogr. p. 139-150.

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.

Thèse (D. en sémiologie)--Université du Québec à Montréal, 2005. / En tête du titre: Université du Québec à Montréal. Bibliogr.: f. 432-439. Publié aussi en version électronique.