Efficient Scalar Multiplication over Elliptic Curve

Published Online April 2016 in MECS

Index Term —Elliptic curve cryptography, double and add operation, affine coordinates.

• I.    Introduction

  Elliptic Curve Cryptography (ECC) was proposed as an alternative mechanism for implementing public- key cryptography in 1985 by Victor Miller (IBM) and Neil Koblitz (University of Washington) [1]. Public-key cryptography, also known as asymmetric cryptography, is a class of cryptographic protocols ba sed on algorithms that needs two separate keys, out of these two, one is secret (or private) and another of public. Elliptic Curve Cryptography is based on discrete logarithms that are more computationally expensive to invert at equivalent

  key lengths [8]. For general elliptic curves, we will present an improved version of scalar multiplication. We’ll present a treble concept as well with its basic operations doubling and addition. Treble method provides fast computation as compare to doubling and addition. Its computation is effective than first applying doubling and after that addition. Besides that we implemented a recursive approach as well where time complexity is reduced but number of functions calling in both approaches remain same but less than the existing approach. The primary advantage promised by ECC is a smaller key size, reducing storage and transmission requirements, i.e. an elliptic curve group could provide the same level of security afforded by an RSA-based system with a large modulus and correspondingly larger key – eg, a 384- bit ECC public key should provide comparable security to a 3072-bit RSA public key.

As the size of key increases, the difference in equivalent key size also increases. Modular arithmetic used in DH provides less security as compare to algebraic curves used in Elliptic curve cryptography. The approximate equivalence in security strength for RSA, DH and Elliptic curve cryptography is given in tables 1 and 2 shows that EC is better to use if key size is large.

Table 1. Key Strength of Elliptic Curve

Table 2. NIST Recommended Key Sizes

• II.    Mathematics of Elliptic Curve Cryptography

We can define Elliptic curves over both prime field and binary field. If P is a prime number or prime power, then FP will denote the field that has exactly P points on the curve [6]. When the greatest common divisor of P and b is 1, the elliptic curve over the field FPis expressed by the following equation:

• E: Y2 = X3 + aX+ b(1)

Whereas, b are the coefficients in FP and 4a3+ 27b2≠ 0. While the general curve equation is defined as:

• E: Y + XY = X + aX+ b(2)

Coordinates (X, Y) are used to define the affine coordinates which satisfy the curve equation. Coordinates for adding two different points

X3 = A2– X1 – X2 mod P(3)

Y3 = A(X1 – X3) – Y1 mod P(4)

Where

A=(Y2-Y1)/(X2-X1) mod P(5)

Coordinates for doubling a point:

X4 = A2– 2X1 mod P(6)

Y4 = A(X1 – X4) – Y1 mod P(7)

Where A= (3X12+a)/2Y1(8)

Table 3. Literature Work with Specified Problem