In today's world, the problem of information security is becoming critical. One of the most common cryptographic approaches is the elliptic curve cryptosystem. However, in elliptic curve arithmetic, the scalar point multiplication is the most expensive compared to the others. In this paper, we analyze the efficiency of the scalar multiplication on elliptic curves comparing Affine, Projective, Jacobian, Jacobi-Chudnovsky, and Modified Jacobian representations of an elliptic curve. For each coordinate system, we compare Fast exponentiation, Nonadjacent form (NAF), and Window methods. We show that the Window method is the best providing lower execution time on considered coordinate systems.
Throughout history, humanity has experienced the need to protect information. Many cryptosystems of
different complexity were created. However, in the last 20 years, due to the growth in the computing
power, most algorithms based on the complexity of factorization have become more vulnerable to
cryptographic attacks. As a result, it became necessary to use alternative approaches to build
cryptosystems with more advanced protocols. Currently, one of the most secure systems in cryptography
is a cryptosystem based on elliptic curves (Elliptic Curve Cryptosystems -ECC). Elliptic cryptography
is secure because there are currently no subexponential algorithms for solving the discrete logarithm
problem [
The most expensive and widely used operation on ECC is scalar point multiplication because it is used for key generation, encryption/decryption of data, and signing/verification of digital signatures. Scalar multiplication denoted by where represents a point on the ellipic curve and represents a scalar. Efficient implementation of multiplying the points of an elliptic curve by a scalar is important.
This research aims to study the methods of scalar point multiplication of NIST FIPS 186 elliptic curves and their implementation in the C++ programming language.
The rest of this paper is organized as follows. Section 2 briefly introduces elliptic curve concept, affine, projective, Jacobian, Jacobi-Chudnovsky, and modified Jacobian coordinate systems. Section 3 describes the actual research and algorithms of scalar multiplication on elliptic curves. The main libraries the calculation of integer values of arbitrary length are reviewed in Sections 4. Section 5 provides experimental analysis on NIST FIPS 186 standard. Finally, we conclude and discuss future works in Section 6.
In the standards such as GOST 34.10-2018, NIST FIPS 186, the elliptical curve is described by the following parameters: • – field characteristic, prime number; • , – constants that are parameters equation of the curve ! = " + + ; • = (, ) – point of a large-order elliptic curve; • – point order ; • ℎ – cofactor determined by the ratio of the total number of points on a curve to the order of a point , which should be the smallest possible.
An elliptic curve over the field # is the set of points (, ) satisfying the following equation [
To achieve efficiency of elliptic cryptosystem implementations, curves over a simple field defined in the Weierstrass form are used:
(#): ! = " + + where , ∊ # – constants satisfying 4" + 27! ≢ 0 ( ) and > 3 and – prime number.
The set of points on the EC form a group (namely, an Abelian group) with the following properties: • • • • • if and ∈ #, then + ∈ #; unit element (point at infinity): + = ; inverse value of the point (; ) – that point −(; −); commutativity: + = + ; associativity: + ( + ) = ( + ) + = + + = .
Let the points (', '), ((, () ∈ (#), then the addition of points ('; ') and ((; () is
called the point (); )) = + then the coordinates of the point will be calculated as follows [
(mod ), if = !∗*N
In practical calculations, an affine coordinate system is inefficient since it requires the calculation of the inverse element in the field #.
A practical solution to this problem can be a transition to other coordinate systems (mainly to projective ones) by eliminating modular inversion. system: ' = '/' и ' = '/' [5, 6].
In the projective coordinate system, the point of an elliptic curve is given by = (': ': '). If # = 0 than = – is a point at infinity. If ' ≠ 0, then the point P can be put in the affine coordinate The equation of an elliptic curve in a projective coordinate system has the following form: 1#2: ! ⋅ Z = " + ⋅ ! + "
The addition operation of points ( + ) on the elliptic curve in a projective coordinate system has the form:
) = ∙ ) = ⋅ 1' ⋅ ( ⋅ ! − 2 − " ∙ ' ∙ (
) = B" ∙ ' ⋅ ( where = ( ⋅ ' − ' ⋅ (, = ( ⋅ ' − ' ⋅ (, = ( ⋅ ' + ' ⋅ ( and = ! ⋅ ' ⋅ ( − ! ∙ C.
The operation of doubling the point (2) is given as follows:
) = 2 ⋅ ) = ⋅ (4 − ) − 8'! ⋅ !
) = 8" where = 3'! + '!, = ' ⋅ ', = ' ⋅ ' ⋅ and = ! − 8.
In the projective Jacobi coordinate system, the point of the elliptic curve is given by = (': ': '). If # = 0 then = – a point at infinity. If ' ≠ 0, then can put a point in the affine coordinate system: ' = '/'! и ' = '/'" [6-8].
The algorithm addition of points on an elliptic curve in projective Jacobi coordinates has the form: ) = −" − 2 ∙ $ ∙ ! + ! ) = −$ ∙ " + ∙ ($ ∙ ! − ))
) = C ∙ ' ⋅ ( where $ = ' ⋅ (! , ! = ( ⋅ '!, $ = ' ⋅ (" , ! = ( ⋅ '", = ! − $ и = ! − $. The point doubling algorithm is specified as follows:
) = t ) = −8'% + ∙ ( − )
) = 2' ∙ ' where = 4' ∙ '!, = 3'! + a ∙ '%, = −2 + !.
In the Jacobi-Chudnovsky projective coordinate system, the point on an elliptic curve is given by five coordinates = (': ': ': !': "') [7, 8]. If ' = 0 then = – a point at infinity. If ' ≠ 0, then can put a point in the affine coordinate system: ' = '/!' and ' = '/"' .
In the modified projective Jacobi coordinate system, the point on the elliptic curve is given by four coordinates = (': ': ': '%) [7, 8]. If ' = 0 then = – a point at infinity. If ' ≠ 0, то can put a point in the affine coordinate system: ' = '/'! и ' = '/'".
Algorithm 1 presents the operation of the scalar point multiplication by the Fast Exponentiation (FE) method.
Let – be a scalar, ∈ (#), then is calculated by the formula = ∑012+3$ 0 ∙ 20 ∙ , where 0 – are the binary digits of the number .
Algorithm 1. Scalar multiplication of an elliptic curve point by FE method [5-12] Input: = (1+$, 1+!, … , $, 3) and ∈ 1#2.
Output: = . 1. = 2. = 0 3. ℎ < : 3.1. 0 == 1: 3.1.1. += 3.2. = 2 3.3. += 1 4. .
NAF (nonadjacent form) is obtained from a modification of the fast exponentiation method by introducing an additional operation of subtracting a point, thereby reducing the amount of operations by representing a number in NAF with coefficients {−1,0,1}.
Algorithm 2 presents the number representation in NAF, and Algorithm 3 describes the scalar point multiplication operation [11-17].
Input: Output: () = (3, $, … , 1+!, 1+$) 1. = 0 2. ℎ ≥ 1: 2.1. 2: 2.1.1. 0 = 2 − ( 4) 2.1.2. −= 0 2.2. else: 0 = 0 2.3. /= 2 2.4. += 1 3. (3, $, … , 1+!, 1+$).
Algorithm 3. Scalar multiplication by the NAF method
If there is enough memory, then window-based methods (window methods) can be used to speed up the operation of multiplying an elliptic curve point by a scalar. It was proposed by Brauer in 1939. The idea is to cut the scalar into digits and process digits at the same time.
The scalar k in window methods is represented in the base 24 (or 25 in the radix-r method), where , > 1. The algorithms in this method would significantly improve the speed of scalar multiplication. It processes the -bit at a time, at the cost of 24+! points in the memory lookup table.
For example, computing ECSM using the windowing method introduced by Thurber requires the set , ∈ {1, 3, 5, 7,· · · , 24+$}, the points must be precomputed and stored in memory. A typical standard method for computing ECSM in radix-r is shown in Algorithm 4. In this algorithm, the average density of non-zero digits is y5 +5$z.
Algorithm 4 shows that the addition operation at step 1.2.1 and subtraction operation at step 1.3 begin only after completing repeated doubling operations at step 1.1.
Algorithm 4. Radix-r standard signed scalar multiplication from left to right [18, 19] Input: -bit Radix-r of and dot ∈ (), где, = (6+$, 6+!, … , $, 3)5, 0 ∈ {0,1,2, … , ( − 1)}.
Output: Point = .
Pre-calculations: |0| for all 0 ∈ {1,2, … , ( − 1)}.
Initialize: = ; Step 1: For = − 1 down to 0 do Step 1.1: = ; /* Perform a re-doubling operation */ Step 1.2: If 0 ≥ 0 Then Step 1.2.1: = + 0; /* Perform the addition operation */ Step 1.3: Else = – 0 /* Perform the subtraction operation */
Step 3: Return .
It is a pure sequential method in computing operations with elliptic curve points at the low level of the addition group.
Note that in order to make these window methods feasible for implementations that support parallel processing at the low level of the addition group, all precomputed points must be doubled − 1 times at each iteration.
Let us denote the cost of the ECSM computational operation using 789:. Then the 78;9: of the -bit scalar using the windows method is approximately equal to: + 1
Notably, the Window Methods (WM) described here do not provide resilience to SCAs. These techniques must be performed in a regular manner to counter most SCAs.
789: = ( − 1) + y z .
Nowadays, cryptography is very often faced with tasks that require the calculation of integer values of arbitrary length. But not all programming languages have built-in tools for such calculations. Hence, you have to either create your solutions or use additional libraries such as GMP, NTL, CLN, MIRACL, etc., which help in calculations with acceptable accuracy.
The independent GMP library, which is one of the fastest libraries and supports most of the latest platforms (Mac OS X/Darwin, GNU/Linux, Windows, and others), has the following advantages [20, 21]: • Practically there are no limits on the accuracy of calculations, except for a limited amount of available memory • user-friendly programming interface • rich set of various functions • supports most modern platforms: Unix-like operating systems such as GNU / Linux, Solaris, HP-UX, Mac OS X / Darwin, BSD, AIX; Windows. There are 32-bit and 64-bit versions of GMP • uses the most efficient algorithms and assembly code optimized for various modern processor systems in all internal cycles.
The main areas of application of the library are cryptographic systems and research, security of internetwork interactions, algebraic packages. The GMP library is part of the GNU Project.
The CLN library, which allows you to perform operations using all existing numeric types, uses GMP as the computing core and is slightly inferior in the speed of calculations [22]. This library implements classes for integers, rational fractions, float numbers, complex numbers, univariant polynomials, modulo calculations. It has a user-friendly interface, a rich set of supported types, transparent mechanisms of interaction, and transformation of various data structures into each other, together with a sufficiently high computation speed, ensure the widespread use of this library. It uses in scientific research by many software products (Octave, maxima, Scilab, etc.).
MIRACL – is a library with a commercial license, which has the following advantages: • rich library of specialized functions for calculations in the field of cryptography on elliptic curves; • availability of implemented C / C++ interfaces and various algorithms for solving problems to choose the optimal option for current needs [23].
The High-performance C ++ NTL library is famous for its high speed in algorithms for factorization and determination of the order of elliptic curves and polynomial arithmetic [24]. NTL represents structure and algorithms for integers, float numbers, polynomials, vectors, and matrices of various lengths and accuracy. All NTL algorithms are implemented in C ++, which ensures the high portability of this library. As a computing core, not only the NTL computing core but also the GMP library.
Since NTL is one of the fastest today, it has been used more than once in setting "world records" in the speed of factorization algorithms and determining the order of elliptic curves. As a library for the implementation of long arithmetic in the C ++ programming language, we will use it.
All algorithms are implemented on an Intel Core i3-2310M dual-core 2.10 GHz processor and 8.00 GB of RAM. The points of each curve are multiplied by 1000 different constants in the range [/2 ; ), where is the order of the point. Also, for the window method, the window size is equal to 23.
Table 1-5 and figure 1 shows the execution time of the algorithms for the scalar point multiplication in the coordinate systems described earlier: Affine, Projective, Jacobian, Chudnovsky Jacobian, and Modified Jacobian.
Tables 1-5 show execution time in seconds of the scalar multiplication in five coordinate systems, using the curve − 192, − 224, − 256, − 384, and − 521 respectively.
For curve − 192 (see, table 1), the best method is VM method showing best time 4.948s for Modified Jacobian coordinate systems and worst time 30.318 for Affine. FE method shows results that are 13.56%- 24.14% worse than WM. NAF method shows results that are 1.63%- 7.72% worse than WM.
For curve − 224 (see, table 2), the best method is VM method showing best time 5.534s for Jacobian coordinate system and worst time 46.301s for Affine. FE method shows results that are 13.91% - 28.66% worse than WM. NAF method shows results that are 2.63%- 7.35% worse than WM.
For curve − 256 (see, table 3), the best method is VM method showing best time 5.534s for Jacobian coordinate system and worst time 46.301s for Affine. FE method shows results that are 13.91% - 28.66% worse than WM. NAF method shows results that are 2.63%- 7.35% worse than WM.
For curve − 384 (see. table 4), the best methods are VM and NAF methods showing best times about 21.131s for Projective coordinate system and worst time 259.123s for Affine. FE method shows results that are 15.78% - 24.94% worse than WM. NAF method shows results that are 0.00% - 7.35% worse than WM.
For curve − 521 (see, table 5), the best methods are VM method showing best times about 36.489s for Chudnovsky Jacobian coordinate system and worst time 786.516s for Affine. FE method shows results that are 14.30% - 24.30% worse than WM. NAF method shows results that are 0.74% - 4.18% worse than WM. 40 35 30 )(s25 e20 im15 T10 5 0
Fast Exponentiation NAF Window method
P-256
Elliptic curve a) Affine Fast Exponentiation NAF Window method
Figure 1 shows that the time grows significantly with increasing the bit size of the curve. Results are obtained with the parameter = 3 in the elliptic curve equation.
Experimental evaluation shows that the WM method is an efficient method of the scalar integer multiplication of an elliptic curve point, especially if there is enough free space in the computer memory (at least for storing 2!! points of the elliptic curve). It gives the better execution time comparing with the Fast Exponentiation and Nonadjacent Form methods in five coordinated systems: Affine, Projective, Jacobian, Chudnovsky Jacobian, and Modified Jacobian.
Acknowledgments. The reported study was funded by RFBR, project number 20-37-70023. [4] Silverman J H 2009 The arithmetic of elliptic curves. (Springer Science and Business Media) v 106 [5] Okeya K, Miyazaki K and Sakurai K 2001 A fast scalar multiplication method with randomized projective coordinates on a Montgomery-form elliptic curve secure against side channel attacks Int. Conf. on Information Security and Cryptology. (Springer, Berlin and Heidelberg) pp 428-39 [6] Cohen H et al. 2005 Handbook of elliptic and hyperelliptic curve cryptography (Chapman and
Hall/CRC) [7] Gutub A A A and Arabia S 2010 Remodeling of elliptic curve cryptography scalar multiplication architecture using parallel jacobian coordinate system Int. Journal of Computer Science and Security (IJCSS) v 4 no. 4 p 409 [8] Gallant R P, Lambert R J and Vanstone S A 2001 Faster point multiplication on elliptic curves with efficient endomorphisms Annual Int. Cryptology Conf. (Springer, Berlin and Heidelberg) pp 190-200 [9] Avanzi R, Cohen H, Doche C, Frey G, Lange T, Nguyen K and Vercauteren F 2005 Handbook of elliptic and hyperelliptic curve cryptography CRC press [10] Daly A, Marnane W, Kerins T and Popovici E 2004 An FPGA implementation of a GF (p) ALU for encryption processors Microprocessors and Microsystems v 28 no. 5-6 pp 253-60 [11] Washington L C 2003 Elliptic curves: number theory and cryptography Discrete Mathematics and Its Applications (Chapman & Hall/CRC) [12] Dormale G M 2007 Destructive and constructive aspects of efficient algorithms and implementation of cryptographic hardware (Catholic University of Louvain, Louvain-laNeuve and Belgium) [13] Trappe W and Washington L C 2007 Introduction to Cryptography [14] Verneuil V 2012 Elliptic curve cryptography and security of embedded devices [15] Galbraith S D, Lin X and Scott M 2011 Endomorphisms for faster elliptic curve cryptography on a large class of curves Journal of cryptology v 24 no. 3 pp 446-69 [16] Molahosseini A S, De Sousa L S and Chang C H 2017 Embedded systems design with special arithmetic and number systems (New York: Springer) p 390 [17] Okeya K and Takagi T 2003 The width-w NAF method provides small memory and fast elliptic scalar multiplications secure against side channel attacks Cryptographers’ Track at the RSA Conf. (Springer, Berlin and Heidelberg) pp 328-43. [18] Taverne J, Faz-Hernandez A, Aranha D F, Rodriguez-Henriquez F, Hankerson D and Lopez J 2011 Speeding scalar multiplication over binary elliptic curves using the new carry-less multiplication instruction Journal of Cryptographic Engineering v 1 no. 3 p 187 [19] Han D G and Takagi T 2005 Some Analysis of Radix-r Representations IACR Cryptology ePrint
[20] Hart W B 2010 Fast library for number theory: an introduction International Congress on
Mathematical Software (Springer, Berlin and Heidelberg) pp 88-91 [21] GMP «Arithmetic without limitation» The GNU Multiple Precision Arithmetic Library (Electronic resource) (Electron. dat. - Access mode: http://gmplib.org/) free Title from the title screen [22] CLN-Class Library for Numbers (Electronic resource) (Electron. dat. - Access mode: http://www.ginac.de/CLN/) free. - Title from the title screen [23] Multiprecision Integer and Rational Arithmetic C/C++ Library (Electronic resource) (Electron.
dat. - Access mode: http://www.shamus.ie/) free. - Title from the title screen. [24] NTL: A Library for doing Number Theory (Electronic resource) (Electron. dat. - Access mode: http://www.shoup.net/ntl/) free. - Title from the title screen. [25] Digital Signature Standard (DSS) (Electronic resource) (Electron. dat. - Access mode: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf) free. - Title from the title screen. [26] Barker E, Mouha N 2017 Recommendation for the triple data encryption algorithm (TDEA) block cipher National Institute of Standards and Technology (no. NIST Special Publication (SP)) pp 800-67 [27] Brown D R L 2010 Standards for efficient cryptography sec 2: Recommended elliptic curve domain parameters Certicom Research, Certicom Corp