Page 70
Scalar multiplication of a point is the central operation in the elliptic curves cryptography (ECC). It’s a complex operation that requires a lot of optimization especially on execution times to reduce resource consumption in systems with low computing power and memory such as embedded systems. Several works on the acceleration of computation and many others on the reduction of the complexity of mathematical methods used in the computations on the elliptic curves have been realized. Many algorithms for computing scalar multiplication are proposed, each using their own calculation technique and mathematical methods. In this paper, we combine the techniques of accelerated computations with optimized mathematical methods and we implement them on algorithms for scalar multiplication of a point. This work aims to distinguish the most efficient computation algorithm with the best acceleration technique. The results show that the Joye algorithm combined with the co-Z DoublingAddition acceleration technique gives better results and saves more than one second of computation time compared to the other algorithms implemented in this paper. Copyright c by the paper’s authors. Copying permitted only for private and academic purposes.
In: Proceedings of the 3rd Edition of the International Conference on Advanced Aspects of Software Engineering (ICAASE18), Constantine, Algeria, 1,2-December-2018, published at http://ceur-ws.org 1
Cryptography has emerged as a reliable and powerful solution for maintaining data confidentiality. To make information eligible, cryptographic mechanisms use complex mathematical methods that often involve intensive computations. This intensity is often a problem for low-resource systems like embedded systems.
There are two ways to encrypt a message; symmetric method (Secret Key Cryptography SKC) based on shared private keys, and asymmetric method (PublicKey Cryptography PKC) based on a couple of public and private keys. The advantage of the latter is that all exchanges are public and its security is based on the difficulty of finding the secret from information exchanged publicly.
One of the most recently used asymmetric cryptosystems is Elliptic Curve Cryptography (ECC). ECC uses short keys for equal security to other asymmetric cryptosystems [MKY16]. It is recommended for systems in which electronic devices have low computing power and very limited memory such as embedded systems.
However, despite recent optimizations on ECC, essentially the reduction of computational complexity, this cryptosystem remains complex and requires further optimization.
The important and costly operation in Elliptic Curve Cryptography for encryption, decryption, digital signature, key exchange, etc is scalar multiplication of a point. This is a complex operation that requires more optimizations for the acceleration of cryptographic computations. The execution time of any ECC operation depends on the execution time of the scalar multiplication.
An embedded system is an autonomous system, generally dedicated to specific tasks, having a limited size and low resources. There are two important constraints of an embedded system: optimized computing power while respecting the temporal and spatial constraints, and an essential security to ensure data confidentiality especially for sensitive applications. The system used The standard algorithm called Dbl-and-add [Knu97] in this work is an Arduino card very limited in memory for calculating scalar multiplication of a point is given resources and computing power. It is an open source by algorithm 1. system, open hardware and open source bootloader.
In this paper, we present an implementation of scalar multiplication algorithms on a low-resource system to compare and derive the most optimized computation method for such systems. We define the scalar multiplication of a point and present some algorithms of its computation, in section 2. Section 3 is dedicated to acceleration techniques of cryptographic computations on a scalar multiplication and to the system of coordinates used. In Section 4, we present the software implementation of acceleration techniques in scalar multiplication algorithms and present the comparison results in Section 5.
Algorithm 1 Standard Dbl-and-add algorithm Require: k = (kd 1,..., k1, k0)2, P 2 E(Fp) Ensure: Q = k P
R0 = 0/ R1 = P for i 1 to d-1 do if ki = 1 then
R0 R0 + R1 end if
R1 2 R1 end for return R0;
This algorithm has a huge disadvantage for the security of the private key used because it is very vulnerable to attacks SPA [MS00] and DPA [KJJ99]. Indeed, by analyzing either the energy consumed or the number of clock cycles performed per operation, an attacker can reconstruct the private key. This fault is corrected by several works [Mon87][Joy07] [LS01][DSF16][FGDM+10], we choose here to work on the algorithms of Mongomery ladder [Mon87] and (1) the algorithm of Joye Dbl-and-add [Joy07] (see algo
rithms 2 and 3). (2) (3) (4)
Algorithm 2 Montgomery ladder algorithm Require: k = (kd 1,..., k1, k0)2, P 2 E(Fp) Ensure: Q = k P
R0 = 0/ R1 = P for i d-1 downto 0 do b ki R1 b
Rb 2 end for return R0;
R1 b + Rb
Rb Algorithm 3 Joye Dbl-and-add algorithm Require: k = (kd 1,..., k1, k0)2, P 2 E(Fp) Ensure: Q = k P
R0 = 0/ R1 = P for i 0 to d-1 do b ki
R1 b + Rb
R1 b end for return R0; 2 2
The basic operation performed in protocols based on Elliptic Curve Cryptography is the scalar multiplication of a point on the curve. Each scalar multiplication requires several thousand operations in a finite field. Let k be a scalar of n bits, P and Q two points of an elliptic curve defined on a finite field F by the Weierstrass equation [Gui13][BJ02]:
E : Y 2 + a1XY + a3 = X 3 + a2X 2 + a4X + a6 where a1, a2, a3, a4 2 F. In this work, we consider the finite prime fields Fp. Equation (1) then becomes:
E : Y 2 = X 3 + aX + b where a, b 2 Fp. The multiplication of the scalar k by the point P of the curve is another point Q s.t Q = k P = P + P + . . . + P (k times).
Two operations are necessary to perform a scalar multiplication: the point doubling P + P = 2P = P’ and the point addition P + P’. The computations of doubling and addition are given by formulas (3) and (4) below. Let P (X1, Y1) and Q (X2, Y2) be two points of the elliptic curve s.t P, Q 2 E (Fp) and P 6= Q : P + P = 2P = (X3, Y3) is computed as follows:
Y3 =
X3 = 3X12 + a 2Y1 3X12 + a 2Y1 2 (X1 2
2X1
X3) Y1 Y4 =
X4 =
Y2 X2
Y2 X2 Y1 X1
Y1 X1 2 2
X1
X2 (X1
X4) Y1 and P + Q = (X4, Y4) is the result of an addition of the two points P and Q is computed as follows: Page 71 The complexity of the computations in scalar multiplication of a point and the large number of point doubling and point addition calculated to perform this operation required a lot of optimization works reduce computations. In this section, we present some algorithms that allow computation accelerations in a scalar multiplication, but before that, we will focus first on the choice of coordinate systems used.
In the Affine coordinate system, the addition and doubling formulas involve point inversion operations in Fp which is considered very expensive on the finite fields. In order to avoid the inversion of points [KS17], we chose to work on the Jacobian coordinates where a point of the curve is represented by three coordinates (X : Y : Z) which corresponds to the Affine point ( ZX2 ; ZY3 ). Equation (2) then becomes:
E : Y 2 = X 3 + aX Z4 + bZ6 (5) The computation of the doubling P + P = 2P = (X3 : Y3 : Z3) and the addition P + Q = (X3 : Y3 : Z3) is given by the table 1.
An additional optimization of the addition, called coZ addition, has been proposed by Meloni [Mel07] where he considers that two entry points share the same Z coordinate. Let P = (X1 : Y1 : Z) and Q = (X2 : Y2 : Z), the addition co-Z of P and Q (with P 6= Q) is defined by P + Q = (X3 : Y3 : Z3) so that :
Y3 = (Y2
X3 = D
Y1)(B (B + C)
X3) E Z3 = Z(X2
X1) (6) where A = (X2 X1)2, B = X1A, C = X2A, D = (Y2 Y1)2 and E = Y1(C-B)
In [Riv11], several algorithms are proposed to perform a scalar multiplication of a point in Jacobian coordinates with Standard Jacobian Formulae and co-Z addition Jacobian Formulae. In Standard Jacobian Formulae, a point doubling 2P is performed by the Jacobian Doubling algorithm, a P + Q point addition by Jacobian Addition and a Doubling-Addition operation (DA) 2P + Q by the Mixed Jacobian Affine algorithm. This last algorithm uses mixed coordinates; a point in Jacobian coordinates and another point in Affine coordinates. In co-Z Jacobian Formulae, a point doubling is computed by the Initial Doubling algorithm (XYcZ-IDBL), an addition by (X;Y)-only co-Z addition (XYcZ-ADD) and a DA by (X;Y)-only co-Z Doubling-Addition (XYcZDA). 4
The various techniques of computational acceleration for point doubling and addition are implemented on the different scalar multiplication algorithms presented above in order to compare the performance of each algorithm with each technique. The algorithms obtained and used as support for our comparisons are presented in the following:
Standard Dbl-and-add with Jacobian doubling and Jacobian addition (see algorithm 4) Standard Dbl-and-add with co-Z Initial doubling and co-Z addition (see algorithm 5) Montgomery ladder with Jacobian doubling and Jacobian addition (see algorithm 6) Montgomery ladder with co-Z Initial doubling and co-Z addition (see algorithm 7) Joye Dbl-and-add with Mixed Jacobian Affine Doubling-Addition (DA) (see algorithm 8) Joye Dbl-and-add with co-Z Doubling-Addition (DA) (see algorithm 9) Algorithm 4 Standard Dbl-and-add with Jacobian doubling and Jacobian addition Require: k = (kd 1,..., k1, k0)2, P 2 E(Fp) Ensure: Q = k P
R0 = 0/ R1 = P for i 1 to d-1 do if ki = 1 then
(R0) Jacobian_addition(R0,R1) end if (R1) Jacobian_doubling(R1) end for return R0; Page 72 Algorithm 5 Standard Dbl-and-add with co-Z Initial doubling and co-Z addition Require: k = (kd 1,..., k1, k0)2, P 2 E(Fp) Ensure: Q = k P
R0 = 0/ R1 = P for i 1 to d-1 do if ki = 1 then
(R1,R0) XYcZ-ADD(R0,R1) end if (R0,R1) XYcZ-IDBL(R0) end for return R0; Algorithm 9 Joye Dbl-and-add with Mixed Jacobian Affine DA Require: k = (kd 1,..., k1, k0)2, P 2 E(Fp) Ensure: Q = k P
R0 = 0/ R1 = P for i 0 to d-1 do b ki (R1 b,Rb) XYcZ-DA(R1 b,Rb) end for return R0; 5
Page 73 notice that the algorithm 9 gives very interesting results with a reduced execution time of 428 ms compared to the algorithm 7 for a 192-bit key and 1102 ms for a 256bit key.
the graph below (see figure 1) gives a global comparison of all implemented algorithms. In this work, we compared the different computational acceleration techniques for scalar multiplication by a point on an embedded system in order to compare them and to distinguish the best method of computing a scalar multiplication in a low-resource system. The hardware used is an Arduino embedded system with a microcontroller limited in resources including memory and computing power. We used Jacobian coordinate system with Standard Jacobian Formulae and co-Z Jacobian Formulae, an improved version of the addition called co-Z addition, since this type of coordinates provides less complex and more efficient computation operations. We Page 74 have implemented acceleration techniques on three al- [KS17] gorithms widely used in practice: the standard Dbl-andadd algorithm, the Montgomery ladder algorithm and the Joye Dbl-and-add algorithm. We found that the Joye Dbl-and-add algorithm widh co-Z Doubling-Addition gives better results if we take into account the level of security offered, unlike the standard algorithm Dbl-andadd which offers a better time but it is very vulnerable [LS01] to SPA and DPA attacks. The time saved for a 256-bit key is more than one second (1102 ms) for scalar multiplication using the Joye Dbl-and-add algorithm coupled with the technique co-Z Doubling-Addition compared to other algorithms implemented in this work. [Mel07] [Gui13]
Aurore Guillevic. Arithmetic of pairings on algebraic curves for cryptography.
PhD thesis, Ecole Normale Supérieure de Paris-ENS Paris, 2013.
Marc Joye. Highly regular right-to-left algorithms for scalar multiplication. In International Workshop on Cryptographic Hardware and Embedded Systems, pages 135–147. Springer, 2007. [BJ02] [DSF16]
Eric Brier and Marc Joye. Weierstraß elliptic curves and side-channel attacks.
In International Workshop on Public Key Cryptography, pages 335–345. Springer, 2002. [MKY16] Giovanni Di Sirio and Giovanni Fontana.
Method for protecting a cryptographic device against spa, dpa and time attacks, [Mon87] August 30 2016. US Patent 9,430,188.
K Keerthi and B Surendiran. Elliptic curve cryptography for secured text encryption. In Circuit, Power and Computing Technologies (ICCPCT), 2017 International Conference on, pages 1–5. IEEE, 2017.
Peter L Montgomery. Speeding the pollard and elliptic curve methods of factorization. Mathematics of computation, 48(177):243–264, 1987.
Rita Mayer-Sommer. Smartly analyzing the simplicity and the power of simple power analysis on smartcards. In International Workshop on Cryptographic Hardware and Embedded Systems, pages 78– 92. Springer, 2000.
Matthieu Rivain. Fast and regular algorithms for scalar multiplication over elliptic curves. IACR Cryptology ePrint Archive, 2011:338, 2011.