# High Performance Scalar Multiplication For Ecc Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Abstract- Wireless Sensor Networks (WSN's) are being widely used in various civilian and military applications. In certain WSN applications, the data among the nodes and the Base Station (BS), needs to be exchanged in a secure manner. The encryption and decryption operations over the data involve additional energy overhead. Hence, it is required to use a security model, which offers security with less computational requirements, as WSN nodes have resource constraints. Elliptic curve cryptography (ECC), a public key cryptographic system, has lesser key size requirements in comparison with RSA algorithm. ECC has been gaining acceptance as another alternative to RSA. In ECC, scalar multiplication accounts for about 80 percent of the key calculation time [1]. This work presents an optimized Sliding Window method with 10s complement technique for scalar multiplication. The same is also compared with two other methods of scalar multiplication, Binary Method and Non-Adjacent Form (NAF) method.

Keywords-WSN, security, ECC, scalar multiplication, sliding window

Introduction

978-1-4673-2907-1/13/$31.00 ©2013 IEEEWireless sensor networks (WSN's) are finding their applications in diversified areas as the tiny WSN nodes have become inexpensive. A WSN is a wireless adhoc network, in which the nodes organise themselves and the sensed measurements are relayed following a muti-hop path towards the Base Station (BS). WSN nodes are deployed even in hostile environments and different terrain types. While attempting to conserve energy WSN nodes can be arranged in a hierarchical manner so that redundancy among multiple measurements from different nodes can be reduced. A tiny WSN node has resource constraints, CPU power, limited storage, finite battery energy. After the deployment of a WSN, it is not always possible or feasible to replace batteries in the nodes. For example, the MICAz mote [2] consists of an 8- bit ATMega 128L microcontroller [MRP2400] working on 2.4 GHz. MICAz mote has maximum data rate of 250 Kbits/s, IEEE 802.15.4 compliant RF transceiver and direct sequence spread spectrum (DSSS)radio, the flash memory size being 512 KB. Apart from these constraints, the on board battery is 3.3.V with 2 AH capacity. Any WSN designer must keep these constraints in mind and energy conscious always. Despite the constraints, certain WSN applications demand the communication within the WSN to be kept confidential allowing only authorised users to gain access to the data and integrity of the data during transit is also to be maintained. To achieve these security requirements, all data transmissions need to be sent over a secure multi-hop wireless connectivity. For this purpose, Elliptic Curve Cryptographic (ECC) algorithm can be used as it provides identical security level as that of RSA [1] with lesser key size requirement. ECC was proposed by Neal Koblitz [3] and Victor Miller [4] independently during the early eighties. The advantage of ECC [5] over other public key cryptography techniques such as RSA, Diffie-Hellman is that the best known algorithm for solving elliptic curve discrete logarithm problem (ECDLP), the underlying hard mathematical problem in ECC, the full exponential time. On the other hand the best algorithm for solving RSA and Diffie-Hellman takes sub exponential time. ECC with a key size of 160- bits provides the same level of security as RSA, DSA with a key size of 1024- bits. An elliptic curve E over GF(p) can be defined by

(1)

where a,b ε GF(p) and 4a3 + 27b2 ≠ 0 in the GF(p) [5].

The point (x, y) on the curve satisfies the equation (1) and

the point at infinity denoted by ∞, is said to be on the elliptic curve. Let there be two points on the EC namely, P(x1, y1), Q(x2, y2) and their sum is given by point R(x3,y3) for point addition and point doubling are given by following equations:

(2)

Here, the addition, subtraction, multiplication and inverse are

the arithmetic operations over GF(p). The rest of the paper is organized as follows: Section II presents the different scalar multiplication techniques, section III presents simulation results and section IV provides conclusions.

## SCALAR MULTIPLICATION

The classical Elliptic Curve Diffie Hellman (EC-DH) scheme is illustrated by the Fig. 1.

## Fig. 1. Diffie-Hellman protocol based on ECC [5]

Initially both Alice and Bob agree on a particular Elliptic curve (EC) within a particular prime field, with a specific base point called as the Generator point G. The generator point is the point on the EC which has the highest order [5]. Both the users set their respective private keys by selecting randomly any scalar integer in the prime field. Their respective public keys are computed by multiplying the generator point, G, with the corresponding private keys namely KA and KB. After sharing public keys, they generate a shared secret key by multiplying public keys by their respective private keys. The secret key is R = KA QA = KB Q, this shared secret key is only known to sender and receiver i.e. to Alice and Bob. With the known values of QA, QB and R, it is computationally infeasible for an eavesdropper to compute KA and KB, which are the private keys of Alice and Bob respectively. As a result, an adversary cannot calculate R, the shared secret key.

In ECC, during the set-up phase of the WSN when the WSN node selects the random number for private key and then multiplies it with the generator point to generate the shared key. Two frequently used operations involved are: scalar multiplication and modular reduction. Gura, Patel and wander [1] showed that about 85 percent of execution time is spent in carrying out scalar multiplication operations alone. The scalar multiplication is the operation of multiplying point P on an elliptic curve, E defined over a field, GF(p) with positive integer k, which involves point addition and point doubling operations.

One point addition when P = Q requires one field inversion and three field multiplications [6]. The squaring operation is treated as multiplication. The cost is denoted by 1I + 3M, where I denotes the cost of inversion and M, denotes the cost of multiplication. One point doubling, when P = Q requires 1I + 4M as the cost of field additions and the cost of multiplications can be ignored.

ECC's computational load largely depends on the scalar multiplication. Generally to improve the efficiency of scalar multiplication two approaches are available

Coordinate system: Mostly to perform the mathematical operation such as point addition and point doubling over Ellip-tic curve, affine coordinate system is used. If these operations are done in projective or Jacobian coordinate systems, the number of addition and inversion operations over GF(p) can be reduced by a significant amount.

Recoding of Integer: The number of point addition and point doubling operations in scalar multiplication depends on the number of 0's and number of 1's in the binary form, their positions and the total number of bits. The Hamming weight is represented by the number of non-zero elements. The recoding of integer consists of the algorithm which attempts to decrease the length and the Hamming weight of the scalar k, hence speeding up the scalar multiplication operation. Expressing an integer, k, in binary format highlights this dependency.

The algorithms available for recoding of integer k are:

A. Binary Method

Scalar multiplication is the computation of the form Q = kP, where P and Q are the EC points and k is a positive integer [7]. In binary method the integer, k, is represented in binary form:

The binary method scans the bits of k, either from left to right or right-to-left. The binary method for the computation of kP is given by Algorithm -1.

Algorithm-1 Left to Right method for point multiplication

Input: A point P Ïµ E(Fq) an l- bit integer

Output: Q = kP

1: Q ← ∞

2: for all j = (l-1) to 0 do

3: Q ← [2]Q

4: if kj = 1 then Q ← Q + P

5: end for

6: Return Q

If the representation has k(l-1) ≠ 0, then the binary method requires (l-1) point doubling and (W-1) point addition operations, where 'l' is the length of the binary form of k, and 'W' is the Hamming weight of k (i.e., the number of non-zero elements in binary form of k). Consider an example, k= 3277 = (110011001101)2, it requires (W-1) = 6- point additions and (l-1) = 11- point doubling operations.

B. NAF Method

The subtraction has virtually the same cost as addition in the elliptic curve group. The negative of point (x, y) is (x, -y) for odd characters. This leads to scalar multiplication methods based on addition-subtraction chains, which help to reduce the number of EC operations. When integer k is represented with the following form, it is a binary signed digit representation [8].

When a signed-digit representation has no adjacent non zero digits, i.e. SjSj+1 for all j ≥ 0 it is called a non-adjacent form (NAF). NAF usually has fewer non-zero digits than binary representations. The average Hamming weight for NAF form is (n-1)/3. So generally it requires (n-1) point doubling and (n-1)/3 point addition operations. The binary method can be revised accordingly [9] to obtain another algorithm for NAF.

The NAF of a positive integer, k, in binary representation is computed by using Algorithm-2

Algorithm- 2 Conversion from Binary to NAF

Input: An integer

Output: NAF

1: C0 ←0

2: for j = 0 to 1 do

3: C(j-1) ← [(kj + k(j+1) + Cj)/2]

4: Sj ← kj+k(j+1)-2C(j+1)

5: end for

6:Return (Sj……..S0)

C. Sliding Window Method

More memory is being added onto the WSN nodes over the years. As the size of the nodes decreases the battery size becomes more constrained and this demands energy efficient technique. The sliding window technique, as described in this section, requires some amount of memory for storing the pre-computations resulting reduced mathematical operations, and thereby proving to be an energy efficient technique. The Algorithm-3 [8], which is based on subtraction based on the 1's complement method, is used. The 1's complement of any binary number can be expressed by the following equation:

C1 = (2a -1) - N,

where C1 = 1's complement of the binary number,

a = the no. of bits in N in terms of binary form,

N = the binary number.

Based on the above equation, any positive integer can be represented by using minimal non-zero bits in its 1's complement form provided that it has a minimum of 50% Hamming weight.

The above equation can be rewritten as:

N = (2a - C1 - 1).

Example:

Let N =1788 = (11011111100)2, C1 = 1's complement of the number N = (00100000011)2, a = 11, the no. bits in N. By substituting these values in the above equation we obtain

N = 1788 = 211 - 00100000011 - 1,

= 100000000000 - 00100000011 - 1

= 2048 - (256 + 2 + 1) - 1

In the example, the Hamming weight of scalar N has reduced from 8 to 5 saving 3- EC addition operations. The above recoding method based on 1's complement subtraction combined with sliding window method provides a more optimized result.

Let us compute [k=3277]P, as another example, with a sliding window algorithm with k recoded in binary form and window sizes of 2, 3, and 5. It is observed that as the window size increases, the number of pre-computations also increases geometrically. At the same time number of addition and doubling operations decreases. Now we present the details for the different window sizes to find out the optimal window size using the following example:

Window Size w = 2

3277 = (110011001101)2

No of pre-computations = 2(w - 1) - 1 = 1

all odd values : [3]P

3277 = (11 00 11 00 11 01)2

The intermediate values of Q are 3P, 6P, 12P, 24P, 48P, 51P, 102P, 204P, 408P, 816P, 819P, 1638P,3276P, and 3277P.

Computational cost = 10 doubling + 3 addition + 1 pre- computation operations.

Window Size w = 3

No of pre-computations = 2(w - 1) - 1 = 3

all odd values : [3]P; [5]P; [7]P

3277 = (110 011 001 101)2

The intermediate values of Q are 3P, 6P, 12P, 24P, 48P, 51P, 102P, 204P, 408P, 409P, 818P, 1636P, 3272P, and 3277P.

Computational cost = 11 doubling + 3 addition + 3 pre-computation operations.

Window Size w = 5

No of pre-computations = 2(w - 1) - 1 = 15

all odd values : [3]P; [5]P; [7]P; [9]P; [11]P; [13]P; [15]P :::

:::: [31]P

3277 = (11001 10011 01)2

The intermediate values of Q are 25P, 50P, 100P, 200P, 400P, 800P, 819P, 1628P, 3276P, and 3277P.

Computational cost = 7 doubling + 2 addition + 15 pre- computation operations.

The Algorithm- 3 shows the steps for the sliding window

scalar multiplication of k.

Algorithm-3 Sliding window scalar multiplication

1: Q ← ∞ and i ← (l - 1)

2: while i ≥ 0 do

3: if ni = 0 then Q ← [2]Q and i ← (i-1)

4: else

5: S ← max(i-k+1,0)

6: while ns = 0 do

7: S ← S+1

8: end while

9: for h = 1 to i-S+1 do

10: Q ← [2]Q

11: end for

12: u ← [ni…….ns]2 [ni = ns = 1 and i-s+1≤k]

13: Q ← Q ⊕ [u]P [u is odd so that [u]P is pre-computed]

14: i←S-1

15: Return Q

16: end while

COMPARISON

In this section, a comparison of three different scalar multiplication techniques is presented. The comparison as given in the Table I, considers number of ECC mathematical operations like point addition and point doubling operations. The sliding window technique for scalar multiplication is also compared with the number of pre-computations required for different window sizes. A sample 160- bit key, a scalar integer, is considered and used for comparing all the three techniques for scalar multiplication and for sliding window technique with different window sizes.

k = (EEEE EEEE EEEE EEEE EEEE EEEE EEEE EEEE EEEE EEEF)16.

Method

No. of doublings

No. of additions

Binary method

159

79

NAF method

159

53

Sliding window (w=3)

158

44

TABLE I

DIFFERENT METHODS AND THE NO. OF ADDITIONS AND DOUBLINGS

In Table I, the sliding window method with a fixed window size of 3 is considered. However, the window size can be varied and this leads us to determine the optimum window size. Table II shows the number of point doublings and the number of point additions required for different values of window sizes. The Table II also includes another parameter, the number pre-computations, which also depends on the window size.

Table II consists of the following fields: window size, Number of point additions, Number of point doublings, Number of pre-computations and Total number of additions. It can be noticed

from Table II that with increase in the window size the number of point doublings and the number of point additions decreases but at the same time the number of pre-computations increases. Hence there is a trade-off between the window size and the number of pre-computations.

Window

No. of

No. of

Pre-

Total

size

Doublings

Additions

computations

Additions

3

158

40

3

44

4

158

39

7

47

5

156

26

15

42

6

156

26

31

58

7

154

19

63

83

8

154

19

127

147

9

152

15

255

241

10

152

15

511

527

11

150

13

1023

1037

12

150

13

2047

2061

13

148

11

4095

4107

14

148

11

8191

8203

15

146

9

16383

16393

TABLE II

WINDOW SIZE AND DOUBLINGS, ADDITIONS AND PRE-COMPUTATIONS

CONCLUSIONS

By comparing binary, NAF and sliding window methods for scalar multiplication, it can be seen that the sliding window method is more suitable for ECC shared key computations. An optimal window size can also be determined by varying the window size. In ECC, the sliding window method with an optimum window size can decrease computations considerably thereby resulting in reduced energy requirements of the WSN nodes involved in secure communication. The security overhead can be minimized by using this scheme in any WSN application demanding security.