Elliptic curve cryptography (ECC) is an alternative to traditional techniques for public key cryptography. It offers smaller key size without sacrificing security level. Tate pairing is a bilinear map used in identity based cryptography schemes. In a typical elliptic curve cryptosystem, elliptic curve point multiplication is the most computationally expensive component. Similarly, Tate pairing is also quite computationally expensive. Therefore, it is more attractive to implement the ECC and Tate pairing using hardware than using software. The bases of both ECC and Tate pairing are Galois field arithmetic units. In this thesis, I propose the FPGA implementations of the elliptic curve point multiplication in GF (2283) as well as Tate pairing computation on supersingular elliptic curve in GF (2283). I have designed and synthesized the elliptic curve point multiplication and Tate pairing module using Xilinx's FPGA, as well as synthesized all the Galois arithmetic units used in the designs. Experimental results demonstrate that the FPGA implementation can speedup the elliptic curve point multiplication by 31.6 times compared to software based implementation. The results also demonstrate that the FPGA implementation can speedup the Tate pairing computation by 152 times compared to software based implementation.

Ensuring trustworthiness through mobile nodes is a serious issue. Indeed, securing the routing protocols in Mobile Ad Hoc Network (MANET) is of paramount importance. A key exchange cryptography technique is one such protocol. Trust relationship between mobile nodes is essential. Without it, security will be further threatened. The absence of infrastructure and a dynamic topology changing reduce the performance of security and trust in mobile networks. Current proposed security solutions cannot cope with eavesdroppers and misbehaving mobile nodes. Practically, designing a key exchange cryptography system is very challenging. Some key exchanges have been proposed which cause decrease in power, memory and bandwidth and increase in computational processing for each mobile node in the network consequently leading to a high overhead. Some of the trust models have been investigated to calculate the level of trust based on recommendations or reputations. These might be the cause of internal malicious attacks. Our contribution is to provide trustworthy communications among the mobile nodes in the network in order to discourage untrustworthy mobile nodes from participating in the network to gain services. As a result, we have presented an Elliptic Curve Diffie-Hellman key exchange and trust framework mechanism for securing the communication between mobile nodes. Since our proposed model uses a small key and less calculation, it leads to a reduction in memory and bandwidth without compromising on security level. Another advantage of the trust framework model is to detect and eliminate any kind of distrust route that contain any malicious node or suspects its behavior.

This work introduces fundamental and alternative definition of Weil pairing and proves their equivalence. The alternative definition is more advantageous for the purpose of computing. We assume basic knowledge of elliptic curves in the affine sense. We explain the K-rational maps and its generalization at the point at infinity, rational map. The proof of equivalence of the two mentioned definitions is based upon the Generalized Weil Reciprocity, which uses a concept of local symbol. The text follows two articles from year 1988 and 1990 written by L. Charlap, D. Robbins a R. Coley, and corrects a certain imprecision in their presentation of the alternative definition. Powered by TCPDF (www.tcpdf.org)

Efficient implementation of the number theoretic transform(NTT), also known as the discrete Fourier transform(DFT) over a finite field, has been studied actively for decades and found many applications in digital signal processing. In 1971 Schonhage and Strassen proposed an NTT based asymptotically fast multiplication method with the asymptotic complexity O(m log m log log m) for multiplication of $m$-bit integers or (m-1)st degree polynomials. Schonhage and Strassen's algorithm was known to be the asymptotically fastest multiplication algorithm until Furer improved upon it in 2007. However, unfortunately, both algorithms bear significant overhead due to the conversions between the time and frequency domains which makes them impractical for small operands, e.g. less than 1000 bits in length as used in many applications. With this work we investigate for the first time the practical application of the NTT, which found applications in digital signal processing, to finite field multiplication with an emphasis on elliptic curve cryptography(ECC). We present efficient parameters for practical application of NTT based finite field multiplication to ECC which requires key and operand sizes as short as 160 bits in length. With this work, for the first time, the use of NTT based finite field arithmetic is proposed for ECC and shown to be efficient. We introduce an efficient algorithm, named DFT modular multiplication, for computing Montgomery products of polynomials in the frequency domain which facilitates efficient multiplication in GF(p^m). Our algorithm performs the entire modular multiplication, including modular reduction, in the frequency domain, and thus eliminates costly back and forth conversions between the frequency and time domains. We show that, especially in computationally constrained platforms, multiplication of finite field elements may be achieved more efficiently in the frequency domain than in the time domain for operand sizes relevant to ECC. This work presents the first hardware implementation of a frequency domain multiplier suitable for ECC and the first hardware implementation of ECC in the frequency domain. We introduce a novel area/time efficient ECC processor architecture which performs all finite field arithmetic operations in the frequency domain utilizing DFT modular multiplication over a class of Optimal Extension Fields(OEF). The proposed architecture achieves extension field modular multiplication in the frequency domain with only a linear number of base field GF(p) multiplications in addition to a quadratic number of simpler operations such as addition and bitwise rotation. With its low area and high speed, the proposed architecture is well suited for ECC in small device environments such as smart cards and wireless sensor networks nodes. Finally, we propose an adaptation of the Itoh-Tsujii algorithm to the frequency domain which can achieve efficient inversion in a class of OEFs relevant to ECC. This is the first time a frequency domain finite field inversion algorithm is proposed for ECC and we believe our algorithm will be well suited for efficient constrained hardware implementations of ECC in affine coordinates.

This M.S. thesis introduces new modulus scaling techniques for transforming a class of primes into special forms which enable efficient arithmetic. The scaling technique may be used to improve multiplication and inversion in finite fields. We present an efficient inversion algorithm that utilizes the structure of a scaled modulus. Our inversion algorithm exhibits superior performance to the Euclidean algorithm and lends itself to efficient hardware implementation due to its simplicity. Using the scaled modulus technique and our specialized inversion algorithm we develop an elliptic curve processor architecture. The resulting architecture successfully utilizes redundant representation of elements in GF(p) and provides a low-power, high speed, and small footprint specialized elliptic curve implementation. We also introduce a unified Montgomery multiplier architecture working on the extension fields GF(p), GF(2) and GF(3). With the increasing research activity for identity based encryption schemes, there has been an increasing need for arithmetic operations in field GF(3). Since we based our research on low-power and small footprint applications, we designed a unified architecture rather than having a seperate hardware for GF{3}. To the best of our knowledge, this is the first time a unified architecture was built working on three different extension fields.

Cette thèse est consacrée à la description et à l'étude de la sécurité de divers protocoles destinés à faire de l'authentification d'objets physiques à distance à base de comparaison de vecteurs binaires. L'objectif des protocoles proposés est de pouvoir réaliser une authentification en garantissant d'une part que les informations envoyées et reçues par le lecteur n'ont pas été manipulées par un adversaire extérieur et d'autre part sans révéler l'identité de l'objet testé à un tel adversaire, ou même, modulo certaines hypothèses raisonnables, aux composantes du système. Nous nous sommes fixés de plus comme objectif d'utiliser des méthodes de cryptographie sur courbe elliptique pour pouvoir profiter des bonnes propriétés de ces dernières, notamment une sécurité accrue par rapport à la taille des clefs utilisées. Nous présentons plusieurs protocoles atteignant l'objectif et établissons pour presque tous une preuve théorique de leur sécurité, grâce notamment à une nouvelle caractérisation d'une notion standard de sécurité. / This thesis is dedicated to the description of several bitrsitring comparison based remote object authentication protocols and the study of their theoretical security. The proposed protocols are designed to carry out the authentication of a given object while simultaneously guaranteeing that the information sent and received by the server cannot be tampered with by outside adversaries and that the identity of the tested object remains hidden from outside and (certain) inside adversaries. Finally it has been our objective to use elliptic curve cryptography, taking advantage of its useful properties, notably a better security level to key-size ratio. We present several protocols reaching these objectives, establishing for almost each protocol a theoretical proof of security using a new characterization of a standard security notion.

<p>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. </p><p>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. </p><p>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).</p>

In this thesis, I have explored the different approaches towards proving Artin's `primitive root' conjecture unconditionally and the elliptic curve analogue of the same. This conjecture was posed by E. Artin in the year 1927, and it still remains an open problem. In 1967, C. Hooley proved the conjecture based on the assumption of the generalized Riemann hypothesis. Thereafter, the mathematicians tried to get rid of the assumption and it seemed quite a daunting task. In 1983, the pioneering attempt was made by R. Gupta and M. Ram Murty, who proved unconditionally that there exists a specific set of 13 distinct numbers such that for at least one of them, the conjecture is true. Along the same line, using sieve theory, D. R. Heath-Brown reduced this set down to 3 distinct primes in the year 1986. This is the best unconditional result we have so far. In the first part of this thesis, we will review the sieve theoretic approach taken by Gupta-Murty and Heath-Brown. The second half of the thesis will deal with the elliptic curve analogue of the Artin's conjecture, which is also known as the Lang-Trotter conjecture. Lang and Trotter proposed the elliptic curve analogue in 1977, including the higher rank version, and also proceeded to set up the mathematical formulation to prove the same. The analogue conjecture was proved by Gupta and Murty in the year 1986, assuming the generalized Riemann hypothesis, for curves with complex multiplication. They also proved the higher rank version of the same. We will discuss their proof in details, involving the sieve theoretic approach in the elliptic curve setup. Finally, I will conclude the thesis with a refinement proposed by Gupta and Murty to find out a finite set of points on the curve such that at least one satisfies the conjecture.

In this thesis, I have explored the different approaches towards proving Artin's `primitive root' conjecture unconditionally and the elliptic curve analogue of the same. This conjecture was posed by E. Artin in the year 1927, and it still remains an open problem. In 1967, C. Hooley proved the conjecture based on the assumption of the generalized Riemann hypothesis. Thereafter, the mathematicians tried to get rid of the assumption and it seemed quite a daunting task. In 1983, the pioneering attempt was made by R. Gupta and M. Ram Murty, who proved unconditionally that there exists a specific set of 13 distinct numbers such that for at least one of them, the conjecture is true. Along the same line, using sieve theory, D. R. Heath-Brown reduced this set down to 3 distinct primes in the year 1986. This is the best unconditional result we have so far. In the first part of this thesis, we will review the sieve theoretic approach taken by Gupta-Murty and Heath-Brown. The second half of the thesis will deal with the elliptic curve analogue of the Artin's conjecture, which is also known as the Lang-Trotter conjecture. Lang and Trotter proposed the elliptic curve analogue in 1977, including the higher rank version, and also proceeded to set up the mathematical formulation to prove the same. The analogue conjecture was proved by Gupta and Murty in the year 1986, assuming the generalized Riemann hypothesis, for curves with complex multiplication. They also proved the higher rank version of the same. We will discuss their proof in details, involving the sieve theoretic approach in the elliptic curve setup. Finally, I will conclude the thesis with a refinement proposed by Gupta and Murty to find out a finite set of points on the curve such that at least one satisfies the conjecture.

Magistro darbe įrodyta elipsinių kreivių L-funkcijų jungtinė diskreti universalumo Voronino prasme teorema. / The aim of the master work is to obtain a joint discrete universality theorem in the Voronin sense for L-function of elliptic curves.