Jean-Marc Robert

Christophe Negre

Thomas Plantard

Efficient Fixed Base Exponentiation and Scalar Multiplication based on a Multiplicative Splitting Exponent Recoding

Keywords: RNS, Multiplicative Splitting, Digital Signature, Fixed Base, Modular Exponentiation, Scalar Multiplication, Memory Storage, Efficient Software Implementation. I. INTRODUCTION

Digital Signature Algorithm (DSA) (resp. ECDSA) involves modular exponentiation (resp. scalar multiplication) of a public and known base by a random one-time exponent. In order to speed-up this operation, well-known methods take advantage of the memorization of base powers (resp. base multiples). Best approaches are the Fixed-base Radix-R method and the Fixed-base Comb method. In this paper we present a new approach for storage/online computation trade-off, by using a multiplicative splitting of the digits of the exponent radix-R representation.

We adapt classical algorithms for modular exponentiation and scalar multiplication in order to take advantage of the proposed exponent recoding. An analysis of the complexity for practical size shows that our proposed approach involves a lower storage for a given level of online computation. This is confirmed by implementation results showing significant memory saving, up to 3 times for the largest NIST standardized key sizes, compared to the state of the art approaches.

is a scalar multiplication k • P for P ∈ E(F p ). In order to cover both cases DSA and ECDSA we consider a multiplicative abelian group (G, ×) in which we have to compute g k for g ∈ G and k ∈ N.

In this article we consider the following practical case: a server has to compute a large number of signatures, which involves a large number of exponentiations g k with the same g ∈ G and several random k. We assume that the server has a large cache and RAM (Random Access Memory) so that we can therefore store a large amount of precomputed data to speed-up these exponentiations. In the sequel, by 'offline computation' we mean the data computed only once and used in every signature generation; by 'online computation' we mean the operations required only in a single exponentiation g k for a given k.

The main known methods of the state of the art which take advantage of large amount of precomputed data are the Fixed-base Radix R presented by Gordon in [START_REF] Gordon | A Survey of Fast Exponentiation Methods[END_REF] and the Fixed-base Comb presented by Lim and Lee in [START_REF] Lim | More flexible exponentiation with precomputation[END_REF].

The Fixed-base Radix R method of [START_REF] Gordon | A Survey of Fast Exponentiation Methods[END_REF] precomputes g aR i for 0 ≤ a < R and then, using the radix-R expression of k, we obtain the exponentiation g k with log R (k) multiplications. The Fixed-base Comb method uses a Comb decomposition of k (instead of a radix-R representation) and requires less precomputed data at the cost of some extra squarings. In [START_REF] Mohamed | Improved Fixed-Base Comb Method for Fast Scalar Multiplication[END_REF] the authors provide a variant of the Radix-R approach using the NAF w recoding resulting in a reduced number of online multiplications than for the radix-R approach but with a penalty of some extra squarings.

Contributions. We investigate some new strategies for a better trade-off between storage and online computation in fixed base exponentiation. To reach this goal, we propose to use the representation of the exponent in radix R as k = -1 i=0 k i R i and then compute a multiplicative splitting of each digit k i . Specifically, we use a radix R = m 0 m 1 with pairwise prime m 0 , m 1 . An RNS representation of a digit k i ∈ [0, R[ in {m 0 , m 1 } leads to a splitting into two parts: one part k (0) i which value is at most m 0 and the other k (1) i which value is at most m 1 . We apply this process to all the digits of the radix R representation of the exponent. While processing the exponentiation, the digits k

(1) i are handled with a look-up table and the digits k (0) i are handled with online computation. This approach was part of a preliminary version of this paper published in the proceedings of the WAIFI 2016 conference [START_REF] Plantard | Enhanced Digital Signature Using RNS Digit Exponent Representation[END_REF].

We present a novel approach for the multiplicative splitting of the digits of the exponent: if we choose the radix R as a prime integer, then processing a partial execution of the extended euclidean algorithm, one can re-express a digit k i as product

k i = k (0) i (k (1)
i ) -1 mod R where |k [START_REF]The GNU Multiple Precision Arithmetic Library (GMP[END_REF] i | < c and |k (0) i | < R/c for a fixed c. Again, this splitting can be applied to all digits of the radix R representation of the exponent. The exponentiation algorithms can then be computed with memorizations related to the (k (1) i ) -1 part of the digit splitting and online computation to handle the part k (0) i of the digit splitting. The main advantage of this version with a prime R is that the resulting exponentiation algorithm is constant time, which means that it is robust against timing attacks.

We study the corresponding complexities and storage amounts, and compare the results with the best approaches of the literature for fixed-base modular exponentiation (resp. scalar multiplication) for NIST recommended fields (resp. curves). The metric chosen for a comparison between the proposed algorithms is the following: for a given level of online computation the best approach is the one which has the lowest amount of precomputed data. Using this metric we show that the proposed approach is the more efficient for a large range of practical case. We also implement these approaches in software and we perform tests in order to validate the complexity analysis. Our approaches provide also some flexibility in terms of required storage amount: one can choose the storage amount according to the device resources available and compatible to the global computation load of the system.

Organization of the paper. In Section II, we review the best approaches of the literature for fixed-base exponentiation and we give their complexities and storage requirements. In Section III, we present a multiplicative splitting recoding of the exponent in radix R = m 0 m 1 and a fixed-base exponentiation using this recoding. In Section IV, we present a multiplicative splitting recoding for R prime and the corresponding exponentiation algorithm. In Section V, we compare the complexity results and software implementations of the proposed approach to the best approaches of the literature for modular exponentiation and scalar multiplication. Finally, in Section VI, we give some concluding remarks and perspectives.

II. STATE OF THE ART OF FIXED-BASE EXPONENTIATION

We consider digital signature algorithms based on discrete logarithm in a finite group. The main ones are DSA where the considered group is a subgroup of prime order q in the multiplicative group F * p and ECDSA where the group is the set of point on an elliptic curve E(F p ) [START_REF] Miller | Use of elliptic curves in cryptography[END_REF], [START_REF] Koblitz | Elliptic curve cryptosystems[END_REF]. For the sake of simplicity, in the sequel, we use a generic abelian multiplicative group (G, ×) of order q. The algorithms presented later in this paper extend directly to abelian groups with additive group law like E(F p ). Generating a digital signature consists in computing (s 1 , s 2 ) from a message m ∈ {0, 1} * , a secret integer x and a random integer k as follows

s 1 ← H 1 (g k ), s 2 ← (H 2 (m) + s 1 x)k -1 mod q.
Here, H 1 is a function G → Z/qZ and H 2 is a cryptographic hash function {0, 1} * → Z/qZ. One can see that the most costly operation in a signature generation is the exponentiation g k of a fixed g ∈ G and where k is a one-time random exponent of size ∼ = q. This exponentiation can be done with the classical Square-and-multiply algorithm.

Square-and-multiply exponentiation. The left-to-right version of the square-and-multiply exponentiation scans the bits k i of k from left to right and performs a squaring followed by a multiplication when k i = 1. In terms of complexity, given the bit length t of k, the number of squarings is t -1 and the number of multiplications to be computed is t/2 on average for a randomly chosen exponent. There is no storage in this case.

Side channel analysis. The above method is threatened by side-channel analysis. These attacks extract part of the exponent by monitoring and analyzing the computation time, the power consumption or the electromagnetic emanations. In this paper, we focus on servers which generate large amounts of signature very quickly and are physically not accessible to an attacker. The main threat in this case is the timing attack. This attack attempts to find the sequence of operations (multiplication and squaring) of an exponentiation by a statistical analysis of several timings of an exponentiation. If the assumed sequence of operations is correct, the attacker can deduce the key bits of the exponent since each multiplication corresponds to a bit equal to 1, otherwise the bit is 0. A general solution November 19, 2018 DRAFT Algorithm 1 Left-to-Right Square-and-multiply Exponentiation Require: Let an integer k = (k t-1 , . . . , k 0 ) 2 , and g an element of G.

Ensure:

X = g k 1: X ← 1 2: for i from t -1 downto 0 do 3: X ← X 2 4: if k i = 1 then 5: X ← X • g 6: return (X)
to thwart this attack is to render the sequence of operations not correlated to key bits, which means that we need to remove any if test on the key bits or digits in the exponentiation algorithm.

Fixed base exponentiation. When the base g is fixed, one can precompute in advance some data in order to reduce the number of operations in the online computation of the exponentiation. This is the case when a server has to intensively compute a number of signatures with the same g. For example, the method presented by Gordon in [START_REF] Gordon | A Survey of Fast Exponentiation Methods[END_REF] is a modified square-and-multiply algorithm: one first stores the t successive squarings of g (that is the sequence of g 2 i ), then for a given computation of g k , one has to multiply the g 2 i corresponding to k i = 1. In terms of complexity, given the bit length t of the exponent, one has now no squarings and the number of multiplications is t/2, in average. As counterpart, one has to store t elements of G. We can even further reduce the amount of online computation by increasing the precomputed data. This is the strategy followed by the main approaches of the literature.

Radix-R method. Gordon in [START_REF] Gordon | A Survey of Fast Exponentiation Methods[END_REF] mentions the generalization of his first idea to radix R = 2 w representation of

the exponent k = -1 i=0 k i R i .
This consists in the memorization of the values g a•R j , with a ∈ [0, ..., R -1] and 0 ≤ j < where is the length of the exponent in radix R representation. If we denote w = log 2 (R) then we have = t/w . In this case, the online computation consists of -1 multiplications, for a storage amount of

• R values in G. In the sequel, we will call this approach the Fixed-base Radix-R exponentiation method (see Algorithm 2). This algorithm is constant time as soon as the multiplications by 1 (i.e., when k i = 0) are performed as any other multiplication or, alternatively, by using the radix R recoding of [START_REF] Joye | Exponent Recoding and Regular Exponentiation Algorithms[END_REF] which avoids k i = 0.

Comb method. Another classical method is the so called Fixed-base Comb method which was initially proposed by Lim and Lee in [START_REF] Lim | More flexible exponentiation with precomputation[END_REF]. This method attempts to trade some of the storage of Algorithm 2 with a few online computed squarings. It is based on the following decomposition of the exponent

k k = d-1 j=0 ( w-1 i=0 k id+j 2 id ) Kj 2 j where d = t/w . (1)
Each integer K j can be seen as a comb as described in the following diagram.

Algorithm 2 Fixed-Base Radix-R Exponentiation Require: k = (k -1 , . . . , k 0 ) R , g a generator of G. Ensure: X = g k 1: Offline precomputation. Store T [a][j] ← g a•R j
, with a ∈ [0, ..., R -1] and 0 ≤ j < .

2: X ← 1

3: for i from -1 downto 0 do 4: X ← X • T [k i ][i] 5: return (X)
The integer w is the number of comb-teeth in each K j and d = t/w is the distance in bits between two consecutive teeth. When all the possible values g Kj are precomputed and stored in table indexed by

I Kj = [k (w-1)d+j k (w-2)d+j . . . , k j ] 2 ,
one can compute g k with a 2 w size look-up table, t/w -1 multiplications and t/w -1 squarings using (1).

This method is shown in Algorithm 3. As in the case of Radix-R method, this approach can be implemented in constant time if the multiplications by 1 (which occurs K j = 0) are computed as an arbitrary multiplication or by using the recoding of [START_REF] Hedabou | A comb method to render ECC resistant against Side Channel Attacks[END_REF] which renders all comb coefficients = 0.

Algorithm 3 Fixed-Base Comb Exponentiation [START_REF] Lim | More flexible exponentiation with precomputation[END_REF] Require: k = (k t-1 , . . . , k 1 , k 0 ) 2 , a generator g of G, a window width 2 w and d = t/w .

Ensure: X = g k mod p

1: Offline precomputation. For all (a w-1 , . . . , a 0 ) ∈ {0, 1} w we set a = a w-1

2 (w-1)d + • • • + a 1 2 d + a 0 and T [(a w-1 , . . . , a 0 ) 2 ] = g a . 2: Split k = d-1 j=0 K j 2 j as in (1) 3: X ← 1 4: for j from d -1 downto 0 do 5: X ← X 2 6: X ← X • T [K j ] 7: return (X)
Fixed base exponentiation with NAF w . In [START_REF] Mohamed | Improved Fixed-Base Comb Method for Fast Scalar Multiplication[END_REF], the authors proposed an alternative approach when inverting an element in the group G is almost free of computation and multi-squarings can be computed efficiently. Their main application is the group of points on a elliptic curves where computing the inverse of a point is really cheap. They use a NAF w representation of k in order to reduce the number of multiplications (this generalizes the approach of [START_REF] Tsaur | Efficient algorithms for speeding up the computations of elliptic curve cryptosystems[END_REF] which uses a NAF representation of k). Specifically, they start by computing the NAF w representation of

the exponent k k = k t-1 2 t-1 + k t-2 2 t-2 + • • • + k 0
where k i ∈ {±1, ±3, . . . , ±2 w-1 -1} and there are at least w zero between two non zero coefficients. For more details on NAF w the reader may refer to [START_REF] Hankerson | Software Implementation of Elliptic Curve Cryptography over Binary Fields[END_REF]. Then they rewrite this N AF w (k) into = t/w consecutive windows of w coefficients:

k = i=0       w-1 j=0 k iw+j 2 j Ki       2 iw . (2)
In [START_REF] Mohamed | Improved Fixed-Base Comb Method for Fast Scalar Multiplication[END_REF] the authors noticed that, in each K i , there is at most one non-zero coefficient k iw+j , which means that

K i = s × a × 2 j
for some s ∈ {-1, 1}, a ∈ {1, 3, . . . , 2 w-1 -1} and 0 ≤ j < w. They then reorder the terms in expression (2) by splitting the parameter i into two parts i = i 1 e + i 0 for some fixed integer e:

k = e-1 i0=0 d-1 i1=0 K i1e+i0 2 i1ew+i0w where d = /e = e-1 i0=0 d-1 i1=0 K i1e+i0 2 i1ew 2 i0w . (3)
For all possible values for K i1e+i0 2 i1ew with K i1e+i0 = sa2 j the term

g a2 j+i 1 ew is stored in a Table T [a][i 1 ][j].
Then Algorithm 4 computes g k based on (3) as a sequence of multiplications/divisions (in Step 9 depending on s = 1 or s -1) and w consecutive squarings (in Step 5).

Algorithm 4 Fixed-Base Exponentiation with NAF w [START_REF] Mohamed | Improved Fixed-Base Comb Method for Fast Scalar Multiplication[END_REF] Require: A scalar k = (k t-1 , . . . , k 1 , k 0 ) N AFw and g in an abelian group G, and positive integers c, w.

Ensure: X = g k 1: = t w and d = e 2: Offline precomputation. T [a][i 1 ][j] = g a2 j+ewi 1 for all a ∈ {1, 3, . . . , 2 w-1 -1}, i 1 ∈ {0, . . . , d -1} and j ∈ {0, . . . , w -1}.

3: X ← 1 4: for i 0 from e -1 downto 0 do 5: X ← X 2 w 6: for i 1 from d -1 downto 0 do 7: (s, a, j) s.t. (k jb+t,w-1 . . . k jb+t,0 ) N AF w = s • a • 2 j 8: if a = 0 then 9: X ← X × (T [a][i 1 ][j]) s 10: return (X)
In Algorithm 4 the number of precomputed elements is equal to dw2 w-2 ∼ = t e 2 w-2 . The online computation consists of w(e -1) squarings and ed(1 -( w w+1 ) w ) ∼ = t w (1 -( w w+1 ) w ) multiplications/divisions (cf. [START_REF] Mohamed | Improved Fixed-Base Comb Method for Fast Scalar Multiplication[END_REF] for details).

III. FIXED-BASE EXPONENTIATION WITH MULTIPLICATIVE

SPLITTING WITH R = m 0 m 1
We now present our approach of a Fixed-base exponentiation with multiplicative splitting with R = m 0 m 1 .

In this section, we review the method presented in a preliminary work at WAIFI 2016 [START_REF] Plantard | Enhanced Digital Signature Using RNS Digit Exponent Representation[END_REF]. The goal is to use a multiplicative splitting of the digits of k in order to provide a better trade-off between storage and online computation in the exponentiation.

A. Digit multiplicative splitting for radix R = m 0 m 1 A natural way to get a splitting of the digits is to use the RNS representation in radix R = m 0 • m 1 which splits any digit into two parts. When all the digits of an exponent are split we can process the exponentiation as follows:

the first part of the digits will be used to select the precomputed values and the second part will be processed by online computation.

We first remind the RNS representation in a base B = {m 0 , m 1 }. Let R = m 0 • m 1 and x ∈ Z such that 0 ≤ x < R. Let us also assume m 0 is prime, since this allows us to invert all non-zero integers < m 0 modulo m 0 , and we choose m 1 < m 0 . In the sequel, we denote |x| m = x mod m.

One represents x with the residues

   x (0) = |x| m0 ,
x (1) = |x| m1 , and x can be retrieved using the Chinese Remainder Theorem as follows:

x = x (0) • m 1 • |m -1 1 | m0 + x (1) • m 0 • |m -1 0 | m1 R . (4)
We now present our recoding approach. We consider an exponent k expressed in radix

R = m 0 • m 1 k = -1 i=0 k i R i with = t/ log 2 (R) .
We represent every radix-R digit in RNS with the RNS base

B = {m 0 , m 1 }: if k i is the i-th digit of k in radix-R,
we denote by (k

(0) i , k (1)
i ) its RNS representation in base B    k (0) i = |k i | m0 , k (1) i
= |k i | m1 .
Let us denote

m 0 = m 1 • |m -1 1 | m0 , m 1 = m 0 • |m -1 0 | m1 .
We recode the digits of k in B = {m 0 , m 1 } as follows November 19, 2018 DRAFT

• If k (1) i = 0: we denote    k (0) i = |k (0) i • (k (1) i ) -1 | m0 , k (1) i = k (1) i .
One keeps

k i = k (1) i |k (0) i • m 0 + m 1 | R (5)
as a representation of k i in a multiplicative splitting form and we have k i = |k i | R with (4). When modifying the digits of k as above, one needs to take into account the correcting term due to the reduction modulo R:

k i = k (1) i |k (0) i • m 0 + m 1 | R -k (1) i • |k (0) i • m 0 + m 1 | R /R • R. Let us denote C = k (1) i • (k (0) i • m 0 + m 1 )/R which satisfies 0 ≤ C < m 1 .
We consider C as a carry that one can subtract to k i+1 . This leads to the following computation

if k i+1 ≥ C then k i+1 ← k i+1 -C C ← 0 else k i+1 ← k i+1 + R -C, C ← 1
and one gets k i+1 ≥ 0.

• If k

(1) i = 0: we define k i as follows

k i = |k (0) i + 1| m0 • m 0 + m 1 R ( * ) -|m 0 + m 1 | R =1 . (6)
and k i satisfies |k i | R = k i This expression is meant to have the part ( * ) as in ( 5): the goal is to use the same precomputed data in the exponentiation algorithm. The term

-|m 0 + m 1 | R = -1 is meant to get back to k i while reducing k i modulo R.
We then set the following coefficients:

   k (0) i = |k (0) i + 1| m0 , k (1) i = 0.

Setting k

(1) i = 0 tells us that this is a special case and we get k i from k

(0) i as k i = |k (0) i • m 0 + m 1 )| R -1 R .
We deal with the carry as it was done when k

i=0 kiR i . Ensure: {(k (0) i , k (1) i ), 0 ≤ i < , (C)} the multiplicative splitting recoding of k in radix R = m0m1. 1: C ← 0 2: for i from 0 to -1 do 3: ki ← ki -C, C ← 0 4: if ki < 0 then 5: ki ← ki + R, C ← 1 6: k (0) i ← |ki|m 0 , k (1) i ← |ki|m 1 . 7: if k (1) i = 0 then 8: (k (0) i , k (1) i ) ← (|k (0) i + 1|m 0 , 0) 9: C ← C + |k (0) i • m 0 + m 1 |R -1 /R 10: else 11: k (0) i ← |k (0) i • (k (1) i ) -1 |m 0 12: k (1) i ← k (1) i 13: C ← C + k (1) i • |k (0) i • m 0 + m 1 |R/R 14: return {(k (0) i , k (1) i ), 0 ≤ i < , k = -C} At the end the recoded exponent k = i=0 k i R i has most of its digits k i expressed as a product k (1) i × |k (0) i • m 0 + m 1 | R and k (1) i is of size m 1 while |k (0) i • m 0 + m 1 | R is indexed with k (0) i which is of size m 0 .
Example 1. We present here an example of the m 0 m 1 recoding with an exponent size t of 20 bits (0 < k < 2 20 ), and B = {11, 8} (i.e. m 0 = 11, m 1 = 8). Thus, in this case, one has the radix R = m 0 •m 1 = 88, = 20/ log 2 (88) = 4, and also

m 0 = 8 • |8 -1 | 11 = 56, m 1 = 11 • |11 -1 | 8 = 33.
Let us take k = 936192 10 , the random exponent. By rewriting k in radix-R, one has

k = 48 + 78 • 88 + 32 • 88 2 + 1 • 88 3 .
We now use Algorithm 5, which consists of a for loop (Steps 2 to 13).

• In the first iteration (i = 0), one has k 0 = 48.

-One has C ← 0 and one skips the if-test steps 4 to 5 since k 0 ≥ 0.

-Step 6, one computes the RNS representation in base B of k 0 = 48:

k (0) 0 = |k 0 | 11 = 4, k (1)
0 = |k 0 | 8 = 0.
-Steps 7 to 9, since k

(1) 0 = 0, one sets

(k (0) 0 , k (1)
0 ) ← (|k

(0) 0 + 1| 11 , 0) = (5, 0).
November 19, 2018 DRAFT and the carry

C ← C + |k (0) 0 • 56 + 33| 88 -1 /88 = 0
• In the second iteration (i = 1), one has k 1 = 78.

-One has C ← 0 and one skips the if-test of Steps 4 to 5 since k 1 ≥ 0.

-Step 6, one computes the RNS representation in base B of k 1 = 78:

k (0) 1 = |k 1 | 11 = 1, k (1)
1 = |k 1 | 8 = 6.
-Steps 10 to 13, since k

1 = 0, one has

|(k (1) 1 ) -1 | 11 ← 2 k (0) 1 = |k (0) 1 • (k (1) 1 ) -1 | 11 ← 2 k (1) 1 = k (1) 1 ← 6 C ← (k (1) 1
• |k

(0) 1 • 56 + 33| 88 )/88 ← 3 • In the third iteration (i = 2), one has now k 2 ← k 2 -C = 29. -The RNS representation in base B of k 2 is k (0) 2 = 7, k (1)
2 = 5. -The Steps 10-13 give C ← 2, and

(k (0) 2 , k (1)
2 ) ← [START_REF] Gordon | A Survey of Fast Exponentiation Methods[END_REF][START_REF] Bosselaers | Comparison of Three Modular Reduction Functions[END_REF].

Without providing all the remaining details, one finally obtains the values returned by the algorithm:

((5, 0), [START_REF]Explicit Formula Database[END_REF][START_REF] Brown | Software implementation of the NIST elliptic curves over prime fields[END_REF], [START_REF] Gordon | A Survey of Fast Exponentiation Methods[END_REF][START_REF] Bosselaers | Comparison of Three Modular Reduction Functions[END_REF], [START_REF] Bernstein | Faster addition and doubling on elliptic curves[END_REF][START_REF] Doche | On the Enumeration of Double-Base Chains with Applications to Elliptic Curve Cryptography[END_REF]), and k 4 = -C = -2.

B. Exponentiation with a multiplicative splitting recoding in

radix R = m 0 m 1
We first rewrite the exponentiation using the recoding of k = i=0 k i R i of the previous subsection as follows:

g k mod p = g i=0 k i •R i = g k •R • -1 i=0 g k i •R i (7)
where each term g k i •R i satisfy one of the following three cases:

• When k (1) i
= 0 and i < :

g k i •R i = g k (1) i •R i •|k (0) i •m 0 +m 1 | R • When k (1) i
= 0 and i < :

g k i •R i = g R i •|k (0) i •m 0 +m 1 | R • g -R i . • when i = we have k ≤ 0 which implies that g k R = (g -R ) |k | .
In order to compute the fixed-base exponentiation g k , one stores the following values:

T [i][j] = g R i •|j•m 0 +m 1 | R , with    0 ≤ i ≤ -1, 0 ≤ j < m 0 .
and one also stores the following inverses:

T [i][-1] = g -R i with 0 ≤ i ≤ .
We use Y j to denote the product of g

R i •|k (0) i •m 0 +m 1 | R for each i such that k (1) i = j.
In other words for j = 0

Y j =    for k (1) i =j,i< T [i][k (0) i ] • T [ ][-1] if |k | = j, for k (1) i =j,i< T [i][k (0) i ] ,
and

Y 0 = for all k (1) i =0,i< T [i][k (0) i ] × T [i][-1].
We can then rewrite the expression of g k in [START_REF] Doche | On the Enumeration of Double-Base Chains with Applications to Elliptic Curve Cryptography[END_REF] in terms of Y j for j = 0, . . . , m 1 -1 as follows:

g k = Y 0 × m1-1 j=1 Y j j .
Each individual exponentiation Y j j is performed with a square-and-multiply approach, which is more efficient than performing j -1 multiplications, even for small m 1 . This approach is depicted in Algorithm 6.

One important drawback of the above algorithm is that it is not constant time, due to the if branching attached to the condition k

(1) i = 0.
Example 2. We present the computation of g k mod p using Algorithm 6, we take B = {11, 8} (i.e. m 0 = 11, m 1 = 8). In terms of storage, one computes the values

T [i][j] = g R i •|j•m 0 +m 1 | R mod p with 0 ≤ i ≤ -1.
One has the values {33, 1, 57, 25, 81, 49, 17, 73, 41, 9, 65} for |j • m 0 + m 1 | R when 0 ≤ j < 11. This leads to

T [i][0..10] = {g 88 i •33 , g 88 i , g 88 i •57 , g 88 i •25 , g 88 i •81 , g 88 i •49 , g 88 i •17 , g 88 i •73 , g 88 i •41 , g 88 i •9 , g 88 i •65 }.
The trace of Algorithm 6 for the computation of g k and k = 936192 using the recoding obtained in Example 1 is provided in Table I.

C. Complexity

For the amount of precomputed data, one can notice that it is equal to (m 0 + 1) × + 1 elements.

The complexity of online computation in Algorithm 6 is evaluated step by step in Table III for the average case.

The number of multiplications (M) is evaluated as follows:

• The costs of Steps 6 to 15 follow directly from Algorithm 6 and are detailed in Table III.

• The first squaring in Step 18 skipped since X = 1, leading to a cost of W -1 squarings.

• The multiplications in Steps 21 and 22 are performed only in case of Y j = 1. This means that in the worst case we save the first multiplication which is an affectation : this is the case considered in Table III.

For the sake of simplicity, we denote by H the sum of the j Hamming weights for each j from m 1 -1 downto 1 Require: An RNS base {m0, m1}, a radix R = m0m1, the exponent k = -1 i=0 kiR i and {(k

(for loop in Step 1c ¸). The value of H is shown in

(0) i , k (1) i
), 0 ≤ i < , (k )} the m0m1 recoding of k and g ∈ G.

Ensure:

A = g k 1: Offline precomputation. Store T [i][j] ← g R i •|j•m 0 +m 1 | R with 0 ≤ i < , 0 ≤ j < m0, T [i][-1] ← g -R i , 0 ≤ i ≤ 2: X ← 1, Yj ← 1 for 0 ≤ j < m1 3: for i from 0 to -1 do 4: if k (1) i = 0 then 5: if Y0 = 1 then 6: Y0 ← T [i][k (0) i ] × T [i][-1] 7: else 8: Y0 ← Y0 × T [i][k (0) i ] × T [i][-1] 9: else 10: if Y k (1) i = 1 then 11: Y k (1) i ← T [i][k (0) i ] 12:
else 13:

Y k (1) i ← Y k (1) i × T [i][k (0) i ] 14: if k = 0 then 15: Y |k | ← Y |k | × T [ ][-1] 16: W ← size of m1 in bits 17: for i from W -1 downto 0 do 18: X ← X 2 19:
for j from m1 -1 downto 1 do 20:

if bit i of j is non zero then 21:

X ← X × Yj 22: return (X × Y0)

IV. FIXED BASE EXPONENTIATION WITH MULTIPLICATIVE SPLITTING WITH R PRIME

In this section we present a novel recoding algorithm based on multiplicative splitting modulo R prime. We will show that the resulting exponentiation algorithm can be made constant time.

A. Digit multiplicative splitting for prime radix R

We present in this subsection a variant of the multiplicative splitting to the case of a prime radix R. When R is a prime we can use a multiplicative splitting modulo R based on an extension of the half-size multiplicative splitting of [START_REF] Negre | Efficient regular modular exponentiation using multiplicative half-size splitting[END_REF]. Our goal is to get the following splitting

k i = k (0) i (k (1) i ) -1 mod R with    |k (0) i | < c |k (1) i | ≤ R/c (8)
for a fixed bound 0 < c < R.

) i = 0 k (0) 0 = 5 k (1) 0 = 0 6: Y 0 ← T [0][k (0) 0 ] × T [0][-1] = g 49 × g -1 = g 48 i = 1 k (0) 1 = 2 k (1) 1 = 6
11:

Y 6 ← T [1][k (0) 1 ] = g 88•57 = g 5016 i = 2 k (0) 2 = 8 k (1) 2 = 5 11: Y 5 ← T [2][k (0) 2 ] = g 88 2 •41 = g 317504 i = 3 k (0) 3 = 3 k (1) 3 = 7
11:

Y 7 ← T [3][k (0) 3 ] = g 88 3 •25 = g 17036800 - - 15: T 2 ← T [4][-1] = g 88 4 •(-1) = g -59969536 - - 17:
to 22: 1) Multiplicative splitting modulo a prime R: The multiplicative splitting modulo a prime radix R is based on the extended Euclidean algorithm. We briefly review this algorithm. We consider a prime integer R and 0 < k < R.

g k = Y 0 × m 1 -1 j=1 Y j j = g 48 g 2•(-59969536) ×g 5•317504 ×g 6•5016 g 7•17036800 = g 936192
Then k and R are pairwise prime gcd(k, R) = 1. The Euclidean algorithm computes gcd(k, R) through a sequence of modular reductions:

r 0 = R, r 1 = k, r 2 = r 0 mod r 1 , . . . . . . , r j+1 = r j-1 mod r j , . . .
The sequence of remainders r j satisfies gcd(r j , r j+1 ) = gcd(R, k)

and is strictly decreasing and thus reaches 0 after some iterations. The last r = 0 satisfies r = gcd(k, R) = 1.

The extended Euclidean algorithm computes a Bezout relation

uR + vk = gcd(k, R)

Complexity

Step Operation Cost

1× Step 6 T [i][k (0) i ] × T [i][-1] 1 M ( /m1 -1)× Step 8 Y0 × T [i][k (0) i ] × T [i][-1] 2 M (m1 -1)× Step 11 - - ( m 1 -1 m 1 -(m1 -1)) × Step 13 Y k (1) i × T [i][k (0) i ] 1 M 1× Step 15 Y |k | × T [ ][-1] 1 M (W -1)× Step 18 X ← X 2 1 S (H -1)× Step 21 X × Yj 1 M 1× Step 22 (X × Y0) 1 M TOTAL ( m 1 +1 m 1 -m1 + H + 1) M +(W -1) S TOTAL STORAGE (m0 + 1) × + 1 elements of G
by maintaining two sequences of integers u j and v j satisfying:

u j R + v j k = r j , for j = 0, 1, . . . , . (9)
The sequence v j is an increasing sequence in magnitude starting from v 0 = 0 and v 1 = 1. The multiplicative splitting of (8) can then be obtained from [START_REF] Hankerson | Software Implementation of Elliptic Curve Cryptography over Binary Fields[END_REF] where we take j such that r The proof of the lemma is given in the appendix.

This leads to the method shown in Algorithm 7 for multiplicative splitting modulo a prime radix R. In this algorithm a third variable s is used for the sign of the multiplicative splitting.

2) Recoding the exponent: We now present our recoding approach for an integer k given in radix-R representation:

k = -1 i=0 k i R i , with = t/ log 2 (R) .
We choose a splitting bound c and we consider a digit k i = 0. Using Algorithm 7 we get s i , k (0) i and k

(1) i such that

k i = s i k (0) i (k (1) i ) -1 mod R with          s i ∈ {-1, 1} k (0) i ∈ [0, c[, k (1)
i Require: k ∈ Z, the prime radix R, and c, the upper bound for k

∈ [0, R/c]. (10)
i . Ensure: (s, k (0) , k (1) ), such as k = |s × k (0) × (k (1) ) -1 |R with 0 ≤ k (0) < c and 0 ≤ k (1) ≤ R/c and s ∈ {-1, 1} when gcd(k, R) = 1.

1: if gcd(k, R) = R then 2:
return (1, 0, 0)

3: else 4: u0 ← 1, v0 ← 0, r0 ← R, u1 ← 0, v1 ← 1, r1 ← |k|R 5:
while (r1 ≥ c) do

6: q ← r0/r1 , r2 ← |r0|r 1 7: u2 ← u0 -q • u1, v2 ← v0 -q • v1 8:
(u0, v0, r0) ← (u1, v1, r1) 9:

(u1, v1, r1) ← (u2, v2, r2)

10: s ← sign(v1), k (0) ← r1, k (1) ← |v1| 11:
return (s, k (0) , k (1) )

We put apart the case k i = 0 which is recoded as (1, 0, 0) (cf. Step 2 of Algorithm 7). We handle the reduction modulo R as follows:

C = (s i k (0) i |(k (1)
i

) -1 | R -k i )/R (exact quotient), k i = s i k (0) i |(k (1) i ) -1 | R -CR.
One notices that C satisfies -c ≤ C < c. We then consider C as a carry that we subtract to k i+1 .

We obtain an expression

k = i=0 k i R i of k in radix R such that each digit k i = s i k (0) i |(k (1) i ) -1 | R is
0) i , k (1) i ), 0 ≤ i < , (k )} the multiplicative splitting recoding of k. 1: C ← 0 2: for i from 0 to -1 do 3: ki ← ki -C 4: si, k (0) i , k (1) i ← TruncatedEEA(ki, R, c). 5: C ← (sik (0) i |(k (1) i ) -1 |R -ki)/R //exact quotient 6: return {(si, k (0) i , k (1) i ), 0 ≤ i < , (k = -C)} (
Example 3. We present an example of multiplicative splitting recoding for a prime radix R = 89 with an exponent size t of 20 bits (0 < k < 2 20 ). In this case, one has = 20/ log 2 (89) = 4. One also sets c = 2 3 = 8, and then, R/c = 12. Let us take k = 901644 10 , the random exponent. By rewriting k in radix-R, one has

k = 74 + 73 • 89 + 24 • 89 2 + 1 • 89 3 .
The execution trace of Algorithm 8 is provided in Table IV. ALGORITHM 8 Iter.

Step Value

i = 0 3: k 0 = 74 does not change since C = 0 4: s 0 = -1, k (0) 0 = 1, k (1)
0 = 6. 5: C ← (s 0 • k (0) 0 • |(k (1) 0 ) -1 | R -k 0 )/R = -1 i = 1 3: k 1 ← 73 + 1 = 74 since C = -1 4: s 1 = -1, k (0) 1 = 1, k (1)
1 = 6. 5: C ← (s 1 • k (0) 1 • |(k (1) 1 ) -1 | R -k 1 )/R = -1 i = 2 3: k 2 ← 24 + 1 = 25 since C = -1 4: s 2 = -1, k (0) 2 = 3, k (1)
2 = 7. 5: C ← (s 2 • k (0) 2 • |(k (1)
2

) -1 | R -k 2 )/R = -2 i = 3 3: k 3 ← 1 + 2 = 3 since C = -2 4: s 3 = 1, k (0) 3
= 3, k (1) 3
= 1. 5: C ← (s 3 • k (0) 3 • |(k (1)
3

) -1 | R -k 3 )/R = 0 ((-1, 1, 6), (-1, 1, 6), (-1, 3, 7), (1, 3, 1)) and k 4 = C = 0

B. Exponentiation Algorithm with multiplicative splitting recoding in a prime radix R

We now present an exponentiation algorithm which takes advantage of the exponent recoding given in Section IV-A2. One wants to compute

g k = g i=0 k i •R i = g k •R • -1 i=0 g k i •R i (11)
with

g k i •R i = g si•k (0) i •|(k (1) i ) -1 | R •R i , if k (1) i = 0, g k i •R i = 1, if k (1) i
= 0(this corresponds to k i = 0).

In order to compute the fixed-base exponentiation g k mod p, one stores the following values:

T [i][s][j] = g R i •s•|j -1 | R , with          0 ≤ i ≤ -1, 1 ≤ j ≤ R/c , s ∈ {-1, 1}. T [i][s][0] = 1 with s ∈ {-1, 1}. T [ ][s] = g sR with s ∈ {-1, 1}.
November 19, 2018 DRAFT One denotes Y j the product of the terms

g si•|(k (1) i ) -1 | R •R i such that of k (0) i = j. This means that for j = |k | Y j =    k (0) i =j T [i][s i ][k (1) i ]    .
and for j = |k | one has

Y j =    k (0) i =j T [i][s i ][k (1) i ]    × T [ ][sign(k )].
We can then rewrite the products in [START_REF] Joye | Exponent Recoding and Regular Exponentiation Algorithms[END_REF] in terms of Y j as follows:

g k = j∈{1,...,c-1} Y j j .
Every individual exponentiation Y j j is performed with a square-and-multiply approach, which is more efficient than performing j -1 multiplications, even for small c. This finally leads to the exponentiation shown in Algorithm 9.

Algorithm 9 Fixed-base exponentiation with multiplicative splitting for prime radix R Require: R a prime integer, an exponent k = -1

i=0 kiR i and {(si, k (0) i , k (1) i ), 0 ≤ i < , k } the multiplicative splitting recoding in radix R of k and g ∈ G. Ensure: X = g k 1: Offline precomputation. For 0 ≤ i ≤ -1, 1 ≤ j ≤ R/c , s ∈ {-1, 1} store T [i][s][j] ← g R i •s•|j -1 | R and T [i][s][0] ← 1 for 0 ≤ i ≤ -1, s ∈ {-1, 1} and T [ ][s] ← g sR for s ∈ {-1, 1}. 2: X ← 1, Yj ← 1 for 0 ≤ j ≤ c 3: for i from 0 to -1 do 4: Y k (0) i ← Y k (0) i × T [i][si][k (1) i ] 5: Y |k | ← Y |k | × T [ ][sign(k )] 6: W ← size of c in bits 7: for i from W -1 downto 0 do 8: X ← X 2 9:
for j from c -1 downto 1 do 10:

if bit i of j is non zero then 11: X ← X × Yj 12: return (X)
The above algorithm can be implemented in a constant time fashion. Indeed there is no if control attached to the digits of the exponent. Then, the algorithm consists in a constant and regular sequence of multiplications and squarings as soon as a multiplication with a 1 is computed as any other multiplication.

We present the computation of g k using Algorithm 9. In terms of storage, one computes the values

T [i][s][j] = g R i •s•|j -1 | R with          0 ≤ i ≤ -1, 1 ≤ j ≤ R/c = 12, s ∈ {-1, 1}.
One has the following values of j -1 R for 1 ≤ j ≤ 12 {1, 45, 30, 67, 18, 15, 51, 78, 10, 9, 81, 52}.

This brings us to store the following values in G:

T [i][1] = {g 89 i , g 89 i •45 , g 89 i •30 , g 89 i •67 , g 89 i •18 , g 89 i •15 , g 89 i •51 , g 89 i •78 , g 89 i •10 , g 89 i •9 , g 89 i •81 , g 89 i •52 } T [i][-1] = {g -89 i , g -89 i •45 , g -89 i •30 , g -89 i •67 , g -89 i •18 , g -89 i •15 , g -89 i •51 , g -89 i •78 , g -89 i •10 , g -89 i •9 , g -89 i •81 , g -89 i •52 }.
The execution of Algorithm 9 is shown step by step in Table V

s 0 = -1 k (0) 0 = 1 k (0) 0 = 6 Y 1 ← Y 1 × T [0][s 0 ][k (1)
0 ] = 1 × g -15 i = 1 4:

s 1 = -1 k (0) 1 = 1 k (1) 1 = 6 Y 1 ← Y 1 × T [1][s 1 ][k (1)
1 ] = g -15 × g -89•15 = g -1350 i = 2 4:

s 2 = -1 k (0) 2 = 3 k (1) 2 = 7 Y 3 ← Y 3 × T [2][s 3 ][k (1) 2 ] = 1 × g -89 2 •51 = g -403971 i = 3
4: - For the online complexity, we evaluate the cost of each step of Algorithm 9 based on the following:

s 3 = 1 k (0) 3 = 3 k (1) 3 = 1 Y 3 ← Y 3 × T [3][s 3 ][k (1) 3
] = g -403971 × g 89 3 •1 = g 300998 - 5: k 4 = 0 Y 0 ← Y 0 × T [ ][sign(k 4 )] = g 59969536
g k = c-1 j=1 Y j j = g
• the multiplications in Step 4 are performed even in case of Y k (0) i = 1, in order to ensure the constant time of the computation;

• the same applies for Step 5.

The number of operations in the final reconstruction is evaluated as follows:

• the squaring in Step 8 is not performed in the first loop iteration (X = 1);

• This first multiplication in Step 11 is skipped since it is an affectation. The other multiplications in Step 11 are performed even in case of Y j = 1, again to ensure a constant computation time.

We denote by H the sum of the j Hamming weights for each j from c -1 downto 1 (for loop in Step 7). The value of H is as follows for the different values of c can be found in Table II.

The contribution of each step is given in Table VI along with the total complexity.

Complexity

Step Operation Complexity

× Step 4 Y k (0) i × T [i][si][k (1) i ] 1 M 1× Step 5 Y |k | × T [ ][sign(k )] 1 M (W -1)× Step 12 X 2 1 S (H -1)× Step 15 X × Yj 1 M TOTAL ( + H) M +(W -1) S TOTAL STORAGE 2( R/c + 1) + 2 elements of G

V. COMPLEXITY AND EXPERIMENTATION COMPARISON

A. Complexity comparison

In Table VII we give the complexities in terms of the number of online operations and storage amount of the state of the art approaches (Section II) and the two proposed approaches in Section III and IV. All the approaches presented in the above table can be implemented in constant time except the Square-and-multiply, Fixed base NAF w and the proposed approach with R = m 0 m 1 .

Let us first see when the Fixed-base Comb method is better than the Fixed-base Radix-R exponentiation. We denote w C the window size of the Comb method and w R the one of the Radix-R method. In order to have both methods with the same number of online operations in G, we take w C = 2w R : in this case, both methods require t/w R online operations in G. Then, considering the storage amount when w C = 2w R , one can see that the Comb method requires 2 2w R while the Radix-R method needs t w R 2 w R elements of G. In other words, for a fixed number

) (e -1)w t e 2 w-2 Proposed ( * ) with R = m 0 m 1 (Algo. 6) no t w m 1 +1 m 1 -m 1 + H + 1 W -1 (2 w /m 1 + 1) t w + 1 Proposed ( * ) with R prime (Algo. 9) yes t w + H W -1 (2 w+1 /c + 1) t w + 1 ( * )
We assume that R is a w bit integer t/w R of online computation, the Comb method is better than the Radix-R as soon as 2 w R < t w R which is the case for small w R , i.e., for small amount of storage.

If we now consider the Fixed base NAF w , we can notice that it does not compare favorably with the radix-R approach. Indeed for e = 1 we would have almost the same number of online multiplications whereas the amount of data in the NAF w is larger by a factor of w. For larger value of e the number of squarings would increase quickly rendering the approach not competitive. Moreover the Fixed base NAF w has the major drawback to not be constant time.

It is more difficult to formally compare the proposed approaches with the Comb and Radix-R approaches. Indeed, they involve a third parameter (c or m 1 ), which means that for a fixed number of online operations, we would have to find the proper parameter which minimizes the amount of storage. We can still notice that for a given c (resp. m 1 ) we divide by c (resp. m 1 ) the amount of storage compared to the Radix-R approach while having an increase of online computation (H and W ). This means that the proposed approaches can be competive only for small c and m 1 .

To have a clearer idea of the impact of the proposed approach so we follow the strategy used in [START_REF] Mohamed | Improved Fixed-Base Comb Method for Fast Scalar Multiplication[END_REF]. Indeed, for practical sizes of group and exponent and for different level of online operations, we evaluate the best choice of parameters which minimizes the amount of precomputation. In the sequel we give the results for DSA and ECDSA, for the fields and curves recommended by the NIST.

B. Complexities and timings for modular exponentiation

In this subsection we focus on exponentiation in ((Z/pZ) * , ×) used in DSA. We evaluate and compare the complexities of the best method of the literature, i.e., Fixed-base Comb (Algorithm 3) and Fixed-base Radix-R (Algorithm 2), with the complexity of our proposed approaches based on a multiplicative splitting recoding of the exponent (Algorithm 6 for R = m 0 m 1 and Algorithm 9 for R prime).

In the sequel of this subsection, we provide complexity evaluations in terms of modular multiplications MM, under the assumption of modular squaring MS = 0.86 MM, which is the average value of our implementations for the NIST DSA recommended field sizes. We warn the reader to keep in mind that the Fixed-base Comb, Radix-R and Algorithm 9 are constant time, and that Algorithm 6 is not, i.e., the only one weak against timing attacks.

The NIST provides recommended key sizes and corresponding field sizes (respectively the size of the primes q and p, see NIST SP800-57 [START_REF] Blank | Recommendation for Key Management[END_REF]). This standardized sizes are as follows: Fig. 1 gives the general behavior of the four algorithms in terms of storage (y axis) with respect to the number of online operations (x axis). In the figure, we present three of the field sizes recommended in the NIST standards (see [START_REF] Blank | Recommendation for Key Management[END_REF]) and the behavior is roughly the same for all sizes, although the benefit of our approach with R = m 0 m 1 is lower for smaller sizes. One can see that the Fixed-base Comb method is the best for small storage amount. Our m 0 m 1 approach (Algorithm 6) is better for larger amount of storage, however, the Fixed-base Radix-R method is the best when the storage is increasing. One can see that the R prime multiplicative splitting approach (Algorithm 9) is less efficient than the R = m 0 m 1 for small storage amounts. The reason is that this requires some additional computations to get a constant time execution, while the m 0 m 1 approach is not constant time and is thus slightly more efficient. Nevertheless, one can see a range of storage/complexity trades-off where the R prime multiplicative splitting approach is the best of the constant-time ones.

Table IX shows numerical application of the complexity comparison between the Fixed-base Comb (Algorithm 3), the Fixed-base Radix-R (Algorithm 2) and the approaches based on our multiplicative splitting recodings (Algorithm 6 and Algorithm 9). For an equivalent number of MMs, we provide the minimum amount of storage.

We can notice the following:

• For all key sizes, we do not provide the results for small amount of storage (values for w < 8). For such storage, the Fixed-base Comb method is the best. One may notice that the Fixed-base Radix-R approach involves the largest storage amount at this complexity level.

• Comparison of the two proposed approaches: R = m 0 m 1 vs R prime. We would like to evaluate the improvements provided by the new approach (Algorithm 9) compared to (Algorithm 6) which was presented at November 19, 2018 DRAFT IX show that the exponentiation with multiplicative splitting with R = m 0 m 1 and R prime are close from each other. But the approach with R = m 0 m 1 is generally slightly better than the one with R prime. But, as noticed earlier, this is the price to pay to get a constant-time algorithm.

• Comparison of constant time approaches. We consider the Fixed-base Comb, Radix-R and multiplicative splitting with R prime approaches. A thorough analysis of the complexities shows that the proposed approach is interesting for intermediate level of online computation. Specifically from Table IX, for a 224 bit key size, one notices that there are not many cases where the proposed multiplicative splitting approach is interesting. However, for the other key sizes t = 256, 384 and 512, one can see a lot of cases where the amount of storage is reduced by 50% compared to Comb and Radix-R approaches.

Remark 1. One may notice that the largest memory storage sizes exceed the common values of Random Access Memory, and in some cases, the maximum allowed for the malloc function of the standard C library for memory allocation. Nevertheless, the storage savings proposed by our method and Fixed-base Radix-R ones allow to keep the level of storage under the limit for lower complexities. 1) Implementation results: Implementation strategies. We review hereafter the main implementation strategies and test process for modular exponentiation for NIST recommended sizes. This applies for the four considered exponentiation algorithms. The algorithms were coded in C, compiled with gcc 4.8.3 and run on the same platform.

• Multi-precision multiplication and squaring. We used the low level functions performing multi-precision multiplication and squaring of the GMP library as building blocks of our codes (GMP 6.0.0, see GMP library [START_REF]The GNU Multiple Precision Arithmetic Library (GMP[END_REF]). According to the GMP documentation, the classical schoolbook algorithm is used for small sizes, and Karatsuba and Toom-Cook subquadratic methods for size ≥ 2048 bits.

• Modular reduction. This operation implements the Montgomery representation and modular reduction method, which avoid multi-precision division in the computation of the modular reduction. This approach was presented by Montgomery in [START_REF] Montgomery | Modular Multiplication Without Trial Division[END_REF]. We use the block Montgomery algorithm suggested by Bosselaers et al. in [START_REF] Bosselaers | Comparison of Three Modular Reduction Functions[END_REF]. In this algorithm, the multi-precision operations combine full size operand with one word operand and are also available in the GMP library [START_REF]The GNU Multiple Precision Arithmetic Library (GMP[END_REF].

• Multiplicative splitting recoding with R = m 0 m 1 and R prime. The conversion in radix-R needs multiprecision divisions. These operations are implemented using the GMP library [START_REF]The GNU Multiple Precision Arithmetic Library (GMP[END_REF]. The size of these operations is decreasing along the algorithm, and this is managed through GMP. The other operations are classical long integer operations. At Step 11 in Algorithm 5 (resp.

Step 5 in Algorithm 8), an inversion modulo m 0 (resp.

R) is required. This operation is performed using the Extended Euclidean Algorithm, over long integer data.

For the considered exponent sizes, the cost of the recoding is negligible. This is explained by the small size of the exponent in comparison with the size of the data processed during the modular exponentiation (see Table VIII). The timings given in the next subsection include this recoding.

• Test processing. The tests involve a few hundred datasets, which consist of random exponent inputs and an exponentiation base with the precomputed stored values. We compute 2000 times the corresponding exponentiation for each dataset and keep the minimum number of clock cycles. This avoids the cold-cache effect and system issues. The timings are obtained by averaging the timings of all datasets.

Tests results and comparison. The four considered exponentiation algorithms were coded in C, compiled with gcc 4.8.3 and run on the following platform: the CPU is an Intel XEON E5-2650 (Ivy bridge), and the operating system is CENTOS 7.0.1406. On this platform, the Random Access Memory is 12.6 GBytes. One notices that the performance results include the Radix-R recoding and the multiplicative splitting of the digits for R = m 0 , m 1 and R prime.

We show the performance results in Fig. 2 which gives a global overview. The implementation results confirm the complexity evaluation, for key sizes of 224, 256, 384, and 512 bits. However, the best results are for 384 and 512 bits.

In Table X, we provide the most significant results. The gains shown are roughly in the same order of magnitude as the one of the complexity evaluation. In particular, for the largest key size (512 bits), the storage of our approach with R = m 0 m 1 is nearly times less than the one required with the Fixed-base Comb method, and nearly 14% less than the one required for the Fixed-base Radix-R method, for the same level of clock-cycles. In the same time, our approach with R prime gives equivalent results for low levels of storage, and better results for higher levels of storage.

C. Complexities and timings for scalar multiplication

In this subsection, we present complexity results and timings of the fixed base scalar multiplication over elliptic curves recommended by NIST.

1) Complexity comparison:

In the fixed-base elliptic curve scalar multiplication case, the main difference with the modular exponentiation is the negligible cost of the inversion of a group element (i.e. an elliptic curve point).

This allows to half the memory requirements, by only storing the points corresponding of the positive sign s i in the recoded coefficients. We provide in appendix A the version of the scalar multiplication algorithm with multiplicative splitting with R prime which takes advantage of a cheap point subtraction.

When computing the complexities, we noticed that the approach using a multiplicative splitting recoding with R = m 0 m 1 was never better than the one with R prime. In addition, the approach with R = m 0 m 1 does not provide a constant time computation. That is why we do not consider the approach with R = m 0 m 1 in remainder of this subsection. Specifically, we only deal with constant-time approaches: Fixed-base Comb, Radix-R and multiplicative splitting with R prime.

We compare explicit complexities for practical situations, which are the three elliptic curves standardized by NIST: P256, P384, P521. One can find in [START_REF] Kerry | Digital Signature Standard (DSS)[END_REF] the Weierstrass curve equations of these three NIST curves which are reviewed in the appendix. For the arithmetic on these curves, we use the Jacobian coordinate system, which provides the fastest curve operations. We use the complexities in terms of operations in F p of point addition and doubling for a Weierstrass curves of [START_REF]Explicit Formula Database[END_REF] to derive the complexity of the considered fixed-base scalar multiplication.

The complexities of the curve operations in terms of the number of modular multiplications (MM) and squarings (MS) are as follows: Addition: 12M M + 4M S,

Doubling: 4M M + 4M S, Mixed-Addition: 7M M + 4M S.
The resulting complexities of the considered scalar multiplication approaches are reported in Table XI and Fig. 3 assuming that M S = 0.8M M .

Fig. 3 gives the general behavior of the storage for a given amount of online computation. This figure shows that, as expected, for small amount of storage the Fixed-base Comb is always the best approach. For larger complexities the proposed approach with a prime radix R is the best choice.

Considering the results in Table XI, one notices that for the four considered methods, one has a slight difference in comparison with the modular exponentiation case. Indeed, for all key sizes and for most of the levels of online computation the proposed approach shows the lowest amount of storage. This is due to the relative cost of the doubling of point and the mixed and full Jacobian addition of points:

• Since the doubling is much cheaper than the additions, this is beneficial to the Fixed-base Comb method and the proposed approach with R prime. Specifically, Fixed-base Comb is the best approach for small amount of storage, that is up to several tens of kilobytes, for the three curves P256, P384 and P521. For larger amounts of storage, the other methods remain more efficient.

• The proposed approach which uses a multiplicative splitting recoding with a prime radix R is the best for the following levels of online computations: for P256 and #M M ∈ {176, ..., 405}, for P384 and #M M ∈ {264, ..., 475} and for P521 and #M M ∈∈ {352, ..., 651}.

2) Implementation results: We now present implementation strategies and results for the constant time fixed-base scalar multiplication over NIST prime curves P256, P384, P521.

Implementation strategies. The implementation strategies and test processes are the same as the ones presented in Subsection V-B1 for modular exponentiation. We review most of them and provides the specific strategies adapted to the considered elliptic curves.

• Curve operations. We use the curve operations in Jacobian coordinate system, which provides the lowest complexities for the considered NIST curves. The doubling formula is from [START_REF] Bernstein | Faster addition and doubling on elliptic curves[END_REF], the mixed addition is from [START_REF] Menezes | Guide to Elliptic Curve Cryptography[END_REF] and the full-addition is from [START_REF]Explicit Formula Database[END_REF].

• Field operations We use the low level functions performing multi-precision addition, subtraction, multiplication and squaring of the GMP library as building blocks of our codes (GMP 6.0.0, see GMP library [START_REF]The GNU Multiple Precision Arithmetic Library (GMP[END_REF]). According to the GMP documentation, the classical schoolbook algorithm is used for small sizes. For the inversion, we use the binary extended Euclidean algorithm, with some specific assembly code portion, which is presented by Brown et al. in [START_REF] Brown | Software implementation of the NIST elliptic curves over prime fields[END_REF]. The field reductions use also the algorithms presented by Brown et al. in [START_REF] Brown | Software implementation of the NIST elliptic curves over prime fields[END_REF].

• Radix R conversion and recoding. The algorithm and the code is the same as the one previously used for modular exponentiation case. However, the size of the scalar in this case is the same as the one of the field elements representing the elliptic curve point coordinates. The computation time of the recoding is no more negligible in this case, as shown by the tests of the conversion alone, and the multiplicative splitting recoding computation (including the conversion). We provide in Table XIII the results of these tests. One sees that the impact of the recoding is at most 8% of the scalar multiplication computation time without recoding, in the worst cases. The most important part of the recoding time is the computation of the multiplicative splittings of the scalar digits, with the repeated use of the Truncated EEA.

Due to the relative cost of the recoding in the multiplicative splitting with R prime, and to the fact that the recoding itself is not regular as implemented, we provide timings without the recoding, considering that in ECDSA, one can directly generate a random scalar k in a multiplicative splitting form and then process the digital signature (this strategy was proposed in [START_REF] Doche | On the Enumeration of Double-Base Chains with Applications to Elliptic Curve Cryptography[END_REF] to avoid costly scalar recoding in double base representation).

• Test processing. The test processing is the same as the one used for the modular exponentiation. This involves a few hundred of datasets, which are random scalars and a fixed base with precomputed data. To get the timings, we perform 2000 times the scalar multiplication and keep the minimal number of clock-cycles. This is meant to avoid the cold-cache effect and system interruptions. The final timings are the average of the dataset timings.

Test results and comparison. The algorithms were coded in C, compiled with gcc 4.8.3. The test were performed on a platform which has the following characteristics: an Intel XEON E5-2650 (Ivy bridge), a RAM of 12.6GBytes and a CENTOS 7.0.1406 operating system.

In Table XII, we report some of the most significant results obtained for the three following approaches: Fixedbase Comb, Fixed-base radix-R and the one based on multiplicative splitting recoding with a prime radix R. These results show that, except in the last case (P521 and 290000 clock-cycles), our approach provides the smallest storage amount for each considered level of clock-cycles. This is consistent with the complexity evaluation shown in Table XI and Fig. 3. Specifically, for a fixed amount of online computation the proposed approach reduce by roughly 50% the amount of storage.

VI. CONCLUSION

In this paper, we considered fixed base modular exponentiation and elliptic curve scalar multiplication. These operations are intensively used in NIST standards for digital signature algorithm. In particular, they are used for remote authentication of web server. We proposed algorithms for modular exponentiation and scalar multiplication based on a multiplicative splitting recoding of the digits of the exponent or scalar. The multiplicative splitting provides more freedom in the distribution of the computational cost into storage and online computation. We evaluated the complexities of the proposed approaches for the security levels recommended by the NIST. We could show that, for a fixed level of computation, the proposed approaches reduce the amount of stored data in most of the considered practical cases. Specifically the storage requirement is reduced by at least 50% in most cases and up to 3 times for the largest NIST standardized key sizes. These complexity results were confirmed by the implementation tests done on an Intel XEON E5-2650.

• Equation of Weierstrass curve:

i , k

i ), 0 ≤ i < , (k )} its multiplicative splitting recoding using W -bit split c and a fixed point P ∈ E(F p ).

Ensure: X = k • P if bit i of j is non zero then 10:

Y k (0) i ← Y k (0) i + (s i ) • T [i][k
X ← X + Y j 11: return (X)

+ si • T [i][k (1)

Algorithm 5

 5 this is detailed in the algorithm. One notices it might be necessary to handle the last carry C generated by the recoding of k -1 with a final correction. This gives a final coefficient k = -C which satisfies |k | < m 1 . Finally, this leads to the recoding algorithm shown in Algorithm 5. November 19, 2018 DRAFT Multiplicative Splitting Recoding with R = m 0 m 1 Require: An RNS base {m0, m1}, a radix R = m0 • m1 and an exponent k = -1

=Lemma 1 .

 1 j ∈ [0, c[ and v j ∈ [0, R/c] and by taking k v j . The following lemma establishes this property. If one chooses c ∈ [0, R[, there exists j such that |r j | ≥ c and r j+1 < c and at the same time |v j | ≤ R/c and |v j+1 | ≥ R/c.

Algorithm 7

 7 Truncated Extended Euclidean Algorithm (TruncatedEEA(k, R, c))

Algorithm 8 1 i=0

 81 given in a multiplicative splitting form. The last coefficient k = -C is necessary to handle the last carry. The resulting recoding algorithm is shown in Algorithm 8. Multiplicative Splitting Recoding for R Prime Require: R prime, k = -kiR i , and c the splitting bound. Ensure: {(si, k

Example 4 .

 4 We consider the exponent k = 901644 10 along with the multiplicative splitting recoding computed in Example 3.

  ((-1, 1, 6), (-1, 1, 6), (-1, 3, 7), (1, 3, 1)) and k 4 = 0.

Figure 1 .

 1 Figure 1. Complexity comparison, Fixed base modular exponentiation NIST DSA, key size 256, 384 and 512 bits (field size 3072, 7360 and 15360 bits).

Figure 2 .

 2 Figure 2. Performance comparison, Fixed base modular exponentiation NIST DSA, key size 224, 256, 384 and 512 bits (field size 2048, 3072, 7360 and 15360 bits).

Figure 3 .

 3 Figure 3. Complexity comparison for constant time Fixed-base scalar multiplication on elliptic Weierstrass curves P256, P384 and P521

y 2 = x 3 + 1 i=0

 231 ax + b with a = -3 and b ∈ F p . The NIST curves used : • P256: One has p = 2 256 -2 224 + 2 192 + 2 96 -1, that is One has p = 2 384 -2 128 -2 96 + 2 32 -1, that is p = 0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe ffffffff 00000000 00000000 ffffffff and b = 0xb3312fa7 e23ee7e4 988e056b e3f82d19 181d9c6e fe814112 0314088f 5013875a c656398d 8a2ed19d 2a85c8ed d3ec2aef Curve subgroup generator: One has p = 2 521 -1, that is p = 0x01ff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff November 19, 2018 DRAFT Algorithm 10 Fixed-base scalar multiplication based on multiplicative splitting recoding with prime radix R Require: A prime integer R ,a scalar k = k i R i with = {(s i , k

1 :

 1 Precomputation. Store T [i][j] ← ( j -1 R • R i ) • P for i = 0, . . . , -1, j = 1, . . . , R/c and T [ ][1] ← R • P and T [i][0] ← O for i = 0, . . . , -1.

2 :

 2 X ← O, Y j ← O for 1 ≤ j ≤ c 3: for i from 0 to -1 do 4:

5 : 8 :

 58 Y |k | ← Y |k | + (sign(k )) • T [ ][1] 6: for i from W downto 0 do 7: X ← 2 × X for j from c -1 downto 1 do 9:

5 Y

 5 |k | + sign(k ) • T [ ][1] 1M ixedAdd (W -1)×Step 7 X ← 2 × X 1Doubling (H -1)×Step 10 X ← X + Yj 1Addition TOTAL ( + 1) × M ixedAdd +(W -1) × Doubling + (H -1) × Addition TOTAL STORAGE × ( R/c + 1) + 1 points on E(Fp)November 19, 2018 DRAFT

  Table II for different practical values of m 1 . Fixed-base exponentiation with multiplicative splitting with radix R = m 0 m 1

	Algorithm 6
	November 19, 2018	DRAFT

Table I EXAMPLE

 I OF AN EXECUTION TRACE FOR AN EXPONENTIATION BASED ON MULTIPLICATIVE SPLITTING RECODING WITH R = m 0 m 1

	Iter.	Exp. coef.	Step	Value
	(loop 3:
	November 19, 2018			DRAFT

Table III COMPLEXITY

 III OF EXPONENTIATION BASED ON MULTIPLICATIVE SPLITTING RECODING WITH R = m 0 m 1

Table IV EXAMPLE

 IV OF AN EXECUTION TRACE OF

Table V EXAMPLE

 V OF AN EXECUTION TRACE FOR AN EXPONENTIATION BASED ON MULTIPLICATIVE SPLITTING RECODING WITH R PRIME

	Iter.	Step	Coeff	Value
	i = 0	4:

Table VI EXPONENTIATION

 VI COMPLEXITY AND STORAGE FOR THE PROPOSED APPROACH WITH A PRIME RADIX R RECODING.

Table VII COMPLEXITIES

 VII AND STORAGE AMOUNTS OF EXPONENTIATION ALGORITHM, AVERAGE CASE, BINARY EXPONENT LENGTH t.

		Constant	#Mul		#Squ.	Storage
		time				(#values
						in G)
	Square-and-mult. (Algo. 1)	no	t 2		t -1	0
	Fixed-base Radix-R ( * ) (Algo. 2)	yes	t w -1		0	t w 2 w
	Fixed-base Comb (Algo. 3) Fixed base NAFw (Algo. 3)	yes no	t w -1 w+1 w (1 -t w	w	t w -1	2 w

Table IX STORAGE

 IX AMOUNT COMPARISON FOR FIXED-BASE COMB, FIXED-BASE RADIX-R AND MODULAR EXPONENTIATION WITH MULTIPLICATIVE SPLITTING RECODING FOR NIST RECOMMENDED EXPONENT SIZES

			Key size t = 224 bits				Key size t = 256 bits
	#MM	Fixed-base Comb	Fixed-base Radix-R	Multiplicative splitting R = m0m1 R-prime	#MM	Fixed-base Comb	Fixed-base Radix-R	Multiplicative splitting R = m0m1 R-prime
	45	127.5 kB w = 9	345 kB R = 31	108 kB (m0, m1) =	240 kB (R, c) =	46	383 kB w = 10	845 kB R = 47	241 kB (m0, m1) =	494 kB (R, c) =
				(11, 9)	(97, 7)				(17, 11)	(97, 5)
	37	511.5 kB w = 11	594 kB R = 61	242 kB (31, 7)	541 kB (179, 5)	39	1535 kB w = 12	1454 kB R = 97	579 kB 47; 7	1116 kB 223; 5
	30	4095.5 kB w = 14	1386 kB R = 179	770 kB (127, 7)	1205 kB (179, 5)	32	12287 kB w = 15	3179 kB R = 257	2070 kB 211; 6	3084 kB 409; 3
	24	32767.5 kB w = 17	4230 kB R = 677	4173 kB (877, 7)	4489 kB (1223, 3)	26	98303 kB w = 18	9846 kB R = 937	9642 kB 1223; 6	10207 kB 1699; 3
	19	524287.5 kB w = 21	27084 kB R = 5417	50409 kB (13441, 5)	27954 kB (6211, 2)	20	1572863 kB w = 22	66676 kB R = 8467	225482 kB 37579; 5	85558 kB 12007; 2
			Key size t = 384 bits				Key size t = 512 bits
	#MM	Fixed-base Comb	Fixed-base Radix-R	Multiplicative splitting R = m0m1 R-prime	#MM	Fixed-base Comb	Fixed-base Radix-R	Multiplicative splitting R = m0m1 R-prime
	63	1918 kB w = 11	4081 kB R = 67	969 kB (m0, m1) =	2274 kB (R, c) =	86	3836 kB w = 11	9841 kB R = 59	1940 kB (m0, m1) =	5004 kB (R, c) =
				(19, 11)	(127, 6)				(13, 11)	(163, 9)
	50	15358 kB w = 14	10087 kB R = 191	3742 kB 101; 11	7182 kB 433; 5	73	15356 kB w = 13	17855 kB R = 127	4747 kB (41, 10)	10005 kB (241, 6)
	41	122878 kB w = 17	26655 kB R = 677	17284 kB 541; 6	22891 kB 937; 3	60	122876 kB w = 16	46775 kB R = 409	16224 kB (179, 11)	29979 kB (739, 5)
	35	983038 kB w = 20	80357 kB R = 2381	64768 kB 2381; 6	65837 kB 3191; 3	52	491516 kB w = 18	93110 kB R = 937	54680 kB (677, 7)	76505 kB (1223, 3)
	30	7864318 kB w = 23	246070 kB R = 8467	315053 kB 13441; 5	235255 kB 13441; 3	48	983036 kB w = 19	156091 kB R = 1699	106185 kB (1489, 10)	136971 kB (2381, 3)
	26	62914558 kB w = 26	951217 kB R = 37579	3256278 kB 165397; 5	1030642 kB 43973; 2	41	7864316 kB w = 22	489112 kB R = 6211	355573 kB (5417, 7)	477551 kB (6211, 2)
	24	503316478 kB w = 29	1750756 kB R = 74699	-kB -	-kB -	35	62914556 kB w = 25	2048419 kB R = 30347	2113890 kB (37579, 7)	1949934 kB (47269, 3)

Table X IMPLEMENTATION

 X RESULTS FOR MODULAR EXPONENTIATION IN TERMS OF CLOCK CYCLES AND STORAGE (KB). TEST PERFORMED ON ANINTEL XEON E5-2650 (IVY BRIDGE), GCC 4.8.3, CENTOS 7.0.1406.

							Scalar multiplication
				State of the art methods				Proposed approach
	Security	Level of	Fixed-base Comb	Radix R			R = m0m1	R prime
	level	clock-	Time Storage w	Time Storage R	Time Storage (m0, m1)	Time Storage (R, c)
		-cycles	(#CC)	(kB)	(#CC)	(kB)		(#CC)	(kB)	(#CC)	(kB)
	112 bits	220000 221108 1023.5 12 227838	829	91	219864	580	(89,6)	217104 1191	(257,3)
	(key 224 bits,	207000 210074 2047.5 13 206888 1324 163	207072	766	(127,7)	206813 1553	(347,3)
	field 2048 bits)	148000 149690 65535 18 147877 7289 1223 146156 21599 (5417,6)	149490 17661 (3719,2)
	128 bits	505000 524539 1535 12 502981 1411	91	501466	897	(79,6)	509581 1420 (307, 5)
	(key 256 bits,	450000 449397 6143 14 445871 2251 163	446444 2056	(211,6)	458936 2372 (307, 3)
	field 3072 bits)	354000 356892 98303 18 354640 6414 571	354071 12843 (1721,7)	353662 15283 (1699, 2)
	192 bits	444000 4442590 1918 11 4492191 3430 53	4409584 1134 (23, 10) 4494471 2171 (127, 6)
	(key 384 bits,	353000 3554339 15358 14 3524896 8290 163 3551437 4164 (113, 10) 3534620 7100 (433, 5)
	field 7680 bits)	270000 2736341 245758 18 2543480 45221 1223 2743399 29961 (1031, 7) 2795363 31915 (1381, 3)
	256 bits	1860000 18632429 15536 13 19260731 13765 91 18550238 4745 (41, 10) 18683547 8653 (257, 7)
	(key 512 bits,	1500000 14848261 122876 16 15401002 34418 163 14812616 22111 (257, 11) 15541482 27853 (641, 5)
	field 15360 bits)	1240000 12477816 983036 19 12193232 119061 1223 12499600 102820 (1381, 7) 12802926 101886 (1699, 3)

Table XII IMPLEMENTATION

 XII RESULTS FOR FIXED BASE SCALAR MULTIPLICATION FOR CONSTANT TIME ALGORITHMS. TEST PERFORMED ON AN INTEL XEON E5-2650 (IVY BRIDGE), GCC 4.8.3, CENTOS 7.0.1406.

						Scalar multiplication
				State of the art methods			Proposed approach
	Security	Level of	Fixed-base Comb		radix R			R-splitting rec.
	level	Clock-cycles	Time	Storage	w	Time	Storage	R	Time	Storage	(R, c)
			(#CC)	(kB)		(#CC)	(kB)		(#CC)	(kB)

Table XIII RECODING

 XIII TESTS, FOR SIZES 256, 384 AND 521 BITS: WORST CASE COMPUTATION TIME IN CLOCK CYCLES

		Recoding
	Scalar size	256 bits #CC	384 bits #CC	521 bits #CC
	Radix R conversion	1200	1640	2250
	R-splitting conversion	14400	21600	27500

Table XIV COMPLEXITY

 XIV EVALUATION OF SCALAR MULTIPLICATION BASED ON MULTIPLICATIVE SPLITTING RECODING WITH R PRIME

				Complexity
	Step			Operation	Cost
	×Step 3	Y	k	(0) i

November 19, 2018 DRAFT

APPENDIX

We review here the NIST recommended curves (see [START_REF] Kerry | Digital Signature Standard (DSS)[END_REF]) used in our implementations. Over a finite field F p , one has: Before proceeding to the proof of Lemma 1 we need to recall the following lemma which states some classical properties of the Extended Euclidean Algorithm. A proof of this lemma can be found in [START_REF] Negre | Efficient regular modular exponentiation using multiplicative half-size splitting[END_REF].

Lemma 2. Let v i and r i be the two sequences of coefficients computed in Algorithm 7. They satisfy the following properties:

The proof is a direct consequence of Lemma 2: statements i) and ii) imply that for i ≥ 1

So if r ic-1 is the last remainder such that r ic-1 ≥ c then we have r ic < c. Then taking i = i c in (13) leads to

We consider an elliptic curve E(F p ) a point P on the curve and a scalar k. The scalar multiplication based on a multiplicative splitting recoding with prime R is shown in Algorithm 10. Table XIV gives the complexity evaluation.