Open access peer-reviewed chapter

The Graphs for Elliptic Curve Cryptography

By Ruma Kareem K. Ajeena

Submitted: September 21st 2018Reviewed: December 17th 2018Published: September 9th 2019

DOI: 10.5772/intechopen.83579

Downloaded: 120

Abstract

The scalar multiplication on elliptic curves defined over finite fields is a core operation in elliptic curve cryptography (ECC). Several different methods are used for computing this operation. One of them, the binary method, is applied depending on the binary representation of the scalar v in a scalar multiplication vP, where P is a point that lies on elliptic curve E defined over a prime field Fp. On the binary method, two methodologies are performed based on the implementation of the binary string bits from the right to the left (RLB) [or from the left to the right (LRB)]. Another method is a nonadjacent form (NAF) which depended on the signed digit representation of a positive integer v. In this chapter, the graphs and subgraphs are employed for the serial computations of elliptic scalar multiplications defined over prime fields. This work proposed using the subgraphs H of the graphs G or the (simple, undirected, directed, connected, bipartite, and other) graphs to represent a scalar v directly. This usage speeds up the computations on the elliptic scalar multiplication algorithms. The computational complexities of the proposed algorithms and previous ones are determined. The comparison results of the computational complexities on all these algorithms are discussed. The experimental results show that the proposed algorithms which are used the sub-graphs H and graphs G need to the less costs for computing vP in compare to previous algorithms which are employed the binary representations or NAF expansion. Thus, the proposed algorithms that use the subgraphs or the graphs to represent the scalars v are more efficient than the original ones.

Keywords

  • ECC
  • scalar multiplication
  • BRL
  • BLR
  • NAF
  • graphs
  • subgraphs
  • computational complexity

1. Introduction

The scalar multiplication on elliptic curves defined over finite fields is considered as a central and most time-consuming operation in elliptic curve cryptography (ECC) [1, 2, 3, 4, 5, 6, 7]. Different methods are used for computing the scalar multiplication such as the binary method, nonadjacent form, and others [8, 9, 10, 11, 12, 13, 14, 15]. The binary method is applied depending on the binary representation of the scalar v in a scalar multiplication vP, where P is a point that lies on elliptic curve E defined over a prime field Fp. On the binary method, two methodologies are performed based on the implementation of the binary string bits from the right to the left (RLB) [or from the left to the right (LRB)], whereas the nonadjacent form (NAF) depends on the signed digit representation of a positive integer v [1].

In this chapter, the computation of the scalar multiplication vP on elliptic curve E defined over a prime field Fp has been done using the (undirected or directed) graph and (undirected or directed) subgraph. These graph and subgraph are used to represent the scalar v in two ways. The first one is the binary representation and the second one is the sign digit representation.

Also, the l-tuple of the elliptic scalar multiplications is computed using the proposed generalized binary methods (GRLB) and (GLRB) and GNAF. The computational complexities of the proposed algorithms and previous ones are determined. The comparison results of the computational complexities on all these algorithms are discussed. Several experimental results showed that the proposed algorithms which are used the graphs G need to the less costs for computing vP in compare to previous algorithms which are employed the binary representations or NAF expansion. Therefore, the proposed algorithms that use the subgraphs or the graphs to represent the scalars v are more efficient than the original ones.

This chapter is organized as follows: Section 2 presents the vector representation of the graph. Section 3 discusses the matrix representation of the graph. Section 4 includes the binary methods of the elliptic scalar multiplication which are the right-to-left binary and left-to-right binary representations. Section 5 explains the non-adjacent form method, whereas Section 6 discusses the graphic binary methods of the elliptic scalar multiplications. Section 7 displays the digraphic NAF method. Section 8 presents the subgraphs for computing the elliptic scalar multiplication. Section 9 determines the computational complexities on the original elliptic scalar multiplication methods. Section 10 shows the computational complexity for serial computing l-tuple of the scalar multiplications. The computational complexity of the graphic elliptic scalar multiplication methods is explained in Section 11. Section 12 illustrates the computational complexity comparison on the serial and graphic computation methods. Finally, Section 13 draws the conclusions.

2. The vector representation of the graph

Suppose Gis a graph as shown in Figure 1.

Figure 1.

The subgraphs H 1 and H 2 of the graph G [16].

A graph Ghas four vertices and five edges e1,e2,e3,e4, and e5.A subgraph H(and any other subgraphs) of Gis represented by a 5-tuple.

This means that E=e1e2e3e4e5such that

ei=1,if eiis in H,

ei=0,if eiis not in H.

The subgraphs H1and H2in Figure 1 can be represented by (1,0,1,0,1) and (0,1,1,1,0), respectively. Here, there are 25 = 32 possible cases for 5-tuples which correspond to 32 subgraphs. Among them are the (0,0,0,0,0) and (1,1,1,1,1) which represent a null graph and a graph Gitself, respectively [16].

3. The matrix representation of the graph

Suppose G is any undirected graph that is formed by two finite sets V and E, which are called the vertices and edges, respectively. In other words, V=v1v2vland E=e1e2em.The matrix representation AG=eijl×mon graph G has been defined by

AG=v1v2vle11e21e31em1e12e22e32em2e1le2le2lemlE1

with lrows corresponding to the lvertices viand the mcolumns corresponding to the medges ei.Whereas the incidence matrix of a connected digraph can be defined by A=eijl×m,where eij0 1.In other words, if jthedge is incident out of ithvertex, then eij=1,while eij=1,if jthedge is incident into ithvertex and if jthedge is neither incident out nor incident into ithvertex, then eij=0[16, 17].

4. The binary methods for the elliptic scalar multiplication

Two methods for computing the scalar multiplication vP have been created based on using the binary representation of a scalar v. One of them is called the right-to-left binary (RLB) method, and another one is called left-to-right binary (LRB) method [1, 9, 10]. These methods depend on the basic repeated-square-and multiply methods for exponentiation with additive version. Using the RLB method, the process of v-bits starts from the right to the left, whereas the v-bits processing starts from the left to the right using the LRB method. The RLB and LRB methods are discussed mathematically as follows.

4.1 The right-to-left binary method

Suppose E is an elliptic curve defined over a prime field Fp. The equation of E is given by E: y2 = x3 + ax + b (mod p). Let P = (x, y) be a generator point that lies on E which has a (large) prime order n. Choosing v to compute vP can be done from the range [1, n−1]. So, it should first write v in a binary representation string (et-1, …, e1, e0)2. The starting will be happened with a point Q in E (Fp), (that is, Q = ∞). With the i index that takes the values 0, 1, …, t − 1, the computation of Q = Q + P can be done if ei = 1. After then, the value 2P is computed and plugging 2P by P. The processing continues until the last value t − 1. Therefore, the last computed value of a point Q is the scalar multiplication point vP [1]. The summary of the RLB method can be given in the following algorithm.

Algorithm 4.1 The RLB algorithm

Input: A scalar v in [1, n-1] and a point P in E(Fp).

Output: A scalar multiplication vP.

  1. Write down a scalar v as a binary string v = (et − 1, …, e1, e0)2.

  2. Q = ∞.

  3. For i = 0,1,…, t − 1 do

    1. If ei = 1 then Q = Q + P.

    2. Compute P = 2P.

    3. Else compute P = 2P.

    4. End if

  4. End for

  5. Return Q = vP.

4.2 The left-to-right binary method

With the same parameters E, P, n, and v which are used in the RLB method, the computation of vP using the LRB method can be done easily. A scalar v can be written in a binary representation string (et − 1, …, e1, e0)2. Let us start with a point Q in E(Fp), where Q = ∞. With the i index which takes the values t − 1,…, 1, 0, then the computation of 2Q can be done and plugged into Q. After then, the value Q = Q + P is computed. The processing continues until the last value 0. Therefore, the last computed value of a point Q is the scalar multiplication point vP. The LRB method can be summarized in Algorithm (4.2) [1].

Algorithm 4.2 The LRB algorithm

Input: A scalar v in [1, n-1] and a point P in E(Fp).

Output: A scalar multiplication vP.

  1. Write down a scalar v as a binary string v = (et − 1,…, e1, e0)2.

  2. Q = ∞.

  3. For i= t − 1,…,1, 0 do

    1. Compute Q = 2Q.

    2. If ei =1 then Q = Q + P.

    3. Else go to step (3.4).

    4. End if

  4. End for

  5. Return Q = vP.

5. The non-adjacent form for the elliptic scalar multiplication

The motivation to use the signed digit representation of a scalar v, in a scalar multiplication vP, is the computation of the subtraction and addition of the points lying on elliptic curve E which has the same efficient. A signed digit representation of v is given by v=i=0l1ei2i,where ei0±1will be explained in this section with more details. The signed digit representation forms the nonadjacent form (NAF) [1, 9, 10] which is given in the next algorithm.

Algorithm 5.1 The NAF computation of a positive integer

Input: A positive integer v in [1, n-1].

Output: The expansion NAF (v).

1. i←0.

2. While v ≥ 1 do

2.1 If v is odd then ei ←2 − (v mod 4),

vvei ;

2.2 Else: ei ←0.

2.3 End if

3. vv /2, ii +1.

4. End while

5. Return ei1e1e0.

The computation of a scalar multiplication vP by employing the NAF algorithm can be done using the following algorithm:

Algorithm 5.2 The NAF method for computing the scalar multiplication

Input: A positive integer v in [1, n-1] and PE(Fp).

Output: A scalar multiplication vP.

1. Algorithm (5.1) uses to compute NAF(v).

2. Q ← ∞.

3. For i = t − 1,…,1,0 do

3.1 Q ← 2Q.

3.2 If ei = 1 then Q ← Q + P.

3.3 ElseIf ei = −1 then Q ← Q − P.

3.4 Else go to step (3.5).

3.5 End if

4. End for

5. Return (Q = vP).

6. The graphic methods for the elliptic scalar multiplications

This section discusses the generalization on the binary methods and NAF to compute l-tuple of the scalar multiplications on elliptic curve E defined over prime field Fp. This generalization employed the simple undirected and directed graphs.

6.1 The graphic right-to-left binary (GRLB) method

Suppose Ecis an elliptic curve defined over a prime field Fp[1, 2, 3, 4, 5, 6, 7]. The equation of Ecis given by

Ec:y2=x3+ax+bmodp.E2

Let P=xybe a point that lies on Ecwhich has a (large) prime order r.Let GVEbe a simple (or multigraph or others) graph, where Vis a vertex set and Eis an edge set. The matrix representation AGon GVEis defined as given in Eq. (1). Directly from the rows of the matrix AG,the binary representation strings em1le1le0l2are obtained. The starting will happen with an elliptic point Q1which belongs to EFp,where Q1=.With the iindex which takes the values 01,11,,m11in the first row of AG,the computation of Q1=Q1+Pcan be done if ei1=1.After then, the value 2Pis computed and plugging it by P.The processing on the first row continues until the last value m1.Therefore, the last computed value of a point Q1is the value of the first scalar multiplication point v1Pin l-tuple vP.In similar way, the processing on others rows can be done. The summary of the GRLB method can be given in the following algorithm:

Algorithm 6.1 The GRLB method

Input: A graph GVE,PEFp,land m, where l and m are the order and size of a graph G, respectively.

Output: The m-tuple of the scalar multiplications vP=v1PvlP.

  1.  Write down the matrix representation AGof the graph GVE.

  2.  Directly determine the binary representation strings vj=em1je1je0j2from AG.

  3.  For j=1,2,,l.

  4.   Qj.

  5.   For i=0j:m1jdo

    1. If eij=1then Qj=Qj+P.

    2. Else go to step (6).

    3. End if

  6.    Compute P2P.

  7.   End for

  8. Return (Qj=vjP).

  9. End for

  10. Return (Q=vP=v1Pv2PvlP).

6.2 The implementation results on the GRLB method

With different kinds of graphs which are given in Figure 2, the matrix representations of the graphs have been computed by AGa,AGb,AGc, and AGd, respectively.

AGa=v1v2v3v4v510110011100000001010000010100001111, AGb=v1v2v3v4101001110100000111011010
AGc=v1v2v3v4v5v6101100001100000000111000010011100000010100000011and AGd=v1v2v3v4v5v6110000010001100100000011001001010010010000101100101000

Figure 2.

Different kinds of graphs [16].

The l-tuple computations of the scalar multiplications that correspond to these graphs are shown in Table 1.

PE (a,b)NGenerator pointGG (l,m)vP
101E (10,2)109P = (68,14)GaGa (5,7)v1Pv2Pv3Pv4Pv5P=
1419(9166)(4468)(551)(934)
61E (4,1)67P = (24,14)GbGb (4, 6)v1Pv2Pv3Pv4P=
060(452)(4321)(01)
191E (7,2)193P = (41,91)GcGc (6, 8)v1Pv2Pv3Pv4Pv5Pv6P=
2413741100,43113,18109,16114(10586)
449E (2,2)467P = (50,27)GdGd (6, 9)v1Pv2Pv3Pv4Pv5Pv6P=
93281405104,9620,266382,236399(31391)

Table 1.

The experimental results of the l-tuple of the scalar multiplications that correspond to the graphs Ga, Gb, Gc, and Gd.

6.3 The graphic left-to-right binary method

With the same parameters p,E,P,G, and Vwhich are used in the GRLB method, the computations of l-tuple vPusing the GLRB method can be done easily. The scalars v1,,vncan be written in the binary representation strings em1je1je0j2,for j = 1, 2, …, l, directly from the matrix representation A(G) of G. Let us start with a point Q1in EFp,where Q1=.With the i index which takes the values m11,,11,01, then the computation of 2Q1can be done and plugged into Q1.After then, the value Q1=Q1+Pis computed. The processing continues until the last value 01.Therefore, the last computed value of a point Q1is the first scalar multiplication point in an l-tuple vP.Similarly, the processing on others rows can be computed. The GLRB method can be summarized in Algorithm (6.2).

Algorithm 6.2 The GLRB method

Input: A graph GVE,PEFp,land m.

Output: The l-tuple of the scalar multiplications vP=v1PvlP.

  1. Write down the matrix representation AGof the graph GVE.

  2. Directly determine the binary representation strings vj=em1je1je0j2,for j=1,2,…, l from AG.

  3. For j=1,2,,l.

  4.   Qj.

  5.   For i=m1j:0jdo

    5.1 Compute Qj=2Qj.

    5.2 If eij=1then Qj=Qj+P.

    5.3 Else go to Step (5.4).

    5.4 End if

  6.   End for

  7.   Return (Qj=vjP).

  8. End for

  9. Return (Q=vP=v1Pv2PvlP).

7. The digraphic NAF for the elliptic scalar multiplication

The signed digit representation of an l -tuple vof scalars vj, which are used to compute an l-tuple vPof the scalar multiplications vjP, can be represented directly from the digraphs. The signed digit representations of vj are given by vj=i=0l1eij2ij,where eij0±1. The signed digit representations form the generalized nonadjacent form (GNAF). These representations are computed using the following algorithm:

Algorithm 7.1 The GNAF computation of an l-tuple of the positive integers

Input: An l-tuple of positive integers vj.

Output:NAFSv=NAFSv1NAFSv2NAFSvl.

1. Determine vj, j = 1, 2, …,l and e1je2jemjin any digraph G.

2. For j = 1, 2, …, l.

3.  For i = 1,…,m.

4.    If vs is an incident out of vt, where s, t j

5.     then eij=1.

6.    Elseif vs is an incident into vt

7.     then eij=1.

8.    Else there is no edge between vs and vt.

9.     then eij=0.

10.   End if

11.  End For

12.  Return e1je2jemj.

13. End For

14. Return NAFvj=emje2je1j.

In Figure 3, the digraph G has the vertices vj for j = 1, 2, 3, 4 and edges em for m = 1, 2, …, 7.

Figure 3.

The digraph has the vertices vj for j = 1, 2, 3, 4 and edges em for m = 1, 2, …, 7.

The incidence matrix of G that is given in Figure 3 is

A=v1v2v3v41001101110001001101000011011.

So, the NAF representations of 4-tuple v1v2v3v4are

1001101(1100010)(0110100)(0011011).

The GNAF method for l-tuple of the scalar multiplications can be performed using Algorithm (7.2).

Algorithm 7.2 The GNAF method for computing l-tuple of the scalar multiplication

Input: The l-tuple of positive integers vj and PE(Fp).

Output: The l-tuple of the scalar multiplications vP.

1. Algorithm (7.1) uses to compute GNAF(v).

2. Qj←∞.

3. For j = 1, 2, …, l

4. For i = t − 1, …, 1, 0

4.1 Qj ←2Qj.

4.2 If eij=1then Qj ← Qj +P.

4.3 Elseif eij=1then Qj ← Qj −P.

4.4 Else go to step (4.5).

4.5 End if

5. End for

6. End for

7. Return Qj=vjP.

Using Algorithm (7.2), the final result of 4-tuple of the scalar multiplications is given by

v1Pv2Pv3Pv4P=2832(4663)(2590)(8215).

8. The subgraphs for the elliptic scalar multiplication

8.1 The binary representations

Suppose G is a graph and Hi, for i = 1, 2, 3 are subgraphs as shown in Figure 4.

Figure 4.

The subgraphs Hi, for i = 1, 2, 3, for a graph G.

Next algorithm can be applied for determining the binary representation of any subgraph from a given graph.

Algorithm 8.1 The graphic binary representation of a subgraph from a given graph

Input: A graph G(V, E), where V = (v1, v2, …, vl) and E = (e1, e2,…, em).

Output: The BRsubgraph(v).

  1. Determine (v1, v2, …, vk) and (e1, e2,…, em) in any subgraph H of G.

  2. i←0.

  3. For j = 0: k, where kl.

  4.    If there is an edge between vs and vt, where s, t j

  5.     then ei=1.

  6.    Else there is no edge between vs and vt.

  7.     then ei=0.

  8.    End if

  9. i← i + 1.

  10. Return BRsubgraph = (em-1, …, e1, e0)2.

The small numerical results based on Figure 4 can be shown in Table 2.

Subgraphs(v1, v2, …, vk)(e1, e2,…, em)BRsubgraph = (em − 1, …, e1, e0)2
H1(v1, v2, v3, v4, v6)(e1, e2, e3, e6, e7)(1, 1, 0, 0, 1, 1, 1)
H2(v1, v2, v3, v4, v6)(e1, e3, e6, e7)(1, 1, 0 ,0, 1, 0, 1)
H3(v1, v2, v3, v4, v5, v6)(e1, e3, e4, e5, e7)(1, 0, 1, 1, 1, 0, 1)

Table 2.

The experimental results of the binary representations of scalars using subgraphs.

On the binary representations which are found directly from the subgraphs, the scalar multiplications HiP on elliptic curve E defined over a prime field Fp can be computed using Algorithm (4.1) or (4.2). Some experimental results for computing the scalar multiplications based on using the subgraphs to represent the scalars are given in Table 3.

pE (a,b)nGen Pt PSubgraphBRsubgraph = (em − 1, …, e1, e0)2HiP
191E (7,2)193P = (41,91)H1(1, 1, 0, 0, 1, 1, 1)(80,142)
H2(1, 1, 0 ,0 ,1, 0, 1)(0,57)
H3(1, 0, 1, 1, 1, 0, 1)(36,146)

Table 3.

The experimental results for computing of the scalar multiplications based on using the binary representation of the subgraphs.

9. The signed digit representations

Suppose G is a digraph and Hi, for i = 1, 2, 3, are directed subgraphs as shown in Figure 5. Algorithm (8.2) can be used to find the signed digit representation of any subgraph from a given graph.

Figure 5.

The directed subgraphs Hi, for i = 1, 2, 3, 4, for a digraph G.

Algorithm 8.2 The di-subgraph signed digit representation of the positive integers

Input: A directed graph G(V, E), where V = (v1, v2, …, vl) and E = (e1, e2, …, em).

Output: The SDRsubgraph(v).

1. Determine (v1, v2, …, vk) and (e0, e1,…, em − 1) in any subgraph H of G.

2. i←0.

3. For j = 0: k, where k ≤ l.

4.   If vs is an incident out of vt, where s, t j

5.    then ei=1.

6.   Elseif vt is an incident into vs

7.    then ei=1.

8.   Else there is no edge between vs and vt.

9.    then ei=0.

10.   End if

11. End for

11. i← i+1.

12. Return (em − 1, …, e1, e0).

The computational results based on Figure 5 and using Algorithm (8.2) are given in Table 4. With the signed digit representations which are given in Table 4, the l-tuple of the scalar multiplications on elliptic curve E defined over a prime field Fp can be computed. Some experimental results for computing the l-tuple of the scalar multiplications based on using the directed subgraphs to represent the scalars are given in Table 5.

Subgraphsl-tuple vl-tuple NAFSv
H1v1v2v3v61000000(1100001)(0110010)0000011
H2v1v2v3v4v61000000(1000001)(0010010)0010000(0000011)
H3v1v2v3v4v5v61000000(1000001)(0011000)0010000(0001100)(0000101)

Table 4.

The experimental results for sign digit representing l-tuple of the scalars using the subgraphs.

PPDirected subgraphsl-tuple vvP
191P = (41,91)H1v1v2v3v613391(17171)(132144)(1677)
H2v1v2v3v4v613391(1791)(177186)(1775)
1677
H3v1v2v3v4v5v613391(1791)(4923)(1775)
7997(10586)

Table 5.

The experimental results for computing l-tuple of the scalar multiplications based on using the subgraphs.

10. The computational complexity on the elliptic scalar multiplication methods

This chapter discusses the problems of the computational complexities which are determined depending on the account operations. These operations are the elliptic curve operations, namely, the addition A and doubling D on the points which lie on elliptic curve E defined over a prime field Fp. Also, the finite field operations which are field inversion I, field multiplication M and a field squaring S. The computational complexity problems are determined first of the original binary methods and NAF for computing the scalar multiplications on E. The computational complexities of the proposed methods which are dependent on the graphs and subgraphs are determined as well.

10.1 The computational complexity of the binary methods

Let #E (Fp) = n, where n is prime number and it is the nearest number to prime p. A point P in E(Fp) which has order n. Suppose v is a scalar such as v is a randomly selected integer from the interval [1, n−1]. The binary representation of v is denoted (em – 1e2.e1.e0)2 where m ≈ t = log2p.

The computational complexity of Algorithm (4.1) or (4.2) is roughly t/2 point additions and t point doublings, which is denoted by

t2A+tD,E3

in addition to the time of binary representation which is approximately t/2d and t/2S, where d and S are normal addition and squaring. Using Lemmas (6.1) and (6.2) in [18, 19], the points addition A and doubling D can be re-expressed by 1I + 2 M + 1S and 1I + 2 M + 2S, respectively. In other words, the computational complexity of Algorithm (4.1) or (4.2) is expressed in terms of field operations by.

3tS+3tM+1.5tI+0.5td.E4

Several computational complexity results to compute a scalar multiplication by applying the binary method are given in Table 6.

PE (a,b)nGen. pt. PvPBin. representationComp. complexity
101E (10,2)109(68,14)93P(1, 0, 1, 1, 1, 0, 1)21S + 21 M + 10.5I + 3.5d
61E (4,1)67(24,14)23P(1, 0, 1, 1, 1)15S + 15 M + 7.5I + 2.5d
113E (12,4)103(52,41)39P(1, 0, 0, 1, 1, 1)18S + 18 M + 9I + 4.5d
149E (13,1)167(32,133)13P(1, 1, 0, 1)12S + 12 M + 6I + 2d
1031E (15,7)1061(217,808)281P(1, 0, 0, 0, 1, 1, 0, 0, 1)27S + 27 M + 13.5I + 4.5d

Table 6.

The experimental results of the computational complexity for the scalar multiplications using the binary method.

10.2 The computational complexity of the NAF

With same the multiplier v which belongs to the interval [1,n − 1], the computational complexity to compute a scalar multiplication vP using the NAF is given by

D+t3A+tD=t3A+t+1D.E5

In Eq. (5), D in the first term is the cost of NAF to represent a positive integer v, t/3A + tD is the cost of computing a scalar multiplication vP using NAF method, and t is the length of the NAF string. In other words, the running time of Algorithm (5.1) is expressed in terms of field operations by

t/31I+2M+1S+t+11I+2M+2S=t/3+t+1I+2/3t+2t+2M+t/3+2t+2S.E6

Some numerical results of the computational complexity to compute a scalar multiplication using the NAF method are given in Table 7.

PE (a,b)NGen. pt. PvPNAF. rep.Comp. complexity
101E (10,2)109(68,14)93P(1, 0, −1, 0, 0, −1, 0, 1)11.6I + 23.3 M + 20.6S
61E (4,1)67(24,14)23P(1, 0, −1, 0, 0, −1)9I + 18 M + 16S
113E (12,4)103(52,41)39P(1, 0, −1, −1, 0, 0, −1)10.3I + 20.6 M + 23S
149E (13,1)167(32,133)13P(1, 0, 0, −1, −1)7.6I + 15.3 M + 13.6S
1031E (15,7)1061(217,808)281P(1, 0, 0, 1, 0, 0, −1, −1, −1)13I + 26 M + 23S

Table 7.

The experimental results of the computational complexity for the scalar multiplications using the NAF method.

11. The computational complexity for serial computing l-tuple of the scalar multiplications

11.1 The computational complexity of the serial GBR

On l-tuple of the scalar multiplications vP=v1Pv2PvlP,the computations of v1P,v2P,,vlPwithout using the graphs or subgraphs can be done serially. So, the computational cost of these computations using the binary representations of v1,v2,,vlis given by

t2lA+tlD+0.5tld.E7

In other words, the running time can be expressed in terms of field operations by

3tlS+3tlM+1.5tlI+0.5tld.E8

Table 8 displays some small experimental results for computational complexities for serial computations of l-tuples vPusing the generalized binary method.

PE (a,b)nGen. pt. PvPComp. complexity
101E (10,2)109(68,14)93P25P66P63S + 63 M + 31.5I + 10.5d
61E (4,1)67(24,14)23P19P12P45S + 45 M + 22.5I + 7.5d
113E (12,4)103(52,41)39P21P36S + 36 M + 18I + 9d
149E (13,1)167(32,133)13P5P24S + 24 M + 12I + 4d
1031E (15,7)1061(217,808)281P91P63P55P108S + 108 M + 54I + 18d

Table 8.

The experimental results for computational complexities for serial computations of l-tuples vPusing the generalized binary method.

11.2 The computational complexity of the serial GNAF

The computational complexity for computing l-tuple of the scalar multiplications using GNAF representations in serial way is given by

lD+t3lA+tlD=t3lA+t+1lD.E9

Using the field operations, the formula in Eq. (9) can be rewritten by.

t/3+t+1lI+2/3t+2t+2lM+t/3+2t+2lS.E10

The computational complexity results for serial computations of l-tuples vPusing the GNAF method are given in Table 9.

PE (a,b)NGen. pt. PvPComp. complexity
101E (10,2)109(68,14)93P25P66P34.8I + 69.9 M + 61.8S
61E (4,1)67(24,14)23P19P12P27I + 54 M + 48S
113E (12,4)103(52,41)39P21P20.6I + 41.2 M + 46S
149E (13,1)167(32,133)13P5P15.2I + 30.6 M + 27.2S
1031E (15,7)1061(217,808)281P91P63P55P52I + 104 M + 92S

Table 9.

The experimental results of the computational complexities for the serial computations of l-tuples vPusing the GNAF.

12. The computational complexity of the graphic elliptic scalar multiplication methods

Suppose vP=v1Pv2PvlPis an l-tuple of the scalar multiplications. The graphic computations of v1P,v2P,,vlPcan be done using the graphs or subgraphs in two ways. One of them is using the graphs directly to find the binary representations of the scalars v1,v2,,vl,whereas another one uses the digraphs to represent these scalars. The computational costs of these computations can be discussed as follows.

12.1 The computational complexity of the graphic binary representation (GBR)

Using the graphs to compute l-tuple of the scalar multiplications costs

t2lA+tlD.E11

In terms of field operations, the computational complexity of GBR can be expressed by

3tlS+3tlM+1.5tlI.E12

Table 10 displays some small experimental results for computational complexities for the graphic representations of l-tuples vPusing the generalized binary method.

PE (a,b)nGen. pt. PvPCGBRusing graphic representations
101E (10,2)109(68,14)93P25P66P63S + 63 M + 31.5I
61E (4,1)67(24,14)23P19P12P45S + 45 M + 22.5I
113E (12,4)103(52,41)39P21P36S + 36 M + 18I
149E (13,1)167(32,133)13P5P24S + 24 M + 12I
1031E (15,7)1061(217,808)281P91P63P55P108S + 108 M + 54I

Table 10.

The experimental results for computational complexities for graphic computations of l-tuples vPusing the generalized binary method.

12.2 The computational complexity of the digraphic NAF

The computational complexity for computing l-tuple of the scalar multiplications using the digraphs is given by

t3lA+tlD.E13

Eq. (13) can be rewritten using field operations by:

t/3+tlI+2/3t+2tlM+t/3+2tlS.E14

Several experimental results for computational complexities for digraph representations of l-tuples vPare given in Table 11.

PE (a,b)NGen. pt. PvPCGBRusing graphic representations
101E (10,2)109(68,14)93P25P66P32I + 64 M + 56S
61E (4,1)67(24,14)23P19P12P24I + 48 M + 42S
113E (12,4)103(52,41)39P21P18.6I + 37.3 M + 32.6S
149E (13,1)167(32,133)13P5P13.3I + 26.6 M + 23.3S
1031E (15,7)1061(217,808)281P91P63P55P48I + 96 M + 84S

Table 11.

The experimental results for computational complexities for graphic computations of l-tuples of vPusing the GNAF method.

13. Computational complexity comparison on the serial and graphic computations of GBR and GNAF methods

This section discusses first the experimental results of the GBR method that uses serial computations to calculate l-tuple of the scalar multiplications and the GBR method that depends directly on using the graphs. Selecting the scalars v1, v2,…. vl from the interval [1. n − 1] to represent using the GBR method which needs the cost 0.5tld, where t is the length of the string binary representation, l is the length of the tuple and d is a normal addition operation. The final computational cost as given in Eq. (8).

Whereas, the binary representing of the scalars v1, v2, … vl can be taken directly from graphs or subgraphs without need to extra cost. This saves the 0.5tld operations to compute l-tuple of the scalar multiplications vP.The total cost of the graphic GBR method has been determined previously in Eq. (12). The serial GBR and graphic GBR computational costs for several experimental results are given in Table 12. In this table, one can see the serial GBR method with various values of p is more costly compared to the graphic GBR method.

PE (a,b)NGen. pt. PCGBRusing serial computationsCGBRusing graphs
101E (10,2)109(68,14)63S + 63 M + 31.5I + 10.5d63S + 63 M + 31.5I
61E (4,1)67(24,14)45S + 45 M + 22.5I + 7.5d45S + 45 M + 22.5I
113E (12,4)103(52,41)36S + 36 M + 18I + 9d36S + 36 M + 18I
149E (13,1)167(32,133)24S + 24 M + 12I + 4d24S + 24 M + 12I
1031E (15,7)1061(217,808)108S + 108 M + 54I + 18d108S + 108 M + 54I

Table 12.

The computational costs of the serial GBR and graphic GBR with different values of p.

Also, the experimental results of the serial GNAF and graphic GNAF methods that are used to calculate l-tuple of the scalar multiplications are discussed in this section. Selecting the scalars v1, v2, … vl from the interval [1. n − 1] to represent using the GNAF method which needs the 1lI + 2lM + 2lS cost, l is the length of the tuple, M is a field multiplication, S is a field squaring, and I is a field inversion. So, the total computational cost as given in Eq. (10).

The graphic GNAF of the scalars v1, v2, …. vl can be taken directly from graphs. So it can save 1lI + 2lM + 2lS operations for computing l-tuple of the scalar multiplications vP.The total cost of the graphic GNAF method is determined previously in Eq. (14). Several experimental results on the serial GNAF and graphic GNAF computational costs are given in Table 13. With various values of p as shown in Table 13, it can observe that the graphic GNAF method is less costly than the serial GNAF method.

PE (a,b)NGen. pt. PCostGNFAusing serial computationsCostGNFAusing graphs
101E (10,2)109(68,14)34.8I + 69.9 M + 61.8S32I + 64 M + 56S
61E (4,1)67(24,14)27I + 54 M + 48S24I + 48 M + 42S
113E (12,4)103(52,41)20.6I + 41.2 M + 46S18.6I + 37.3 M + 32.6S
149E (13,1)167(32,133)15.2I + 30.6 M + 27.2S13.3I + 26.6 M + 23.3S
1031E (15,7)1061(217,808)52I + 104 M + 92S48I + 96 M + 84S

Table 13.

The computational costs of the serial GNAF and graphic GNAF with different values of p.

14. Conclusions

The present chapter was concerned with presenting new graphic elliptic scalar multiplication algorithms for speeding up the computations of the scalar multiplication defined on elliptic curves over a prime field in different ways. These ways employed the undirected graphs and subgraphs to construct the binary representations of the scalars v in the scalar multiplications vP. Also, the sign digit representation of v has been obtained directly from using the digraphs or di-subgraphs. These representations are used to compute one scalar multiplication vP and l-tuple <vP> of the scalar multiplications. The computational complexities of the proposed graphic elliptic scalar multiplication algorithms have been determined. The computational complexity comparison of the proposed algorithms and original ones is discussed based on the elliptic curve and field operations. The experiment results of the computational complexities show that the proposed algorithms are less costly for computing the scalar multiplication or l-tuple of the scalar multiplications than original algorithms which are dependent on the computations of the binary representations or NAF expansions. The new propositions with graphic representations speed up the computations on elliptic scalar multiplication algorithms. Also, it gives the generalized cases with the computations of the l-tuples <vP> using (undirected or directed) graphs or subgraphs. This insight makes the working with graphic elliptic scalar multiplication algorithms more efficient in comparison with the serial original ones.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Ruma Kareem K. Ajeena (September 9th 2019). The Graphs for Elliptic Curve Cryptography, Applied Mathematics, Bruno Carpentieri, IntechOpen, DOI: 10.5772/intechopen.83579. Available from:

chapter statistics

120total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

A Study of Bounded Variation Sequence Spaces

By Vakeel Ahmad Khan, Hira Fatima and Mobeen Ahmad

Related Book

First chapter

Using Wavelets for Gait and Arm Swing Analysis

By Yor Jaggy Castaño-Pino, Andrés Navarro, Beatriz Muñoz and Jorge Luis Orozco

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us