Thèse de doctorat : Informatique : Metz : 2007. / DC = Différence de deux fonctions Convexes. DCA = DC algorithmes. Titre provenant de l'écran-titre. Notes bibliogr.

Le défi primaire dans le développement matériel de la cryptographie moderne est de faire des implémentations optimales en ressources, et rapide, en garantissant une résistance contre les attaques. Cette recherche porte sur les implémentations pratiques des opérations de cryptographie basées sur la cryptographie à clé publique dans les corps finis. Durant cette thèse nous avons proposé des composants matériels de base. L'arithmétique des corps finis constitue le noyau de la cryptographie à clé publique comme RSA, ECC ou une cryptographie basée sur le couplage. Nous avons proposé dans cette thèse des architectures du calcul arithmétique haute performance pour implémenter les primitives de cryptographie asymétrique. Les composants décrits dans notre travail ont été implémentés dans des Field Programmable Gate Array platforms (FPGA) de Xilinx. Nous avons utilisé le VHDL pour développer nos composants et nos architectures. Nos résultats présentent des performances en ressources et en vitesse jamais égalées auparavant dans la littérature publique sur ce type de technologie. La particularité de ces architectures est l'utilisation de l'architecture systolique pour développer une multiplication modulaire. Cette thèse traite la mise en œuvre matérielle efficace de la méthode CIOS (Coarsely Integrated Operand Scanning) de la multiplication modulaire de Montgomery combinée avec une architecture systolique efficace. D'après nos connaissances, c'est la première implémentation d'une telle conception. Nos architectures visaient à réduire le nombre de cycles d'horloge de la multiplication modulaire. Les résultats d'implémentation des algorithmes CIOS se concentrent sur différents niveaux de sécurité utiles en cryptographie. Cette architecture a été conçue pour utiliser le DSP48 flexible sur les FPGA de Xilinx. Nos architectures sont évolutives et dépendent uniquement du nombre et de la taille des mots. Par exemple, nous fournissons des résultats d'implémentation pour des longs mots de 8, 16, 32 et 64 bits en 33, 66, 132 et 264 cycles d'horloge. Nous décrivons également un design pour calculer une inversion et/ou une division dans Fp. L'inversion peut être utilisée dans les systèmes de la cryptographie de courbe elliptique et de la cryptographie basée sur le couplage. / The primary challenge in the hardware development of the modern cryptography is to make an optimal implementations in resources and speed, with guaranteeing a resistance against attacks. This research focuses on practical implementations of cryptographic operations based on public key cryptography in finite fields. During this thesis we proposed basic hardware components. Finite field arithmetic is the core of public key cryptography such as RSA, ECC, or pairing-based cryptography. We proposed in this thesis a high-performance architectures of arithmetic calculation to implement asymmetric cryptographic primitives. The components described in this thesis have been implemented in Xlinx Field Programmable Gate Array Platforms (FPGAs). We used the VHDL to devolve our components and architectures. Our results show a performance and speed never presented before in the literature on this type of technology. The particularity of these architectures is the use of systolic architecture to develop a modular multiplication. This thesis deals with the effective physical implementation of the Coarsely Integrated Operand Scanning (CIOS) method of Montgomery's modular multiplication combined with an effective systolic architecture. According to our knowledge, this is the first implementation of such a design. Our architectures were aimed at reducing the number of clock cycles of modular multiplication. The implementation results of the CIOS algorithms focus on different levels of security useful in cryptography. This architecture was designed to use the flexible DSP48 on Xilinx FPGAs. Our architectures are scalable and depend only on the number and size of the words. For instance, we provide implementation results for 8, 16, 32, and 64 bit long words in 33, 66, 132, and 264 clock cycles. We describe also a design to compute an inversion in Fp as well as division. Inversion can be used in Elliptic Curve Cryptography systems and pairing-based cryptography.

Le sujet de cette thèse est la cryptographie et son interconnexions avec la théorie des codes. En particulier, on utilise des techniques issues de la théorie des codes pour construire et analyser des protocoles cryptographiques avec des propriétés nouvelles ou plus avancées. On se concentre d'abord sur le partage de secret ou secret sharing, un sujet important avec de nombreuses applications pour la Cryptographie actuelle. Dans la variante à laquelle on s'intéresse, un schéma de partage de secret reçoit en entrée un élément secret, et renvoie en sortie n parts de telle façon que chaque ensemble de parts de taille suffisamment petite ne donne aucune information sur le secret (confidentialité), tandis que chaque ensemble de taille suffisamment grande permet de reconstituer le secret (reconstruction). Un schéma de partage de secret peut donc être vu comme une solution à un problème de communication où un émetteur Alice est connectée avec un destinataire Bob par n canaux distincts, dont certains sont contrôlés par un adversaire Ève. Alice peut utiliser un schéma de partage de secret pour communiquer un message secret a Bob de telle façon qu'Ève n'apprenne aucune information sur le secret en lisant les données transmises sur les canaux qu'elle contrôle, tandis que Bob peut recevoir le message même si Ève bloque ces dits canaux. Notre contributions au partage de secret concernent ses liens avec la théorie des codes ; comme les deux domaines partagent un même but (récupérer des données à partir d'informations partielles), ce n'est pas surprenant qu'ils aient connu une interaction longue et fertile. Plus précisément, Massey commença une analyse fructueuse à propos de la construction et de l'étude d'un schéma de partage de secret à partir d'un code correcteur. L'inconvénient de cette analyse est que la confidentialité d'un schéma de partage de secret est estimé grâce au dual du code sous-jacent ; cela peut être problématique vu qu'il pourrait ne pas être possible d'obtenir des codes avec des propriétés souhaitables qui aient aussi un bon code dual. On contourne ce problème en établissant une connexion nouvelle entre les deux domaines, telle que la confidentialité d'un schéma de partage de secrets n'est plus contrôlée par le dual du code sous-jacent. Cela nous permet d'exploiter complètement le potentiel de certaines constructions récentes de codes pour obtenir des meilleurs schémas; on illustre ceci avec deux applications. Premièrement, en utilisant des codes avec codage et décodage en temps linéaire on obtient une famille de schémas de partage de secret où le partage (calcul des parts issues du secret) tout comme la reconstruction peuvent s'effectuer en temps linéaire ; pour des seuils de confidentialité et de reconstruction croissants, ceci restait jusqu'à présent un problème ouvert. Deuxièmement, on utilise des codes avec décodage en liste pour construire des schémas de partage de secret robustes, c'est-à-dire des schémas qui peuvent reconstituer le secret même si certaines parts sont incorrectes, sauf avec une petite probabilité d'erreur. etc... / The topic of this dissertation is Cryptography, and its connections with Coding Theory. Concretely, we make use of techniques from Coding Theory to construct and analyze cryptographic protocols with new and/or enhanced properties. We first focus on Secret Sharing, an important topic with many applications to modern Cryptography, which also forms the common ground for most of the concepts discussed in this thesis. In the flavor we are interested in, a secret-sharing scheme takes as input a secret value, and produces as output n shares in such a way that small enough sets of shares yield no information at all on the secret (privacy), while large enough sets of shares allow to recover the secret (reconstruction). A secret-sharing scheme can thus be seen as a solution to a secure communication problem where a sender Alice is connected to a receiver Bob via $n$ distinct channels, some of which are controlled by an adversary Eve. Alice can use a secret-sharing scheme to communicate a secret message to Bob in such a way that Eve learns no information on the message by eavesdropping on the channels she controls, while Bob can receive the message even if Eve blocks the channels under her control. Our contributions to Secret Sharing concern its connection with Coding Theory; since the two fields share the goal of recovering data from incomplete information, it is not surprising that Secret Sharing and Coding Theory have known a long and fruitful interplay. In particular, Massey initiated a very successful analysis on how to construct and study secret-sharing schemes from error-correcting codes. The downside of this analysis is that the privacy of secret-sharing schemes is estimated in terms of the dual of the underlying code; this can be problematic as it might not be possible to obtain codes with desirable properties that have good duals as well. We circumvent this problem by establishing a new connection between the two fields, where the privacy of secret-sharing schemes is no longer controlled by the dual of the underlying code. This allows us to fully harness the potential of recent code constructions to obtain improved schemes; we exemplify this by means of two applications. First, by making use of linear-time encodable and decodable codes we obtain a family of secret-sharing schemes where both the sharing (computation of the shares from the secret) and the reconstruction can be performed in linear time; for growing privacy and reconstruction thresholds, this was an hitherto open problem. Second, we make use of list-decodable codes to construct robust secret-sharing schemes, i.e., schemes that can recover the secret even if some of the shares are incorrect, except with a small error probability. The family we present optimizes the trade-off between the extra data that needs to be appended to the share to achieve robustness and the error probability in the reconstruction, reaching the best possible value. etc...

La sécurité des chiffrements par bloc évolue constamment au fur et à mesure que de nouvelles techniques de cryptanalyse sont découvertes. Lors de la conception de nouveaux chiffrements par bloc, il est donc nécessaire de considérer ces nouvelles techniques dans l'analyse de sécurité. Dans cette thèse, nous montrons comment construire certaines opérations internes des chiffrements par bloc pour améliorer la résistance à certaines attaques. Nous commençons par donner une méthode pour trouver les permutations paires-impaires optimales selon un certain critère pour les Réseaux de Feistel Généralisés. Grâce à une nouvelle caractérisation et à un algorithme efficace, nous sommes notamment capables de résoudre un problème ouvert depuis 10 ans. Nous donnons ensuite de nouvelles techniques de cryptanalyse pour améliorer la division property, qui nous permet également de donner un nouveau critère optimal pour la conception de boîtes-S. Nous continuons avec de nouvelles observations pour un cadencement de clé alternatif pour AES. Ceci nous permet de donner un nouveau cadencement de clé, à la fois plus efficace et augmentant la sécurité face à certaines attaques par rapport à l’original. Pour finir, nous présentons un algorithme général très effiace permettant d’attaquer la majorité des propositions pour la cryptographie en boîte blanche, ainsi qu’une attaque dédiée sur un schéma non attaqué jusque là, donnant lieu à une attaque qui n’a besoin que de quelques secondes pour retrouver la clé. / Along with new cryptanalysis techniques, the security of block ciphers is always evolving. When designing new block ciphers, we thus need to consider these new techniques during the security analysis. In this thesis, we show how to build some core operations for block ciphers to improve the security against some attacks. We first start by describing a method to find optimal (according to some criterion) even-odd permutations for a Generalized Feistel Network. Using a new characterization and an efficient algorithm, we are able to solve a 10-years old problem. We then give new cryptanalysis techniques to improve the division property, along with a new proven optimal criterion for designing S-boxes. We continue with new observations for the design of an alternative key-schedule for AES. We thus give a new key-schedule, which is both more efficient and more secure against some attacks compared to the original one. Finally, we describe a very efficient generic algorithm to break most proposals in white-box cryptography, as well as a dedicated attack on a previously not analyzed scheme, leading to a key-recovery attack in a few seconds.

Cette thèse porte sur les problèmes algorithmiques qui apparaissent lorsque l'on souhaite mettre en œuvre un cryptosystème basé sur un code correcteur d'erreur ou bien une cryptanalyse d'un tel système. L'intérêt de ces système provient de leur excellente complexité algorithmique, meilleure de plusieurs ordres de grandeurs en termes de complexité que les schémas à clé publique traditionnels. Ils fournissent également une alternative crédible aux systèmes actuels qui pour la plupart se repose sur la théorie des nombres et sur le problème de la factorisation et celui du logarithme discret. Outre l'absence de preuve mathématique de la réelle difficulté de ces problèmes, P. Shor a montré que ces deux problèmes pouvaient être résolus en temps polynomial dans le modèle de l’ordinateur quantique. Cet ordinateur quantique est encore loin d'être fonctionnel mais il faudra, le jour venu, disposer d'alternatives de confiance et disposant de mises en œuvre performantes. / This thesis is about algorithmic problems arising when someone wants to implement a cryptosystem based on error correcting codes or a cryptanalysis of such a system. The benefits of these systems come from their excellent algorithmic complexity, better of several orders than the classical public key schemes. They also bring a credible alternative to the current systems that for most of them rely on number theory and on the problems of factorisation and discrete logarithm. P.Shor showed that these two problems could be solved in polynomial time in the quantum computer model. This computer is far from being operational but we will need alternatives we can trust and that have efficient implementations.

Les attaques en fautes (FA) et par canaux cachés (SCA), permettent de récupérer des données sensibles stockées dans des équipements cryptographiques, en exploitant une fuite d'information provenant de leur implémentation matérielle. Le but de cette thèse est donc de formuler un état de l'art des contre-mesures aux SCA adaptées aux FPGA, ainsi que d'implémenter celles qui seront retenues en minimisant les pertes de performance et de complexité. Le cas des algorithmes symétriques tel AES est spécialement étudié, révélant plusieurs faiblesses des contre-mesures habituelles (DPL et masquage) en terme de résistance et de coût. Trois nouvelles contre-mesures sont donc proposées: 1.Des stratégies de placement/routage équilibrés destinées à amélioré la résistance des DPL sur FPGA. 2.Un nouveau type de DPL appelée BCDL (Balanced Cell-based Dual-rail Logic) dont le but est de supprimer la plupart des vulnérabilités liées aux DPLs. BCDL est également résilient à la majeure partie des FA et optimisé pour les FPGA, ce qui induit des complexité et performance compétitives. 3. RSM (Rotating S-Box Masking), une nouvelle technique de masquage pour AES qui montre un haut niveau de performances et résistance pour une complexité réduite. Finalement, plusieurs nouvelles SCA sont présentées et évaluées. RC (Rank Corrector) est un algorithme permettant d'améliorer les autres SCA. La FPCA introduit un nouveau distingueur basée sur la PCA. Puis plusieurs combinaisons (distingueur et mesures) sont proposées et résultent en une diminution du nombre de trace nécessaire à l'attaque. / Side-Channel Analysis (SCA) and Fault Attacks (FA) are techniques to recover sensitive information in cryptographic systems by exploiting unintentional physical leakage, such as the power consumption. This thesis has two main goals: to draw a review of the state of the art of FPGA-compatible countermeasures against SCA and implement t the selected ones with the minimum area and performances overhead. Symmetrical algorithms, specially AES, are studied and several vulnerabilities of usual protections, namely Dual-rail with Precharge Logic (DPL) and masking are analysed, as well as the issue of performance and area overheads. In this context, three new countermeasures are considered: 1. Balance placement and routing (PAR) strategies aiming at enhancing existing DPLs robustness when implemented in modern FPGAs. 2. A new type of DPL called Balanced Cell-based Dual-railLogic (BCDL), to thwart most of the known DPL weaknesses. BCDL also possess a fault resilience mechanism and provides implementation optimisations on FPGA, achieving competitive performances and area overhead. 3. The Rotating S-Box Masking (RSM), a new masking technique for the AES that shows high leveles of robustness and performances while bringing a significant reduction of the area overhead. Finally, several new SCAs are presented and evaluated. Firstly the “Rank Corrector” a SCA enhancement algorithm. Secondly, The FPCA, introduces a novel SCA distinguisher based on the PCA. Then, combinations of either acquisition methods or SCA distinguishers are discussed and show significant decrease in the number of measurements required to perform a successful attack.

Avec l'avènement des systèmes basées sur la position, les systèmes d'aide au positionnement doivent répondre à de nouvelles exigences sécuritaires: authentifier la positon géographique annoncée par un utilisateur avant qu'il lui soit octroyé accès à une ressource géolocalisée. Dans cette thèse, nous nous intéressons à l'étude de protocoles de sécurité pouvant garantir l'authenticité de la position annoncée par un utilisateur sans la disponibilité au préalable d'une architecture de confiance. Un premier résultat de notre étude est la proposition d'un protocole délimiteur de distance basée sur la cryptographie asymétrique permettant à un noeud possédant une clé publique d'authentifier la partie détentrice de la clé privée associée, tout établissant une mesure de confiance sur la distance les séparant. La mesure de distance est résistante aux attaques par relais, par distance et aux attaques terroristes. Nous utilisons ensuite ce premier ré! sultat de recherche afin définir une architecture générique pour la collecte de preuves de localisation respectueuses de la vie privée. Nous définissons une preuve de localisation comme étant un certificat numérique attestant de la présence effective d'un individu à une position géographique à un instant donné. Les propriétés de la vie privée que nous garantissons par le biais de notre système sont: l'anonymat des utilisateurs, la non-chaînabilité de leurs actions à l'intérieur du système et une liaison forte entre chaque utilisateur et la preuve de localisation qui lui est associée. De plus, les preuves récoltées peuvent servir à prouver différentes granularité de la position associée. / With the advent of Location-Based-Systems, positioning systems must face new security requirements: how to guarantee the authenticity of the geographical positon announced by a user before granting him access to location-restricted! resources. In this thesis, we are interested in the study of ! security ! protocols that can ensure autheniticity of the position announced by a user without the prior availability of any form of trusted architecture. A first result of our study is the proposal for a distance-bounding protocol based on asymmetric cryptography which allows a node knowing a public key to authenticate the holder of the associated private key, while establishing confidence in the distance between them. The distance measurement procedure is sufficently secure to resist to well-known attacks such as relay attacks, distance-, mafia- and terrorist-attacks. We then use such distance-bounding protocol to define an architecture for gathering privacy friendly location proofs. We define a location proof as a digital certificate attesting of presence of an individual at a location at a given time. The privacy properties we garanty through the use of our system are: the anonymity of users, un-linkability of their actions within the system and a strong binding between each user ! and the localization proof it is associated. on last property of our system is the possibility to use the same location proof to demonstrate different granularity of the associated position.

Ce mémoire présente une brève introduction aux fonctions de hachage : les principales fonctions de hachage utilisées ainsi que leurs principales utilisations. Une nouvelle fonction de hachage, développée par Yong Wang , Xiaofeng Liao, Di Xao et Kwok-Wo Wong [1], sera introduite et une modification de cette dernière sera proposée. Cette fonction de hachage est basée sur un système dynamique chaotique, ce qui conduit à l'étude des exposants de Lyapunov.

L’amélioration de la sécurité des communications et la confidentialité de l’information exige de développer des nouvelles solutions reposant sur diverses stratégies. Une solution de sécurité multicouche pour les systèmes de communication numérique est d’abord explorée en considérant les effets conjoints de sécurité de codage de canal de la couche physique avec la couche d’application de la cryptographie. Nous présentons ensuite des modèles pratiques de codage qui peuvent être utilisés en conjonction avec la cryptographie pour assurer des taux d’erreur importants sur les observations d’un espion sur les données chiffrées, tout en garantissant des communications idéalement sans erreur pour les utilisateurs légitimes. Dans ce mémoire, on présente une étude des techniques de sécurité au niveau de la couche physique récemment proposées dans la littérature. Ces techniques utilisent les codes LDPC avec ensembles d’arrêt permettant de nuire au processus de décodage par un utilisateur non légitime, ou espion, à de faibles taux d’erreur. Ces codes sont très efficaces lorsque le récepteur légitime bénéficie d’un canal de retour authentifié. On s’intéresse également au codage sécuritaire à travers un canal gaussien AWGN. L’objectif est de construire des codes permettant de compromettre le décodage au niveau de l’espion aussitôt que le bruit au niveau du canal d’écoute dépasse un certain seuil. Les techniques utilisées dans ce contexte reposent sur les codes LDPC avec poinçonnage, avec insertion des bits virtuels et avec brouillage. / Improving communications security and confidentiality of information requires the development of new solutions based on various strategies. A multilayer security solution for digital communication systems is first explored by considering the effects of joint security channel coding at the physical layer with cryptography at the application layer. We then present practical coding models that can be used in conjunction with cryptography to ensure high error rate observations for an eavesdropper on encrypted data, while ensuring reliable communications for the legitimate users. In this Master’s thesis, we present a study of security techniques at the physical layer recently proposed in the literature. These techniques use LDPC codes with stopping sets to prevent the decoding of information by the eavesdropper even with the lowest error rates. These codes are very efficient when the legitimate receiver has access to an authenticated feedback channel. The thesis also focuses on secure coding through AWGN Gaussian channels. The goal is to construct codes that prevent proper decoding at the eavesdropper end’s as soon as the noise in the wiretap channel exceeds a certain threshold. The techniques used in this context are based on LDPC codes with puncturing, insertion of dummy bits and scrambling.

Les schémas de Chiffrement Complètement Homomorphe (FHE) permettent de manipuler des données chiffrées avec grande flexibilité : ils rendent possible l'évaluation de fonctions à travers les couches de chiffrement. Depuis la découverte du premier schéma FHE en 2009 par Craig Gentry, maintes recherches ont été effectuées pour améliorer l'efficacité, atteindre des nouveaux niveaux de sécurité, et trouver des applications et liens avec d'autres domaines de la cryptographie. Dans cette thèse, nous avons étudié en détail ce type de schémas. Nos contributions font état d'une nouvelle attaque de récuperation des clés au premier schéma FHE, et d'une nouvelle notion de sécurité en structures hierarchiques, évitant une forme de trahison entre les usagers tout en gardant la flexibilité FHE. Enfin, on décrit aussi des implémentations informatiques. Cette recherche a été effectuée au sein du Laboratoire de Mathématiques de Versailles avec le Prof. Louis Goubin. / Fully Homomorphic Encryption schemes allow public processing of encrypted data. Since the groundbreaking discovery of the first FHE scheme in 2009 by Craig Gentry, an impressive amount of research has been conducted to improve efficiency, achieve new levels of security, and describe real applications and connections to other areas of cryptography. In this Dissertation, we first give a detailed account on research these past years. Our contributions include a key-recovery attack on the ideal lattices FHE scheme and a new conception of hierarchic encryption, avoiding at some extent betrayal between users while maintaining the flexibility of FHE. We also describe some implementations. This research was done in the Laboratoire de Mathématiques de Versailles, under supervision of Prof. Louis Goubin.