# A Novel Elliptic Curve Scalar Multiplication Algorithm against Power Analysis

Authors: Hongming Liu; Yujie Zhou; Nianhao Zhu
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Nowadays, power analysis attacks are becoming more and more sophisticated. Through power analysis attacks, an attacker can obtain sensitive data stored in smart cards or other embedded devices more efficiently than with any other kind of physical attacks. Among power analysis, simple power analysis (SPA) is probably the most effective against elliptic curve cryptosystem, because an attacker can easily distinguish between point addition and point doubling in a single execution of scalar multiplication. To make elliptic curve scalar multiplication secure against SPA attacks, many methods have been proposed using special point representations. In this paper, a simple but efficient SPA-resistant multiscalar multiplication is proposed. The method is to convert the scalar into a nonadjacent form (NAF) representation at first and then constitute it in a new signed digit representation. This new representation is undertaken at a small precomputation cost, as each representation needs just one doubling and 1/2 additions for each bit. In addition, when combined with randomization techniques, the proposed method can also guard against differential power analysis (DPA) attack.


---

## Body

## 1. Introduction

Since being proposed independently by Koblitz [1] and Miller [2] in the mid 1980s, elliptic curve cryptosystem (ECC) has been widely applied in public key cryptography, especially in pairing cryptosystems [3, 4]. This is due to ECC using a much shorter key size than other traditional public key cryptosystems such as RSA to provide a corresponding level of security. For instance, 160 bit ECC provides about the equivalent level of security as 1024 bit RSA [5]. Due to the shorter key length, higher speed, and lower power consumption, ECC has been attractive for wireless and smart card applications which have limited bandwidth and storage resources. The security of ECC is based on the hardness of the discrete logarithm problem (DLP) on an elliptic curve called elliptic curve discrete logarithm problem (ECDLP) [6]. Given a scalar multiplication kP=Q, where k is an integer, and P,  Q are the points on an elliptic curve, according to ECDLP, if k is large enough, then it is unable to calculate k when the values of P and Q are given. When ECC is implemented in the wireless or smart card devices, they are very vulnerable to power analysis attacks [7, 8].In power analysis attacks, which were proposed by Kocher et al. [8], an attacker can obtain the secret key stored inside a device by monitoring the cryptographic device’s power consumption. Generally speaking, simple power analysis (SPA) [7] and differential power analysis (DPA) [8] are the two main types of power analysis attacks. SPA can observe secret information through analysis on a single execution of a cryptographic operation, while DPA may need many executions and to analyze them using a statistical process. As different operations executed by the device consume different amounts of time and power, the different time and power consumptions can be used to determine which operations were performed in what order. In the case of scalar multiplication, it may be possible for an attacker to distinguish which parts of the operation were performed by a point doubling, and which parts were performed by a point addition, although he has no knowledge about the private keys. With this the attacker can  obtain the secret key, from the acquired information, for using as the scalar in the elliptic curve scalar multiplication.In the past decade, various scalar multiplication algorithms that resist SPA or DPA have been proposed, for example, [9–17]. In [10], Coron first generalized a DPA attack to the elliptic curve cryptosystem and introduced double-and-add always algorithm to resist SPA and randomization method to resist DPA. Since then, many countermeasures, which are based on randomization and scalar recoding, have been proposed. Reference [11] proposed the randomized addition-subtraction chains method, and [17] introduced the randomized window method. Lee first proposed a SPA-resistant countermeasure based on multiscalar multiplication [13]. Then, [14–16] not only introduced multi-scalar multiplication to resist SPA, but also used randomization method to resist DPA. However, those methods provide security at the cost of efficiency. In this paper, we propose a novel efficient SPA-resistant multi-scalar multiplication method and combine it with a randomization method to resist DPA.The rest of the paper is organized as follows. Section2 gives a brief introduction to ECC, scalar multiplication, and previous SPA-resistant algorithms. Section 3 describes the proposed scalar multiplication algorithm. Section 4 compares the performance of our strategies with the previous countermeasures. Finally, Section 5 concludes this paper.


## 2. Preliminaries

### 2.1. Elliptic Curve Arithmetic

This subsection presents a brief introduction to ECC. For extended details, the reader can refer to [6, 18]. Let GF(p) be a finite prime field. An elliptic curve E over GF(p) can be defined by the Weierstrass equation:
(1)y2+a1xy+a3y=x3+a2x2+a4x+a6,
where a1,a2,a3,a4,a6∈GF(p). The set of points on an elliptic curve E and the point at infinity (denoted by O) form an Abelian group under a point addition operation. The formula for computing point operation consists of two basic operations: the elliptic curve addition (ECADD) when computing P+Q according to a group addition rule when two points P and Q on the curve are given and P is not equal to Q, and the elliptic doubling (ECDBL) when computing 2P when a point P is given. This needs expensive filed inversions in the computation of point operations when using (x,y) known as affine coordinates to represent the points on the curve E. So, the most efficient implementations adopt representations of the form (X:Y:Z), known as projective coordinates, including standard projective coordinates, Jacobian projective coordinates, Chudnovsky Jacobian coordinates, and Lopez-Dahab projective coordinates [6].


### 2.2. Scalar Multiplication

Scalar multiplication is the basic operation in ECDSA signature [19] and ECDH key agreement [20] protocols. The operation calculates the multiples of a point kP=P+P+⋯+P (k times), where P is a point on curve E and k is an integer scalar. As the most time consuming operation in the previously mentioned protocols, many algorithms have been proposed to improve the efficiency of scalar multiplication during the past decade. Among them, the nonadjacent form (NAF) [21] is the standard one. An NAF of a positive integer k is an expression
(2)kNAF=∑i=0l-1ki2i,
where ki∈{0,±1}, kl-1≠0, and no two consecutive digits of  ki are nonzero. The computation of NAF of a positive integer k is described as in Algorithm 1. Then, it is possible to compute the scalar multiplication using NAF method following Algorithm 2.Algorithm 1:NAF of a positive integer k.
Input: Positive integerk,k = (kl-1,kl-2,…,k0)2
Output:kNAF, kNAF = (kl,kl-1,kl-2,…,k0)NAF
(1)i = 0.
(2) While (k > 0) do
(2.1) if (k is odd) then
(2.2) ki= 2 − (k mod 4);
(2.3) else
(2.4) ki= 0;
(2.5) k = (k-ki)/2;
(2.6) i=i+1;
(3)Return (k).Algorithm 2:Binary NAF method for scalar multiplication.
Input: Positive integerk, P∈E
Output:Q=kP
(1) Use Algorithm1 to compute kNAF.
(2)Q=O.
(3) Fori from l-1 downto 0 do
(3.1) Q = 2Q.
(3.2) If ki = 1 then Q=Q+P;
(3.3) If ki= −1 then Q=Q-P;
(4) Return (Q).Each positivek has a unique NAF. Among all signed binary representations, NAF(k) has the fewest nonzero digits. It is known that the average density of nonzero bits of  NAF is approximately 1/3. This means that scalar multiplication using NAF needs n ECDBL + (n/3) ECADD.


### 2.3. Previous Algorithms

#### 2.3.1. Ciet and Joye’s Algorithm

This algorithm [14] uses the variant of Shamir’s double ladder to compute the multi-scalar multiplication k1P+k2Q. The main difference is to insert a dummy operation in the computation. So, each loop includes one doubling and one addition, and the operation order is DADADADADA in Algorithm 3. Hence, one point doubling and one point addition per bit is needed.Algorithm 3:Ciet and Joye's algorithm.
Input:P,k = (kl-1,kl-2,…,k0)2, S,
d = (dl-1,dl-2,…,d0)2
Output:Q=[k]P+[d]S
(1)R1=P;R2=S;R3=P+S;
(2)j=2dl-1+kl-1;R0=Rj
(3) Fori from l-2 downto 0 do
(3.1) R0=2R0,R1=P;
(3.2) c = !(ki||di), j=2di+ki;
(3.3) Rc=Rc+Rj;
(4) Return (R0).


#### 2.3.2. Lee’s Algorithm

To resist SPA, Lee improved the simultaneous scalar multiplication [21] in [13]. He changed the values of (ki, mi) when (ki, mi) = (0, 0) to construct another adequate digit pair with at least one non-zero digit. Of course, the adjacent pair (ki+1, mi+1) should be modified as well. The transformation rules can be described as in Table 1.Table 1
Transformation rules of Lee's algorithm.
(
k
i
+
1
,
m
i
+
1
)
(
k
i
,
m
i
)
(
k
i
+
1
′
,
m
i
+
1
′
)
(
k
i
′
,
m
i
′
)
(0, 0)
(0, 0)
(0, 1)
(0, −2)
(0, 1)
(0, 0)
(0, 2)
(0,-2)
(1, 0)
(0, 0)
(1, 1)
(0, −2)
(1, 1)
(0, 0)
(1, 0)
(0, 2)After the transformation, the digit pair(ki,mi) cannot be all zero. Therefore, the modified simultaneous scalar multiplication was proposed by Lee to resist SPA; see Algorithm 4. Obviously, the cost of Lee's algorithm is also one point doubling and one point addition per bit.Algorithm 4:Lee's algorithm.
Input:P,k=(kl-1,kl-2,…,k0)2,S,m=(ml-1,ml-2,…,m0)2
Output:Q=[k]P+[m]S
(1)(k,m) is transformed to (k′,m′) as Table 1 rule;
(2) Pre-computation
T[0,1]=S;T[1,0]=P;T[1,1]=P+S;
T[0,2]=2S;T[0,-2]=-2S;
(3)R=T[kl-1′,ml-1′];
(4) Fori from l-2 downto 0 do
(4.1) R=2R;
(4.2) R=R+T[ki′,mi′];
(5 ) Return (R).


#### 2.3.3. Zhang, Chen, Xiao’s Algorithm

This algorithm [16] proposes four scalar multiplication algorithms against power analysis. Those algorithms are all based on the highest-weight binary form (HBF) of the scalars and randomization to resist power analysis. Although those four countermeasures have no dummy operations, the efficiency of them is similar to Ciet and Joye’s algorithm. They also almost need one point doubling and one point addition per bit. One of these algorithms can be seen as follows in Algorithm 5.Algorithm 5:Zhang, Chen, Xiao's algorithm.
Input:P,k = (kl-1,kl-2,…,k0)2
Output:Q=[k]P
(1) Select a randomr;
r=(rl-1,rl-2,…,r0)2;
k′=k-r;
(2) HBF(r,l);
(3) Fori from 0 downto l-1
If  r+ki′=0
(kl-1′,…,ki+1′) +ki′,ki′ = -ki′
(4) Construct a pre-computation tableT
T=O;T[1]=P;T[-1]=-P;
T[2] = 2P; T[-2] = -2P;
(5) Fori from l-1 downto 0 do
(5.1) T=2T;
(5.2) T=T+T[r+ki′];
(6) Return(T).


#### 2.3.4. Liu, Tan, and Dai’s Algorithm

Liu et al. also propose a multi-scalar multiplication to resist SPA in [15]. The difference is that they use a joint sparse form (JSF) to represent a pair of integers and process two or three JSF columns each time. Although the processed column number may be different, the algorithm always performs four point doublings and two point additions in each loop. This means that it is not possible for useful information related to the private key to be obtained by the attacker through SPA.Next,k=213, m=408 are selected as a simple example. The JSF of (213, 408) is
(3)213=(0100-10-1-101)408=(100-1-10-1000).
Then, this algorithm processes the JSF columns as follows:
(4)(010)(0-1)(0-1-1)(01)(100)(-1-1)(0-10)(00).
That is to say, it needs four iterations to complete the whole operation; so, sixteen point doubling and eight point addition operations are required. The theoretical analysis and simulation results show that this algorithm needs 1.384 point doublings and 0.692 point additions per bit.


## 2.1. Elliptic Curve Arithmetic

This subsection presents a brief introduction to ECC. For extended details, the reader can refer to [6, 18]. Let GF(p) be a finite prime field. An elliptic curve E over GF(p) can be defined by the Weierstrass equation:
(1)y2+a1xy+a3y=x3+a2x2+a4x+a6,
where a1,a2,a3,a4,a6∈GF(p). The set of points on an elliptic curve E and the point at infinity (denoted by O) form an Abelian group under a point addition operation. The formula for computing point operation consists of two basic operations: the elliptic curve addition (ECADD) when computing P+Q according to a group addition rule when two points P and Q on the curve are given and P is not equal to Q, and the elliptic doubling (ECDBL) when computing 2P when a point P is given. This needs expensive filed inversions in the computation of point operations when using (x,y) known as affine coordinates to represent the points on the curve E. So, the most efficient implementations adopt representations of the form (X:Y:Z), known as projective coordinates, including standard projective coordinates, Jacobian projective coordinates, Chudnovsky Jacobian coordinates, and Lopez-Dahab projective coordinates [6].


## 2.2. Scalar Multiplication

Scalar multiplication is the basic operation in ECDSA signature [19] and ECDH key agreement [20] protocols. The operation calculates the multiples of a point kP=P+P+⋯+P (k times), where P is a point on curve E and k is an integer scalar. As the most time consuming operation in the previously mentioned protocols, many algorithms have been proposed to improve the efficiency of scalar multiplication during the past decade. Among them, the nonadjacent form (NAF) [21] is the standard one. An NAF of a positive integer k is an expression
(2)kNAF=∑i=0l-1ki2i,
where ki∈{0,±1}, kl-1≠0, and no two consecutive digits of  ki are nonzero. The computation of NAF of a positive integer k is described as in Algorithm 1. Then, it is possible to compute the scalar multiplication using NAF method following Algorithm 2.Algorithm 1:NAF of a positive integer k.
Input: Positive integerk,k = (kl-1,kl-2,…,k0)2
Output:kNAF, kNAF = (kl,kl-1,kl-2,…,k0)NAF
(1)i = 0.
(2) While (k > 0) do
(2.1) if (k is odd) then
(2.2) ki= 2 − (k mod 4);
(2.3) else
(2.4) ki= 0;
(2.5) k = (k-ki)/2;
(2.6) i=i+1;
(3)Return (k).Algorithm 2:Binary NAF method for scalar multiplication.
Input: Positive integerk, P∈E
Output:Q=kP
(1) Use Algorithm1 to compute kNAF.
(2)Q=O.
(3) Fori from l-1 downto 0 do
(3.1) Q = 2Q.
(3.2) If ki = 1 then Q=Q+P;
(3.3) If ki= −1 then Q=Q-P;
(4) Return (Q).Each positivek has a unique NAF. Among all signed binary representations, NAF(k) has the fewest nonzero digits. It is known that the average density of nonzero bits of  NAF is approximately 1/3. This means that scalar multiplication using NAF needs n ECDBL + (n/3) ECADD.


## 2.3. Previous Algorithms

### 2.3.1. Ciet and Joye’s Algorithm

This algorithm [14] uses the variant of Shamir’s double ladder to compute the multi-scalar multiplication k1P+k2Q. The main difference is to insert a dummy operation in the computation. So, each loop includes one doubling and one addition, and the operation order is DADADADADA in Algorithm 3. Hence, one point doubling and one point addition per bit is needed.Algorithm 3:Ciet and Joye's algorithm.
Input:P,k = (kl-1,kl-2,…,k0)2, S,
d = (dl-1,dl-2,…,d0)2
Output:Q=[k]P+[d]S
(1)R1=P;R2=S;R3=P+S;
(2)j=2dl-1+kl-1;R0=Rj
(3) Fori from l-2 downto 0 do
(3.1) R0=2R0,R1=P;
(3.2) c = !(ki||di), j=2di+ki;
(3.3) Rc=Rc+Rj;
(4) Return (R0).


### 2.3.2. Lee’s Algorithm

To resist SPA, Lee improved the simultaneous scalar multiplication [21] in [13]. He changed the values of (ki, mi) when (ki, mi) = (0, 0) to construct another adequate digit pair with at least one non-zero digit. Of course, the adjacent pair (ki+1, mi+1) should be modified as well. The transformation rules can be described as in Table 1.Table 1
Transformation rules of Lee's algorithm.
(
k
i
+
1
,
m
i
+
1
)
(
k
i
,
m
i
)
(
k
i
+
1
′
,
m
i
+
1
′
)
(
k
i
′
,
m
i
′
)
(0, 0)
(0, 0)
(0, 1)
(0, −2)
(0, 1)
(0, 0)
(0, 2)
(0,-2)
(1, 0)
(0, 0)
(1, 1)
(0, −2)
(1, 1)
(0, 0)
(1, 0)
(0, 2)After the transformation, the digit pair(ki,mi) cannot be all zero. Therefore, the modified simultaneous scalar multiplication was proposed by Lee to resist SPA; see Algorithm 4. Obviously, the cost of Lee's algorithm is also one point doubling and one point addition per bit.Algorithm 4:Lee's algorithm.
Input:P,k=(kl-1,kl-2,…,k0)2,S,m=(ml-1,ml-2,…,m0)2
Output:Q=[k]P+[m]S
(1)(k,m) is transformed to (k′,m′) as Table 1 rule;
(2) Pre-computation
T[0,1]=S;T[1,0]=P;T[1,1]=P+S;
T[0,2]=2S;T[0,-2]=-2S;
(3)R=T[kl-1′,ml-1′];
(4) Fori from l-2 downto 0 do
(4.1) R=2R;
(4.2) R=R+T[ki′,mi′];
(5 ) Return (R).


### 2.3.3. Zhang, Chen, Xiao’s Algorithm

This algorithm [16] proposes four scalar multiplication algorithms against power analysis. Those algorithms are all based on the highest-weight binary form (HBF) of the scalars and randomization to resist power analysis. Although those four countermeasures have no dummy operations, the efficiency of them is similar to Ciet and Joye’s algorithm. They also almost need one point doubling and one point addition per bit. One of these algorithms can be seen as follows in Algorithm 5.Algorithm 5:Zhang, Chen, Xiao's algorithm.
Input:P,k = (kl-1,kl-2,…,k0)2
Output:Q=[k]P
(1) Select a randomr;
r=(rl-1,rl-2,…,r0)2;
k′=k-r;
(2) HBF(r,l);
(3) Fori from 0 downto l-1
If  r+ki′=0
(kl-1′,…,ki+1′) +ki′,ki′ = -ki′
(4) Construct a pre-computation tableT
T=O;T[1]=P;T[-1]=-P;
T[2] = 2P; T[-2] = -2P;
(5) Fori from l-1 downto 0 do
(5.1) T=2T;
(5.2) T=T+T[r+ki′];
(6) Return(T).


### 2.3.4. Liu, Tan, and Dai’s Algorithm

Liu et al. also propose a multi-scalar multiplication to resist SPA in [15]. The difference is that they use a joint sparse form (JSF) to represent a pair of integers and process two or three JSF columns each time. Although the processed column number may be different, the algorithm always performs four point doublings and two point additions in each loop. This means that it is not possible for useful information related to the private key to be obtained by the attacker through SPA.Next,k=213, m=408 are selected as a simple example. The JSF of (213, 408) is
(3)213=(0100-10-1-101)408=(100-1-10-1000).
Then, this algorithm processes the JSF columns as follows:
(4)(010)(0-1)(0-1-1)(01)(100)(-1-1)(0-10)(00).
That is to say, it needs four iterations to complete the whole operation; so, sixteen point doubling and eight point addition operations are required. The theoretical analysis and simulation results show that this algorithm needs 1.384 point doublings and 0.692 point additions per bit.


## 2.3.1. Ciet and Joye’s Algorithm

This algorithm [14] uses the variant of Shamir’s double ladder to compute the multi-scalar multiplication k1P+k2Q. The main difference is to insert a dummy operation in the computation. So, each loop includes one doubling and one addition, and the operation order is DADADADADA in Algorithm 3. Hence, one point doubling and one point addition per bit is needed.Algorithm 3:Ciet and Joye's algorithm.
Input:P,k = (kl-1,kl-2,…,k0)2, S,
d = (dl-1,dl-2,…,d0)2
Output:Q=[k]P+[d]S
(1)R1=P;R2=S;R3=P+S;
(2)j=2dl-1+kl-1;R0=Rj
(3) Fori from l-2 downto 0 do
(3.1) R0=2R0,R1=P;
(3.2) c = !(ki||di), j=2di+ki;
(3.3) Rc=Rc+Rj;
(4) Return (R0).


## 2.3.2. Lee’s Algorithm

To resist SPA, Lee improved the simultaneous scalar multiplication [21] in [13]. He changed the values of (ki, mi) when (ki, mi) = (0, 0) to construct another adequate digit pair with at least one non-zero digit. Of course, the adjacent pair (ki+1, mi+1) should be modified as well. The transformation rules can be described as in Table 1.Table 1
Transformation rules of Lee's algorithm.
(
k
i
+
1
,
m
i
+
1
)
(
k
i
,
m
i
)
(
k
i
+
1
′
,
m
i
+
1
′
)
(
k
i
′
,
m
i
′
)
(0, 0)
(0, 0)
(0, 1)
(0, −2)
(0, 1)
(0, 0)
(0, 2)
(0,-2)
(1, 0)
(0, 0)
(1, 1)
(0, −2)
(1, 1)
(0, 0)
(1, 0)
(0, 2)After the transformation, the digit pair(ki,mi) cannot be all zero. Therefore, the modified simultaneous scalar multiplication was proposed by Lee to resist SPA; see Algorithm 4. Obviously, the cost of Lee's algorithm is also one point doubling and one point addition per bit.Algorithm 4:Lee's algorithm.
Input:P,k=(kl-1,kl-2,…,k0)2,S,m=(ml-1,ml-2,…,m0)2
Output:Q=[k]P+[m]S
(1)(k,m) is transformed to (k′,m′) as Table 1 rule;
(2) Pre-computation
T[0,1]=S;T[1,0]=P;T[1,1]=P+S;
T[0,2]=2S;T[0,-2]=-2S;
(3)R=T[kl-1′,ml-1′];
(4) Fori from l-2 downto 0 do
(4.1) R=2R;
(4.2) R=R+T[ki′,mi′];
(5 ) Return (R).


## 2.3.3. Zhang, Chen, Xiao’s Algorithm

This algorithm [16] proposes four scalar multiplication algorithms against power analysis. Those algorithms are all based on the highest-weight binary form (HBF) of the scalars and randomization to resist power analysis. Although those four countermeasures have no dummy operations, the efficiency of them is similar to Ciet and Joye’s algorithm. They also almost need one point doubling and one point addition per bit. One of these algorithms can be seen as follows in Algorithm 5.Algorithm 5:Zhang, Chen, Xiao's algorithm.
Input:P,k = (kl-1,kl-2,…,k0)2
Output:Q=[k]P
(1) Select a randomr;
r=(rl-1,rl-2,…,r0)2;
k′=k-r;
(2) HBF(r,l);
(3) Fori from 0 downto l-1
If  r+ki′=0
(kl-1′,…,ki+1′) +ki′,ki′ = -ki′
(4) Construct a pre-computation tableT
T=O;T[1]=P;T[-1]=-P;
T[2] = 2P; T[-2] = -2P;
(5) Fori from l-1 downto 0 do
(5.1) T=2T;
(5.2) T=T+T[r+ki′];
(6) Return(T).


## 2.3.4. Liu, Tan, and Dai’s Algorithm

Liu et al. also propose a multi-scalar multiplication to resist SPA in [15]. The difference is that they use a joint sparse form (JSF) to represent a pair of integers and process two or three JSF columns each time. Although the processed column number may be different, the algorithm always performs four point doublings and two point additions in each loop. This means that it is not possible for useful information related to the private key to be obtained by the attacker through SPA.Next,k=213, m=408 are selected as a simple example. The JSF of (213, 408) is
(3)213=(0100-10-1-101)408=(100-1-10-1000).
Then, this algorithm processes the JSF columns as follows:
(4)(010)(0-1)(0-1-1)(01)(100)(-1-1)(0-10)(00).
That is to say, it needs four iterations to complete the whole operation; so, sixteen point doubling and eight point addition operations are required. The theoretical analysis and simulation results show that this algorithm needs 1.384 point doublings and 0.692 point additions per bit.


## 3. The New Algorithm

Based on the algorithms mentioned earlier, a simple but efficient scalar multiplication algorithm is proposed to resist known power analysis attacks in this section. The method first transforms the NAF of the multi-scalar(k,m) then combines it with the window method and modifies the value of the digit pair with all zero digits; so, the new algorithm can be obtained.


### 3.1. Scalar Representation

In a scalar multiplication, it can be seen that each bit requires at least a point doubling, while the number of point addition varies in different algorithms. Therefore, the best way to improve the efficiency of the scalar multiplication is to reduce the number of point addition. In this approach, a window method with the NAF form is used to reduce the number of point addition.First, the window method with the NAF form for a single scalark is described. Let w be the window size, SHW(w) the maximum Hamming weight, and SPN(w) the point number of the precomputation table in each window. The NAF of a scalar k is denoted by kNAF, and generally it can be represented as (2), where l is the bit length of the NAF of k. When using the window method, it can be represented as ∑i=0m-1ki′2i, where m=l/w and w bit k′∈Sw, in which Sw is the set of all possible w-bit parts of the NAF integers. Consider
(5)SHW(w)={w2(wiseven),⌊w2⌋+1(wisodd),(6)SPN(w)={2(w-1)+2(w-3)+⋯+21(wiseven),2(w-1)+2(w-3)+⋯+20(wisodd).
In Table 2, we only list the values of SHW(w) and SPN(w) for w from 2 to 6, but from (6), it can be seen that SPN(w) rises by times with the increase of w.Table 2
Values of SHW(w) and SPN(w) for different window sizes.
w
2
3
4
5
6
SHW(w)
1
2
2
3
3
SPN(w)
2
5
10
21
42Next, the window method with the NAF form for multi-scalar(k,m) is introduced, where w is the window size, MHW(w) is the maximum Hamming weight, and MPN(w) is the point number of pre-computation table in each window (Table 3). Now, in each window, there are two scalars; so, MHW(w) is double SHW(w), but MPN(w) is much larger than SPN(w). MPN(w) is the combination of two numbers (SPNk(w), SPNm(w)). Consider
(7)MHW(w)={w2(wiseven),⌊w2⌋+1(wisodd),(8)MPN(w)=SPNk(w)+SPNm(w)+SPNk(w)*SPNm(w)*2.
From (8), it can be seen that MPN(w) rises exponentially with an increase of w. So, in this paper, w=2 was selected as the window size.Table 3
Values of MHW(w) and MPN(w) for different window sizes.
w
2
3
4
5
6
MHW(w)
2
4
4
6
6
MPN(w)
12
60
220
924
3612When(ki+1,ki)=(0,0) and (mi+1,mi)=(0,0), no point addition is performed. Hence, an attacker can determine this case through SPA. To assist SPA, (ki+1,ki)=(0,0) and (mi+1,mi)=(0,0) should be converted, so that a real point addition happens. This is to say that (ki+1,ki)=(0,0) and (mi+1,mi)=(0,0) are converted to another digit pair with at least one non-zero digit. In this paper, we select to transform (mi+1,mi)=(0,0). Of course, the adjacent pair (mi+3,mi+2) should be considered as well. According to the NAF coding rule, there are five possible cases related to the digit pair (mi+3,mi+2). The transformation rules can be described as in Table 4.Table 4
Transformation rules of new algorithm.
(
m
i
+
3
,
m
i
+
2
)
(
m
i
+
1
,
m
i
)
(
m
i
+
3
′
,
m
i
+
2
′
)
(
m
i
+
1
′
,
m
i
′
)
(0, 0)
(0, 0)
(0, 1)
(−2, 0)
(0, −1)
(0, 0)
(−1, 0)
(2, 0)
(0, 1)
(0, 0)
(1, 0)
(−2, 0)
(−1, 0)
(0, 0)
(0, −1)
(−2, 0)
(1, 0)
(0, 0)
(0, 1)
(2, 0)After the transformation, the digit pair (mi+1′,mi′) adds two more cases, but the pre-computation table only adds one more point due to the different symbol between the two cases.


### 3.2. Proposed New Multiscalar Multiplication Algorithm

Now, the new algorithm to calculate[k]P+[m]S based on the new representation mentioned earlier can be described. The algorithm has a uniform doubling and adding operation, but no dummy operation.From Algorithm6, it can be found that two doublings and one addition are performed in each window. It is assumed that the power consumption of subtraction is the same as the addition. There are fifteen points in the pre-computation table.Algorithm 6:New multi-scalar multiplication algorithm.
Input:P,k,S,m
Output:Q=[k]P+[m]S
(1) Compute the NAF form of (k,m);
(2) Add leading 0's in (k,m) so that the number of bits in
(k,m) is multiple of 2, k=(kl-1,kl-2,…,k0)NAF,
m=(ml-1,ml-2,…,m0)NAF;
(3) i=0;
(4) While (i<(l-2)) do
(4.1) if ((ki+1,ki)=(0,0) and (mi+1,mi) = (0, 0)) then
(4.2) if ((mi+3,mi+2)=(0,0)) then
(4.3)  set (mi+3,mi+2)=(0,1) and (mi+1,mi)
=
(
-
2
,
0
);
(4.4) else if((mi+3,mi+2)=(0,-1)) then
(4.5)  set (mi+3,mi+2)=(-1,0)and(mi+1,mi)
=
(
2
,
0
);
(4.6) else if ((mi+3,mi+2)=(0,1)) then
(4.7)  set (mi+3,mi+2)=(1,0) and (mi+1,mi)
=
(
-
2
,
0
);
(4.8) else if ((mi+3,mi+2)=(-1,0) then
(4.9)  set (mi+3,mi+2)=(0,-1) and (mi+1,mi)
=
(
-
2
,
0
);
(4.10) else
(4.11)  set (mi+3,mi+2)=(0,1) and (mi+1,mi)
=
(
2
,
0
);
(4.12) else
(4.13) i=i+2;
(5) Pre-computation
T[0,1]=S;T[0,2]=2S;T[0,4]=4S;T[1,0]=P
;T[2,0]=2P;T[1,1]=P+S;T[1,2]=P+2S;
T[1,-1]=P-S;T[1,-2]=P-2S;T[2,1]=2P+S;
T
[
2,2
]
=
2
P
+
2
S
;
T
[
2
,
-
1
]
=
2
P
-
S;
T[2,-2]=2P-2S;
(6) R=T[(kl-1,kl-2),(ml-1,ml-2)];
(7) For i from l-2 downto 0 i=i-2 do
(7.1) R=2R;
(7.2) R=2R;
(7.3) if ((ki-1,ki-2)<0) then
(7.4) R=R-T[-(ki-1,ki-2),-(mi-1,mi-2)];
(7.5) else if ((ki-1,ki-2)==0) then
(7.6)  if ((mi-1,mi-2)<0) then
(7.7 )  R=R-T[(ki-1,ki-2),-(mi-1,mi-2)];
(7.8) else
(7.9)  R=R+T[(ki-1,ki-2),(mi-1,mi-2)];
(7.10) else
(7.11) R=R+T[(ki-1,ki-2),(mi-1,mi-2)];
(8) Return (R).Next, a simple example that shows how Algorithm6 works is described, and the NAF of (209, 416) is
(9)209=(010-1010001)416=(10-10100000).After transformation according to Table4, the new representation of (209, 416) is
(10)209=(010-1010001)416=(10-10012000).
Then, the process of Algorithm 6 computing 209P+416S is illustrated in Table 5.Table 5
Example of Algorithm6.
i
(
k
i
-
1
,
k
i
-
2
) (mi-1,mi-2)
Operation
R
9
(0, 1)(1, 0)
R
=
T
[
1,2
]
P + 2S
7
(0, −1)(−1, 0)
R
=
2
R; R=2R; R=R-T[1,2]
3P + 6S
5
(0, 1)(0, 1)
R
=
2
R; R=2R; R=R+T[1,1]
13P + 25S
3
(0, 0)(2, 0)
R
=
2
R; R=2R; R=R+T[0,4]
52P + 104S
1
(0, 1)(0, 0)
R
=
2
R; R=2R; R=R+T[1,0]
209P+416S


### 3.3. Proposed DPA-Resistant Scalar Multiplication Algorithm

Among the various DPA countermeasures [22], random key splitting is the most common method to resist DPA. The scalar k can be split in at least two different ways; one is k=(k-r)+r, and the other is k=⌊k/r⌋r+(kmodr), where r is random and the length of r is the same of k. In this paper, the first way k=k1+k2 was chosen, where k1=k-r,  k2=r. It can be observed that this method is the same as multi-scalar approach. Then, a similar method as in Algorithm 6 can be used to compute the scalar multiplication. The difference is that the point S is equal to P. Of course, the transformation rule and pre-computation table are also different. To assist an SPA, k1 and k2 when (k1i+1,k1i)+(k2i+1,k2i)=(0,0) should be converted, so that a real point addition happens. Algorithm 7 describes this in detail.Algorithm 7:DPA-resistant scalar multiplication algorithm.
Input:P, k
Output:Q = [k]P
(1) Select a random r, k1=k-r,k2=r;
(2) Compute the NAF form of (k1,k2);
(3) Add leading 0's in (k1,k2) so that the number of bits in
(
k
1
,
k
2
) is multiple of 2, k1=(k1l-1,k1l-2,…,k10)NAF,
k
2
=
(
k
2
l
-
1
,
k
2
l
-
2
,
…
,
k
2
0
)
NAF;
(4) i=0;
(5) While (i<(l-2)) do
(5.1) set c=(k1i+1,k1i)+(k2i+1,k2i);
(5.2) if (c=0) then
(5.3) if ((k2i+3,k2i+2)>0) then
(5.4)  set (k2i+3,k2i+2)-=(0,1) and (k2i+1,k2i)
=
(
-
2
,
0
);
(5.5)  else
(5.6)  set (k2i+3,k2i+2)+=(0,1) and (k2i+1,k2i)
=
(
2
,
0
);
(5.7) else
(5.8) i=i+2;
(6) Pre-computation
T
[
1
]
=
P
;
T
[
2
]
=
2
P
;
T
[
3
]
=
3
P
;
T
[
4
]
=
4
P;
(7) if ((k1l-1,k1l-2)+(k2l-1,k2l-2)=0) then
R=O;
else
R
=
T
[
(
k
1
l
-
1
,
k
1
l
-
2
)
+
(
k
2
l
-
1
,
k
2
l
-
2
)
];
(8) For i from l-2 downto 0 i=i-2 do
(8.1) c=(k1i-1,k1i-2)+(k2i-1,k2i-2);
(8.2) R=2R;
(8.3) R=2R;
(8.4) if (c<0) then
(8.5) R=R-T[-c];
(8.6) else
(8.7) R=R+T[c];
(9) Return (R).It can be seen that there are only four points in the pre-computation table for Algorithm7, but the program sequence is also DDA. Therefore, due to the uniform operation sequence, it can resist SPA, and to ensure that there is no correlation between two times, a random r was inserted. Of course, the attacker cannot obtain any information through DPA.


## 3.1. Scalar Representation

In a scalar multiplication, it can be seen that each bit requires at least a point doubling, while the number of point addition varies in different algorithms. Therefore, the best way to improve the efficiency of the scalar multiplication is to reduce the number of point addition. In this approach, a window method with the NAF form is used to reduce the number of point addition.First, the window method with the NAF form for a single scalark is described. Let w be the window size, SHW(w) the maximum Hamming weight, and SPN(w) the point number of the precomputation table in each window. The NAF of a scalar k is denoted by kNAF, and generally it can be represented as (2), where l is the bit length of the NAF of k. When using the window method, it can be represented as ∑i=0m-1ki′2i, where m=l/w and w bit k′∈Sw, in which Sw is the set of all possible w-bit parts of the NAF integers. Consider
(5)SHW(w)={w2(wiseven),⌊w2⌋+1(wisodd),(6)SPN(w)={2(w-1)+2(w-3)+⋯+21(wiseven),2(w-1)+2(w-3)+⋯+20(wisodd).
In Table 2, we only list the values of SHW(w) and SPN(w) for w from 2 to 6, but from (6), it can be seen that SPN(w) rises by times with the increase of w.Table 2
Values of SHW(w) and SPN(w) for different window sizes.
w
2
3
4
5
6
SHW(w)
1
2
2
3
3
SPN(w)
2
5
10
21
42Next, the window method with the NAF form for multi-scalar(k,m) is introduced, where w is the window size, MHW(w) is the maximum Hamming weight, and MPN(w) is the point number of pre-computation table in each window (Table 3). Now, in each window, there are two scalars; so, MHW(w) is double SHW(w), but MPN(w) is much larger than SPN(w). MPN(w) is the combination of two numbers (SPNk(w), SPNm(w)). Consider
(7)MHW(w)={w2(wiseven),⌊w2⌋+1(wisodd),(8)MPN(w)=SPNk(w)+SPNm(w)+SPNk(w)*SPNm(w)*2.
From (8), it can be seen that MPN(w) rises exponentially with an increase of w. So, in this paper, w=2 was selected as the window size.Table 3
Values of MHW(w) and MPN(w) for different window sizes.
w
2
3
4
5
6
MHW(w)
2
4
4
6
6
MPN(w)
12
60
220
924
3612When(ki+1,ki)=(0,0) and (mi+1,mi)=(0,0), no point addition is performed. Hence, an attacker can determine this case through SPA. To assist SPA, (ki+1,ki)=(0,0) and (mi+1,mi)=(0,0) should be converted, so that a real point addition happens. This is to say that (ki+1,ki)=(0,0) and (mi+1,mi)=(0,0) are converted to another digit pair with at least one non-zero digit. In this paper, we select to transform (mi+1,mi)=(0,0). Of course, the adjacent pair (mi+3,mi+2) should be considered as well. According to the NAF coding rule, there are five possible cases related to the digit pair (mi+3,mi+2). The transformation rules can be described as in Table 4.Table 4
Transformation rules of new algorithm.
(
m
i
+
3
,
m
i
+
2
)
(
m
i
+
1
,
m
i
)
(
m
i
+
3
′
,
m
i
+
2
′
)
(
m
i
+
1
′
,
m
i
′
)
(0, 0)
(0, 0)
(0, 1)
(−2, 0)
(0, −1)
(0, 0)
(−1, 0)
(2, 0)
(0, 1)
(0, 0)
(1, 0)
(−2, 0)
(−1, 0)
(0, 0)
(0, −1)
(−2, 0)
(1, 0)
(0, 0)
(0, 1)
(2, 0)After the transformation, the digit pair (mi+1′,mi′) adds two more cases, but the pre-computation table only adds one more point due to the different symbol between the two cases.


## 3.2. Proposed New Multiscalar Multiplication Algorithm

Now, the new algorithm to calculate[k]P+[m]S based on the new representation mentioned earlier can be described. The algorithm has a uniform doubling and adding operation, but no dummy operation.From Algorithm6, it can be found that two doublings and one addition are performed in each window. It is assumed that the power consumption of subtraction is the same as the addition. There are fifteen points in the pre-computation table.Algorithm 6:New multi-scalar multiplication algorithm.
Input:P,k,S,m
Output:Q=[k]P+[m]S
(1) Compute the NAF form of (k,m);
(2) Add leading 0's in (k,m) so that the number of bits in
(k,m) is multiple of 2, k=(kl-1,kl-2,…,k0)NAF,
m=(ml-1,ml-2,…,m0)NAF;
(3) i=0;
(4) While (i<(l-2)) do
(4.1) if ((ki+1,ki)=(0,0) and (mi+1,mi) = (0, 0)) then
(4.2) if ((mi+3,mi+2)=(0,0)) then
(4.3)  set (mi+3,mi+2)=(0,1) and (mi+1,mi)
=
(
-
2
,
0
);
(4.4) else if((mi+3,mi+2)=(0,-1)) then
(4.5)  set (mi+3,mi+2)=(-1,0)and(mi+1,mi)
=
(
2
,
0
);
(4.6) else if ((mi+3,mi+2)=(0,1)) then
(4.7)  set (mi+3,mi+2)=(1,0) and (mi+1,mi)
=
(
-
2
,
0
);
(4.8) else if ((mi+3,mi+2)=(-1,0) then
(4.9)  set (mi+3,mi+2)=(0,-1) and (mi+1,mi)
=
(
-
2
,
0
);
(4.10) else
(4.11)  set (mi+3,mi+2)=(0,1) and (mi+1,mi)
=
(
2
,
0
);
(4.12) else
(4.13) i=i+2;
(5) Pre-computation
T[0,1]=S;T[0,2]=2S;T[0,4]=4S;T[1,0]=P
;T[2,0]=2P;T[1,1]=P+S;T[1,2]=P+2S;
T[1,-1]=P-S;T[1,-2]=P-2S;T[2,1]=2P+S;
T
[
2,2
]
=
2
P
+
2
S
;
T
[
2
,
-
1
]
=
2
P
-
S;
T[2,-2]=2P-2S;
(6) R=T[(kl-1,kl-2),(ml-1,ml-2)];
(7) For i from l-2 downto 0 i=i-2 do
(7.1) R=2R;
(7.2) R=2R;
(7.3) if ((ki-1,ki-2)<0) then
(7.4) R=R-T[-(ki-1,ki-2),-(mi-1,mi-2)];
(7.5) else if ((ki-1,ki-2)==0) then
(7.6)  if ((mi-1,mi-2)<0) then
(7.7 )  R=R-T[(ki-1,ki-2),-(mi-1,mi-2)];
(7.8) else
(7.9)  R=R+T[(ki-1,ki-2),(mi-1,mi-2)];
(7.10) else
(7.11) R=R+T[(ki-1,ki-2),(mi-1,mi-2)];
(8) Return (R).Next, a simple example that shows how Algorithm6 works is described, and the NAF of (209, 416) is
(9)209=(010-1010001)416=(10-10100000).After transformation according to Table4, the new representation of (209, 416) is
(10)209=(010-1010001)416=(10-10012000).
Then, the process of Algorithm 6 computing 209P+416S is illustrated in Table 5.Table 5
Example of Algorithm6.
i
(
k
i
-
1
,
k
i
-
2
) (mi-1,mi-2)
Operation
R
9
(0, 1)(1, 0)
R
=
T
[
1,2
]
P + 2S
7
(0, −1)(−1, 0)
R
=
2
R; R=2R; R=R-T[1,2]
3P + 6S
5
(0, 1)(0, 1)
R
=
2
R; R=2R; R=R+T[1,1]
13P + 25S
3
(0, 0)(2, 0)
R
=
2
R; R=2R; R=R+T[0,4]
52P + 104S
1
(0, 1)(0, 0)
R
=
2
R; R=2R; R=R+T[1,0]
209P+416S


## 3.3. Proposed DPA-Resistant Scalar Multiplication Algorithm

Among the various DPA countermeasures [22], random key splitting is the most common method to resist DPA. The scalar k can be split in at least two different ways; one is k=(k-r)+r, and the other is k=⌊k/r⌋r+(kmodr), where r is random and the length of r is the same of k. In this paper, the first way k=k1+k2 was chosen, where k1=k-r,  k2=r. It can be observed that this method is the same as multi-scalar approach. Then, a similar method as in Algorithm 6 can be used to compute the scalar multiplication. The difference is that the point S is equal to P. Of course, the transformation rule and pre-computation table are also different. To assist an SPA, k1 and k2 when (k1i+1,k1i)+(k2i+1,k2i)=(0,0) should be converted, so that a real point addition happens. Algorithm 7 describes this in detail.Algorithm 7:DPA-resistant scalar multiplication algorithm.
Input:P, k
Output:Q = [k]P
(1) Select a random r, k1=k-r,k2=r;
(2) Compute the NAF form of (k1,k2);
(3) Add leading 0's in (k1,k2) so that the number of bits in
(
k
1
,
k
2
) is multiple of 2, k1=(k1l-1,k1l-2,…,k10)NAF,
k
2
=
(
k
2
l
-
1
,
k
2
l
-
2
,
…
,
k
2
0
)
NAF;
(4) i=0;
(5) While (i<(l-2)) do
(5.1) set c=(k1i+1,k1i)+(k2i+1,k2i);
(5.2) if (c=0) then
(5.3) if ((k2i+3,k2i+2)>0) then
(5.4)  set (k2i+3,k2i+2)-=(0,1) and (k2i+1,k2i)
=
(
-
2
,
0
);
(5.5)  else
(5.6)  set (k2i+3,k2i+2)+=(0,1) and (k2i+1,k2i)
=
(
2
,
0
);
(5.7) else
(5.8) i=i+2;
(6) Pre-computation
T
[
1
]
=
P
;
T
[
2
]
=
2
P
;
T
[
3
]
=
3
P
;
T
[
4
]
=
4
P;
(7) if ((k1l-1,k1l-2)+(k2l-1,k2l-2)=0) then
R=O;
else
R
=
T
[
(
k
1
l
-
1
,
k
1
l
-
2
)
+
(
k
2
l
-
1
,
k
2
l
-
2
)
];
(8) For i from l-2 downto 0 i=i-2 do
(8.1) c=(k1i-1,k1i-2)+(k2i-1,k2i-2);
(8.2) R=2R;
(8.3) R=2R;
(8.4) if (c<0) then
(8.5) R=R-T[-c];
(8.6) else
(8.7) R=R+T[c];
(9) Return (R).It can be seen that there are only four points in the pre-computation table for Algorithm7, but the program sequence is also DDA. Therefore, due to the uniform operation sequence, it can resist SPA, and to ensure that there is no correlation between two times, a random r was inserted. Of course, the attacker cannot obtain any information through DPA.


## 4. Performance Comparison

In this section, the performance of Algorithm7 is analyzed and compared with previous algorithms. In Algorithm 7, each loop processes two bits and has two point doubling and one point addition. Each bit needs one point doubling and 1/2 point addition. In order to show the performance of Algorithm 7, a comparison with previous methods is listed in Table 6.Table 6
Performance comparison of algorithms.
Point number inPre-Computationtable
Computations per bit
Doublings
Additions
Algorithm in [14]
3
1
1
Algorithm in [13]
5
1
1
Algorithm in [16]
5
1
1
Algorithm in [15]
5
1.384
0.692
Algorithm7
4
1
0.5According to [23], one projective elliptic doubling in prime case needs 4S (S denotes module square) and 4M (M denotes module multiplication), and one projective elliptic addition on prime case needs 4S and 12M. We resume S≈0.8M [24]. Then, algorithm in [13, 14, 16] needs 8S+16M≈22.4M per bit, and algorithm in [15] needs about 20.4M, while Algorithm 7 only needs 6S+10M≈14.8M per bit. Hence, it Algorithm 7 can improve performance by at least 25% compared with previous algorithms, and, sacrifices a small amount of memory to store pre-computation points.


## 5. Conclusion

In this paper, a simple but efficient elliptic scalar multiplication against power analysis attacks has been presented. First, we analyze previous algorithms which can resist SPA or DPA. Then, we present the new multi-scalar multiplication to endure SPA. This algorithm is based on NAF and processes two columns each loop. When computing scalar multiplicationkP, we adopt a random number r to split scalar k and combine it with the multi-scalar multiplication. So, the new DPA-resistant scalar multiplication algorithm is proposed in this work. The proposed DPA-resistant scalar multiplication algorithm not only can resist SPA and DPA, but also provides good performance at a cost of only a few storage spaces.



---

*Source: 862508-2013-04-04.xml*