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.

The geostationary orbit : a critical legal geography of space’s most valuable real estate

This chapter attends to the legal and political geographies of one of Earth's most important, valuable, and pressured spaces: the geostationary orbit. Since the first, NASA, satellite entered it in 1964, this small, defined band of Outer Space, 35,786km from the Earth's surface, and only 30km wide, has become a highly charged legal and geopolitical environment, yet it remains a space which is curiously unheard of outside of specialist circles. For the thousands of satellites which now underpin the Earth's communication, media, and data industries and flows, the geostationary orbit is the prime position in Space. The geostationary orbit only has the physical capacity to hold approximately 1500 satellites; in 1997 there were approximately 1000. It is no overstatement to assert that media, communication, and data industries would not be what they are today if it was not for the geostationary orbit. This chapter provides a critical legal geography of the geostationary orbit, charting the topography of the debates and struggles to define and manage this highly-important space. Drawing on key legal documents such as the Outer Space Treaty and the Moon Treaty, the chapter addresses fundamental questions about the legal geography of the orbit, questions which are of growing importance as the orbit’s available satellite spaces diminish and the orbit comes under increasing pressure. Who owns the geostationary orbit? Who, and whose rules, govern what may or may not (literally) take place within it? Who decides which satellites can occupy the orbit? Is the geostationary orbit the sovereign property of the equatorial states it supertends, as these states argued in the 1970s? Or is it a part of the res communis, or common property of humanity, which currently legally characterises Outer Space? As challenges to the existing legal spatiality of the orbit from launch states, companies, and potential launch states, it is particularly critical that the current spatiality of the orbit is understood and considered. One of the busiest areas of Outer Space’s spatiality is international territorial law. Mentions of Space law tend to evoke incredulity and ‘little green men’ jokes, but as Space becomes busier and busier, international Space law is growing in complexity and importance. The chapter draws on two key fields of research: cultural geography, and critical legal geography. The chapter is framed by the cultural geographical concept of ‘spatiality’, a term which signals the multiple and dynamic nature of geographical space. As spatial theorists such as Henri Lefebvre assert, a space is never simply physical; rather, any space is always a jostling composite of material, imagined, and practiced geographies (Lefebvre 1991). The ways in which a culture perceives, represents, and legislates that space are as constitutive of its identity--its spatiality--as the physical topography of the ground itself. The second field in which this chapter is situated—critical legal geography—derives from cultural geography’s focus on the cultural construction of spatiality. In his Law, Space and the Geographies of Power (1994), Nicholas Blomley asserts that analyses of territorial law largely neglect the spatial dimension of their investigations; rather than seeing the law as a force that produces specific kinds of spaces, they tend to position space as a neutral, universally-legible entity which is neatly governed by the equally neutral 'external variable' of territorial law (28). 'In the hegemonic conception of the law,' Pue similarly argues, 'the entire world is transmuted into one vast isotropic surface' (1990: 568) on which law simply acts. But as the emerging field of critical legal geography demonstrates, law is not a neutral organiser of space, but is instead a powerful cultural technology of spatial production. Or as Delaney states, legal debates are “episodes in the social production of space” (2001, p. 494). International territorial law, in other words, makes space, and does not simply govern it. Drawing on these tenets of the field of critical legal geography, as well as on Lefebvrian concept of multipartite spatiality, this chapter does two things. First, it extends the field of critical legal geography into Space, a domain with which the field has yet to substantially engage. Second, it demonstrates that the legal spatiality of the geostationary orbit is both complex and contested, and argues that it is crucial that we understand this dynamic legal space on which the Earth’s communications systems rely.

Analysis of regionally enhanced GPS orbit and clock solutions and contribution to improvement of real-time precise point positioning

This work experimentally examines the performance benefits of a regional CORS network to the GPS orbit and clock solutions for supporting real-time Precise Point Positioning (PPP). The regionally enhanced GPS precise orbit solutions are derived from a global evenly distributed CORS network added with a densely distributed network in Australia and New Zealand. A series of computational schemes for different network configurations are adopted in the GAMIT-GLOBK and PANDA data processing. The precise GPS orbit results show that the regionally enhanced solutions achieve the overall orbit improvements with respect to the solutions derived from the global network only. Additionally, the orbital differences over GPS satellite arcs that are visible by any of the five Australia-wide CORS stations show a higher percentage of overall improvements compared to the satellite arcs that are not visible from these stations. The regional GPS clock and Uncalibrated Phase Delay (UPD) products are derived using the PANDA real time processing module from Australian CORS networks of 35 and 79 stations respectively. Analysis of PANDA kinematic PPP and kinematic PPP-AR solutions show certain overall improvements in the positioning performance from a denser network configuration after solution convergence. However, the clock and UPD enhancement on kinematic PPP solutions is marginal. It is suggested that other factors, such as effects of ionosphere, incorrectly fixed ambiguities, may be the more dominating, deserving further research attentions.

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.

Magnetic resonance imaging: An accurate, radiation-free, alternative to computed tomography for the primary imaging and three-dimensional reconstruction of the bony orbit

Purpose: To determine the extent to which the accuracy of magnetic resonance imaging (MRI) based virtual 3-dimensional (3D) models of the intact orbit can approach that of the gold standard, computed tomography (CT) based models. The goal was to determine whether MRI is a viable alternative to CT scans in patients with isolated orbital fractures and penetrating eye injuries, pediatric patients, and patients requiring multiple scans in whom radiation exposure is ideally limited. Materials and Methods: Patients who presented with unilateral orbital fractures to the Royal Brisbane and Women’s Hospital from March 2011 to March 2012 were recruited to participate in this cross-sectional study. The primary predictor variable was the imaging technique (MRI vs CT). The outcome measurements were orbital volume (primary outcome) and geometric intraorbital surface deviations (secondary outcome)between the MRI- and CT-based 3D models. Results: Eleven subjects (9 male) were enrolled. The patients’ mean age was 30 years. On average, the MRI models underestimated the orbital volume of the CT models by 0.50 0.19 cm3 . The average intraorbital surface deviation between the MRI and CT models was 0.34 0.32 mm, with 78 2.7% of the surface within a tolerance of 0.5 mm. Conclusions: The volumetric differences of the MRI models are comparable to reported results from CT models. The intraorbital MRI surface deviations are smaller than the accepted tolerance for orbital surgical reconstructions. Therefore, the authors believe that MRI is an accurate radiation-free alternative to CT for the primary imaging and 3D reconstruction of the bony orbit. �

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.