Research Journal of Information Technology

Year: 2015 | Volume: 7 | Issue: 2 | Page No.: 80-100
DOI: 10.17311/rjit.2015.80.100

Performance Analysis of Signed-Digit {0,1,3}-NAF Scalar Multiplication Algorithm in Lopez-Dahab Model

Sharifah Md. Yasin, Ramlan Mahmod and Rozi Nor Haizan Nor

Abstract: Scalar multiplication is a major operation in an elliptic curve cryptosystem. It is the mostly costly and time consuming operations. This study proposes a new signed-digit {0,1,3}-NAF scalar multiplication algorithm for elliptic curve over binary field with the scalar multiplier in base 2 and using digits {0, 1, 3}. The digit 3 requires tripling operations in the execution of the scalar multiplication algorithm. Thus, a tripling formula is also proposed and the proof of the formula is presented in this study. Complexity analysis is carried out to compare the proposed scalar multiplication algorithm with the addition-subtraction algorithm. At average case analysis, the proposed scalar multiplication algorithm has better performance than the addition-subtraction algorithm exceptionally when only one digit 3 occurs in the scalar multiplier. When compared with traditional NAF scalar, the proposed scalar has better performance except when the Hamming weight and the bit-length of the proposed scalar and the traditional NAF are the same.

Keywords: elliptic curve, binary field, scalar multiplication, Elliptic curve cryptosystem and Hamming weight

INTRODUCTION

Elliptic curve cryptography is proposed by Miller and Koblitz in mid 80’s. Elliptic Curve Cryptosystem (ECC) is used to secure digital information. The security of an elliptic curve cryptosystem is based on Elliptic Curve Discrete Logarithm Problem (ECDLP) over the points on the elliptic curves. Security services provided by ECC are key agreement, digital signatures and encryption (Morales-Sandoval and Feregrino-Uribe, 2006). ECC is favourable in memory constraint devices since ECC uses shorter key size for the same security level with its competitor the RSA cryptosystem. Also, current mobile technology creates more challenges to ECC implementation (Paryasto et al., 2009).

In related studies, the major problem in the implementation of ECC is how to compute the scalar multiplication kP efficiently. The scalar multiplication (kP) is also a major operation in Elliptic Curve Cryptosystem (ECC). It is the most costly and time consuming operation. It is computed as Q = kP = P+P+…+P (k times), where P and Q are points on an elliptic curve E and scalar k is a very large integer. The operation is a consecutive sum of points that can be performed using elliptic curve point additions when the sum is using two different point (P+Q) and using elliptic curve point doublings when the sum is using the same point (P+P). Several methods have been developed to improve the scalar multiplication operation. Some of the method involves with recording the scalar into a different representation which gives result to a minimum number of nonzero digits in the scalar. Some method consists of rewriting or formulation of the point operation formula.

The objective of this study is to reduce the complexity of the scalar multiplication by recording the scalar into a new representation, formulation of a new tripling formula and introducing a new scalar multiplication algorithm that utilizes the proposed scalar and the proposed tripling.

ELLIPTIC CURVE IN LOPEZ-DAHAB MODEL

There are two types of elliptic curve that are widely used in cryptography: Binary GF(2^m) and prime GF(p) fields. Scalar multiplication involved with elliptic curve point operations and field operations. Elliptic curve point operations involved with point additions and point doublings. Whereas, elliptic curve field operation involved with multiplication, inversion, squaring and adding. In most research, either Lopez-Dahab or Jacobian coordinates is used. Both coordinates are free of inversion operation since inversion is the most costly field operation. Lopez-Dahab or Jacobian coordinates are also called projective coordinates.

This study mainly focuses on elliptic curve over binary field. A non-supersingular elliptic curve equation of characteristic 2 or defined over a binary field has the following form:

where, a, b∈GF(2^m), b≠0. If P = (x, y), then the inverse of P is -P = (x, x+y).

For Lopez-Dahab coordinates, Eq. 1 is transformed to Lopez-Dahab projective form by substituting x = X/Z and y = Y/Z², then by clearing the denominator, Lopez-Dahab projective equation is given below (Lopez and Dahab, 1999; Qingwei, 2008):

Every equivalent class of the triples (X, Y, Z), on the projective plane, with Z ≠ 0, can be mapped back to the affine point by x = X/Z^α and y = Y/Z^β. There is only one point at the infinity O that can be represented with Z = 0. Also, there is only one element that can be represented with Z = 1, which is corresponding to the affine coordinates (Longa, 2007):

Lopez-Dahab point addition: Consider P = (X₀, Y₀, Z₀), Q = (X₁, Y₁, Z₁) such that P ≠ ±Q then P⊕Q = (X₂, Y₂, Z₂). Lopez and Dahab (1999) proposed a general addition formula that needs 14M+6S+8A, where M, S and A are multiplication, squaring and addition, respectively:

Higuchi and Takagi (2000) improved Lopez-Dahab general addition formula to 13M+4S+9A, where, P = (X₁, Y₁, Z₁), Q = (X₂, Y₂, Z₂) and P ⊕ Q = (X₃, Y₃, Z₃) where:

Al-Daoud et al. (2002) proposed point addition formula for mixed affine-Lopez-Dahab coordinates. If a∈{0,1}, then only eight general multiplications are required. Consider P = (X₁, Y₁, 1), Q = (X₂, Y₂, Z₂) such that P ≠ ± Q, P is an affine and Q is a Lopez-Dahab coordinates, then, P ⊕ Q = (X₃, Y₃, Z₃) is given by:

Lopez-Dahab point doubling: The doubling formula is given by Lopez and Dahab (1999) and the cost is 5M+5S+4A. For a = 1, the following equations requires 4M+5S+3A. The doubling formula is given below:

If P = (X₁, Y₁, Z₁) then 2P = 2(X₁, Y₁, Z₁) = (X₂, Y₂, Z₂) where:

Lange (2004) improved Lopez-Dahab doubling formula and it takes 5M+4S+5A including one multiplication by a. If P = (X₁, Y₁, Z₁) then 2P = (X₂, Y₂, Z₂), the Eq. 8 is as the following:

REVIEW OF SIGN-DIGIT RECORDING

Scalar representation can be improved by recording the scalar to a different representation with a minimal Hamming weight. The Hamming weight is a measurement used on the number of nonzero digit in a scalar. This study focuses on signed numbers representation similar with the traditional NAF scalar. There are two modes of recordings; right-to-left and left-to-right recording. Selection of radix or digit set for a scalar must satisfies the characteristics of the scalar multiplication algorithm or implementation technology (Phillips and Burgess, 2004). Proper selection of radix and digit set for the scalar can promote an increment of the frequency of useful digits such as zero and a reduction in the total number of nonzero digits to represent a number.

Left-to-right recording is a real-time recording because the recorded scalar is used straight away for scalar multiplication algorithm. This is possible because scanning digits of the scalar for recording and scalar multiplication algorithm are done using the same mode, which is from left-to-right. In the literature, this type of recording promotes better memory usage and mostly preferred for memory constraint devices (Khabbazian et al., 2005). Whereas, in the right-to-left recording, the recorded digits are saved before it is used in the scalar multiplication algorithm. This is because scanning digits of the scalar for recording and scalar multiplication algorithm initiated from different modes that is the recording mode is from right-to-left and the scalar multiplication mode is from left-to-right. Generally, this type of recording needs an additional n-bit RAM for storage, where n is the bit size of the scalar (Okeya et al., 2004).

Right-to-left {-1,0,1}-NAF recording: Reitwiesner (1960) proposed a right-to-left NAF recording which converts a binary number into a traditional NAF using digit {-1,0,1}. In this study, it is labeled as {-1,0,1}-NAF to differentiate with the proposed {0,1,3}-NAF. NAF means non-adjacent form which ensures that there is no consecutive non-zero digit in the scalar k. In the {-1,0,1}-NAF recording, a binary number of the form with , converted into a canonical form with using Algorithm 1.

Left-to-right recording: Joye and Yen (2000) proposed an optimal left-to-right signed-digit recording algorithm. This algorithm used look-up table as shown in Table 1. This recording method does not have NAF property but still has a minimal Hamming weight and as efficient as the Reitweisner’s Algorithm 2.

METHODOLOGY

In this study, a new scalar multiplication algorithm is proposed. In this study, the following steps are carried out: Propose a new scalar representation; propose a new point operation and propose a new scalar multiplication algorithm.

Propose a new scalar representation: In this study, we propose a recording technique based on Joye and Yen (2000) that converts a binary number into a new representation in base 2 with digit {0,1,3}. Mode of the recording is from Left-to-Right (LR). The new scalar adopted the Non-Adjacent Form (NAF) property. Consider a binary number, r = (r_m-1, …, r₀)₂ where r_i∈{0,1} and m is the bit length of r. Let h denotes the Hamming weight of r and p be the number of digit 3 in r where:

Algorithm 3 (Yasin et al., 2014) and Table 2 are used to convert a binary r into:

where, Then, h₁ denotes the Hamming weight of r’. Also, r’ can be written as Special case in Table 3 is a special s-block is defined for the case where r = (r_m-1, …, r_i+1, r_i, r_i-1, r_i-2,…, r_s-1, r_s,…, r₁, r₀)₂ such that r_i+1 = 0 and r_s = 0. Therefore, s-block consists of consecutive digit ‘1’ where r_i = r_i-1 = r_i-2 = … = r_s-1 = 1. This special case occurs when the count of digit ‘1’ in the s-block is greater than or equal to 2.

The proposed recording algorithm is implemented in Visual C++ ver 6.0. The conversion of a binary expansion to a new {0,1,3}-NAF representation is running successfully.

Hamming weight of the traditional {-1,0,1}-NAF scalar: Performance of a scalar is based on the Hamming weight (H_w) and bit-length of the scalar k. Heuberger and Prodinger (2007) studied a relation between the expected Hamming weight of the {-1,0,1}-NAF scalar when recorded from a binary expansion with length n and Hamming weight h. The expected Hamming weight of {-1,0,1}-NAF satisfies the following theorem (Heuberger and Prodinger, 2007):

Where:

and α is in the interval (0,1). The expected Hamming weight of {-1,0,1}-NAF is equal to n/3 when:

otherwise, the scalar is smaller.

The coordinates of the random vector asymptotically becomes independent and normally distributed.

Non-adjacency property: Based on the proving technique used by Joye and Yen (2000), each row in Table 3 is examined for the non-adjacency property, The proof of non-adjacency property is as shown below (Yasin, 2011):

Row 1:

Row 2:

Row 3:

Row 4:

Row 5:

Therefore, it is proven that r’_i. r’_i-1 = 0.

Row 6:

Case 1: If (b_i, r_i, r_i-1, r_i-2) = (1, 1, 1, 0), then r’_i-1 = 3
Case 2: If (b_i, r_i, r_i-1, r_i-2) = (1, 1, 1, 1), then r’_i-1 = 3

Therefore, it is proven that r’_i. r’_i-1 = 0.

Row 7:

Row 8:

Row 9:

Row 10:

Case 1: For r’_i = 0 and r’_i-2 = 0, then r’_i-1 = 1
Case 2: For r’_i = 3 and r’_i-2 = 1, then r’_i-1 = 0

Therefore, it is proven that r’_i. r’_i-1 = 0.

Row 11:

Case 1: For r’_i = 0 and r’_i-2 = 0, then r’_i-1 = 1
Case 2: For r’_i = 3 and r’_i-2 = 1, then r’_i-1 = 0

Therefore, it is proven that r’_i. r’_i-1 = 0.

Row 12:

Case 1: For r’_i = 0 and r’_i-2 = 0, then r’_i-1 = 0
Case 2: For r’_i = 3 and r’_i-2 = 1, then r’_i-1 = 0

Therefore, it is proven that r’_i. r’_i-1 = 0.

Row 13:

Case 1: For r’_i = 0 and r’_i-2 = 0, then r’_i-1 = 0
Case 2: For r’_i = 3 and r’_i-2 = 1, then r’_i-1 = 0

Therefore, it is proven that r’_i. r’_i-1 = 0.

Row 14 and 15:

Case 1: For r’_i = 0 and r’_i-2 = 0, then r’_i-1 = 3
Case 2: For r’_i = 3 and r’_i-2 = 1, then r’_i-1 = 0

Therefore, it is proven that r’_i. r’_i-1 = 0.

From the above, each row in Table 2 is proven to have the non-adjacency property.

Proposed {0,1,3}-NAF vs. traditional {-1,0,1}-NAF scalars: Analysis of the scalar k is carried out using 144 data of binary number with 24 bit-length. Each binary data (k) is converted into traditional {-1,0,1}-NAF and proposed {0,1,3}-NAF scalars by using Algorithm 1 and 3, respectively. Then, at average case, the Hamming weight and bit-length of each data is compared and analyzed. The average case is defined as:

where, h is the Hamming weight of binary and l is the corresponding bit-length. Table 4 shows the average case for Hamming weight differences after conversion from binary.

This data are derived from 144 data and for values h = 12. In Table 4, as we go down the table p varies from 1-6 and 6 is the maximum value of p when h = 12. The values of h and l are fixed so that the variation of p, h₁ and h₂ can be monitored. Cases for the Hamming weight h₁ = h₂ only occur for data No. 3, 6, 9, 11, 13 and 16. Whereas, the remaining data are having the Hamming weight h₁<h₂. This indicates an improvement in the Hamming weight when using the proposed scalar.

Propose new point tripling operation: This section focuses on elliptic curve point operations. Research development on point operations mostly involved with reducing the number of multiplications in the point operation. Some research involved with formulation of new formula with reduced number of multiplications. Review on Lopez-Dahab and Jacobian coordinates for elliptic curve over binary field are shown in Table 3.

Traditionally, a tripling can be computed as 3P = 2P+P where one doubling (Eq. 8) followed by one general addition (Eq. 5). The cost is (5M+4S)+(13M+4S) = (18M+8S). In this study, a tripling operation is proposed using one doubling (Eq. 8) followed by one mixed addition (Eq. 6). The mixed addition (Al Daoud et al., 2002) is using affine and Lopez-Dahab coordinates since it has better cost than the general addition. Theoretically, the cost for the proposed tripling is given below:

When Eq. 12 is compared with the cost of traditional tripling, the tripling with mixed addition has better cost than the traditional tripling.

The proposed point tripling formula is shown below. Let P = (X₁, Y₁, 1), then, 3P = 2P+P = (X₂, Y₂, Z₂)+(X₁, Y₁, 1) = (X₃, Y₃, Z₃) where:

By treating the field addition cost as negligible, the cost of Eq. 13 is (12M+7S). When compared with Eq. 12, it saved 2M+2S. Also, when compared with traditional tripling, the new formula saved 6M+1S. For NIST curve, the value of a is equal to 1 and the cost of the proposed tripling formula becomes (10M+7S).

Proof of the proposed tripling formula: We need to show that the proposed tripling formula is equivalent with the affine tripling formula. Since there is no existing tripling formula in affine, we need to derive the affine formula first, then we will compare the formula with our tripling formula and they should be equivalent.

Consider P = (x₁, y₁) and Q = (x₂, y₂), where P and Q are affine coordinates in elliptic curve over binary field, Q ≠ -P and Q ≠ P. Then, R = (x₃, y₃) = P+Q has the following Eq. 14 (Cohen and Frey, 2005):

If Q = P, then R = P+P = 2P is called as elliptic curve point doubling has the following Eq. 15 (Cohen and Frey, 2006):

For affine coordinates, to generate an affine tripling formula, we need one doubling (Eq. 15), followed by one addition (Eq. 14). Then, consider P = (x₁, y₁), then using Eq. 15, then 2P = (x₂, y₂) is as the following:

Secondly, using Eq. 14 and 16 compute point tripling as:

Then, the tripling in affine 3P = (x₃, y₃) is given below:

Thirdly, using Eq. 13, we need to prove that:

and:

The processes are shown below:

Use Z₁ = 1, also:

Then:

Use X₃ = x₃. Z₃, then substitute Z₂ = 1 and Z₃ = 1:

Thus, the tripling Eq. 13 in Lopez-Dahab coordinates is the same as the affine tripling formula in Eq. 17. Algorithm 4 for the proposed tripling is shown below:

Propose new scalar multiplication algorithm: In this study, a new scalar multiplication algorithm is proposed namely signed-digit {0,1,3}-NAF scalar multiplication algorithm.

In Algorithm 5, line 7 performs exactly m-1 times. In general, if the Hamming weight of the {0,1,3}-NAF scalar is h₁, then the expected running time of Algorithm 5 is given below:

where, h₁ and m are the Hamming weight and bit length of the signed-digit {0,1,3}-NAF scalar, respectively. Aso, A, D and T are point addition, doubling and tripling, respectively. Equation 20 is proven true when it is tested on 144 data.

In Algorithm 6, line 3 performs exactly l-1 times. In general, if the Hamming weight of the {-1,0,1}-NAF scalar is h₂, then the expected running time of Algorithm 6 is given below:

where, A and D are point addition and point doubling, respectively.

Complexity analysis: Complexity analysis provides running time estimation for performing scalar multiplication for any system specification with any parameters (Sullivan, 2007).

The complexity is based on the number of point operations involved per scalar throughout the execution of the scalar multiplication algorithm.

In scalar multiplication operation, the traditional {-1,0,1}-NAF scalar using addition-subtraction algorithm (Hankerson et al., 2004) and the proposed {0,1,3}-NAF scalar using the proposed signed-digit {0,1,3}-NAF scalar multiplication algorithm. In this study, complexity analysis is carried out to compare performance of the proposed scalar multiplication algorithm with the traditional addition-subtraction algorithm.

For complexity analysis, there same 144 random binary data of 24 bit-length. Cost of the Algorithm 5 and 6 are measured based on the expected cost in Eq. 20 and 21. For average case analysis, only data with h = 12 are selected and displayed in 5. Cost estimation in Table 5 is derived by using the following point operation cost:

A = 9M+5S; D = (5M+4S) and T = (12M+7S)

Also, the following field operation cost of Multiplication (M) and Squaring (S) as used in Edoh (2009):

M = 148.34 microseconds; S = 118.82 microseconds

(p = No. of digit 3; h₁, h₂ = Hamming weight of the proposed {0,1,3}-NAF and {-1,0,1}-NAF, respectively; l₁, l₂ = bit size of the proposed {0,1,3}-NAF and {-1,0,1}-NAF, respectively).

RESULTS

Table 4 provides overall cost estimation for addition-subtraction and the proposed scalar multiplication algorithms. The values of p, Hamming weight and bit length of a scalar k are significant parameters in the performance of the scalar multiplication algorithm. To study the behavior of these parameters, the values of h and l are fixed (i.e., h = 12 and l = 24).

Based on Table 5, the value of p is increasing from 1 to 6, that is from data (a) until data (k). The variation of h₁, h₂, l₁ and l₂ are monitored. For all cases, the values of h₁ are lower than h₂, (i.e., h₁<h₂), indicate that the Hamming weight of the proposed {0,1,3}-NAF scalar is better than the Hamming weight of the traditional {-1,0,1}-NAF. Also, by observation, the values of h₁ are decreasing from data (a) to data (k). For some cases, the values of l₁ are lower than l₂ indicate that the bit length of the proposed {0,1,3}-NAF scalar is better than the bit length of the {-1,0,1}-NAF scalar. By observation, for cases l₁ = l₂, means that there is no changes in bit length after the digit conversion.

From Table 5, the percentage of cost reduction helps to identify significant improvement of the scalar multiplication algorithms. The highest percentage of cost reduction is 16.2, which happens when p = 6. Negative percentage of cost reduction of -1.4, -6 and -6.6 indicate no improvement in the cost of the proposed algorithm. The value p = 1 may be the reason for the negative value in percentage of cost reduction in data (a). Thus, the value h₁ = h₂ and l₁ = l₂ may be the reason for the negative values in the percentage of cost reduction in data (c) and (g).

Cases where, l₁ < l₂ (i.e., l₁ = 23) happens in data (d), (i), (j) and (k). Table 6 shows tracing of Algorithm 5 and 6 using data (d). In Table 6, Algorithm 6 has 24 iterations whereas Algorithm 5 has 22 iterations. The same cases happen for data (i), (j) and (k). In conclusion, reduction of bit length (i.e., l₁ = 23) occurs because 3 is the MSD for the proposed {0,1,3}-NAF scalar.

At the same time, increment of bit-length (i.e., l₂ = 25) occurs in data (d), (i), (j) and (k) for the traditional NAF scalar. Thus, when digit 3 is at the MSD, the proposed scalar multiplication algorithms has less number of iteration than the addition-subtraction algorithm. Thus, the proposed scalar multiplication algorithm achieved higher percentage of cost reduction than in normal cases.

DISCUSSION

Generally, at average case:

Case 1: When p = 1
Case 2: When h₁ = h₂ and l₁ = l₂

From Table 5, parameters h₁ and h₂ affect the cost of the scalar multiplication algorithm. Therefore, the following mathematical analysis is carried out in order to identify the behavior of h₁ and h₂.

From Eq. 20:

where, l₁ = l or l-1 and h₁ = h-p. The case l₁ = l-1 happens in Table 5 for data (d), (i), (j) and (k). For this case, the proposed scalar multiplication algorithm has l-1 number of instructions.

From Eq. 21:

The point operation cost such as mixed Addition (A), Doubling (D) and Tripling (T) are (9M+5S), (5M+4S) and (12M+7S), respectively.

Then, from Eq. 23:

where, l₂ = l or l+1. The case l₂ = l+1 happens in Table 5, for data (d), (e), (f), (i), (j) and (k). For this cases, the addition-subtraction algorithm has l+1 instructions to be executed.

Suppose that:

Cost (Algorithm 5)<Cost (Algorithm 6)

Then, from Eq. 22 and 24:

In some cases, when a binary of length l is recorded into the proposed {0,1,3}-NAF representation, either l is maintained (i.e., l₁ = l) or reduced by 1 bit (i.e., l₁ = l-1). Also, when a binary of length l is recorded into a {-1,0,1}-NAF representation, either l is maintained (i.e., l₂ = l) or increased by 1 bit (i.e., l₂ = l+1). Therefore, we need to consider analysis of the scalar multiplication cost for two cases:

Case 1: l₁<l₂ where l₁ = l-1 and l₂ = l+1

From Eq. 25:

⇒(9h₁+5(l-1)-9h₂ -5(l+1)+12)M<(5h₂+4(l+1) -5h₁-4(l-1)-7)S
⇒(9h₁-9h₂+2)M<(5h₂-5h₁+1)S
⇒(9(h₁-h₂)+2)M<-(5(h₁-h₂)+1)S

Using M = 148.34 and S = 118.82 (Edoh, 2009):

In conclusion, for case l₁< l₂ (i.e., l₁ = l-1 and l₂ = l+1), from Eq. 26, the proposed scalar multiplication algorithm has better cost than the addition-subtraction algorithm when (h₂-h₁)>0.09:

Case 2: l₁ = l₂ = l

From Eq. 25:

⇒(9h₁+5l-9h₂-5l+12)M<(5h₂+4l-5h₁-4l-7)S
⇒(9h₁+5l-9h₂-5l+12)M<(5h₂+4l-5h₁-4l-7)S
⇒(9(h₁-h₂)+12)M<(-5(h₁-h₂)-7)S

Using M = 148.34 and S = 118.82 (Edoh, 2009):

In conclusion, for case l₁ = l₂ = l, from Eq. 27, the proposed scalar multiplication algorithm has better cost than the addition-subtraction algorithm (Hankerson et al., 2004) when (h₂-h₁)>1.35.

From Eq. 26 and 27, for average case, we can conclude that the proposed scalar multiplication algorithm has better cost than the addition-subtraction algorithm for the following cases:

When the proposed tripling is compared with Eq. 12, it saved 14% multiplications and 22% squarings. Also, when compared with traditional tripling, the proposed tripling saved 33% multiplications and 12.5% squaring. For NIST curve, the value of a is equal to 1 and more reduction in scalar multiplication cost is achieved.

CONCLUSION

The digit 3 in the {0,1,3}-NAF scalar need tripling operations in the execution of the proposed scalar multiplication algorithm. At average case, the digit 3 also helps to minimize the Hamming weight of the scalar multiplier. From the result, at average case the proposed signed-digit {0,1,3}-NAF scalar multiplication algorithm is better than the addition-subtraction algorithms except when only one digit 3 in the proposed scalar. Finally, the proposed scalar multiplication algorithm is better than the addition-subtraction algorithms when the Hamming weight and the bit-length of the proposed {0,1,3}-NAF scalar is not equal to the Hamming weight and the bit-length of the {-1,0,1}-NAF scalar.

REFERENCES