Elliptic curves, group law, and efficient computation

This thesis is about the derivation of the addition law on an arbitrary elliptic curve and efficiently adding points on this elliptic curve using the derived addition law. The outcomes of this research guarantee practical speedups in higher level operations which depend on point additions. In particular, the contributions immediately find applications in cryptology. Mastered by the 19th century mathematicians, the study of the theory of elliptic curves has been active for decades. Elliptic curves over finite fields made their way into public key cryptography in late 1980’s with independent proposals by Miller [Mil86] and Koblitz [Kob87]. Elliptic Curve Cryptography (ECC), following Miller’s and Koblitz’s proposals, employs the group of rational points on an elliptic curve in building discrete logarithm based public key cryptosystems. Starting from late 1990’s, the emergence of the ECC market has boosted the research in computational aspects of elliptic curves. This thesis falls into this same area of research where the main aim is to speed up the additions of rational points on an arbitrary elliptic curve (over a field of large characteristic). The outcomes of this work can be used to speed up applications which are based on elliptic curves, including cryptographic applications in ECC. The aforementioned goals of this thesis are achieved in five main steps. As the first step, this thesis brings together several algebraic tools in order to derive the unique group law of an elliptic curve. This step also includes an investigation of recent computer algebra packages relating to their capabilities. Although the group law is unique, its evaluation can be performed using abundant (in fact infinitely many) formulae. As the second step, this thesis progresses the finding of the best formulae for efficient addition of points. In the third step, the group law is stated explicitly by handling all possible summands. The fourth step presents the algorithms to be used for efficient point additions. In the fifth and final step, optimized software implementations of the proposed algorithms are presented in order to show that theoretical speedups of step four can be practically obtained. In each of the five steps, this thesis focuses on five forms of elliptic curves over finite fields of large characteristic. A list of these forms and their defining equations are given as follows: (a) Short Weierstrass form, y2 = x3 + ax + b, (b) Extended Jacobi quartic form, y2 = dx4 + 2ax2 + 1, (c) Twisted Hessian form, ax3 + y3 + 1 = dxy, (d) Twisted Edwards form, ax2 + y2 = 1 + dx2y2, (e) Twisted Jacobi intersection form, bs2 + c2 = 1, as2 + d2 = 1, These forms are the most promising candidates for efficient computations and thus considered in this work. Nevertheless, the methods employed in this thesis are capable of handling arbitrary elliptic curves. From a high level point of view, the following outcomes are achieved in this thesis. - Related literature results are brought together and further revisited. For most of the cases several missed formulae, algorithms, and efficient point representations are discovered. - Analogies are made among all studied forms. For instance, it is shown that two sets of affine addition formulae are sufficient to cover all possible affine inputs as long as the output is also an affine point in any of these forms. In the literature, many special cases, especially interactions with points at infinity were omitted from discussion. This thesis handles all of the possibilities. - Several new point doubling/addition formulae and algorithms are introduced, which are more efficient than the existing alternatives in the literature. Most notably, the speed of extended Jacobi quartic, twisted Edwards, and Jacobi intersection forms are improved. New unified addition formulae are proposed for short Weierstrass form. New coordinate systems are studied for the first time. - An optimized implementation is developed using a combination of generic x86-64 assembly instructions and the plain C language. The practical advantages of the proposed algorithms are supported by computer experiments. - All formulae, presented in the body of this thesis, are checked for correctness using computer algebra scripts together with details on register allocations.

An exploration of affine group laws for elliptic curves

Several forms of elliptic curves are suggested for an efficient implementation of Elliptic Curve Cryptography. However, a complete description of the group law has not appeared in the literature for most popular forms. This paper presents group law in affine coordinates for three forms of elliptic curves. With the existence of the proposed affine group laws, stating the projective group law for each form becomes trivial. This work also describes an automated framework for studying elliptic curve group law, which is applied internally when preparing this work.

Key Agreement Protocol Using Elliptic Curve Matrix Power Function

* Work is partially supported by the Lithuanian State Science and Studies Foundation.

Group law computations on Jacobians of hyperelliptic Curves

We derive an explicit method of computing the composition step in Cantor’s algorithm for group operations on Jacobians of hyperelliptic curves. Our technique is inspired by the geometric description of the group law and applies to hyperelliptic curves of arbitrary genus. While Cantor’s general composition involves arithmetic in the polynomial ring F_q[x], the algorithm we propose solves a linear system over the base field which can be written down directly from the Mumford coordinates of the group elements. We apply this method to give more efficient formulas for group operations in both affine and projective coordinates for cryptographic systems based on Jacobians of genus 2 hyperelliptic curves in general form.

Twisted Edwards curves revisited

This paper introduces fast algorithms for performing group operations on twisted Edwards curves, pushing the recent speed limits of Elliptic Curve Cryptography (ECC) forward in a wide range of applications. Notably, the new addition algorithm uses for suitably selected curve constants. In comparison, the fastest point addition algorithms for (twisted) Edwards curves stated in the literature use . It is also shown that the new addition algorithm can be implemented with four processors dropping the effective cost to . This implies an effective speed increase by the full factor of 4 over the sequential case. Our results allow faster implementation of elliptic curve scalar multiplication. In addition, the new point addition algorithm can be used to provide a natural protection from side channel attacks based on simple power analysis (SPA).

Dynamics of nonlinearly coupled magnetic-field-aligned electromagnetic electron-cyclotron waves near the zero-group-dispersion point in magnetized plasmas

The nonlinear coupling between two magnetic-field-aligned electromagnetic electron-cyclotron (EMEC) waves in plasmas is considered. Evaluating the ponderomotive coupling between the EMEC waves and quasistationary plasma density perturbations, a pair of coupled nonlinear Schrodinger equations (CNLSEs) is obtained. The CNLSEs are then used to investigate the occurrence of modulational instability in magnetized plasmas. Waves in the vicinity of the zero-group-dispersion point are considered, so that the group dispersion terms may either bear the same or different signs. It is found that a stable EMEC wave can be destabilized due to its nonlinear interactions with an unstable one, while a pair of unstable EMEC waves yields an increased instability growth rate. Individually stable waves remain stable while interacting with one another. Stationary nonlinear solutions of the coupled equations are presented. The relevance of our investigation to nonlinear phenomena in space plasmas is discussed. (c) 2005 American Institute of Physics.

Hardware elliptic curve cryptographic processor over GF(p)

A novel hardware architecture for elliptic curve cryptography (ECC) over GF(p) is introduced. This can perform the main prime field arithmetic functions needed in these cryptosystems including modular inversion and multiplication. This is based on a new unified modular inversion algorithm that offers considerable improvement over previous ECC techniques that use Fermat's Little Theorem for this operation. The processor described uses a full-word multiplier which requires much fewer clock cycles than previous methods, while still maintaining a competitive critical path delay. The benefits of the approach have been demonstrated by utilizing these techniques to create a field-programmable gate array (FPGA) design. This can perform a 256-bit prime field scalar point multiplication in 3.86 ms, the fastest FPGA time reported to date. The ECC architecture described can also perform four different types of modular inversion, making it suitable for use in many different ECC applications. © 2006 IEEE.

Computing the Cassels–Tate pairing on the 3-Selmer group of an elliptic curve

We extend the method of Cassels for computing the Cassels-Tate pairing on the 2-Selmer group of an elliptic curve, to the case of 3-Selmer groups. This requires significant modifications to both the local and global parts of the calculation. Our method is practical in sufficiently small examples, and can be used to improve the upper bound for the rank of an elliptic curve obtained by 3-descent.

The Performance of Elliptic Curve Based Group Diffie-Hellman Protocols for Secure Group Communication over Ad Hoc Networks

The security of the two party Diffie-Hellman key exchange protocol is currently based on the discrete logarithm problem (DLP). However, it can also be built upon the elliptic curve discrete logarithm problem (ECDLP). Most proposed secure group communication schemes employ the DLP-based Diffie-Hellman protocol. This paper proposes the ECDLP-based Diffie-Hellman protocols for secure group communication and evaluates their performance on wireless ad hoc networks. The proposed schemes are compared at the same security level with DLP-based group protocols under different channel conditions. Our experiments and analysis show that the Tree-based Group Elliptic Curve Diffie-Hellman (TGECDH) protocol is the best in overall performance for secure group communication among the four schemes discussed in the paper. Low communication overhead, relatively low computation load and short packets are the main reasons for the good performance of the TGECDH protocol.

Elliptic curve algorithm integration in the secure shell transport layer

This document describes algorithms based on Elliptic Cryptography (ECC) for use within the Secure Shell (SSH) transport protocol. In particular, it specifies Elliptic Curve Diffie-Hellman (ECDH) key agreement, Elliptic Curve Menezes-Qu-Vanstone (ECMQV) key agreement, and Elliptic Curve Digital Signature Algorithm (ECDSA) for use in the SSH Transport Layer protocol.

Duke University Law School Addition, Durham, North Carolina, 1988-1995

[Early Conceptual Sketch], untitled. Blue ink sketch on tracing paper, 18 x 32 1/4 inches [from photographic copy by Lance Burgharrdt]

Duke University Law School Addition, Durham, North Carolina, 1988-1995

[Early Conceptual Sketch], untitled. Blue ink sketch on tracing paper, 18 x 28 3/4 inches [from photographic copy by Lance Burgharrdt]