*This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year.*

*In this week, we describe the NAF scalar multiplication algorithm.*

*The NAF scalar multiplication algorithm is an enhanced form of scalar multiplication, in which the use of Non-Adjacent Form (NAF) representation decreases the expected running time of the algorithm. In more detail:*

*Let k be a positive integer and P a point on an elliptic curve E over the field $\mathbb{F}_{q}$. The operation that computes the multiplication $Q = k\cdot P$ is known as the elliptic curve scalar multiplication (or point multiplication) and dominates the execution time of elliptic curve cryptographic schemes.*

*One of the most basic methods to compute a scalar multiplication is based on a double-and-add variant of Horner's rule, known as the binary method. As the name suggests, the two most prominent building blocks of this method are the*

**point doubling and point addition**primitives. More particularly, to calculate $k\cdot P$, integer k is represented as $k=k_{n-1}2^{n-1}+k_{n-2}2^{n-2}+ \cdots +k_{1}+k_{0}$ , where $k_{i} \in \{0,1\}$, $i= 0,1,2...,n-1$ (binary representation form). The following algorithms form the additive versions of the basic repeated-square-and-multiply methods for exponentiation [1,2].
INPUT: k = (kt−1,..., k1, k0)2, P ∈ E(

OUTPUT: k $\cdot$ P.

Q←$\infty$.

For i from 0 to t−1 do

If ki = 1 then Q←Q+P.

P←2P.

Return(Q).

*$\mathbb{F}_{q}$*).OUTPUT: k $\cdot$ P.

Q←$\infty$.

For i from 0 to t−1 do

If ki = 1 then Q←Q+P.

P←2P.

Return(Q).

INPUT: k = (kt−1,..., k1, k0)2, P ∈ E(

OUTPUT: k $\cdot$ P.

Q←$\infty$.

For i from t−1 down to 0 do

Q←2Q.

If ki = 1 then Q←Q+P.

Return(Q).

*$\mathbb{F}_{q}$*).OUTPUT: k $\cdot$ P.

Q←$\infty$.

For i from t−1 down to 0 do

Q←2Q.

If ki = 1 then Q←Q+P.

Return(Q).

*The first algorithm processes the bits of k from right to left, while the second processes the bits from left to right. The expected number of ones in the binary representation of k for both algorithms is t/2≈m/2, therefore the expected running time of both algorithms is approximately m/2 point additions and ￼￼￼m point doublings [1]:*

*$\frac{m}{2} \cdot A + m \cdot D$.*

*In 1951, Booth [3] proposed a new scalar binary representation called signed binary method and later Rietweisner [4] proved that every integer could be uniquely represented in this format [5]. More particularly,* If P=(x,y)$\in$E(

*$\mathbb{F}_{q}$*

*) then −P=(x,x+y) if*

*$\mathbb{F}_{q}$*

*is a binary field, and −P=(x,−y) if*

*$\mathbb{F}_{q}$*

*has characteristic > 3. Thus subtraction of points on an elliptic curve is just as efficient as addition. This motivates us to use a signed digit representation $k=\sum_{i=0}^{l-1} k_i \cdot 2^i$, where $k_i \in \{0, \pm \}$. A particularly useful signed digit representation is the non-adjacent form (NAF).*

*A NAF representation of a positive integer k is an expression $k=\sum_{i=0}^{l-1} k_i \cdot 2^i$ , where $k_i \in \{0, \pm \}$ , $k_{l-1} \ne 0$ , and no two consecutive digits ki are non-zero. The length of the NAF is l [1].*

**Properties of NAF [1]**:- k has a unique NAF denoted NAF(k).
- NAF(k) has the fewest non-zero digits of any signed digit representation of k.
- The length of NAF(k) is at most one more than the length of the binary representation of k.
- If the length of NAF(k) is l, then 2l /3 < k < 2l+1/3.
- The average density of non-zero digits among all NAFs of length l is approximately 1/3.

**NAF(k)**can be efficiently computed using the following algorithm [1]:

INPUT: A positive integer k.

OUTPUT: NAF(k).

i←0.

While k≥1 do

If k is odd then: ki ←2−(k mod 4), k←k−ki;

Else: ki ←0.

k←k/2, i←i+1.

Return(ki−1, ki−2,..., k1, k0).

OUTPUT: NAF(k).

i←0.

While k≥1 do

If k is odd then: ki ←2−(k mod 4), k←k−ki;

Else: ki ←0.

k←k/2, i←i+1.

Return(ki−1, ki−2,..., k1, k0).

*The last algorithm presents*the way we can modify the left-to-right binary method for

**scalar multiplication by using NAF(k)**instead of the binary representation of k [1]:

INPUT: Positive integer k, P ∈ E(

OUTPUT: k $\cdot$ P.

Based on previous algorithm compute NAF(k)

Q←$\infty$.

For i from l−1 down to 0 do

Q←2Q.

If ki = 1 then Q←Q+P.

If ki = −1 thenQ←Q−P.

Return(Q).

Based on the third and

*$\mathbb{F}_{q}$*).OUTPUT: k $\cdot$ P.

Based on previous algorithm compute NAF(k)

*=$\sum_{i=0}^{l-1} k_i \cdot 2^i$*.Q←$\infty$.

For i from l−1 down to 0 do

Q←2Q.

If ki = 1 then Q←Q+P.

If ki = −1 thenQ←Q−P.

Return(Q).

Based on the third and

*fifth properties of NAF, the expected running time of the NAF scalar multiplication algorithm is approximately [1]:*

*$\frac{m}{3} \cdot A + m \cdot D$.*

[1] Hankerson, Darrel, Scott Vanstone, and Alfred J. Menezes. "

*Guide to elliptic curve cryptography"*. Springer Science & Business Media, 2004.

[2] Jonathan Taverne, Armando Faz-Hernández, Diego F. Aranha, Francisco Rodríguez-Henríquez, Darrel Hankerson, Julio López. "Speeding scalar multiplication over binary elliptic curves using the new carry-less multiplication instruction", Journal of Cryptographic Engineering, Vol. 1, No 3, pp. 187-199, 2011.

[3] A.D.Booth, “A Signed binary multiplication technique”, Journal of Applied Mathematics, Vol. 4. No. 2, pp.236-240, 1951

[4] G.W.Reitwiesner, “Binary Arithmetic”, Advances in computers, Academic Press, Vol. 1, pp.231-308, 1960

[5] Karthikeyan, E. “Survey of elliptic curve scalar multiplication algorithms.” International Journal of Advanced Networking and Applications, Vol. 4, No 2, pp. 1581-1590, 2012

## No comments:

## Post a Comment