Faster group operations on elliptic curves

This paper improves implementation techniques of Elliptic Curve Cryptography. We introduce new formulae and algorithms for the group law on Jacobi quartic, Jacobi intersection, Edwards, and Hessian curves. The proposed formulae and algorithms can save time in suitable point representations. To support our claims, a cost comparison is made with classic scalar multiplication algorithms using previous and current operation counts. Most notably, the best speeds are obtained from Jacobi quartic curves which provide the fastest timings for most scalar multiplication strategies benefiting from the proposed 12M + 5S + 1D point doubling and 7M + 3S + 1D point addition algorithms. Furthermore, the new addition algorithm provides an efficient way to protect against side channel attacks which are based on simple power analysis (SPA). Keywords: Efficient elliptic curve arithmetic,unified addition, side channel attack.

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.

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.

Adaptive finite element analysis of elliptic problems based on bubble-type local mesh generation

A new mesh adaptivity algorithm that combines a posteriori error estimation with bubble-type local mesh generation (BLMG) strategy for elliptic differential equations is proposed. The size function used in the BLMG is defined on each vertex during the adaptive process based on the obtained error estimator. In order to avoid the excessive coarsening and refining in each iterative step, two factor thresholds are introduced in the size function. The advantages of the BLMG-based adaptive finite element method, compared with other known methods, are given as follows: the refining and coarsening are obtained fluently in the same framework; the local a posteriori error estimation is easy to implement through the adjacency list of the BLMG method; at all levels of refinement, the updated triangles remain very well shaped, even if the mesh size at any particular refinement level varies by several orders of magnitude. Several numerical examples with singularities for the elliptic problems, where the explicit error estimators are used, verify the efficiency of the algorithm. The analysis for the parameters introduced in the size function shows that the algorithm has good flexibility.

Equivariant Birch-Swinnerton-Dyer Conjecture for the Base Change of Elliptic Curves: An Example

Let E be an elliptic curve defined over Q and let K/Q be a finite Galois extension with Galois group G. The equivariant Birch-Swinnerton-Dyer conjecture for h(1)(E x(Q) K)(1) viewed as amotive over Q with coefficients in Q[G] relates the twisted L-values associated with E with the arithmetic invariants of the same. In this paper I prescribe an approach to verify this conjecture for a given data. Using this approach, we verify the conjecture for an elliptic curve of conductor 11 and an S-3-extension of Q.

Lopsided spiral galaxies

The light distribution in the disks of many galaxies is ‘lopsided’ with a spatial extent much larger along one half of a galaxy than the other, as seen in M101. Recent observations show that the stellar disk in a typical spiral galaxy is significantly lopsided, indicating asymmetry in the disk mass distribution. The mean amplitude of lopsidedness is 0.1, measured as the Fourier amplitude of the m=1 component normalized to the average value. Thus, lopsidedness is common, and hence it is important to understand its origin and dynamics. This is a new and exciting area in galactic structure and dynamics, in contrast to the topic of bars and two-armed spirals (m=2) which has been extensively studied in the literature. Lopsidedness is ubiquitous and occurs in a variety of settings and tracers. It is seen in both stars and gas, in the outer disk and the central region, in the field and the group galaxies. The lopsided amplitude is higher by a factor of two for galaxies in a group. The lopsidedness has a strong impact on the dynamics of the galaxy, its evolution, the star formation in it, and on the growth of the central black hole and on the nuclear fuelling. We present here an overview of the observations that measure the lopsided distribution, as well as the theoretical progress made so far to understand its origin and properties. The physical mechanisms studied for its origin include tidal encounters, gas accretion and a global gravitational instability. The related open, challenging problems in this emerging area are discussed.

Contribution from normal and starburst galaxies to the extragalactic gamma-ray background (EGRB)

The extragalactic diffuse emission at gamma-ray energies has interesting cosmological implications since these photons suffer little or no attenuation during their propagation from the site of origin. The emission could originate from either truly diffuse processes or from unresolved point sources such as AGNs, normal galaxies and starburst galaxies. Here, we examine the unresolved point source origin of the extragalactic gamma-ray background emission from normal galaxies and starburst galaxies. gamma-ray emission from normal galaxies is primarily coming from cosmic-ray interactions with interstellar matter and radiation (similar to 90%) along with a small contribution from discrete point sources (similar to 10%). Starburst galaxies are expected to have enhanced supernovae activity which leads to higher cosmic-ray densities, making starburst galaxies sufficiently luminous at gamma-ray energies to be detected by the current gamma-ray mission(Fermi Gamma-ray Space Telescope).

The onset of warps in Spitzer observations of edge-on spiral galaxies

We analyse warps in the nearby edge-on spiral galaxies observed in the Spitzer/Infrared Array Camera (IRAC)4.5-mu m band. In our sample of 24 galaxies, we find evidence of warp in 14 galaxies. We estimate the observed onset radii for the warps in a subsample of 10 galaxies. The dark matter distribution in each of these galaxies are calculated using the mass distribution derived from the observed light distribution and the observed rotation curves. The theoretical predictions of the onset radii for the warps are then derived by applying a self-consistent linear response theory to the obtained mass models for six galaxies with rotation curves in the literature. By comparing the observed onset radii to the theoretical ones, we find that discs with constant thickness can not explain the observations; moderately flaring discs are needed. The required flaring is consistent with the observations. Our analysis shows that the onset of warp is not symmetric in our sample of galaxies. We define a new quantity called the onset-asymmetry index and study its dependence on galaxy properties. The onset asymmetries in warps tend to be larger in galaxies with smaller dis scalelengths. We also define and quantify the global asymmetry in the stellar light distribution, that we call the edge-on asymmetry in edge-on galaxies. It is shown that in most cases the onset asymmetry in warp is actually anticorrelated with the measured edge-on asymmetry in our sample of edge-on galaxies and this could plausibly indicate that the surrounding dark matter distribution is asymmetric.

Generation of rotationally dominated galaxies by mergers of pressure-supported progenitors

Through the analysis of a set of numerical simulations of major mergers between initially non-rotating, pressure-supported progenitor galaxies with a range of central mass concentrations, we have shown that: (1) it is possible to generate elliptical-like galaxies, with outside one effective radius, as a result of the conversion of orbital- into internal-angular momentum; (2) the outer regions acquire part of the angular momentum first; (3) both the baryonic and the dark matter components of the remnant galaxy acquire part of the angular momentum, the relative fractions depending on the initial concentration of the merging galaxies. For this conversion to occur the initial baryonic component must be sufficiently dense and/or the encounter should take place on an orbit with high angular momentum. Systems with these hybrid properties have recently been observed through a combination of stellar absorption lines and planetary nebulae for kinematic studies of early-type galaxies. Our results are in qualitative agreement with these observations and demonstrate that even mergers composed of non rotating, pressure-supported progenitor galaxies can produce early-type galaxies with significant rotation at large radii.