Applications of finite-field wavelets, paraunitary matrices, and multivariate polynomials in the design of efficient cryptographic algorithms for resource-limited devices and wireless sensor nodes is the main topic of this thesis. In this research, multivariate paraunitary matrices over fields of characteristic two are of special importance. Therefore, the factorization of their bivariate counterpart into the product of fully-parameterized building blocks was studied. Result were a two-level factorization algorithm and new building blocks over the ring of polynomials that allow a complete first-level factorization. One of the contributions in this thesis was a completely new design for self-synchronizing stream ciphers based on wavelets over fields of characteristic two. Since these wavelets can be efficiently designed and implemented using paraunitary matrices, the designed cipher is highly efficient in terms of encryption and decryption complexities. The cryptanalysis of the proposed cipher did not reveal any vulnerabilities to the current state of the art attacks developed for stream ciphers. A completely novel framework for the design of multivariate asymmetric cryptosystems (based on paraunitary matrices) is a main contribution in this thesis. Using algebraic properties of paraunitary matrices, the computational security of systems designed based on this framework was studied. It was proved, for the first time, that breaking any instance of such systems provides a positive answer to an algebraic longstanding (non- computational) open problem. Therefore, the proposed framework certainly is an improvement toward the design of provably secure multivariate cryptosystems. Using this approach, a public-key cryptosystem and a digital signature scheme was proposed. Considering the attractiveness of algebraic techniques, their applications in the design of cryptographic algorithms for wireless sensor networks was investigated. A novel key pre-distribution scheme for data confidentiality in sensor networks was proposed. This scheme outperforms all previous designs in terms of network resiliency against the node capture. Theoretical analysis showed improvement over previous schemes and also robustness in design. In addition to key pre-distribution, a location-aware scheme was proposed that provides authenticity and availability for sensor networks. Main ingredients of this scheme are node collaboration for entity authenticity, hash tree for data authenticity, and random network coding for data availability. This scheme is the first one in its category that provides a practical solution to all the aforementioned security services.

Thesis (M.App.Sc.) - Carleton University, 2006. / Includes bibliographical references (p. 80-82). Also available in electronic format on the Internet.

Orientador: Marco Aurelio Amaral Henriques / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-16T22:16:21Z (GMT). No. of bitstreams: 1 Oliveira_MatheusFernandesde_M.pdf: 924070 bytes, checksum: b0355f2150875c0a6c636bf2da2ea8a9 (MD5) Previous issue date: 2010 / Resumo: Emparelhamentos bilineares sobre curvas elípticas são funções matemáticas que viabilizam o desenvolvimento de uma série de novos protocolos criptográficos, entre eles, os criptossistemas baseados em identidades. Esses criptossistemas representam uma nova forma de se implementar criptografia de chaves públicas na qual são atenuadas ou completamente retiradas as restrições relativas ao tipo, tamanho e formato das chaves públicas. Este trabalho apresenta um estudo sobre a implementação de criptossistemas baseados em emparelhamentos bilineares sobre curvas elípticas em cartões inteligentes de oito bits. O trabalho mostra ainda o desenvolvimento de equações específicas baseadas no método conhecido como Montgomery's Ladder para multiplicação escalar de curvas elípticas supersingulares em corpos binários. Estas novas equações tornam o algoritmo mais rápido sem perder suas características de segurança originais. O trabalho apresenta também a técnica de delegação segura de emparelhamentos, na qual um dispositivo computacionalmente restrito, como um cartão inteligente, delega o cálculo do emparelhamento para um dispositivo com maior poder computacional. É proposta uma modificação nesta técnica que diminui o número de operações executadas pelo cartão inteligente / Abstract: Bilinear pairings over elliptic curves are mathematical functions that enable the development of a set of new cryptographic protocols, including the so called identity based cryptosystems. These cryptosystems represent a new way to implement public- key cryptography in such a way that the restrictions related to public keys type, size and format are reduced or completely removed. This work presents a study about implementation of pairing based cryptosystems in 8-bit smart cards. It also presents new equations to be used in Montgomery's Ladder algorithm for scalar multiplication of supersingular ellipitic curves over binary fields. These equations make the algorithm faster without compromising its security characteristics. Finally, it discusses the secure delegation of pairing computation, that enables a computationally limited device, like a smart card, to delegate the computation of pairings to a more powerful device. It is proposed a modification in this technique to decrease the number of operations executed by the smart card / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

Orientador: Júlio César Lopez Hernández / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T05:47:42Z (GMT). No. of bitstreams: 1 Aranha_DiegodeFreitas_D.pdf: 2545815 bytes, checksum: b630a80d0f8be161e6cb7519072882ed (MD5) Previous issue date: 2011 / Resumo: O advento da criptografia assimétrica ou de chave pública possibilitou a aplicação de criptografia em novos cenários, como assinaturas digitais e comércio eletrônico, tornando-a componente vital para o fornecimento de confidencialidade e autenticação em meios de comunicação. Dentre os métodos mais eficientes de criptografia assimétrica, a criptografia de curvas elípticas destaca-se pelos baixos requisitos de armazenamento para chaves e custo computacional para execução. A descoberta relativamente recente da criptografia baseada em emparelhamentos bilineares sobre curvas elípticas permitiu ainda sua flexibilização e a construção de sistemas criptográficos com propriedades inovadoras, como sistemas baseados em identidades e suas variantes. Porém, o custo computacional de criptossistemas baseados em emparelhamentos ainda permanece significativamente maior do que os assimétricos tradicionais, representando um obstáculo para sua adoção, especialmente em dispositivos com recursos limitados. As contribuições deste trabalho objetivam aprimorar o desempenho de criptossistemas baseados em curvas elípticas e emparelhamentos bilineares e consistem em: (i) implementação eficiente de corpos binários em arquiteturas embutidas de 8 bits (microcontroladores presentes em sensores sem fio); (ii) formulação eficiente de aritmética em corpos binários para conjuntos vetoriais de arquiteturas de 64 bits e famílias mais recentes de processadores desktop dotadas de suporte nativo à multiplicação em corpos binários; (iii) técnicas para implementação serial e paralela de curvas elípticas binárias e emparelhamentos bilineares simétricos e assimétricos definidos sobre corpos primos ou binários. Estas contribuições permitiram obter significativos ganhos de desempenho e, conseqüentemente, uma série de recordes de velocidade para o cálculo de diversos algoritmos criptográficos relevantes em arquiteturas modernas que vão de sistemas embarcados de 8 bits a processadores com 8 cores / Abstract: The development of asymmetric or public key cryptography made possible new applications of cryptography such as digital signatures and electronic commerce. Cryptography is now a vital component for providing confidentiality and authentication in communication infra-structures. Elliptic Curve Cryptography is among the most efficient public-key methods because of its low storage and computational requirements. The relatively recent advent of Pairing-Based Cryptography allowed the further construction of flexible and innovative cryptographic solutions like Identity-Based Cryptography and variants. However, the computational cost of pairing-based cryptosystems remains significantly higher than traditional public key cryptosystems and thus an important obstacle for adoption, specially in resource-constrained devices. The main contributions of this work aim to improve the performance of curve-based cryptosystems, consisting of: (i) efficient implementation of binary fields in 8-bit microcontrollers embedded in sensor network nodes; (ii) efficient formulation of binary field arithmetic in terms of vector instructions present in 64-bit architectures, and on the recently-introduced native support for binary field multiplication in the latest Intel microarchitecture families; (iii) techniques for serial and parallel implementation of binary elliptic curves and symmetric and asymmetric pairings defined over prime and binary fields. These contributions produced important performance improvements and, consequently, several speed records for computing relevant cryptographic algorithms in modern computer architectures ranging from embedded 8-bit microcontrollers to 8-core processors / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

La cryptographie basée sur les réseaux a connu depuis quelques années un très fort développement notamment du fait qu’il existe des systèmes cryptographiques basés sur les réseaux avec des propriétés de sécurité plus fortes que dans les cas plus classiques de théorie des nombres. Les problèmes difficiles des réseaux, par exemple le problème de trouver des vecteurs courts non nuls, semblent résister aux attaques utilisant des ordinateurs quantiques et les meilleurs algorithmes qui existent pour les résoudre sont exponentiels en fonction du temps. L’objet de cette thèse est la construction de primitives cryptographiques à clé publique pour l’ano- nymat dont la sécurité repose sur des problèmes difficiles des réseaux.Nous nous intéressons aux schémas de signature de cercle. Tout d’abord, nous proposons une nouvelle définition d’anonymat et nous exposons un nouveau schéma de signature de cercle. Ensuite, nous donnons une étude de sécurité rigoureuse suivant deux définitions de résistance la contrefaçon. La première est la résistance à la contrefaçon contre les attaques à sous-cercles choisis et la deuxième est la résistance à la contrefaçon contre les attaques de corruption interne.Nous présentons ensuite un nouveau schéma d’identification de cercle et nous développons une analyse complète de sa sécurité. Enfin, nous montrons que les techniques utilisées pour construire le schéma précédent peuvent être utilisées pour construire un schéma d’identification de cercle à seuil. / Lattice-based cryptography has known during the last decade rapid develop- ments thanks to stronger security properties. In fact, there exist lattice-based cryp- tographic systems whose security is stronger than those based on the conventional number theory approach. The hard problems of lattices, for example the problem of finding short non-zero vectors, seems to resist quantum computers attacks. Mo- reover, the best existing algorithms solving them are exponential in time. The pur- pose of this thesis is the construction of public key cryptographic primitives for anonymity, whose security is based on the latter.In particular, we are interested in ring signature schemes. First, we propose a new formal definition of anonymity and we present a new ring signature scheme. Second, we give a rigorous study of security, following two definitions of unfor- geability. The first of which is unforgeability against chosen-subring attacks and the other one is unforgeability with respect to insider corruption.Afterwards, we present a new ring identification scheme and we develop a full analysis of its security. Finally, we show that the techniques used to build this scheme, can be used to construct a threshold ring identification scheme.

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.

This work consists in a performance evaluating of Asymmetrical cryptographic algorithms in embedded platforms used in Wireless Sensor Networks (WSN). The sensor devices have low computing power and energy, therefore safety techniques should not consume large amounts of resources. The asymmetric cryptographic algorithms RSA, ECC and MQQ were evaluated on platforms Desktop, ARM, MSP430 and AVR. The evaluations were performed using the SimpleScalar simulators, Sim-Panalyzer, MSPsim and AVRORA . The evaluation criteria were: processing time, memory usage and processor, as well as energy consumption. The data showed that the algorithm MQQ was more efficient than RSA and ECC algorithms in most assessment criteria, in addition, the ECC algorithm obtained the best results when compared with the RSA algorithm / Esse trabalho consiste na avaliação de desempenho de algoritmos criptográficos assimétrico em plataformas embarcadas usadas em Redes de Sensores Sem Fio (RSSF). Os dispositivos sensores têm baixa capacidade computacional e energética, portanto técnicas de segurança não devem consumir grande quantidade de recursos. Os algoritmos criptográficos assimétricos RSA, ECC e MQQ foram avaliados nas plataformas Desktop, ARM, MSP430 e AVR. A avaliação de desempenho foi realizada com auxílio dos simuladores SimpleScalar, Sim- Panalyzer, MSPsim e AVRORA. Os critérios de avaliação foram: tempo de processamento, uso de memória e processador, além do consumo de energia. Os dados revelaram que o algoritmo MQQ foi mais eficiente que os algoritmos RSA e ECC na maioria dos critérios de avaliação, além disso, o algoritmo ECC obteve os melhores resultados quando comparado com o algoritmo RSA

Cílem této práce je zpracovat úvod do problematiky hypereliptických křivek s důrazem na konečná pole. T práci je dále popsán úvod do teorie divizorů na hypereliptických křivkách, jejich reprezentace, aritmetika nad divizory a jejich využití v kryptografii. Teorie je hojně demonstrována příklady a výpočty v systému Mathematica.

In today’s society, especially after everything that was reported by Edward Snowden when he, during 2013, showed how USA’s NSA worked with global surveillance, there is a great need to keep communication secure. Se- cure both in such a way that the contents in messages are protected from unwanted parties as well as in such a way that messages’ authenticity can be verified. It’s just as important to know who one is communicating with as it is to know that no unauthorized person can read material not meant for them. We see more and more solutions like for instance Let’s Encrypt that offer free encryption for web traffic but when it actually comes to SMS traffic there aren’t as many effective options available. The purpose of this work is to develop a system to examine how one most effectively could treat SMS in a secure and authenticated fashion. The goal is to, contrary to many other solutions, not be dependent upon a third party but rather utilize the existing SMS protocol and to make sure that the con- tents is encrypted by use of public key cryptography. This leads to it being enough to use the application to be able to communicate securely as there would be no central server that could be closed down or in other ways af- fected to lessen the security of the communication. We also get a system that is much less dependent on mobile data and will thus become more flexible in areas where this can be costly or hard to reach. Beyond this a system for verification of external keys will be explored. Even if it, in case the user chooses to use it, will need access to mobile data, it could be a useful tool for authentication of communication with parties with whom one has not been in contact with before since they can publish their public key and then refer to it within the message. An example use case for this would be a gov- ernment needing to publish information to its citizens; then this key can be published on their web site so that anyone easily could verify it (the goal is to have this be done automatically during message retrieval). / I dagens samhälle, särskilt efter bland annat allt som rapporterades av Ed- ward Snowden när han under 2013 påvisade hur USAs NSA jobbade med global övervakning, är det av stor vikt av att kommunikation bör hållas säker. Säker både på så sätt att innehållet i meddelanden skyddas från oön- skade personer och på så sätt att meddelandens autenticitet kan styrkas. Det är minst lika viktigt att veta vem man kommunicerar med som att veta att ingen obehörig kan läsa material som inte är ämnat för dem. Vi ser fler och fler lösningar som till exempel Let’s Encrypt som erbjuder gratis kryptering av webbtrafik men när det gäller just SMS-trafik finns inte lika många och effektiva lösningar. Syftet med det här arbetet är att utveckla ett system för att undersöka hur man på bästa sätt skulle kunna behandla SMS på ett säkert och autentis- erat sätt. Målet är att, till skillnad mot många andra lösningar, inte vara beroende av en tredje part utan istället nyttja det befintliga SMS-protokollet men se till att innehållet är krypterat med hjälp av public key cryptography. Detta leder till att det räcker att använda applikationen för att kunna kom- municera säkert, det finns ingen central server som skulle kunna stängas ner eller på andra sätt påverkas för att försämra kommunikationens säker- het. Vi får också ett system som är mycket mindre beroende av mobildata och blir därför mer flexibelt i områden där dessa kan vara kostsamma eller svåråtkomliga. Utöver detta kommer ett system för extern autentisering av nycklar undersökas. Även om detta, om avsändaren väljer att utnyttja det, kommer att kräva tillgång till mobil datatrafik så skulle det vara ett nyttigt verktyg för att kunna autentisera kommunikation med personer som man aldrig tidigare varit kontakt med då dessa i så fall kan publicera sin nyckel online och sedan hänvisa till den i meddelandet. Exempel på användning för detta är om en myndighet behöver gå ut med information till medbor- garna; då kan denna nyckel publiceras på dess webbsida så att alla enkelt kan kontrollera den (målet är i så fall att detta skall ske automatiskt under hämtning av ett meddelande).

Cette thèse se concentre sur les problèmes liés à l’authentification dans la technologie RFID. Cette technologie est l’une des technologies les plus prometteuses dans le domaine de l’informatique ubiquitaire, elle est souvent désignée comme la prochaine révolution après Internet. Cependant, à cause des ressources très limitées en termes de calcul, mémoire et énergie sur les étiquettes RFID, les algorithmes classiques de sécurité ne peuvent pas être implémentés sur les étiquettes à bas coût rendant ainsi la sécurité et la vie privée un important sujet de recherche aujourd’hui. Dans un premier temps, nous étudions le passage à l’échelle dans les systèmes RFID à bas coût en développant un module pour ns-3 qui simule le standard EPC Class 1 Generation 2 pour établir un cadre stricte pour l’identification sécurisée des RFID à bas coût, ce qui nous conduit à l’utilisation de la cryptographie à clés publiques. Ensuite, nous proposons un protocole d’authentification basé sur une adaptation que nous avons introduit sur le célèbre cryptosystème NTRU. Ce protocole est spécialement conçu pour les RFID à bas coût comme les étiquettes n’implémentent que des opérations simples (xor, décalages, addition) et il garantit le passage à l’échelle. Enfin, nous considérons l’identification à divulgation nulle de connaissance, ce type d’approches est très utile dans de nombreuses applications RFID. Nous proposons deux protocoles à divulgation nulle de connaissance basés sur cryptoGPS et cryptoGPS randomisé. Ces approches consistent à stocker sur le serveur des coupons pré-calculés, ainsi la sécurité et la vie privée sont mieux supportées que dans les autres approches de ce type / This thesis focuses on issues related to authentication in low-cost radio frequency identification technology, more commonly referred to as RFID. This technology it is often referred to as the next technological revolution after the Internet. However, due to the very limited resources in terms of computation, memory and energy on RFID tags, conventional security algorithms cannot be implemented on low-cost RFID tags making security and privacy an important research subject today. First of all, we investigate the scalability in low-cost RFID systems by developing a ns-3 module to simulate the universal low-cost RFID standard EPC Class-1 Generation-2 in order to establish a strict framework for secure identification in low-cost RFID systems. We show that, the symmetrical key cryptography is excluded from being used in any scalable low-cost RFID standard. Then, we propose a scalable authentification protocol based on our adaptation of the famous public key cryptosystem NTRU. This protocol is specially designed for low-cost RFID systems, it can be efficiently implemented into low-cost tags. Finally, we consider the zero-knowledge identification i.e. when the no secret sharing between the tag and the reader is needed. Such identification approaches are very helpful in many RFID applications when the tag changes constantly the field of administration. We propose two lightweight zero-knowledge identification approaches based on GPS and randomized GPS schemes. The proposed approaches consist in storing in the back-end precomputed values in the form of coupons. So, the GPS-based variant can be private and the number of coupons can be much higher than in other approaches thus leading to higher resistance to denial of service attacks for cheaper tags