Les besoins constants d’innovation en matière de performances et d’économie des ressources nous poussent à effectuer des optimisations dans la conception et l’utilisation des outils cryptographiques. Cela nous amène à étudier plusieurs aspects dans cette thèse : les algorithmes cryptographiques parallèles, les algorithmes cryptographiques incrémentaux et les dictionnaires authentifiés.Dans le cadre de la cryptographie parallèle, nous nous intéressons aux fonctions de hachage basées sur des arbres. Nous montrons en particulier quelles structures arborescentes utiliser pour atteindre un temps d’exécution optimum avec un nombre de processeurs que nous cherchons à minimiser dans un second temps. Nous étudions également d'autres formesd'arborescence favorisant l'équité et la scalabilité.Les systèmes cryptographiques incrémentaux permettent, lorsque nous modifions des documents, de mettre à jour leurs formes cryptographiques efficacement. Nous montrons que les systèmes actuels restreignent beaucoup trop les modifications possibles et introduisons de nouveaux algorithmes s’appuyant sur ces derniers, utilisés comme des boites noires, afin de rendre possible une large gamme de modifications aux documents tout en conservant une propriété de secret de l’opération effectuée.Notre intérêt porte ensuite sur les dictionnaires authentifiés, utilisés pour authentifier les réponses aux requêtes des utilisateurs sur un dictionnaire, en leur fournissant une preuve d’authenticité pour chaque réponse. Nous nous focalisons sur des systèmes basés sur des arbres de hachage et proposons une solution pour amoindrir leur principal inconvénient, celui de la taille des preuves. / The need for continuing innovation in terms of performances and resource savings impel us to optimize the design and the use of cryptographic mechanisms. This leads us to consider several aspects in this dissertation: parallel cryptographic algorithms, incremental cryptographic algorithms and authenticated dictionaries.In the context of parallel cryptography we are interested in hash functions. In particular, we show which tree structures to use to reach an optimal running time. For this running time, we show how to decrease the amount of involved processors. We also explore alternative (sub-optimal) tree structures which decrease the number of synchronizations in multithreaded implementations while balancing at best the load of the work among the threads.Incremental cryptographic schemes allow the efficient updating of cryptographic forms when we change some blocks of the corresponding documents. We show that the existing incremental schemes restrict too much the possible modification operations. We then introduce new algorithms which use these ones as black boxes to allow a broad range of modification operations, while preserving a privacy property about these operations.We then turn our attention to authenticated dictionaries which are used to authenticate answers to queries on a dictionary, by providing to users an authentication proof for each answer. We focus on authenticated dictionaries based on hash trees and we propose a solution to remedy their main shortcoming, the size of proofs provided to users.

This thesis describes methods of secret communication based on latin squares and their close relative, quasigroups. Different types of cryptosystems are described, including ciphers, public-key cryptosystems, and cryptographic hash functions. There is also a chapter devoted to different secret sharing schemes based on latin squares. The primary objective is to present previously described cryptosystems and secret sharing schemes in a more accessible manner, but this text also defines two new ciphers based on isotopic latin squares and reconstructs a lost proof related to row-latin squares. / Denna uppsats beskriver kryptosystem och metoder för hemlighetsdelning baserade på latinska kvadrater och det närliggande konceptet kvasigrupper. Olika sorters chiffer, både symmetriska och asymmetriska, behandlas. Dessutom finns ett kapitel tillägnat kryptografiska hashfunktioner och ett tillägnat metoder för hemlighetsdelning. Huvudsyftet är att beskriva redan existerande metoder för hemlig kommunikation på ett mer lättillgängligt sätt och med nya exempel, men dessutom återskapas ett, till synes, förlorat bevis relaterat till rad-latinska kvadrater samt beskrivs två nya chiffer baserade på isotopa latinska kvadrater.

La stéganographie est l’art de la dissimulation de l’information secrète dans un médium donné (cover) de sorte que le médium résultant (stégo) soit quasiment identique au médium cover. De nos jours, avec la mondialisation des échanges (Internet, messagerie et commerce électronique), s’appuyant sur des médiums divers (son, image, vidéo), la stéganographie moderne a pris de l’ampleur. Dans ce manuscrit, nous avons étudié les méthodes de stéganographie LSB adaptatives, dans les domaines spatial et fréquentiel (DCT, et DWT), permettant de cacher le maximum d’information utile dans une image cover, de sorte que l’existence du message secret dans l’image stégo soit imperceptible et pratiquement indétectable. La sécurité du contenu du message, dans le cas de sa détection par un adversaire, n’est pas vraiment assurée par les méthodes proposées dans la littérature. Afin de résoudre cette question, nous avons adapté et implémenté deux méthodes (connues) de stéganographie LSB adaptatives, en ajoutant un système chaotique robuste permettant une insertion quasi-chaotique des bits du message secret. Le système chaotique proposé consiste en un générateur de séquences chaotiques robustes fournissant les clés dynamiques d’une carte Cat 2-D chaotique modifiée. La stéganalyse universelle (classification) des méthodes de stéganographie développées est étudiée. A ce sujet, nous avons utilisé l’analyse discriminante linéaire de Fisher comme classifieur des vecteurs caractéristiques de Farid, Shi et Wang. Ce choix est basé sur la large variété de vecteurs caractéristiques testés qui fournissent une information sur les propriétés de l’image avant et après l’insertion du message. Une analyse des performances des trois méthodes de stéganalyse développées, appliquées sur des images stégo produites par les deux méthodes de stéganographie LSB adaptatives proposées, est réalisée. L’évaluation des résultats de la classification est réalisée par les paramètres: sensibilité, spécificité, précision et coefficient Kappa. / Steganography is the art of the dissimulation of a secret message in a cover medium such that the resultant medium (stego) is almost identical to the cover medium. Nowadays, with the globalization of the exchanges (Internet, messaging and e-commerce), using diverse mediums (sound, embellish with images, video), modern steganography is widely expanded. In this manuscript, we studied adaptive LSB methods of stéganography in spatial domain and frequency domain (DCT, and DWT), allowing of hiding the maximum of useful information in a cover image, such that the existence of the secret message in the stégo image is imperceptible and practically undetectable. Security of the message contents, in the case of its detection by an opponent, is not really insured by the methods proposed in the literature. To solve this question, we adapted and implemented two (known) methods of adaptive stéganographie LSB, by adding a strong chaotic system allowing a quasi-chaotic insertion of the bits of the secret message. The proposed chaotic system consists of a generator of strong chaotic sequences, supplying the dynamic keys of a modified chaotic 2D Cat map. Universal steganalysis (classification) of the developed methods of stéganography, is studied. On this question, we used the linear discriminating analysis of Fisher as classifier of the characteristic vectors of Farid, Shi and Wang. This choice is based on the wide variety of tested characteristic vectors that give an information about the properties of the image before and after message insertion. An analysis of the performances of three developed methods of steganalysis, applied to the produced stego images by the proposed adaptive methods of stéganography, is realized. Performance evaluation of the classification is realized by using the parameters: sensibility, specificity, precision and coefficient Kappa.

Mobile communication devices have become a popular tool for gathering and disseminating information and data. With the evidence of the growth of wireless technology and a need for more flexible, customizable and better-optimised security schemes, it is evident that connection-based security such as HTTPS may not be sufficient. In order to provide sufficient security at the application layer, developers need access to a cryptography package. Such packages are available as third party mobile cryptographic toolkits or are supported natively on the mobile device. Typically mobile cryptographic packages have reduced their number of API methods to keep the package lightweight in size, but consequently making it quite complex to use. As a result developers could easily misuse a method which can weaken the entire security of a system without knowing it. Aside from the complexities in the API, mobile cryptography packages often do not apply sound cryptography within the implementation of the algorithms thus causing vulnerabilities in its utilization and initialization. Although FIPS 140-2 and CAPI suggest guidelines on how cryptographic algorithms should be implemented, they do not define the guidelines for implementing and using cryptography in a mobile environment. In our study, we do not define new cryptographic algorithms, instead, we investigate how sound cryptography can be applied practically in a mobile application environment and developed a framework called Linca (which stands for Logical Integration of Cryptographic Architectures) that can be used as a mobile cryptographic package to demonstrate our findings. The benefit that Linca has is that it hides the complexity of making incorrect cryptographic algorithm decisions, cryptographic algorithm initialization and utilization and key management, while maintaining a small size. Linca also applies sound cryptographic fundamentals internally within the framework, which radiates these benefits outwards at the API. Because Linca is a framework, certain architecture and design patterns are applied internally so that the cryptographic mechanisms and algorithms can be easily maintained. Linca showed better results when evaluated against two mobile cryptography API packages namely Bouncy Castle API and Secure and Trust Service API in terms of security and design. We demonstrate the applicability of Linca on using two realistic examples that cover securing network channels and on-device data. / Dissertation (MSc (Computer Science))--University of Pretoria, 2007. / Computer Science / MSc / unrestricted

Algebraic attacks constitute an effective class of cryptanalytic attacks which have come up recently. In algebraic attacks, the relations between the input, output and the key are expressed as a system of equations and then solved for the key. The main idea is in obtaining a system of equations which is solvable using reasonable amount of resources. The new approaches proposed in this work and experimental studies on the existing algebraic attacks on stream ciphers will be presented. In the first attack on filter generator, the input-output relations are expressed in conjunctive normal form. The system of equations is then solved using modified Zakrevskij technique. This was one of the earliest algebraic attacks on the nonlinear filter generator. In the second attack, we relaxed the constraint on algebraic attack that the entire system description be known and the output sequence extension problem where the filter function is unknown is considered. We modeled the problem as a multivariate interpolation problem and solved it. An advantage of this approach is that it can be adapted to work for noisy output sequences where as the existing algebraic attacks expect the output sequence to be error free. Adding memory to filter/combiner function increases the degree of system of equations and finding low degree equations in this case is computeintensive. The method for computing low degree relations for combiners with memory was applied to the combiner in E0 stream cipher. We found that the relation given in literature [Armknecht and Krause] was incorrect. We obtained the correct equation and verified its correctness. A time-data size trade off attack for clock controlled filter generator was developed. The time complexity and the data requirements are in between the two approaches used in literature. A recent development of algebraic attacks - the Cube attack was studied. Cube attack on variants of Trivium were proposed by Dinur and Shamir where linear equations in key bits were obtained by combining equations for output bit for same key and a set of Initialization Vectors (IVs). We investigated the effectiveness of the cube attack on Trivium. We showed that the linear equations obtained were not general and hence the attack succeeds only for some specific values of IVs. A reason for the equations not being general is given and a modification to the linear equation finding step suggested.

Secret sharing is critical to most applications making use of security and remains one of the most challenging research areas in modern cryptography. In this thesis, we propose a novel efficient multi-secret sharing scheme based on the Chinese remainder theorem (CRT) with two verification methods, while the previous works are mostly based on the Lagrange polynomial. Key management schemes play an important role in communication security in Wireless Sensor Networks (WSNs). While the previous works mainly targeting on two different types of WSNs: distributed and hieratical, in this thesis, we propose our flexible WSN key management scheme, which is based on (n,t,n) multi-secret sharing technique, to provide a key management solution for heterogeneous architecture. The powerful key managers are responsible for most of the communicational and computational workload. They can provide Peer-to-Peer pair-wise keys for a pair of sensors to establish a secure communication session, and in the same time, they can also form communication clusters as cluster heads according to different application requirements. Internet of Things (IoT) becomes more and more popular and practical in recent years. Considering the diversity of the devices and the application scenarios, it is extremely hard to couple two devices or sub-networks with different communication and computation resources. In this thesis, we propose novel key agreement schemes based on (n,t,n) multi-secret sharing techniques for IoT in order to achieve light weighted key exchange while using Host Identity Protocol (HIP). We refer the new schemes as HIP-MEXs with different underlying multi-secret sharing techniques. We analyzed the computational and communication costs of the extremely resource constrained device which is referred to as Initiator, and CRT based HIP-MEX successfully outsource the heavy workload to the proxy, which are considered more powerful, when establishing new secret key.

Aujourd'hui, nous utilisons de plus en plus d'appareils "connectés" (téléphone portable, badge d'accès ou de transport, carte bancaire NFC, ...), et cette tendance ne va pas s'inverser. Ces appareils requièrent l'utilisation de primitives cryptographiques, embarquées dans des composants électroniques, dans le but de protéger les communications. Cependant, des techniques d'attaques permettent d'extraire de l'information du composant électronique ou fauter délibérément son fonctionnement. Un nouveau médium d'attaque, exploitant les ondes électromagnétiques est en pleine expansion. Ce médium, par rapport à des techniques de fautes à base de perturbations par faisceau LASER, propose l'avantage d’être à relativement faible coût. Nous présentons dans cette thèse la résistance d'un type de bloc cryptographique, à savoir les générateurs de nombres réellement aléatoires, aux ondes électromagnétiques. Nous montrons qu'il est possible d'extraire de l'information sensible du champ électromagnétique produit par le composant électronique, et qu'il est également possible de perturber un générateur en le soumettant à un fort champ électromagnétique harmonique / Nowadays, our society is using more and more connected devices (cellphones, transport or access card NFC debit card, etc.), and this trend is not going to reverse. These devices require the use of cryptographic primitives, embedded in electronic circuits, in order to protect communications. However, some attacks can allow an attacker to extract information from the electronic circuit or to modify its behavior. A new channel of attack, using electromagnetic waves is skyrocketing. This channel, compared to attacks based on LASER beam, is relatively inexpensive. We will, in this thesis, present a new attack, using electromagnetic waves, of a certain type of cryptographic primitive: the true random number generator. We will show that it is possible to extract sensitive information from the electromagnetic radiation coming from the electronic device. We will also show that it is possible to completly modify the behavior of the true random number generator using a strong electromagnetic field

Ces travaux de thèse portent sur l'accélération de calculs de la cryptographie sur courbes elliptiques (ECC) grâce à une représentation peu habituelle des nombres, appelée représentation modulaire des nombres (ou RNS pour residue number system). Après un état de l'art de l'utilisation du RNS en cryptographie, plusieurs nouveaux algorithmes RNS, plus rapides que ceux de l'état de l'art, sont présentés. Premièrement, nous avons proposé un nouvel algorithme d'inversion modulaire en RNS. Les performances de notre algorithme ont été validées via une implantation FPGA, résultant en une inversion modulaire 5 à 12 fois plus rapide que l'état de l'art, pour les paramètres cryptographiques testés. Deuxièmement, un algorithme de multiplication modulaire RNS a été proposé. Cet algorithme décompose les valeurs en entrée et les calculs, afin de pouvoir réutiliser certaines parties lorsque c'est possible, par exemple lors du calcul d'un carré. Il permet de réduire de près de 25 % le nombre de pré-calculs à stocker et jusqu'à 10 % le nombre de multiplications élémentaires pour certaines applications cryptographiques (p. ex. le logarithme discret). Un algorithme d'exponentiation reprenant les mêmes idées est aussi présenté, réduisant le nombre de multiplications élémentaires de 15 à 22 %, contre un surcoût en pré-calculs à stocker. Troisièmement, un autre algorithme de multiplication modulaire RNS est proposé, ne nécessitant qu'une seule base RNS au lieu de 2 pour l'état de l'art, et utilisable uniquement dans le cadre ECC. Cet algorithme permet, pour certains corps bien spécifiques, de diviser par 2 le nombre de multiplications élémentaires et par 4 les pré-calculs à stocker. Les premiers résultats FPGA donnent des implantations de notre algorithme jusqu'à 2 fois plus petites que celles de l'algorithme de l'état de l'art, pour un surcoût en temps d'au plus 10 %. Finalement, une méthode permettant des tests de divisibilités multiples rapides est proposée, pouvant être utilisée en matériel pour un recodage de scalaire, accélérant certains calculs pour ECC. / The main objective of this PhD thesis is to speedup elliptic curve cryptography (ECC) computations, using the residue number system (RNS). A state-of-art of RNS for cryptographic computations is presented. Then, several new RNS algorithms, faster than state-of-art ones, are proposed. First, a new RNS modular inversion algorithm is presented. This algorithm leads to implementations from 5 to 12 times faster than state-of-art ones, for the standard cryptographic parameters evaluated. Second, a new algorithm for RNS modular multiplication is proposed. In this algorithm, computations are split into independant parts, which can be reused in some computations when operands are reused, for instance to perform a square. It reduces the number of precomputations by 25 % and the number of elementary multiplications up to 10 %, for some cryptographic applications (for example with the discrete logarithm). Using the same idea, an exponentiation algorithm is also proposed. It reduces from 15 % to 22 % the number of elementary multiplications, but requires more precomputations than state-of-art. Third, another modular multiplication algorithm is presented, requiring only one RNS base, instead of 2 for the state-of-art. This algorithm can be used for ECC and well-chosen fields, it divides by 2 the number of elementary multiplications, and by 4 the number of precomputations to store. Partial FPGA implementations of our algorithm halves the area, for a computation time overhead of, at worse, 10 %, compared to state-of-art algorithms. Finally, a method for fast multiple divisibility tests is presented, which can be used in hardware for scalar recoding to accelerate some ECC computations.

Ces travaux de thèse se concentrent sur l'étude des attaques par canaux cachés et les implications sur les mesures à prendre pour un concepteur de circuits sécurisés. Nous nous intéressons d'abord aux différentes attaques par canaux cachés en proposant une amélioration pour un type d'attaque générique particulièrement intéressante : l'attaque par analyse d'information mutuelle. Nous étudions l'effet des différentes techniques d'estimation d'entropie sur les résultats de l'attaque. Nous proposons l'utilisation de fonctions B-splines comme estimateurs étant donné qu'elles sont bien adaptées à notre scénario d'attaques par canaux cachés. Nous étudions aussi l'impact que peut avoir ce type d'attaques sur un cryptosystème symétrique connu, l'Advanced Encryption Standard (AES), en proposant une contre-mesure basée sur la structure algébrique de l'AES. L'opération principale de la majorité des systèmes ECC est la multiplication scalaire qui consiste à additionner un certain nombre de fois un point de courbe elliptique avec lui-même. Dans une deuxième partie, nous nous intéressons à la sécurisation de cette opération. Nous proposons un algorithme de multiplication scalaire à la fois efficace et résistant face aux principales attaques par canaux cachés. Nous étudions enfin les couplages, une construction mathématique basée sur les courbes elliptiques, qui possède des propriétés intéressantes pour la création de nouveaux protocoles cryptographiques. Nous évaluons finalement la résistance aux attaques par canaux cachés de ces constructions. / This thesis focuses on the study of side-channel attacks as well as their consequences on the secure implementation of cryptographic algorithms. We first analyze different side-channel attacks and we propose an improvement of a particularly interesting generic attack: the mutual information analysis. We study the effect of state of the art entropy estimation techniques on the results of the attack. We propose the use of B-spline funtions as estimators as they are well suited to the side-channel attack scenario. We also investigate the consequences of this kind of attack on a well known symmetric cryptosystem, the Advanced Encryption Standard (AES), and we propose a countermeasure based on the algebraic structure of AES. The main operation of ECC is the scalar multiplication that consists of adding an elliptic curve point to itself a certain number of times. In the second part, we investigate how to secure this operation. We propose a scalar multiplication algorithm that is both efficient and secure against main side-channel attacks. We then study pairings, a mathematical construction based on elliptic curves. Pairings have many interesting properties that allow the creation of new cryptographic protocols. We finally evaluate the side-channel resistance of pairings.

Bitcoin and other cryptocurrencies are getting into common usage more and more frequently. Unfortunately this spread is connected with attempts to misuse their principles for personal benefit. The goal of this thesis is to explain the main principles of using bitcoin in relation to the internet identity. This connection is represented by two sources in the thesis: the first is a bitcoin blockchain, the second is the sum of various user profiles used in discussion forums and similar websites. The aim is to create and explain the process how to, by using the combination of this two sources, reveal the identity of a human using cryptocurrencies for payment (from a private person point of view). First, methods used for extraction of correct and useful data from the blockchain and internet profiles must be developed to be able to mine data from the joint database, merging into a full user profile containing personal data. Results of this investigation are extended by the rules of preserving anonymity on the internet, containing both technological and behavioural measures avoiding a share of personal data. The end of this thesis explains possible attack vectors that might be used for compromising cryptocurrencies. The methods of searching of the internet identity are a useful tool for facing these attacks.