Dans ce mémoire, nous proposons des protocoles cryptographiques d'échange de clef, de mise en gage, et de transfert équivoque. Un premier protocole de transfert équivoque, primitive cryptographique universelle pour le calcul multi-parties, s'inspire du protocole d'échange de clef par puzzle de Merkle, et améliore les résultats existants. Puis, nous montrons qu'il est possible de construire ces mêmes primitives cryptographiques sans l'hypothèse des fonctions à sens unique, mais avec le problème 3SUM. Ce problème simple ---dans une liste de n entiers, en trouver trois dont la somme a une certaine valeur--- a une borne inférieure conjecturée de Omega(n^2). / In this work, we propose cryptographic protocols for key exchange, bit commitment and oblivious transfer. Our oblivious transfer protocol, universal cryptographic primitive for multipartie computation, is inspired from Merkle's key exchange protocol with puzzles, and improves on existing results. Then, we show that it's possible to build those same cryptographic primitives without the hypothesis of one-way functions, but with the 3SUM problem. This simple problem ---in a list of n integers, find three that sum is a desired value--- has a conjectured lower bound of Omega(n^2).

L’application du concept de synchronisation appliqué aux composants photoniques non-linéaires a permis l’avènement des communications chaotiques optiques. Les systèmes optoélectronique dans ces chaines de transmission ont déjà démontré leur potentiel en termes de sécurité additionnelle au niveau de la couche physique des réseaux optiques. Cependant, la quantification du niveau de sécurité et l’absence d’un cadre déduit aux aspects multi-utilisateurs (techniques de multiplexage spécifiques) ont fortement freiné le déploiement de ces techniques à large échelle. La recherche effectuée dans le cadre de cette thèse a contribué à l’avancement de ces deux questions ouvertes. Dans premier temps, nous nous sommes intéressés à la sécurité d’une classe de générateur optique particulière: les lasers à semi-conducteur à cavité externe (ECSL). Nous proposons d’attaquer le système dans le contexte le plus difficile, celui dans lequel aucune information n’est a priori disponible. La sortie du laser chaotique (l’intensité optique) est enregistrée, et les séries temporelles obtenues sont analysées. La sécurité est comprise dans ce contexte comme étant la quantité d’information sur les paramètres du système (analogue d’une clé dans les systèmes de cryptage conventionnels) et/ou la fonction non-linéaire du système (l’équivalent de l’algorithme de cryptage). Un ECSL est un système possédant un délai (aussi appelé retard), un paramètre critique pour la sécurité. Nous avons étudié l’influence des paramètres ajustable de l’ECSL chaotique sur l’identification du délai: l’intensité de la rétroaction optique, la valeur du délai, et le courant alimentant le laser (aussi appelé courant de pompe). Dans un deuxième temps nous interprétons ces résultats sur la base des régimes dynamiques précédent l’apparition du chaos dans l’ECSL. Nous avons proposé par la suite une architecture pour multiplexer des signaux chaotiques optiques générés par des ECSL. Nous démontrons la supériorité de cette approche en terme d’efficacité spectrale relativement aux méthodes de multiplexage en longueur d’onde (wavelength division multiplexing, WDM) appliquées aux communications optiques par chaos (aussi connues sous le nom de chaotic WDM ). Nous avons adapté un concept fondamental de la théorie de la synchronisation: la décomposition active-passive (APD) en utilisant des composants optiques simples. Nous démontrons la possibilité de multiplexer et démultiplexage de deux signaux chaotiques optiques par synchronisation (en utilisant deux émetteurs et deux récepteurs). Les performances et la robustesse de cette structure sont analysées ainsi que la possibilité de crypter et de décrypter des messages. Après cela, nous avons utilisé une classe de systèmes optoélectroniques différente de celle correspondant au deux premières sections, avec l’objectif d’utiliser un seul oscillateur chaotique pour encoder plusieurs messages au lieu de considérer un oscillateur par message. A cette fin, nous avons modifié une structure d’un générateur de chaos électro-optique existant dans la littérature en lui ajoutant plusieurs boucles de rétroactions non-linéaires. Chacune d’elle est utilisée pour l’encryptage d’un message, réalisée, par exemple, par la modulation du gain non-linéaire de la boucle. Nous avons analysé différentes configurations possibles, ainsi que les propriétés des signaux chaotiques générés au sein de chaque boucle et utilisés pour transporter les différents messages. Nous avons expliqué dans quelle mesure l’orthogonalité (ou décorrélation) entre les différents signaux peut être utilisée à notre avantage pour dériver des équations de décodage de faible complexité algorithmique (comme fonction du nombre d’utilisateurs). Enfin, nous analysons comment certains phénomènes d’interférences entre signaux porteurs peuvent être pris en compte afin de toujours permettre la récupération des messages. / With the rapid development of optical communications and the increasing amount of data exchanged, it has become utterly important to provide effective architectures to protect sensitive data. The use of chaotic optoelectronic devices has already demonstrated great potential in terms of additional computational security at the physical layer of the optical network. However, the determination of the security level and the lack of a multi-user framework are two hurdles which have prevented their deployment on a large scale. In this thesis, we propose to address these two issues. First, we investigate the security of a widely used chaotic generator, the external cavity semiconductor laser (ECSL). This is a time-delay system known for providing complex and high-dimensional chaos, but with a low level of security regarding the identification of its most critical parameter, the time delay. We perform a detailed analysis of the influence of the ECSL parameters to devise how higher levels of security can be achieved and provide a physical interpretation of their origin. Second, we devise new architectures to multiplex optical chaotic signals and realize multi-user communications at high bit rates. We propose two different approaches exploiting known chaotic optoelectronic devices. The first one uses mutually coupled ECSL and extends typical chaos-based encryption strategies, such as chaos-shift keying (CSK) and chaos modulation (CMo). The second one uses an electro-optical oscillator (EOO) with multiple delayed feedback loops and aims first at transposing coded-division multiple access (CDMA) and then at developing novel strategies of encryption and decryption, when the time-delays of each feedback loop are time- dependent.

In the presented work we focus on applications of decision problems from combinatorial group theory. Namely we analyse the Shpilrain-Zapata pro- tocol. We give formal proof that small cancellation groups are good platform for the protocol because the word problem is solvable in linear time and they are generic. We also analyse the complexity of the brute force attack on the protocol and show that in a theoretical way the protocol is immune to attack by adversary with arbitrary computing power.

Title: Goppa codes and their applications Author: Bc. Jaroslav Kotil Department: Department of algebra Supervisor: prof. RNDr. Aleš Drápal, CSc., DSc. Abstract: In this diploma paper we introduce Goppa codes, describe their para- metres and inclusion in Alternant codes, which are residual Generalized Reed- Solomon codes, and Algebraic-geometry codes. Aftewards we demonstrate deco- ding of Goppa codes and introduce Wild Goppa codes. We also describe post- quantum cryptography member: McEliece cryptosystem for which no effective attacks with quantum computers are known. We outline a usage of this crypto- system with Goppa codes and describe the security of the cryptosystem together with possible attacks of which the most effective ones are based on information- set decoding. Keywords: Goppa codes, Generalized Reed-Solomon codes, Algebraic-geometry codes, Post-quantum cryptography, McEliece cryptosystem 1

Les générateurs de nombres véritablement aléatoires (TRNG) sont des composants cruciaux dans certaines applications cryptographiques sensibles (génération de clés de chiffrement, génération de signatures DSA, etc). Comme il s’agit de composants très bas-niveau, une faille dans le TRNG peut remettre en question la sécurité de tout le système cryptographique qui l’exploite. Alors que beaucoup de principes de TRNG existent dans la littérature, peu de travaux analysent rigoureusement ces architectures en termes de sécurité. L’objectif de cette thèse était d’étudier les avantages des techniques de conception asynchrone pour la conception de générateurs de nombres véritablement aléatoires (TRNG) sûrs et robustes. Nous nous sommes en particulier intéressés à des oscillateurs numériques appelés anneaux auto-séquencés. Ceux-ci exploitent un protocole de requêtes et acquittements pour séquencer les données qui y circulent. En exploitant les propriétés uniques de ces anneaux, nous proposons un nouveau principe de TRNG, avec une étude théorique détaillée sur son fonctionnement, et une évaluation du cœur du générateur dans des cibles ASIC et FPGA. Nous montrons que ce nouveau principe permet non seulement de générer des suites aléatoires de très bonne qualité et avec un très haut débit (>100 Mbit/s), mais il permet aussi une modélisation réaliste de l’entropie des bits de sortie (celle-ci peut être réglée grâce aux paramètres de l’extracteur). Ce travail propose également une méthodologie complète pour concevoir ce générateur, pour le dimensionner en fonction du niveau de bruit dans le circuit, et pour le sécuriser face aux attaques et défaillances / True Random Number Generators (TRNG) are ubiquitous in many critical cryptographic applications (key generation, DSA signatures, etc). While many TRNG designs exist in literature, only a few of them deal with security aspects, which is surprising considering that they are low-level primitives in a cryptographic system (a weak TRNG can jeopardize a whole cryptographic system). The objective of this thesis was to study the advantages of asynchronous design techniques in order to build true random number generators that are secure and robust. We especially focused on digital oscillators called self-timed rings (STR), which use a handshake request and acknowledgement protocol to organize the propagation of data. Using some of the unique properties of STRs, we propose a new TRNG principle, with a detailed theoretical study of its behavior, and an evaluation of the TRNG core in ASICs and FPGAs. We demonstrate that this new principle allows to generate high quality random bit sequences with a very high throughput (> 100 Mbit/s). Moreover, it enables a realistic estimation for the entropy per output bit (this entropy level can be tuned using the entropy extractor parameters). We also present a complete methodology to design the TRNG, to properly set up the architecture with regards to the level of noise in the circuit, and to secure it against attacks and failures

L’émergence des systèmes embarqués a permis le développement des réseaux de capteurs sans fil dans de nombreux domaines différents. Cependant, la sécurité reste un problème ouvert. La vulnérabilité des nœuds est principalement liée au manque de ressources. En effet, l’unité de traitement ne dispose pas d’assez de puissance et de mémoire pour gérer des mécanismes de sécurité très complexes.La cryptographie est une solution qui est largement utilisée pour sécuriser les réseaux. Par rapport à la cryptographie symétrique, la cryptographie asymétrique nécessite des calculs plus compliqués,mais elle offre une distribution de clés plus sophistiquée et la signature numérique. Dans cette thèse, nous essayons d’optimiser la performance d’ECC (Elliptic Curve Cryptography), un cryptosystème asymétrique qui est connu pour sa robustesse et son utilisation de clé plus courte par rapport à RSA. Nous proposons d’utiliser le parallélisme pour accélérer le calcul de la multiplication scalaire, qui est reconnue comme l’opération la plus coûteuse sur les courbes elliptiques. Les résultats de tests ont montré que notre solution offre un gain intéressant malgré une augmentation de la consommation d’énergie.La deuxième partie de la contribution concerne l’application de la tolérance aux pannes dans notre architecture de parallélisation. Nous utilisons les nœuds redondants pour la détection des pannes et la restauration du calcul. Ainsi, en utilisant l’ECC et la tolérance aux pannes, nous proposons une solution de sécurité efficace et sûre pour les systèmes embarqués. / The emergence of embedded systems has enabled the development of wireless sensor networks indifferent domains. However, the security remains an open problem. The vulnerability of sensor nodesis mainly due to the lack of resources. In fact, the processing unit doesn’t have enough power ormemory to handle complex security mechanisms.Cryptography is a widely used solution to secure networks. Compared with symmetric cryptography,the asymmetric cryptography requires more complicated computations, but it offers moresophisticated key distribution schemes and digital signature.In this thesis, we try to optimize the performance of ECC. An asymmetric cryptosystem which isknown for its robustness and the use of shorter keys than RSA. We propose to use parallelismtechniques to accelerate the computation of scalar multiplications, which is recognized as the mostcomputationally expensive operation on elliptic curves. The test results have shown that our solutionprovides a significant gain despite an increase in energy consumption.The 2nd part of our contribution is the application of fault tolerance in our parallelism architecture.We use redundant nodes for fault detection and computation recovery. Thus, by using ECC and faulttolerance, we propose an efficient and reliable security solution for embedded systems.

The Signal protocol can be considered state-of-the-art when it comes to secure messaging, but advances in quantum computing stress the importance of finding post-quantum resistant alternatives to its asymmetric cryptographic primitives. The aim is to determine whether existing post-quantum cryptography can be used as a drop-in replacement for the public-key cryptography currently used in the Signal protocol and what the performance trade-offs may be. An implementation of the Signal protocol using commutative supersingular isogeny Diffie-Hellman (CSIDH) key exchange operations in place of elliptic-curve Diffie-Hellman (ECDH) is proposed. The benchmark results on a Samsung Galaxy Note 8 mobile device equipped with a 64-bit Samsung Exynos 9 (8895) octa-core CPU shows that it takes roughly 8 seconds to initialize a session using CSIDH-512 and over 40 seconds using CSIDH-1024, without platform specific optimization. To the best of our knowledge, the proposed implementation is the first post-quantum resistant Signal protocol implementation and the first evaluation of using CSIDH as a drop-in replacement for ECDH in a communication protocol.

Cryptosystems based on elliptic curves are in wide-spread use, they are considered secure because of the difficulty to solve the elliptic curve discrete logarithm problem. Pollard's rho method is regarded as the best method for attacking the logarithm problem to date, yet it is still not efficient enough to break an elliptic curve cryptosystem. This is because its time complexity is O(√n) and for uses in cryptography the value of n will be very large. The objective of this thesis is to see if there are ways to improve Pollard's rho method. To do this, we study some modifications of the original functions used in the method. We also investigate some different functions proposed by other researchers to see if we can find a version that will improve the performance. From the experiments conducted on these modifications and functions, we can conclude that we get an improvement in the performance for some of them.

Diversas aplicações de redes de sensores sem fio necessitam de serviços de segurança, como confidencialidade, integridade e autenticação de origem de dados. Contudo, dadas as limitações de processamento, memória e suprimento de energia dos dispositivos, os mecanismos de segurança tradicionais podem causar efeitos indesejáveis na rede, como atraso na comunicação e aumento no consumo de energia, impondo obstáculos para seu uso na tecnologia em questão. Muitas propostas de esquemas de segurança baseados em criptografia simétrica projetados especificamente para redes de sensores sem fio são encontradas na literatura. Contudo, essas soluções são focadas na segurança salto-a-salto. Tal abordagem é adequada para garantir a segurança dos enlaces deste tipo de rede, mas não garante a segurança na comunicação fim-a-fim. Neste trabalho são apresentados cenários e desafios de implementação de segurança neste tipo de rede, e a concepção, o projeto e a implementação de uma arquitetura de segurança para redes de sensores sem fio, que tem como objetivos: prover segurança na comunicação fim-a-fim; permitir a interoperabilidade entre diferentes sistemas; e possibilitar uma maior flexibilidade em relação à utilização de chaves criptográficas em diferentes cenários e topologias. Adicionalmente, a solução proposta suporta ativação e desativação de seus serviços em tempo de execução. O projeto da referida arquitetura, atuante na camada de aplicação da pilha de protocolos de rede, foi construído com base na análise das características de arquiteturas encontradas na literatura, bem como de estratégias adotadas por estas. Para a construção da implementação foram selecionados mecanismos e algoritmos criptográficos a partir da avaliação de desempenho que considerou assimétricas de uso de memória, tempo de execução e consumo de energia. Como resultados são apresentados a especificação da arquitetura, a avaliação qualitativa da mesma e a avaliação de desempenho da implementação desenvolvida como prova de conceito. Além disso, é apresentada uma análise do impacto de diferentes topologias e características de disposição na tarefa de distribuição de chaves criptográficas em redes de sensores sem fio. / Many wireless sensor networks applications need security services, such as confidentiality, data integrity and data source authentication. On the other hand, because of device limitations, security mechanisms may affect the network energy consumption and communication delay, which impose a great challenge for practical implementation of security mechanisms in such scenario. Many solutions based on symmetric cryptography were proposed for the specific challenges of wireless sensor networks. Nevertheless, they are focused on hop-by-hop security. Such approach is suited to provide link-layer security, but it cannot guarantee end-to-end security. This work presents scenarios and challenges to implement security in wireless sensor networks, and the conception, design and implementation of a security architecture, which aims to provide: security in end-to-end communication; interoperability between different systems, and enable greater flexibility in cryptographic keys distribution in different scenarios and topologies. Additionally, the proposed solution supports on-the-y adjustment of its security services. The architecture design, which targets the application layer of the network protocol stack, was based on the main properties of the architectures found in literature as well as adopted strategies. For the implementation, mechanisms and cryptographic algorithms were selected through the performance evaluation that considers memory usage, execution time and power consumption as metrics. The results were the architecture specification and its qualitative analysis, and the performance evaluation of the implementation developed as proof of concept. Furthermore, we present an analysis of topology and deployment impact on key distribution task.

Os sistemas criptográficos de chave pública amplamente utilizados hoje em dia tem sua segurança baseada na suposição da intratabilidade dos problemas de fatoração de inteiros e do logaritmo discreto, sendo que ambos foram demonstrados inseguros sob o advento dos computadores quânticos. Sistemas criptográficos baseados em Multivariáveis Quadráticas (MQ) utilizam como base o problema MQ, que consiste em resolver um sistema de equações polinomiais multivariáveis quadráticas sobre um corpo finito. O problema MQ foi provado como sendo NP-completo e até hoje não se conhece algoritmo, nem mesmo quântico, de tempo polinomial que possa resolver o problema, fazendo com que sistemas criptográficos baseados nesta primitiva mereçam ser investigados e desenvolvidos como reais candidatos a proverem nossa criptografia pós-quântica. Durante a CRYPTO\'2011 Sakumoto, Shirai e Hiwatari introduziram dois novos protocolos de identificação baseados em polinômios multivariáveis quadráticos, os quais chamamos de MQID-3 e MQID-5, e que em especial e pela primeira vez, tem sua segurança reduzida apenas ao problema MQ. Baseados nestas propostas iremos apresentar uma versão aprimorada do protocolo MQID-3 na qual teremos uma redução da comunicação necessária em aproximadamente 9%. / The public-key cryptography widely used nowadays have their security based on the assumption of the intractability of the problems of integer factorization and discrete logarithm, both of which were proven unsafe in the advent of quantum computers. Cryptographic systems based on Multivariate Quadratic polynomials (MQ) are based on the MQ problem, which consists in solve a system of multivariate quadratic polynomials over a finite field. The MQ problem has been proven NP-complete and so far no polynomial time algorithm is known, not even quantum, which would resolve this problem, making worthwhile to be investigated and developed as a real candidate to provide post-quantum cryptography. In CRYPTO\'2011 Sakumoto, Shirai and Hiwatari introduced two new identification protocols based on multivariate quadratic polynomials, which we call MQID-3 and MQID-5, in particular, for the first time, their security is based only on the MQ problem. Using these proposals, we will present an improved version of the protocol MQID-3 that reduces communication by approximately 9%.