Improved method of López-Dahab-Montgomery scalar point multiplication in binary elliptic curve cryptography

Published Online December 2018 in MECS

Nowadays information technologies develop and define the world’s progress while we talk about the information flow, methods of IT processing and managing patterns. As a result, the issues of data security are becoming more and more important in aspects of the methods of transferring unencrypted data which is unsafe and unreliable to use. Thus, we find ourselves in the situation where data encryption is not simply a necessary option but it is vital, and if one wants his data to be transferred securely, he‘d better to use data encryption methods more or less [1].

One of the efficient data encryption technologies is elliptic curve cryptography which is constructed by focusing on Galois Fields. One of the most important areas of applying elliptic curve over Galois Field operations is systems of cryptographic protection of information [2]. One of the most costly operations in terms of computing in implementing the methods is to cryptography data encoding which uses elliptic curves, it is multiplication of a point on an elliptic curve by a number. That is why the issue of speeding up the scalar point multiplication is relevant.

• II.    Galois Field Concepts. Binary Field Arithmetic

Field is an algebraic structure with two operations – addition (+) and multiplication ( • ), which satisfies the following conditions:

• •    Closeness and associativity of the operations;

• •    Unity element existing (for adding the unity element is 0, for multiplication – 1);

• •    Inverse element existing (for adding the unity

element is – a , for multiplication a ^–1);

• •    Commutative addition law;

• •    Commutative multiplication law for non-zero

elements;

• •    Distributive law.

The real numbers, the rational numbers, and the complex numbers under addition and multiplication are examples of algebraic fields [3].

The field is called finite or Galois field if it contains a finite number of elements.

There are two kind of finite fields:

• •    prime Galois fields, denoted as GF ( p ) ;

• •    Galois fields extension, denoted as GF ( p m ) .

All the elements of a GF ( p ) are integer numbers from 0 to p – 1. The operations in this field are performed modulo p , where p is a prime number. A polynomial form representation or normal form representation is usually used for building a GF ( p m ) . Let’s take a closer look at the polynomial representation. It is followed by building a finite field, its elements are the polynomial of the power which are not more than m – 1:

GF ( p m ) = { a_w - i x^{m — 1}

+ a m _— 2 x m 2 + ••• + a 2 x 2 + a 1 x + a ₀ ^: a i ^e {0,1

Meanwhile, cryptosystems over GF (2 ^m ) are widely used.

The elements of GF (2 ^m ) are the binary polynomials of degree value, the maximum value is m – 1.

The operations exceeding GF (2 ^m ) are performed by modulo irreducible polynomial of power m .

m — 1

A field element a ( x ) = ^ a i x is associated with the i = 0

binary vector a ( x ) = ( a m _— 1 , a m _{— 2},...,a1,a ₀) of length m . Elements addition in terms of GF (2 ^m ) is performed by bitwise modulo addition of two vectors (bitwise exclusive-or A ® B ), which contains the elements of the fields. Elements multiplication in terms of GF (2 ^m ) is performed by modulo irreducible polynomial.

• III.    Elliptic Curve Arithmetic

Cryptographic mechanisms based on elliptic curves depend on how we operate the points of the used curve. Meanwhile, curve arithmetic is defined by some field (meaning the operations of this field). As the greater focus is placed on the efficiency, the operations of the chosen field must be efficient enough [4] .

Elliptic curve over a field K is a set of points where lie in a plane and satisfy the affine equation:

2     32

y + a_xxy + a₃y = x + a₂x + a₄x + a ₆ ,

In which, the points are at infinity.

The number of the curve points is also named by the order of the elliptic curve.

Variables x , y and the coefficients a i , i = 1..6 take the values which are the elements of the field K .

Depending on the characteristics of the field K, the general equation of an elliptic curve can be expressed in a simplified form.

Let us review the form of the equation of an elliptic curve over the GF (2 ^m ) . The characteristic of this field is

• 2.    Depending on the value of the a ₁ , we get two types of elliptic curves over GF (2 ^m ) :

• •    if a 1 ^ 0 , then we get the equation of a non-super singular curve: y ² + xy = x ³ + ax ² + b ;

• •    if a 1 = 0 , then we get the equation of a super singular curve:

y2 + a3y = x3 + a2x2 + b, a3 ^ 0 .

In cryptography, the usage of super singular curves is not recommended. Special properties of these curves allow reduce discrete logarithm problem over the elliptic curve to the discrete logarithm problem over the finite field. This fact causes strength reduction in modern cryptosystems built upon such curves [5].

Base operation over the points of an elliptic curve are point addition and point doubling.

Let P = ( x1; y1) and    Q = ( x2; y 2).    Then

P + Q = ( x3; y3 )   , where    x3 = 22 + 2 + ц ,

y3 = (1 + 2) x3 + v , and

2 = ^

Д y+ y2)(x+ x2) 1, P *± Q; _ x + yi xi—1, P = Q;

Гx1 + x2 + a, P ^ ±Q;      | 2x1 + y1, P ^ ±Q;

Ц = i                    v = <

[ a, P = Q;                [x12, P = Q.

In case P = Q (elliptic curve point doubling), it substitute the values of 2 , and ц , we get the following formula to get x ₃ : x ₃ = ( x 1 + y 1 x 1 ¹ ) + x 1 + y 1 x 1 ¹ + a = = x 1 + 2 y 1 + y 1 x 1 + x 1 + y 1 x 1 + a .

An elliptic curve is defined over GF (2 ^m ), then 2 y 1 = 0. From the elliptic curve equation of x ^ 0, the value of x ₃ can be obtained as following:

y ² + xy = x ³ + ax ² + b ^ y ² x ^-2 + yx ^{— 1} = x + a + bx ^-2 ^ ^ bx ^-2 = y ² x ^-2 + yx ^{— 1} — x — a ^ ^ bx ^-2 = y ² x ^-2 + x + yx ^{— 1} + a .

So, x3 = x2 + bx-2.

Also, all the operations over the coordinates of elliptic curves points are performed by the rules of GF (2 ^m ) accordingly.

Sometimes a necessity appears to calculate the point which is inverse to the equation P = ( x; y ) . Such operation in terms of using a non-super singular curve over the field GF (2 ^m ) is performed by substituting the second coordinate’s value to x + y , so the point –P locates the following coordinates: ( x ; x + y ) .

• IV.    Existing Point Multiplication Methods

Presume E presents an elliptic curve defined by GF (2 ^m ) . Our task is to compute s P , where s is a positive integer and P is a point on an elliptic curve E . This operation is called point multiplication or scalar multiplication , and is widely used in the modern elliptic cryptography methods, which is one of the most important and costly operations in processing encryption/decryption. The core operations in elliptic-curve cryptography are based specifically on scalar multiplication (e.g. single-scalar multiplication ( s , P     s P )     ,     double-scalar     multiplication

(s, n, P, Q     sP + nQ) , etc.) [6]. So far, there have been presented a lot of methods for executing this operation. In this article, only single-scalar multiplication methods are going to be analyzed. Also, only those methods that perform sequential point multiplications will be reviewed further [7].

All the methods of elliptic curve scalar point multiplication are based on the analysis of scalar’s binary representation. The versions of algorithms which analyze each bit (one after another) per step of the algorithm are the classic ones. Depending on the order of the analysis of bits (from low to high and vice versa), there are two types of algorithms: RL (right-to-left) and LR (left-to-right).

• A.    Basic binary methods

Algorithm 1. Implementation of RL-binary method

Input: s = ( s i - ! ,..., s 1 , S o ) 2 , P e E ( GF (2 m ) )

Output: sP

• 1.    Q ^ ^

• 2.    For i from 0 to l – 1 do

  • 2.1.    If s i = 1 then Q ^ Q + P

  • 2.2. P ^ 2 P

• 3.    Return Q

Algorithm 2. Implementation of LR-binary method

Input: s = ( s i — J ,..., s j , S o ) 2 , P e E ( GF (2 m ) )

Output: sP

• 1.    Q ^ ш

• 2.    For i from l – 1 downto 0 do

  • 2.1.    Q ^ 2 Q

  • 2.2.    If s i = 1 then Q ^ Q + P

• 3.    Return Q

• B.    Methods that use a Non-Adjacent Form of a scalar

A non-adjacent form (NAF) of a positive integer s is i - 1

an expression s = ^ s i 2 i where s i e { 0, ± 1 } , s l _ 1 ^ 0, i = 0

and no two consecutive digits s_i are nonzero [5].

Algorithm 3. Implementation of binary NAF RL-method

Input: P e E ( GF (2 m ) ) , s

Output: sP

• 1.    Compute

• 2.    Q ^ ^

• 3.    For i from 0 to l – 1 do

  • 3.1.    If S i = 1 then Q ^ Q + P

  • 3.2.    Else if s i = - 1 then Q ^ Q - P

  • 3.3.    P ^ 2 P

• 4.    Return Q

l - 1

NAF(s) = £Si2, Si e {0;±1}; Si- * 0

i = 0

Algorithm 4. Implementation of binary NAF LR-method

Input: P e E ( GF (2 m ) ) , s

Output: sP

• 1.    Compute

• 2.    Q ^ ^

• 3.    For i from l – 1 downto 0 do

  • 3.1.    Q ^ 2 Q

  • 3.2.    If s i = 1 then Q ^ Q + P

  • 3.3.    Else if s i = - 1 then Q ^ Q - P

• 4.    Return Q

l - 1

NAF(s) = ^Si2, Si e {0;±1}; Si-, ^ 0

i = 0

• C.    Window methods

The time of Algorithm 3 and 4 can be decreased by using a window method which allows us to process w digits of s at a time. Yet it requires some extra memory to be performed [8].

In case w >  2 , it is a positive integer. A width-w NAF of a positive integer s is expressed by the following i - 1

expression:  s = ^ si 2 i  and where each nonzero i=0

coefficient s i is odd, | s i | <  2 ^{w - 1}, s _i - 1 ^ 0 , and at most one of any w consecutive digits is nonzero. Let’s also put that the width- w NAF (NAF _w ) has length l [6].

NAF w of a positive integer s can be obtained using Algorithm 5.

Algorithm 5. Computing the width- w NAF of a positive integer

Input: window width w , s

Output: NAF w ( s )

• 1.    i —— 0

• 2.    While 5 >  1 do

  • 2.1.    If s is odd then

• 2.2.    Else s i — 0

• 2.3.    s —— s /2, i —— i + 1

• 3.    Return( s_; - 1 , s i - 2,... , s i , » o )

s i — 5 mod 2 w , s — s - s i

Algorithm 6. Implementation of window NAF LR-method

Input: P e E ( GF (2 ^m ) ) , window width w , s

Output: sP i-1

• 1.    Use Algorithm 5 to compute NAF w ( s ) = ^ s i 2 i

• 2.    Compute P i = iP for i e { 1,3,5,...,2 ^{w - 1} - 1 }

• 3.    Q — ^

• 4.    For i from l – 1 downto 0 do

  • 4.1.    Q — 2 Q

  • 4.2.    If s i ^ 0then

• 5.    Return Q

i = 0

If s i >  0 then Q — Q + P _s

Else Q — Q - P-Si

Window NAF RL-method construction is inexpedient at each step of such algorithm. It is necessary to recalculate the table of precomputations which reduces the speed of the algorithm.

• V. López-Dahab Coordinates

Besides the affine coordinate system, there also exist several coordinate systems of projective types. One of the systems is named López-Dahab projective coordinate system (LD projective coordinate system), it is very popular. In terms of using this coordinate system, point addition is performed in mixed coordinates , i.e., one point is given in affine coordinates while the other is given in projective coordinates [9].

In this system, a point ( X ; Y ; Z ) is called projective and represents points in affine coordinate system: x = X • Z ^{- 1} y = X • Z ^{- 2} . According to this statement, we can get a new view for the elliptic curve equation in terms of using LD projective coordinates:

• Y2 + X • Y • Z = X3 • Z + a • X2 • Z2 + Z 4.

Points represented in LD projective coordinates satisfy the properties that differ from those that are valid for the points in affine coordinate system. Here are two of them:

• 1.    The point at infinity is represented as the point O = (1; 0; 0). And for any point P on the curve is true that: P + O = O + P = P.

• 2.    If P = ( X ; Y ; Z ) is a point on a curve, then the point – P = ( X ; X + Y ; Z ). This operation is also called the inverse of point P .

• VI. López-Dahab Montgomery Scalar Point Multiplication Method

Presume E is a non-super singular elliptic curve over GF (2 ^m ) , its coordinate satisfies the affine equation y ² + xy = x ³ + ax ² + b,      and      the      equation

Y ² + X • Y • Z = X ³ • Z + a • X ² • Z ² + Z ⁴ is valid for LD projective coordinates.

Peter Laurence Montgomery introduced a method of speeding up performance of the modulo multiplication operation for big values of the modulo (more than 128 bit) in 1985. Before executing of the multiplication, the operands must be converted into Montgomery form. For the obtained result, an inverse transformation must be made. The last operation is computationally expensive because it contains the computation of multiplicative inverse [10]. Thus, Montgomery multiplication is used only in the algorithms of exponentiation.

Exponentiation algorithm that contain Montgomery arithmetic can be split into three phases [10]:

• 1.    Operand’s conversion is converted into Montgomery form.

• 2.    Classic exponentiation algorithm execution in terms of Montgomery forms (a lot of multiplications).

• 3.    Converting the result from Montgomery form.

Further Peter Montgomery in his work that was dedicated to speed up the algorithms of factorization of the elliptic curves introduced in a new algorithm of scalar point multiplication (Algorithm 7) [11].

Algorithm 7. Implementation of Montgomery point multiplication method

Input: ( s i - 1 , s i - 2 ,..., s 1 , s 0 ) 2 with s t - 1 = 1,

P e E ( GF (2 ^m ) )

Output: sP

• 1.    R 0 — P , R 1 — 2 P

• 2.    For i from l – 2 downto 0 do

• 3.    Return R 0

R 1 - s. — R 1 - s , + R s,

R,, — 2 Rs,

López and Dahab later introduced a modification (also for binary curves over GF(2m) ) that was actually an improved Montgomery algorithm [11]. The scientists presented the idea that the sum of two points can be evaluated using only the operations that involve the x-coordinates of the points in procedures of doubling and adding per iteration.

In this algorithm that was called MDouble , the point P = ( x , y ) is represented in the LD-projective form P = ( X ■ Z - 1 , Y ■ Z - ² ) (Algorithm 8).

Similarly, the point addition algorithm was called MAdd (Algorithm 9) . Thus, following the modification designed by López and Dahab, we get Algorithm 10 [12, 13].

T —   "X 2

X ₂ — X ₂ ⁴ + bX 4

Z ₂ — T ² Z ₂ ²

2.2. Else

> MDouble

T ^{— Z} 2

Z ₂ — ( X 1 Z ₂ + X ₂ Z 1 ) ² ^ MAdd

X 2 — xZ 2 + X 1 X 2 Z 1 T

Algorithm 8. MDouble operation in López-Dahab

Montgomery point multiplication method

Input: b e GF (2 m ), P ( X : Y : Z ) e E ( GF (2 ^m ) )

Output: X ■ Z ^{- 1} is affine x -coordinate of the point 2 P

• 1.    X — X ²

• 2.    Z — Z ²

• 3.    T — Z ²

• 4.    Z — Z ■ X

• 5.    X — X ²

• 6.    T — b ■ T

• 7.    X — X + T

• 8.    Return X ■ Z ^{- 1}

X 1 ⁴

> MDouble

Z, — T2 Z2

1 ■ z-

4. уз — (x + x3)

"(X1 + xZ1 )■

■(X2 + xZ2 ) + +(x2+у )■ _■(Z1Z2 )

5. Return( x ₃, y ₃)

( xZ₁ Z ₂ ) ¹ + y

Algorithm 9. MAdd operation in López-Dahab Montgomery point multiplication method

Input: P ( x,y ), P 1 ( X 1 : Y : Z J, P 2 ( X 2 : Y 2 : Z 2 ) e

e E ( GF(2m ))

Output: affine x -coordinate X ■ Z - ¹ of the point P + P

The algorithm is considered to be a faster approach of the basic Montgomery method which thanks to a fewer numbers of operations to be performed per iteration, it secondly contains no inversion which is once used in the basic version.

• 1.   T₁ — Z₁ ■ X ₂

• 2.   T ₂ — Z ₂ ■ X ₁

• 3. Z — T 1 + T ₂

• 4.    X — x ■ Z ₁

• 5.   T ₁ — T ₁ ■ T ₂

• 6. X 1 — X 1 + T 1

• 7.    Return X 1 ■ Z ^{- 1}

Algorithm 10. Implementation of López-Dahab

Montgomery point multiplication method

Input: ( s i — 1 , s i — 2 ,..., S 1 , s o ) 2 with s t — 1 = 1,

P = ( x , у ) e E ( GF (2 ^m ) )

Output: sP

• 1.    X 1 —— x , Z 1 —— 1, X 2 —— x + b , Z 2 —— x

• 2.    For i from l – 2 downto 0 do

2.1. If s i = 1, then

T — Z

Z₁ — ( X 1 Z ₂ + X ₂ Z_x ) ²

X₁ — xZ₁ + X 1 X ₂ TZ ₂

MAdd

• VII. Improved Mdouble

m - 1

Let c = bb ^ c = b , where m is the order of the curve. Thus, we can achieve speed-up of the algorithm by precomputing c and getting rid of squaring, as we know that the following statement is true: ( a + b ) ² = a ² + b ² for GF (2 ^m )  . Using this, we can say that the

Q = X ⁴ + b ■ Z ⁴ expression could be reformed as: Q = ( X ² + c ■ Z ² ) 2 .

So, we suggest a new modification of the MDouble algorithm (Algorithm 11).

Algorithm 11. Improved MDouble

Input: c e GF (2 ^m ) , where c = bb , b e GF (2 ^m ), X ■ Z ^{- 1} is affine x -coordinate of the point P e E ( GF (2 ^m ) )

Output: X ■ Z ^{- 1} is affine x -coordinate of the point 2 P

• 1. X — X ²

• 2. Z — Z ²

• 3. T — c ■ Z

• 4. Z — Z ■ X

• 5.    X ^ X + T

• 6.    X ^ X ²

• 7.    Return X • Z - 1

So, we can see that the number of operations in Algorithm 11 is fewer than the number of operations in Algorithm 8 (table 1).

Table 1. Number of operations performed per one doubling

	Squaring	Multiplication	Addition
1. MDouble	4	2	1
2. Improved MDouble	3	2	1

May we have an elliptic curve E , where: a = z ³, b = z ³ + 1, c = z ³ + z + 1, and irreducible polynomial z ⁴ + z + 1. May the scalar s = 5₁₀ = 101₂.

May the point P = { z ³ + 1 : z ³ + z ² + z + 1 : 1}.

Let’s compare the results of calculations during the doubling of a point of an elliptic curve while using Algorithm 8 and Algorithm 9 (table 2, 3). It calculates the value of Z -coordinate in step 4 of both algorithms that is further used for computing Z ^–1. It calculates the X value in the last step of both algorithms.

• VIII.    The Experimental Research

  The software for performing experimental researches was designed in Visual Studio 2017 by using C# programming language. The hardware characteristics of the program are the following: CPU Intel Core I7-6500U @2.5 – 2.6 GHz, random access memory 8 Gb. The research was mainly based on comparing the timings of elliptic curves points’ multiplication with different lengths of scalars and different orders of elliptic curves (table 4, 5).

• Table 4.    Lengths of scalars used for multiplication, bits

  128      256      512      1024     2048     4096

• Table 5.    Orders of elliptic curves

  32     64    128    256    512   1024   2048   4096

Using these orders enable us to understand if the algorithm is viable for cryptography. Further researches are presented on the tables which contains the comparison of timings of the LD-Montgomery scalar point multiplication method and its modification with the improved MDouble (tables 6 – 11).

Table 2. The first doubling results during the process of multiplication. P i = ({1 0 0 1} : {0001})

Step	MDouble		Improved MDouble
	Var.	Value	Var.	Value
1	X	{1 1 0 1}	X	{1 1 0 1}
2	Z	{0 0 0 1}	Z	{0 0 0 1}
3	T	{0 0 0 1}	T	{1 0 1 1}
4	Z	{1 1 0 1}	Z	{1 1 0 1}
5	X	{1 1 1 0}	X	{0 1 1 0}
Step	Var.	Value	Var.	Value
6	T	{1 0 0 1}	X	{0 1 1 1}
7	X	{0 1 1 1}		–
X • Z - 1	( z 2 + z + 1 ) - ( z 3 + z 2 + 1 )		( z 2 + z + 1 ) " ( z 3 + z 2 + 1 )

Table 3. The second doubling results during the process of multiplication. P i = ({1 1 1 1} : {1 0 0 0})

Step	MDouble		Improved MDouble
	Var.	Value	Var.	Value
1	X	{1 0 1 0 }	X	{1 0 1 0}
2	Z	{1 1 0 0 }	Z	{1 1 0 0}
3	T	{1 1 1 1 }	T	{1 1 0 1}
4	Z	{0 0 0 1}	Z	{0 0 0 1}
5	X	{1 0 0 0 }	X	{0 1 1 1}
6	T	{1 1 1 0 }	X	{0 1 1 0}
7	X	{0 1 1 0 }		–
X • Z - 1	( z 2 + z ) ^ ( 1 )- 1		( z 2 + z ) ^ ( 1 )- 1

Table 6. Point multiplication execution time with m = 32

Scalar length, bits	LD-Montgomery method, ms	LD-Montgomery method with improved MDouble, ms
128	0,95	0,7
256	1,17	1,04
512	1,97	1,8
1024	3,59	3,47
Scalar length, bits	LD-Montgomery method, ms	LD-Montgomery method with improved MDouble, ms
2048	7,05	6,4
4096	14,01	13,82

Table 7. Point multiplication execution time with m = 64

Scalar length, bits	LD-Montgomery method, ms	LD-Montgomery method with improved MDouble, ms
128	0,77	0,74
256	1,24	1,15
512	2,15	2,01
1024	4,07	3,86
2048	7,6	7,3
4096	14,93	14,33

Table 8. Point multiplication execution time with m = 128

Scalar length, bits	LD-Montgomery method, ms	LD-Montgomery method with improved MDouble, ms
128	0,93	0,89
256	1,49	1,32
512	2,55	2,39
1024	4,79	4,63
2048	8,76	8,45
4096	17,01	16,7

Table 9. Point multiplication execution time with m = 256

Scalar length, bits	LD-Montgomery method, ms	LD-Montgomery method with improved MDouble, ms
128	1,11	1,01
256	2,35	1,64
512	3,84	2,94
1024	6,11	5,9
2048	5,33	5,19
4096	10,82	10,58

Table 10. Point multiplication execution time with m = 512

Scalar length, bits	LD-Montgomery method, ms	LD-Montgomery method with improved MDouble, ms
128	2,32	1,77
256	2,9	2,35
512	4,96	4,3
1024	8,53	7,82
2048	14,34	14,19
4096	29,44	28,29

Table 11. Point multiplication execution time with m = 1024

Scalar length, bits	LD-Montgomery method, ms	LD-Montgomery method with improved MDouble, ms
128	2,98	2,64
256	4,59	4,33
512	7,27	6,69
1024	12,14	12,14
2048	23,11	23,04
Scalar length, bits	LD-Montgomery method, ms	LD-Montgomery method with improved MDouble, ms
4096	46,78	45,82

Table 12. Point multiplication execution time with m = 2048

Scalar length, bits	LD-Montgomery method, ms	LD-Montgomery method with improved MDouble, ms
128	5,57	5,46
256	11,91	8
512	22,31	22,06
1024	21,77	21,28
2048	40,82	37,77
4096	76,72	77,39

Table 13. Point multiplication execution time with m = 4096

Scalar length, bits	LD-Montgomery method, ms	LD-Montgomery method with improved MDouble, ms
128	9,8	9,58
256	26,63	25,52
512	41,08	38,36
1024	38,73	37,57
2048	70,44	68,85
4096	145,7	142,95

Thus, we can see that speed performance has been slightly improved for every scalar length presented here and for every order of elliptic curve from what have been reviewed. Even more, with the order growth, the delta between the time-values slowly rises, it comes up with the thought that MDouble-method and the presented modification are effective for cryptography purposes [14].

• IX.    С ONCLUSIONS

Considering the methods used to perform point multiplication, the most powerful performance statistic is the MDouble-method created by López-Dahab through modifying the initial Montgomery double-and-add method [15].

The method contains two operations, it is obvious that improving the operation is working in some way to speed up the algorithm overall. Being used in cryptography and taking into account the fact that big data encryption is widely using multiple processors, a slight performance improvement could even lead to big one in general.

Thus, a modification of the MDouble operation was introduced. Increasing performance was achieved by using precomputations. The result gave an algorithm modification with fewer operations and performance time improvements.

Review the multiplication results of different orders curves (from 32 to 4096) by the scalars of different byte length (from 16 to 512), the following results are obtained: the average increase value is 4-5% (20 points per scalar were used). As mentioned above, considering all the processors working at the same time, multiprocessor systems that the encryption technologies based on Galois Fields theory will obtain even bigger improvements [16].

Using improved operations potentially in terms of working with polynomials over Galois Field (addition, multiplication etc.), operations can be also improved in terms of working with scalar point multiplication, a better result could be obtained in future.