# Implementation of Elliptic Curve Arithmetic Operations for Prime Field and Binary Field using java BigInteger Class

DOI : 10.17577/IJERTV6IS080211

Text Only Version

#### Implementation of Elliptic Curve Arithmetic Operations for Prime Field and Binary Field using java BigInteger Class

Tun Myat Aung

University of Computer Studies, Yangon Myanmar

Ni Ni Hla

University of Computer Studies, Yangon Myanmar

AbstractThe security of elliptic curve cryptosystems depends on the difficulty of solving the Elliptic Curve Discrete Log Problem (ECDLP). Elliptic curves with large group order are used for elliptic curve cryptosystems not to solve ECDLP. We implement elliptic curve arithmetic operations by using java BigInteger class to study and analyze any elliptic curve cryptographic protocol under large integer for prime field and binary field.

Keywords Implementation; Elliptic Curve Arithmetic Operations; Java Biginteger Class

1. INTRODUCTION

Elliptic Curve Arithmetic was applied on cryptography known as of Elliptic Curve Cryptography (ECC) was discovered in 1985 by Victor Miller (IBM) and Neil Koblitz (University of Washington) as an alternative mechanism for implementing public-key cryptography (PKC). ECC is a public key cryptography. In public key cryptography each user or the device taking part in the communication generally have a pair of keys, a public key and a private key, and a set of operations associated with the keys to do the cryptographic operations. Only the particular user knows the private key whereas the public key is distributed to all users taking part in the communication. Some public key algorithm may require a set of predefined constants to be known by all the devices taking part in the communication. Domain parameters in ECC is an example of such constants. Public key cryptography, unlike private key cryptography, does not require any shared secret between the communicating parties but it is much slower than the private key cryptography.

ECC can be used for providing the following security services:

• confidentiality,

• authentication,

• data integrity,

• non-repudiation,

• authenticated key exchange.

The recent progress in factorization and parallel processing leads to the need of larger and larger keys for public-key cryptosystems. But, the growth of keys length will do these cryptosystems slower than before. The use of ECC allows the increasing of security. In the same time, ECC decreases the overloading. ECC security consists in the difficulty to calculate logarithms in discrete fields (discrete logarithms problem): being given A (an element from a finite field) and

, it is practically impossible to calculate x when A is big

enough. Actually, there are several cryptosystems which are based on discrete logarithms problem in multiplicative group

. But these cryptosystems can be also defined in any other finite group, as the group of points of an elliptic curve.

The elliptic curves are suitable in applications where:

• the computing power is limited (intelligent cards, wireless devices, PC boards);

• memory size on integrated circuit is limited;

• a great speed of computing is necessary;

• digital signing and its verification are used intensively;

• signed messages have to be transmitted or memorized;

• digital bandwidth is limited (mobile communications, certain computer networks).

From the advantages of ECC usage, there can be mentioned:

• increased security: cryptographic resistance per bit is much greater than those of any public-key cryptosystem known at present time;

• substantial economies in calculus and memory needs in comparison with other cryptosystems;

• great encryption and signing speed both in software and hardware implementation;

• ECC are ideal for small size hardware implementations (as intelligent cards);

• encryption and signing can be done in separate stages.

The intense research done on public-key cryptosystems, based on elliptic curves, demonstrated that ECC are suitable for the vast majority of existing applications. An ECC with 160-bit key offers a security level equivalent with that offered by a cryptosystem based on a 1024-bit Zp field. Because of this, ECC provide a feasible method of implementation for a high level security system on a PC card, on an intelligent card or on a mobile communications device.

The purpose of this paper is to provide a detailed implementation for elliptic curve arithmetic operations over prime field and binary field under large integers. This work supports to implement, analyze and study any elliptic curve cryptosystems over prime field and binary field under large integers. The organization of this paper is as follows. The section 2 includes finite field arithmetic operations over prime field and binary field and their properties. In section 3, we describe in details elliptic curve arithmetic operations over prime field and binary field and their geometric properties. The section 4 illustrates the implementation of elliptic curve

arithmetic operations and their experimental results. Finally, we conclude this paper by discussion on performance results in section 5.

2. FINITE FIELD ARITHMETIC

A finite field is a field containing a finite number of elements. Fields are abstractions of familiar number systems (such as the rational numbers Q, the real numbers R, and the complex numbers C) and their essential properties. They consist of a set F together with two operations, addition (denoted by +) and multiplication (denoted by Â·), that satisfy the usual arithmetic properties:

• (F,+) is an abelian group with (additive) identity denoted by 0.

• (F\{0}, Â·) is an abelian group with (multiplicative) identity denoted by 1.

• The distributive law holds: (a+b) Â· c = (a Â· c) + (b Â· c) for all a, b, c F.

If the set F is finite, then the field is said to be finite. Galois showed that for a field to be finite, the number of elements should be pm , where p is a prime number called the characteristic of F and m is a positive integer. The finite fields are usually called Galois fields and also denoted as GF(pm). If m = 1, then GF is called a prime field. If m 2, then F is called an extension field. The order of a finite field is the number of elements in the field. Any two fields are said to be isomorphic if their orders are the same [4].

1. Field Operations

A field F is equipped with two operations, addition and multiplication. Subtraction of field elements is defined in terms of addition: for a,b F, a b = a +(b) where b is the unique element in F such that b+(b) = 0 (b is called the negative or additive inverse of b). Similarly, division of field elements is defined in terms of multiplication: for a, b F with b = 0, a/b = a Â· b1 where b1 is the unique element in F such that b Â· b1 = 1. (b1 is called the multiplicative inverse of b.)

2. Prime Field

Let p be a prime number. The integers modulo p, consisting of the integers {0,1,2, . . ., p 1} with addition and multiplication performed modulo p, is a finite field of order p. We shall denote this field by GF(p) and call p the modulus of GF(p). For any integer a, a mod p shall denote the unique integer remainder r, 0 r p1, obtained upon dividing a by p; this operation is called reduction modulo p [1].

Example (1). (prime field GF(29)) The elements of GF(29) are {0,1,2,

. . .,28}. The following are some examples of arithmetic operations in GF(29).

1. Addition: 17+20 = 8 since 37 mod 29 = 8.

2. Subtraction: 1720 = 26 since 3 mod 29 = 26.

3. Multiplication: 17 Â· 20 = 21 since 340 mod 29 = 21.

4. Inversion: 171 = 12 since 17 Â· 12 mod 29 = 1.

3. Binary Field

Finite fields of order 2m are called binary fields or characteristic-two finite fields. One way to construct GF(2m) is to use a polynomial basis representation. Here, the elements of GF(2m) are the binary polynomials (polynomials whose coefficients are in the field GF(2) = {0,1}) of degree at most m

1:

(2) = 11 + 22 + + 22 + 1 +

0: {0,1}.

An irreducible binary polynomial f (x) of degree m is chosen. Irreducibility of f(x) means that f(x) cannot be factored as a product of binary polynomials each of degree less than m. Addition of field elements is the usual addition of polynomials, with coefficient arithmetic performed modulo 2. Multiplication of field elements is performed modulo the reduction polynomial f(x). For any binary polynomial a(x), a(x) mod f(x) shall denote the unique remainder polynomial r(x) of degree less than m obtained upon long division of a(x) by f(x); this operation is called reduction modulo f(x) [1].

Example (2). (binary field GF(24)) The elements of GF(24) are the 16 binary polynomials of degree at most 3:

0 2 3 3 + 2

1 2 + 1 3 + 1 3 + 2 + 1

2 + 3 + 3 + 2 +

+ 1 2 + + 1 3 + + 1 3 + 2 + + 1

The following are some examples of arithmetic operations in

GF(24) with reduction Polynomial () = 4 + + 1.

(a). Addition: (3 + 2 + 1) + (2 + + 1) = 3 + .

(b). Subtraction: (3 + 2 + 1) (2 + + 1) = 3 + .

(c).Multiplication: (3 + 2 + 1). (2 + + 1) = 2 + 1 since

(3 + 2 + 1). (2 + + 1) = 5 + + 1 and

(5 + + 1) (4 + + 1) = 2 + 1.

(d). Inversion: (3 + 2 + 1)1 = 2 since

(3 + 2 + 1). 2 (4 + + 1) = 1.

3. ELLIPTIC CURVE ARITHMETIC

1. Elliptic Curves over Prime Field -GF(p)

The elliptic curve over finite field E(GF) is a cubic curve defined by the general Weierstrass equation: 2 + 1 +

3 = 3 + 22 + 4 + 6 over GF where and GF is a finte field. The following elliptic curves are adopted from the general Weierstrass equation. The elliptic curve E(GF(p)) over prime field GF(p) is defined by the equation [1]:

2 = 3 + +

where > 3 is a prime and , () satisfy that the discriminant 43 + 272 0 (a1 = a2 = a3 = 0; a4 = a and a6

= b corresponding to the general Weierstrass equation).

1. Points on E(GF(p))

The elliptic curve E(GF(p)) consists of a set of points { = (, )| 2 = 3 + + , , , , ()} together with a point at infinity defined as O. Every point on the curve has its inverse. The inverse of a point (x, y) on E(GF(p)) is (x, -y). The number of points on the curve, including a point at infinity, is called its order #E. The pseudocode for finding the points on the elliptic curve E(GF(p)) is shown in Algorithm (1).

Algorithm (1). Pseudocode for finding the points on the elliptic curve E(GF(p))

Input: a, b, p Output: = (, )

Begin x = 0;

while( x < p ){

= (3 + + ) .

(b). If = (, ) (()), then (, ) + (, ) = .

The point (x, -y) is denoted by (-P), and is called the

inverse of P; observe that P is indeed a point on the curve.

(c). (Point addition). Let = ( , ) (()) and =

If(w is perfect square in ) output (, ) (, ) 1 1

x = x + 1.

}

(2, 2) (()), where Â±. Then + = (3, 3), where

3 = 2 1 2 and 3 = (1 3) 1. In this

End

Example (3). Let p = 13 and consider the elliptic curve : 2 = 3 + 5 + 4 defined over GF(p) where a = 5 and b = 4. Note that 43 + 272 = 500 + 432 = 932 13 = 9, so E is indeed an elliptic curve. The points on E(GF(p)) and its graph are shown in Figure (1). The order of the elliptic curve : 2 = 3 + 5 + 4 over GF(13) is 17.

y O

12

 (0, 2) (0, 11) (1, 6) (1, 7) (2, 3) (2, 10) (4, 6) (4, 7) (6, 4) (6, 9) (8, 6) (8, 7) (10, 1) (10, 12) (11, 5) (11, 8)

11

10

9

8

7

6

5

4

3

2

1

0 0 1 2 3 4 5 6 7 8 9 10 11 12 x

Points Graph

Figure (1). Points on : 2 = 3 + 5 + 4

2. Arithmetic Operations on E(GF(p))

There is a rule, called the chord-and-tangent rule, for adding two points on an elliptic curve E(GF(p)) to give a third elliptic curve point. Together with this addition operation, the set of points E(GF(p)) forms a group with O serving as its identity. It is this group that is used in the construction of elliptic curve cryptosystems. The addition rule is best explained geometrically. Let = (1, 1) and = (2, 2) be two distinct points on an elliptic curve E. Then the sum of P and Q, denoted = (3, 3), is defined as follows. First draw the line through P and Q; this line intersects the elliptic curve in a third point. Then R is the reflection of this point in the x- axis. This is depicted in Figure (2.a). The elliptic curve in the figure consists of two parts, the ellipse-like figure and the infinite curve. If = (1, 1), then the double of P, denoted

= (3, 3), is defined as follows. First draw the tangent line to the elliptic curve at P. This line intersects the elliptic curve in a second point. Then R is the reflection of this point in the x-axis. This is depicted in Figure (2.b).

case, = (2 1)(2 1).

(d). (Point doubling). Let = (1, 1) (()), where

. Then 2 = (3, 3), where 3 = 2 21 and

3 = (1 3) 1.

In this case, = (312 + )21.

Example (4). (elliptic curve addition and doubling) Lets consider the elliptic curve defined in Example (3).

a. Addition. Let = (1, 6) and = (4, 6). Then + = (8, 7).

b. Doubling. Let = (1, 6). Then 2 = (10, 1).

c. Inverse. Let = (1, 6). Then = (1, 7).

2. Elliptic Curves over Binary Field – GF(2m)

A reduction polynomial () must be firstly chosen to construct a binary field GF(2m). The elements generated by the reduction polynomial are applied to construct an elliptic curve E(GF(2m)). The elliptic curve E(GF(2m)) over binary field GF(2m) is defined by the equation [1]:

2 + = 3 + +

where , (2) and 0.

1. Points on E(GF(2m))

The elliptic curve E(GF(2m)) consists of a set of points:{ = (, )|2 + = 3 + + , , , ,

(2)} together with a point at infinity. Every point on the curve has its inverse. The inverse of a point (x, y) on E(GF(2m)) is (, ). The number of points on the curve,

including a point at infinity, is called its order #E. The pseudocode for finding the points on the elliptic curve E(GF(2m)) is shown in Algorithm (2).

Algorithm (2). Pseudocode for finding the points on the elliptic curve E(GF(2m))

Input: a, b, ()

Output: = (, )

Begin

x = {0, 1, 1, , 2 }

y y

-R -R

Q

P

= {0, 1, 1, , 2 }

for(i=0; i<2m; i++){ for(j=0; j < 2m ;j++){

x x

= 3 .

P 1

2

2 =

R

Fig (a). Addition. (R = P + Q)

R

Fig (b). Doubling. (R = P + P)

If(1 = 2) output (, ) (, )

}

}

Figure (2). Geometric Description

The following algebraic formula[1] for the sum of two points and the double of a point can now be derived from the gometric description.

(a). P + O = O + P = P for all (()).

End

Example (5). Let () = 4 + + 1 be the reduction polynomial. Then 16 elements of GF(24) are shown in Table (1).

Table (1). Elements of GF(24)

 0000 0 1000 3 0001 1 1001 3 + 1 0010 1010 3 + 0011 + 1 1011 3 + + 1 0100 2 1100 3 + 2 0101 2 + 1 1101 3 + 2 + 1 0110 2 + 1110 3 + 2 + 0111 2 + + 1 1111 3 + 2 + + 1

Table (2) shows the power representation of g for elements of GF(24) generated by the polynomial () = 4 + + 1. The element of

= = (0010) is a generator of GF(24) because its order is 15

(24 1) as the following calculation show.

Table (2). Power representation of elements

 0010 5 0110 9 1010 13 1101 2 0100 6 1100 10 0111 14 1001 3 1000 7 1011 11 1110 15 0001 4 0011 8 0101 12 1111

Using the elliptic curve : 2 + = 3 + + 1, with = and

= 1, we can find the points on the curve, as shown in Figure (3). The order of the elliptic curve : 2 + = 3 + + 1 over GF(24) is 16.

y O

 (0, 1) O (1, 7) (1, 9) (3, 0) (3, 3) (5, 12) (5, 14) (6, 7) (6, 10) (9, 2) (9, 11) (10, 2) (10, 4) (12, 2) (12, 7)

g15 g14 g13 g12

g11

g10 g9 g8 g7 g6 g5 g4 g3 g2 g 1

0 0 1 g g2 g3 g4 g5 g6 g7 g8 g9 g10 g11 g12 g13 g14 g15 x

Points Graph

Figure (3). Points on : 2 + = 3 + + 1

2. Arithmetic Operations on E(GF(2m))

As with elliptic curves over GF(2m), there is a rule, called the chord-and-tangent rule, for adding two points on an elliptic curve E(GF(2m)) to give a third elliptic curve point. Together with this addition operation, the set of points E(GF(2m)) forms a group with O serving as its identity. The algebraic formula [1] for the sum of two points and the double of a point are the following.

(a). P + O = O + P = P for all ((2)). (b). If = (, ) ((2)),

then (, ) + (, + ) = .

The point (x, x+y) is denoted by (-P), and

is called the inverse of P; observe that P is indeed a

Example (6). (elliptic curve addition and doubling) Lets consider the elliptic curve defined in Example (5).

a. Addition. Let = (5, 12) and = (6, 7). Then +

= (12, 7).

b. Doubling. Let = (5, 12).

Then 2 = (1, 7).

c. Inverse. Let = (5, 12).

Then = (5 + 14).

3. Elliptic Curve Discrete Logarithm Problem

The security of ECC depends on the difficulty of Elliptic Curve Discrete Logarithm Problem (ECDLP). Let P and Q be two points on an elliptic curve such that kP = Q, where k is a scalar. Given P and Q, it is computationally infeasible to obtain k, if k is sufficiently large. k is the discrete logarithm of Q to the base P. Hence the main operation involved in ECC is point multiplication. i.e. multiplication of a scalar k with any point P on the curve to obtain another point Q on the curve.

1. Point Multiplication

Scalar multiplication is the computation of the form Q =

k.P where P and Q are the elliptic curve points and k is an integer. This is achieved by repeated point addition and doubling operations. To calculate the above, integer k is represented as = 121 + 222 + + 1 + 0 where 1 = 1 and {0, 1}, = 0, 1, 2, , 1. This method is called binary method [2] which scans the bits of k either from left-to-right or right-to-left. The Algorithm-3 given below illustrates the computation of kP using binary method. It can be used for both elliptic curves over prime field GF(p) and binary field GF(2m).

Algorthm (3). Binary Method

Input : Binary representation of k and point P Output : Q = kP

Q=P

For i = n-1 to 0 do Q = 2Q (Doubling) If ki = 1 then

Q = Q + P (Addition)

Return Q

The cost of multiplication depends on the length of the binary representation of k and the number of 1s in this representation. The number of non-zero digits is called the Hamming Weight of scalar. In an average, binary method requires (n-1) doublings and (n-1)/2 additions. For each bit .1., we need to perform point doubling and point addition, if the bit is .0., we need only point doubling operation. So if we reduce the number of 1s in the scalar representation or hamming weight, the speed of elliptic curve scalar multiplication will improve.

2. Order of Points

point on the curve.

( )

Let P E(GF(p)). The order of P is the smallest positive

(c). (Point addition). Let = (1, 1) ( 2 ) and = (2, 2) ((2)), where Â±. Then + = (3, 3), where

3 = 2 + + 1 + 2 + and

3 = (1 + 3) + 3 + 1.

integer, r, such that rP = O where O is the group identity. Hasses theorem [4] say that

+ 1 2 + 1 + 2.

3. Attacks on ECDLP

In this case, = (2 + 1)(2 + 1).

( )

The following algorithms can compute the elliptic curve

(d). (Point doubling). Let = (1, 1) ( 2

), where

discrete logarithm. Attacks on the ECDLP can be divided into

. Then

2 = (3, 3), where 3 = 2

+ + and

three main categories:

3 = 12 + 3 + 3. In this case, = 1 + (11).

1. Algorithms that work in arbitrary groups, such as the exhaustive search and the Baby-Step Giant-Step algorithm,

2. Algorithms that work in arbitrary groups with special conditions present in the group, like Pollards rho method and Pollards lambda method, and

3. Algorithms that work only in specific groups, such as the Index Calculus and Pohlig-Hellman method.

The discrete logarithm problem is of fundamental importance to the area of public key cryptography. Many of the most commonly used cryptography systems are based on the assumption that the discrete logarithm is extremely difficult to compute; the more difficult it is, the more security it provides a data transfer. One way to increase the difficulty of the discrete logarithm problem is to base the cryptosystem on a larger group.

4. IMPLEMENTATION

The elliptic curve cryptosystems on a small group are susceptible to the attacks described above. Therefore, we have to implement the elliptic curve cryptosystems under large integers to increase the difficulty of the discrete logarithm problem. At first level, we implement finite field arithmetic operations using java BigInteger class[6]. For prime fields, we implement a PrimeField class with methods of arithmetic oerations for addition, subtraction, multiplication, multiplicative inverse and division of elements in the prime field GF(p). And, for binary fields, we implement a BinaryField class with methods of arithmetic operations for addition, subtraction, multiplication, multiplicative inverse and division of elements in the binary field GF(2m) with reduction polynomial p. At second level, we implement elliptic curve arithmetic operations by using PrimeField class and BinaryField class. The ECCfp class is implemented by using methods of PrimeField class for point addition and point doubling over prime field GF(p). And the ECCf2m class is implemented by using methods of BinaryField class for point addition and point doubling over binary field GF(2m). At third level, we implement point multiplication for both ECCfp and ECCf2m by using algorithm (3). At fourth level, we will implement elliptic curve cryptosystems for our future research. For the implementation logic design of elliptic curve cryptosystems, the general hierarchy is shown in Figure (4).

EC Cryptosystems

fourth level

EC Point Multiplication

third level

EC Point Double

EC Point Inv

second level

GF mul

GF div/inv

first level

BigInteger

Figure (4). General logic design of implementation

We measure the performance of elliptic curve arithmetic basic operations: point addition and point doubling under prime field and binary field for comparison of execution time on the processor Intel Core i5@1.60GHz, 2.30GHz. The National Institute of Standards and Technology (NIST) submitted a report to recommend a set of elliptic curves for federal government use with larger key sizes [5]. We use NIST recommended elliptic curves for our research. The experimental results of elliptic curve arithmetic operations are shown in section (4.1). The performance results are listed in Table (3).

A. Experimental Results

Prime Field (P-192)

(()): 3 = 2 + + . p=6277101735386680763835789423207666416083908700390324961279.

= 3. b=64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1. The order = 627710173538668076383578942317605 9013767194773182842284081.

Points on the curve

= (1, 1).

1 = 188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012.

1 = 07192b95ffc8da78631011ed6b24cdd573f977a11e794811.

= (2, 2).

2 = 5701b8be342fb767752f13a308e2eff016b41fd348ef1ea.

2 = 77aeacae8fd493a524b9b18509c9a60e7e2a7da86882d82c.

= + = (3, 3).

3 = c5675f8265cf98e933db304666558478ca70c5ebba4da630.

3 = 2c2560e527695bbe883084abf6736e0a7e06b489ba57cb39.

Point Doubling

2 = (4, 4).

4 = dd6bda0d993da0fa46b27bbc141b868f59331afa5c7e93ab. Point Multiplication

. = .

Binary Field (K-163)

((2)): 2 + = 3 + 2 + .

() = 163 + 7 + 6 + 3 + 1.

= 1.

= 1.

The order = 5846006549323611672814741753598448348329118574063.

Points on the curve.

= (1, 1).

1 = 2fe13c0537bbc11ac aa07d793de4e6d5e5c94eee8.

1 = 289070fb05d38ff58321f2e800536d538ccdaa3d9.

= (2, 2).

2 = 4ec251aba46dc1dd4d6a0d18d25f98deb6e0cba68.

2 = f35a742feaeb3ec71b751605457513c6f20a82b.

= + = (3, 3).

3 = fd5f739b49278be0cc385ab2a0f66a695775312e.

3 = 44dfc418c0590df2951cbc876ba30dbffd4b945b1.

Point Doubling

2 = (4, 4).

4 = cb5ca2738fe300aacfb00b42a77b828d8a5c41eb.

4 = 229c79e9ab85f90acd3d5fa3a696664515efefa6b. Point Multiplication

. = .

Table (3). The results of performance

 EC Arithmetic Operations Prime Field (ms/100000times) Binary Field (ms/100000times) Addition Doubling 3770 3521 87548 85244
5. CONCLUSION

The performance of elliptic curve arithmetic basic operations, point addition and point doubling, under prime field and binary field, depends on the performance of equivalent finite field arithmetic operations. As a result of the performance for finite field arithmetic operations in the paper [6], it proved that the java BigInteger class is more efficient for the software implementation of finite field arithmetic operations in prime field than in binary field. Therefore, the results of performance in the table (1) more proved that the java BigInteger class is more efficient for the software implementation of elliptic curve arithmetic operations in prime field than in binary field.

REFERENCES

[1]. Behrouz A. Forouzan, Cryptography and Network Security, McGraw-Hill press, International Edition, 2008.

[2]. Darrel Hankerson, Alfred Menezes, Scott Vanstone. Guide to Elliptic Curve Cryptography, Springer press, 2004.

[3]. Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, Second Edition, Taylor & Francis Group, LLC, 2008.

[4]. Rudolf Lidl and Harald Niederreiter, Introduction to Finite Field Arithmetic and their Applications, Cambridge University Press, 1986.

[5]. Recommended Elliptic Curves for Federal Government Use, NIST, 1999.

[6]. Ni Ni Hla, Tun Myat Aung. Implementation of Finite Field Arithmetic Operations for Large Prime and Binary Fields Using java BigInteger class, International Journal of Engineering Research and Technology (IJERT), Volume. 6, Issue. 08, August – 2017.