In an ever-increasing digital world, the need for secure communications over unsecured channels like Internet has exploded. To meet the different security requirements, communication devices have to perform expensive cryptographic operations. Hardware processors are therefore often needed to meet goals such as speed, ubiquity or cost-effectiveness. For such devices, the size of security parameters is chosen as small as possible to save resources and time. It is therefore necessary to know the effective security of given sets of parameters in order to achieve the best trade-off between efficiency and security. The best way to address this problem is by means of accurate estimations of dedicated hardware attacks. In this thesis, we investigate two aspects of cryptographic hardware: constructive applications that deal with general purpose secure devices and destructive applications that handle dedicated hardware attacks against cryptosystems. Their set of constraints is clearly different but they both need efficient algorithms and hardware architectures. First, we deal with efficient and novel modular inversion and division algorithms on Field-Programmable Gate Array (FPGA) hardware platform. Such algorithms are an important building block for both constructive and destructive use of elliptic curve cryptography. Then, we provide new or highly improved architectures for attacks against RC5 cipher, GF(2m) elliptic curves and RSA by means of efficient elliptic curve-based factorization engines (ECM). We prove that FPGA-based solutions are much more cost-effective and low power than software-based solutions. Our resulting cost assessments should serve as a basis for improving the accuracy of current hardware or software-based security evaluations. Finally, we handle the efficiency-flexibility trade-off problem for high-speed hardware implementations of elliptic curve. Then, we present efficient elliptic curve digital signature algorithm coprocessors for smart cards. We also show that, surprisingly, affine coordinates can be an attractive solution for such an application.

Bilinear pairings on elliptic curves have many cryptographic applications such as identity based encryption, one-round three-party key agreement protocols, and short signature schemes. The elliptic curves which are suitable for pairing-based cryptography are called pairing friendly curves. The prime-order pairing friendly curves with embedding degrees k=3,4 and 6 were characterized by Miyaji, Nakabayashi and Takano. We study this characterization of MNT curves in details. We present explicit algorithms to obtain suitable curve parameters and to construct the corresponding elliptic curves. We also give a heuristic lower bound for the expected number of isogeny classes of MNT curves. Moreover, the related theoretical findings are compared with our experimental results.

Bilinear pairings on elliptic curves have many cryptographic applications such as identity based encryption, one-round three-party key agreement protocols, and short signature schemes. The elliptic curves which are suitable for pairing-based cryptography are called pairing friendly curves. The prime-order pairing friendly curves with embedding degrees k=3,4 and 6 were characterized by Miyaji, Nakabayashi and Takano. We study this characterization of MNT curves in details. We present explicit algorithms to obtain suitable curve parameters and to construct the corresponding elliptic curves. We also give a heuristic lower bound for the expected number of isogeny classes of MNT curves. Moreover, the related theoretical findings are compared with our experimental results.

Traditionally number theorists have studied, both theoretically and computationally, elliptic curves and their L-functions over number fields, in particular over the rational numbers. Much less work has been done over function fields, especially computationally, where the underlying geometry of the function field plays an intimate role in the arithmetic of elliptic curves. We make use of this underlying geometry to develop a method to compute the L-function of an elliptic curve and its twists over the function field of the projective line over a finite field. This method requires computing the number of points on an elliptic curve over a finite field, for which we present a novel algorithm. If the j-invariant of an elliptic curve over a function field is non-constant, its L-function is a polynomial, hence its analytic rank and value at a given point can be computed exactly. We present data in this direction for a family of quadratic twists of four fixed elliptic curves over a few function fields of differing characteristic. First we present analytic rank data that confirms a conjecture of Goldfeld, in stark contrast to the corresponding data in the number field setting. Second, we present data on the integral moments of the value of the L-function at the symmetry point, which on the surface appears to refute random matrix theory conjectures. / text

This report discusses the history, use, and future of elliptic curves. Uses of elliptic curves in various number theory settings are presented. Fermat’s Last Proof is shown to be proven with elliptic curves. Finally, the future of elliptic curves with respect to cryptography and primality is shown. / text

In this paper we explain the congruent number problem and its connection to elliptic curves. We begin with a brief history of the problem and some early attempts to understand congruent numbers. We then introduce elliptic curves and many of their basic properties, as well as explain a few key theorems in the study of elliptic curves. Following this, we prove that determining whether or not a number n is congruent is equivalent to determining whether or not the algebraic rank of a corresponding elliptic curve En is 0. We then introduce L-functions and explain the Birch and Swinnerton- Dyer (BSD) Conjecture. We then explain the machinery needed to understand an algorithm by Tim Dokchitser for evaluating L-functions at 1. We end by computing whether or not a given number n is congruent by implementing Dokchitser’s algorithm with Sage and by using Tunnel’s Theorem.

This thesis examines the rank of elliptic curves. We first examine the correspondences between projective space and affine space, and use the projective point at infinity to establish the group law on elliptic curves. We prove a section of Mordell’s Theorem to establish that the abelian group of rational points on an elliptic curve is finitely generated. We then use homomorphisms established in our proof to find a formula for the rank, and then provide examples of computations.

Orientador: Ricardo Dahab / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-11T02:09:49Z (GMT). No. of bitstreams: 1 Silva_RosembergAndreda_M.pdf: 824860 bytes, checksum: 48ed40bc241415f1692ca283d3e1f65b (MD5) Previous issue date: 2006 / Resumo: A escolha dos parâmetros sobre os quais uma dada implementação de Criptografia sobre Curvas Elípticas baseia-se tem influência direta sobre o desempenho das operações associadas bem como sobre seu grau de segurança. Este trabalho visa analisar a forma como os padrões mais usados na atulalidade lidam com este processo de seleção, mostrando as implicações que tais escolhas acarretam / Abstract: The choice of parameters associated with a given implementation of ECC (Elliptic Curve Cryptography) has direct impact on its performance and security leveI. This dissertation aims to compare the most common standards used now-a-days, taking into account their selection criteria and their implications on performance and security / Mestrado / Engenharia de Software / Mestre em Ciência da Computação

Orientador: Marco Aurélio 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-26T04:02:15Z (GMT). No. of bitstreams: 1 Sangalli_LeandroAparecido1988-_M.pdf: 2889538 bytes, checksum: 474d1ae695fc20d0f0b214ac8ba4716f (MD5) Previous issue date: 2014 / Resumo: Emparelhamentos bilineares sobre curvas elípticas são funções matemáticas que podem viabilizar protocolos criptográficos promissores. Porém, um fato que enfraquece o desenvolvimento destes protocolos é o alto custo computacional para calcular estes emparelhamentos. Diversas técnicas de otimização foram propostas nos últimos anos para realizar este cálculo de forma mais eficiente. Dentre estas técnicas existem as que mudam o tipo de emparelhamentos, o tipo de curvas elípticas ou a forma de cálculo dos emparelhamentos. As curvas Barreto-Naehrig são conhecidas como curvas amigáveis para emparelhamentos, pois se destacam para aplicações que buscam eficiência no cálculo dos mesmos. Este trabalho avalia em detalhes o custo das operações presentes no cálculo de alguns dos emparelhamentos mais utilizados atualmente definidos sobre curvas Barreto-Naehrig. Por meio desta análise, foi possível realizar uma comparação destes emparelhamentos no nível de operações de adição, multiplicação, quadrado, inversão e redução modular sobre um corpo finito primo e sobre um processador genérico. Os resultados mostram que de acordo com os parâmetros adotados, um dos emparelhamentos mais utilizados (Optimal Ate) pode não apresentar o melhor desempenho entre os analisados. Além disso, foi possível avaliar como o cálculo dos emparelhamentos é afetado pela adoção de diferentes processadores, desde aqueles com palavras curtas até aqueles que no futuro poderão ter palavras muito longas / Abstract: Bilinear pairings over elliptic curves are functions that support promising cryptographic protocols. However, a fact that hinders the development of these protocols is their high computational cost. Many techniques seeking more efficiency in the calculation of pairings have been proposed in the last years. Among these techniques are those that change the pairing type, the curve type and/or the pairing calculation method. Barreto-Naehrig curves are known as pairing-friendly curves, because they perform well in applications that require more efficiency in the pairing calculation. This work evaluates the cost of operations present in the most used pairings that are based on Barreto-Naehrig curves. With this evaluation, it was possible to compare these pairings at the level of basic operations as addition, multiplication, square, inversion and modular reduction over a prime finite field in a generic processor. The results show that, for the security parameters adopted in this work, one of the most used pairing algorithms (Optimal Ate) is not the fastest among those evaluated. Moreover, this work estimates the impact caused in the pairing calculation by different processors, ranging from the current short-medium word processors to the future very long word ones / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

This thesis aims to prove the following statement, where the Weierstrass p-function has algebraic invariants and complex multiplication by Q(alpha): "If beta_1,..., beta_n are algebraic numbers which are linearly independent over Q(alpha), then p(beta_1),...,p(beta_n) are algebraically independent over Q." This was proven by Philippon in 1983, and the proof in this thesis follows his ideas. The difference lies in the strength of the tools used, allowing certain arguments to be simplified. This thesis shows that the above result is equivalent to imposing the restriction (beta_1,...,beta_n)=(1,beta,...,beta^{n-1}), where n=[Q(alpha,beta):Q(alpha)]. The core of the proof consists of developing height estimates, constructing representations for morphisms between products of elliptic curves, and finding height and degree estimates on large families of polynomials which are small at a point in Q(alpha,beta,g_2,g_3)(p(1),p'(1),...,p(beta^{n-1}),p'(beta^{n-1})). An application of Philippon's zero estimate (1986) and his criterion of algebraic independence (1984) is then used to obtain the main result.