The Internet of Things (IoT) is increasingly becoming an integral component of many applications in consumer, industrial and other areas. Notions such as smart industry, smart transport, and smart world are, in large part, enabled by IoT. At its core, the IoT is underpinned by a group of devices, such as sensors and actuators, working collaboratively to provide a required service. One of the important requirements most IoT applications are expected to satisfy is ensuring the security and privacy of users. Security is an umbrella term that encompasses notions such as confidentiality, integrity and privacy, that are typically achieved using cryptographic encryption techniques. A special form of communication common in many IoT applications is group communication, where there are two or more recipients of a given message. In or-der to encrypt a message broadcast to a group, it is required that the participating parties agree on a group key a priori. Establishing and managing a group key in IoT environments, where devices are resources-constrained and groups are dynamic, is a non-trivial problem. The problem presents unique challenges with regard to con-structing protocols from lightweight and secure primitives commensurate with the resource-constrained nature of devices and maintaining security as devices dynamically leave or join a group. This thesis presents lightweight group key management protocols proposed to address the aforementioned problem, in a widely adopted model of a generic IoT network consisting of a gateway with reasonable computational power and a set of resource-constrained nodes. The aim of the group key management protocols is to enable the gateway and the set of resource-constrained devices to establish and manage a group key, which is then used to encrypt group messages. The main problems the protocols attempt to solve are establishing a group key among participating IoT devices in a secure and computationally feasible manner; enabling additionor removal of a device to the group in a security preserving manner; and enabling generation of a group session key in an efficient manner without re-running the protocol from scratch. The main challenge in designing such protocols is ensuring that the computations that a given IoT device performs as part of participating in the protocol are computationally feasible during initial group establishment, group keyupdate, and adding or removing a node from the group. The work presented in this thesis shows that the challenge can be overcome by designing protocols from lightweight cryptographic primitives. Specifically, protocols that exploit the lightweight nature of crypto-systems based on elliptic curves and the perfect secrecy of the One Time Pad (OTP) are presented. The protocols are designed in such a way that a resource-constrained member node performs a constant number of computationally easy computations during all stages of the group key management process. To demonstrate that the protocols are practically feasible, implementation resultof one of the protocols is also presented, showing that the protocol outperforms similar state-of-the-art protocols with regard to energy consumption, execution time, memory usage and number of messages generated. / <p>Vid tidpunkten för framläggningen av avhandlingen var följande delarbete opublicerat: delarbete 3 (manuskript).</p><p>At the time of the defence the following paper was unpublished: paper 3 (manuscript).</p> / SMART (Smarta system och tjänster för ett effektivt och innovativt samhälle)

This thesis introduces a new tower field representation, optimal tower fields (OTFs), that facilitates efficient finite field operations. The recursive direct inversion method presented for OTFs has significantly lower complexity than the known best method for inversion in optimal extension fields (OEFs), i.e., Itoh-Tsujii's inversion technique. The complexity of OTF inversion algorithm is shown to be O(m^2), significantly better than that of the Itoh-Tsujii algorithm, i.e. O(m^2(log_2 m)). This complexity is further improved to O(m^(log_2 3)) by utilizing the Karatsuba-Ofman algorithm. In addition, it is shown that OTFs are in fact a special class of OEFs and OTF elements may be converted to OEF representation via a simple permutation of the coefficients. Hence, OTF operations may be utilized to achieve the OEF arithmetic operations whenever a corresponding OTF representation exists. While the original OTF multiplication and squaring operations require slightly more additions than their OEF counterparts, due to the free conversion, both OTF operations may be achieved with the complexity of OEF operations. Furthermore, efficient finite field algorithms are introduced which significantly improve OTF multiplication and squaring operations. The OTF inversion algorithm was implemented on the ARM family of processors for a medium and a large sized field whose elements can be represented with 192 and 320 bits, respectively. In the implementation, the new OTF inversion algorithm ran at least six to eight times faster than the known best method for inversion in OEFs, i.e., Itoh-Tsujii inversion technique. According to the implementation results obtained, it is indicated that using the OTF inversion method an elliptic curve scalar point multiplication operation can be performed at least two to three times faster than the known best implementation for the selected fields.

This PhD thesis focuses on the study, the hardware design, the theoretical and practical validation, and eventually the comparison of different arithmetic operators for cryptosystems based on elliptic curves (ECC). Provided solutions must be robust against some side-channel attacks, and efficient at a hardware level (execution speed and area). In the case of ECC, we want to protect the secret key, a large integer, used in the scalar multiplication. Our protection methods use representations of numbers, and behaviour of algorithms to make more difficult some attacks. For instance, we randomly change some representations of manipulated numbers while ensuring that computed values are correct. Redundant representations like signed-digit representation, the double- (DBNS) and multi-base number system (MBNS) have been studied. A proposed method provides an on-the-fly MBNS recoding which operates in parallel to curve-level operations and at very high speed. All recoding techniques have been theoretically validated, simulated extensively in software, and finally implemented in hardware (FPGA and ASIC). A side-channel attack called template attack is also carried out to evaluate the robustness of a cryptosystem using a redundant number representation. Eventually, a study is conducted at the hardware level to provide an ECC cryptosystem with a regular behaviour of computed operations during the scalar multiplication so as to protect against some side-channel attacks.

Secure communication is critical to many applications. To this end, various security goals can be achieved using elliptic/hyperelliptic curve and pairing based cryptography. Polynomial multiplication is used in the underlying operations of these protocols. Therefore, as part of this thesis different recursive algorithms are studied; these algorithms include Karatsuba, Toom, and Bernstein. In this thesis, we investigate algorithms and implementation techniques to improve the performance of the cryptographic protocols. Common factors present in explicit formulae in elliptic curves operations are utilized such that two multiplications are replaced by a single multiplication in a higher field. Moreover, we utilize the idea based on common factor used in elliptic curves and generate new explicit formulae for hyperelliptic curves and pairing. In the case of hyperelliptic curves, the common factor method is applied to the fastest known even characteristic hyperelliptic curve operations, i.e. divisor addition and divisor doubling. Similarly, in pairing we observe the presence of common factors inside the Miller loop of Eta pairing and the theoretical results show significant improvement when applying the idea based on common factor method. This has a great advantage for applications that require higher speed.

Der Vortrag erläutert das Grundprinzip des Diffie-Hellman-Schlüsseltausches mithilfe des diskreten Logarithmus unter Zuhilfenahme elliptischer Kurven über endlichen Körpern.

Elliptic curves were first proposed as a basis for public key cryptography in the mid 1980's. They provide public key cryptosystems based on the difficulty of the elliptic curve discrete logarithm problem (ECDLP) , which is so called because of its similarity to the discrete logarithm problem (DLP) over the integers modulo a large prime. One benefit of elliptic curve cryptosystems (ECCs) is that they can use a much shorter key length than other public key cryptosystems to provide an equivalent level of security. For example, 160 bit ECCs are believed to provide about the same level of security as 1024 bit RSA. Also, the level of security provided by an ECC increases faster with key size than for integer based discrete logarithm (dl) or RSA cryptosystems. ECCs can also provide a faster implementation than RSA or dl systems, and use less bandwidth and power. These issues can be crucial in lightweight applications such as smart cards. In the last few years, ECCs have been included or proposed for inclusion in internationally recognized standards. Thus elliptic curve cryptography is set to become an integral part of lightweight applications in the immediate future. This thesis presents an analysis of several important issues for ECCs on lightweight devices. It begins with an introduction to elliptic curves and the algorithms required to implement an ECC. It then gives an analysis of the speed, code size and memory usage of various possible implementation options. Enough details are presented to enable an implementer to choose for implementation those algorithms which give the greatest speed whilst conforming to the code size and ram restrictions of a particular lightweight device. Recommendations are made for new functions to be included on coprocessors for lightweight devices to support ECC implementations Another issue of concern for implementers is the side-channel attacks that have recently been proposed. They obtain information about the cryptosystem by measuring side-channel information such as power consumption and processing time and the information is then used to break implementations that have not incorporated appropriate defences. A new method of defence to protect an implementation from the simple power analysis (spa) method of attack is presented in this thesis. It requires 44% fewer additions and 11% more doublings than the commonly recommended defence of performing a point addition in every loop of the binary scalar multiplication algorithm. The algorithm forms a contribution to the current range of possible spa defences which has a good speed but low memory usage. Another topic of paramount importance to ECCs for lightweight applications is whether the security of fixed curves is equivalent to that of random curves. Because of the inability of lightweight devices to generate secure random curves, fixed curves are used in such devices. These curves provide the additional advantage of requiring less bandwidth, code size and processing time. However, it is intuitively obvious that a large precomputation to aid in the breaking of the elliptic curve discrete logarithm problem (ECDLP) can be made for a fixed curve which would be unavailable for a random curve. Therefore, it would appear that fixed curves are less secure than random curves, but quantifying the loss of security is much more difficult. The thesis performs an examination of fixed curve security taking this observation into account, and includes a definition of equivalent security and an analysis of a variation of Pollard's rho method where computations from solutions of previous ECDLPs can be used to solve subsequent ECDLPs on the same curve. A lower bound on the expected time to solve such ECDLPs using this method is presented, as well as an approximation of the expected time remaining to solve an ECDLP when a given size of precomputation is available. It is concluded that adding a total of 11 bits to the size of a fixed curve provides an equivalent level of security compared to random curves. The final part of the thesis deals with proofs of security of key exchange protocols in the Canetti-Krawczyk proof model. This model has been used since it offers the advantage of a modular proof with reusable components. Firstly a password-based authentication mechanism and its security proof are discussed, followed by an analysis of the use of the authentication mechanism in key exchange protocols. The Canetti-Krawczyk model is then used to examine secure tripartite (three party) key exchange protocols. Tripartite key exchange protocols are particularly suited to ECCs because of the availability of bilinear mappings on elliptic curves, which allow more efficient tripartite key exchange protocols.

Made available in DSpace on 2016-06-02T19:07:09Z (GMT). No. of bitstreams: 1 ARRUDA_Tiago_2014.pdf: 1705313 bytes, checksum: d85ede1a4ed22df35254baa0fd095df5 (MD5) Previous issue date: 2014-12-15 / Financiadora de Estudos e Projetos / Multicore processors adoption is due to the need of expansion on the computational capacity, what have been done in mobile devices, due to the high availability of online applications in such devices. Elliptic curve cryptography (ECC) can be used in these applications, to ensure the confidentiality in the communication performed by the mobile device. This algorithm has its security on the hardness to solve the elliptic curve discrete logarithm problem (ECDLP), what is harder to solve than RSA s problem, owning equivalent security at the cost of much smaller keys, hence reducing the computational cost of the solutions which implement it. Scalar multiplication is the main and most costly operation in ECC and is composed by the computation of many modular operations. Parallel modular multiplication algorithms where evaluated in this work, which timings were compared with timings of some sequential algorithms. Experiments were performed on a SabreLite IMX6Quad development board, with an architecture similar to a mobile device. On this platform, it was evaluated the transition from the low to the high frequency of CPU, which occurs in ondemand CPU mode during the execution of the algorithms. The relation of proportion among the timings of the algorithms evaluated on performance mode was similar to the powersave CPU mode. Some parallel algorithms were faster than the sequentials in operations among operands with at least 768 bits. Evaluating the behavior of each algorithm when integrated in the computation of scalar multiplication, it was observed that the parallels were faster in operations with a 1536-bit supersingular curve. / A adoção de processadores multi-core se deve à necessidade de expandir a capacidade computacional, o que vem sendo feito em dispositivos móveis, devido à alta disponibilidade de aplicações online em tais dispositivos. A criptografia de curvas elípticas (ECC) pode ser utilizada em tais aplicações, a fim de garantir o sigilo na comunicação realizada pelo dispositivo. Este algoritmo possui sua segurança baseada no problema do logaritmo discreto em curvas elípticas (ECDLP), que é mais difícil de solucionar que o problema do RSA, possuindo segurança equivalente ao custo de chaves muito menores, reduzindo portanto o custo computacional das soluções que o utilizam. A multiplicação escalar é a operação principal e mais custosa do ECC e envolve o cálculo de diversas operações modulares. Algoritmos de multiplicação modular paralelos foram avaliados neste trabalho, cujos tempos de execução foram comparados com os de alguns sequenciais. Foram realizados experimentos em uma placa de desenvolvimento SabreLite IMX6Quad, com arquitetura similar a de um dispositivo móvel. Nesta plataforma, foi avaliada a transição do modo de baixa para o de alta frequência, realizada pela CPU no modo ondemand durante a execução dos algoritmos. A relação de proporção entre os tempos dos algoritmos avaliados no modo performance foi similar à obtida no modo powersave. Alguns algoritmos paralelos foram mais rápidos que os sequenciais nas operações com operandos a partir de 768 bits. Ao avaliar o comportamento de cada algoritmo, quando incorporado no cálculo da multiplicação escalar, observou-se que os paralelos foram mais rápidos nas operações com uma curva supersingular de 1536 bits.

Orientador: Jose Raimundo de Oliveira / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-09T13:54:55Z (GMT). No. of bitstreams: 1 Dias_MauricioAraujo_D.pdf: 794928 bytes, checksum: a328a640d35118ea7fb606ac9f4ab2b2 (MD5) Previous issue date: 2007 / Resumo: Este trabalho propõe um sistema criptográfico para Criptografia baseada em Curvas Elípticas (ECC). ECC é usada alternativamente a outros sistemas criptográficos, como o algoritmo RSA (Rivest-Shamir-Adleman), por oferecer a menor chave e a maior segurança por bit. Ele realiza multiplicação de pontos (Q = kP) para curvas elípticas sobre corpos finitos binários. Trata-se de um criptosistema programável e configurável. Graças às propriedades do circuito programável (FPGA) é possível encontrar soluções otimizadas para diferentes curvas elípticas, corpos finitos e algoritmos. A característica principal deste criptosistema é o uso de um circuito combinacional para calcular duplicações e adições de pontos, por meio da aritmética sobre corpos finitos. Os resultados deste trabalho mostram que um programa de troca de chaves fica aproximadamente 20.483 vezes mais rápido com a ajuda do nosso sistema criptográfico. Para desenvolver este projeto, nós consideramos que o alto desempenho tem prioridade sobre a área ocupada pelos seus circuitos. Assim, nós recomendamos o uso deste circuito para os casos em que não sejam impostas restrições de área, mas seja exigido alto desempenho do sistema / Abstract: This work proposes a cryptosystem for Elliptic Curve Cryptography (ECC). ECC has been used as an alternative to other public-key cryptosystems such as the RSA (Rivest-Shamir-Adleman algorithm) by offering the smallest key size and the highest strength per bit. The cryptosystem performs point multiplication (Q = kP) for elliptic curves over binary polynomial fields (GF(2m)). This is a programmable and scalable cryptosystem. It uses the abilities of reconfigurable hardware (FPGA) to make possible optimized circuitry solutions for different elliptic curves, finite fields and algorithms. The main feature of this cryptosystem is the use of a combinatorial circuit to calculate point doublings and point additions, through finite field arithmetic. The results of this work show that the execution of a key-exchange program is, approximately, 20,483 times faster with the help of our cryptosystem. To develop this project we considered that high-performance has priority over area occupied by its circuit. Thus, we recommend the use of this circuit in the cases for which no area constraints are imposed but high performance systems are required. / Doutorado / Engenharia de Computação / Doutor em Engenharia Elétrica

This thesis aims at implementing methods for factorisation of large numbers. Seeing that there is no deterministic algorithm for finding the prime factors of a given number, the task proves rather difficult. Luckily, there have been developed some effective probabilistic methods since the invention of the computer so that it is now possible to factor numbers having about 200 decimal digits. This however consumes a large amount of resources and therefore, virtually all new factorisations are achieved using the combined power of many computers in a distributed system. The nature of the distributed system can vary. The original goal of the thesis was to develop a client/server system that allows clients to carry out a portion of the overall computations and submit the result to the server. Methods for factorisation discussed for implementation in the thesis are: the quadratic sieve, the number field sieve and the elliptic curve method. Actually implemented was only a variant of the quadratic sieve: the multiple polynomial quadratic sieve (MPQS).

Dans cette thèse, on aborde plusieurs questions autour des modèles de Néron de variétés abéliennes sur un corps de valuation discrète. On dit qu’une variété abélienne a réduction scindée si la suite exacte définissant le groupe des composantes de la fibre spéciale est scindée. On donne un exemple de variété abélienne modérément ramifiée qui n’a pas réduction scindée. Pour les variétés jacobiennes,on montre que l’on obtient réduction scindée après toute extension modérément ramifiée de degré plus grand qu’une constante ne dépendant que de la dimension.On considère aussi le lien avec le conducteur de Swan. Ensuite, on s’intéresse aux groupes formels des variétés abéliennes. Pour les courbes elliptiques, on détermine le rayon du plus grand voisinage de 0 qui est isomorphe à un polydisque muni de sa structure de groupe usuelle. On s’intéresse aussi aux groupes des composantes de modèles lisses, de type fini et séparés du groupe additif ou multiplicatif ainsi qu’à leurs sous-groupes des points rationnels. Enfin, on montre que le conducteur efficace d’une courbe algébrique ne peut pas s’exprimer uniquement en fonction deson conducteur d’Artin. / In this thesis, we tackle several questions about Néron models of abelian varieties on a discrete valuation field. We say that an abelian variety has split reduction if the exact sequence defining the group of components of the special fiber is split. We give an example of a tamely ramified abelian variety which does not have split reduction. For Jacobian varieties, we show that one gets split reduction after any tamely ramified extension of degree greater than aconstant depending on the dimension only. We also consider the link with theSwan conductor. Then, we deal with formal groups of abelian varieties. For elliptic curves, we compute the radius of the largest neighbourhood of 0 which is isomorphic to a polydisk equipped with its usual group law. We also deal with groups of components of smooth and separated models of finite type of the additive or multiplicative group as well as their subgroups of rational points. Finally, we show that the efficient conductor of an algebraic curve cannot be expressed interms of its Artin conductor only.