El-Gamal encryption on elliptic curves : side-channel

attacks and counter-measures

Gabriel Mattos Langeloh Martin Gendreau

ENSIMAG ENSIMAG
gabriel.mattos-langeloh@ martin.gendreau@
ensimag.grenoble-inp.fr ensimag.grenoble-inp.fr

ABSTRACT After adding a point at infinity, which is used as the neutral

This paper describes two fault attacks on an El-Gamal en- element, this law makes E an additive group[7]. It is then
cryption system reinforced by the use of elliptic curves : a possible to multiply an element of this set by an Integer.
fault in the base point and a fault in the curve parameters. This operation is called scalar multiplication and defined,
After implementing these attacks, we tried to find the best when n is positive, by
parameters for each, and found that they depend on the
[n]P = P + P + · · · + P
curve used. We managed in some cases to lower the security | {z }
of a curve by 32 bits. This paper also includes a few simple n

counter-measures for both attacks. When n is negative, we use

[n]P = [−n](−P )
1. INTRODUCTION
The most famous cryptographic attacks are on the strength
and the implementation of the algorithm itself. But there 2.1.2 Finding an elliptic curve
are some which use side channels in the software or in the Before using elliptic curves for encryption, one has to find
hardware it is implemented on. For example, it is possible to a curve. It may be either a precomputed, authority-advised
retrieve parts of the RSA private key stored in a debit card curve1 , or an original one. To create a curve, one may use
by shooting lasers at it when it is computing, and seeing how the method 1, described by B. Holm. This method finds, if
it affects the output[2, 3, 10]. We here study a comparable possible, a N -point elliptic curve over a field Fp . In practice,
attack, but on the El-Gamal encryption over elliptic curves. this algorithm can only work for some choices of p and N . If
we fix N as a parameter, we can use Cornacchia’s algorithm
In this article, we proceed to the study of two side chan- (for an explanation and proof of the algorithm, see, for ex-
nel attacks on the El-Gamal encryption system over elliptic ample, [1]) to choose an adequate value of p if possible. This
curves. Each of these studies includes a theoretical study, method is further explained in Holm’s thesis[5].
an implementation of the attack, an analysis of the results
and a description of simple counter-measures. Algorithm 1 Holm’s method
P ← (1, 1)
2. BACKGROUND t←p+1−N
i←0
2.1 Elliptic curves S ← Fp \ { −27 }
4
2.1.1 Basics repeat
In this paper, we focus on a variant of classic encryption Pick a random a ∈ S
systems : instead of using a finite field, such as Z/pZ, com- Ea ← y 2 = x3 + ax − a
putation is made on an elliptic curve, which means working if P is annihilated by p + 1 − t then
on return Ea
else if P is annihilated by p + 1 + t then
E = {(x, y) ∈ F2p | y 2 = x3 + ax + b}, (a, b) ∈ F2p
return quadratic twist of Ea
where p 6= 2, 3. An addition law is defined on this set : we end if
define S ← S − {a}
until S = ∅
− P = (xP , −yP ) (1) return Error : No curve found
and compute R = P + Q by:
( yP −yQ
xP −xQ
if xP 6= xQ Given d ∈ Fp , a quadratic non-residue, we define a quadratic
s= 3x2
(2)
P −a twist of an elliptic curve E(Fp ) of parameters a, b ∈ Fp as
2yP
if xP = xQ
the curve
E d (Fp ) = {(x, y) ∈ F2p | y 2 = x3 + d2 ax + d3 b}
(
xR = s2 − xP − xQ
(3) 1
yR = s(xP − xR ) − yP Find some: http://safecurves.cr.yp.to
A quadratic non-residue is easily found by trying the follow- This is the most simple version of this algorithm, and it is
ing equation on the first primes. The computation is fast, as, vulnerable to timing attacks. Although, as the timing-safe
on the assumption of the Generalised Riemann hypothesis, versions are equally vulnerable to the attacks described in
n  (log p)2 . this article, we will, for simplicity purposes, use this version.
n(p−1)/2 ≡ p − 1 mod p
2.4 Computing the discrete logarithm
As explained in section 2.2, to find the private key of the
Holm’s method assumes that the input is within the bound system given the public key (E, G, H), one must find x such
of Hasse’s theorem on elliptic curves[4]. This bound is that H = [x]G in the curve E. This problem is called the
√
|N − (p − 1)| ≤ 2 p (4) discrete logarithm problem over a finite field, in this case,
the elliptic curve E. There is no known classical algorithm
This algorithm is expected to run in O(N 1/2+ ) for some to solve this problem with polynomial running time in the
small . Thus, it is not viable to use it to generate curves of number of digits of |E| = n, although Shor’s quantum algo-
sufficiently big order for cryptography. There exist, however, rithm for factorisation can be adapted to this problem and
more efficient algorithms for curve generation, such as the it’s not proven that no such classical algorithm exists.
Complex Multiplication method, explained, for example, in
[5]. There exist, however,√ algorithms with a pseudopolynomial
running time of O( n), such as the Baby-Step Giant-Step
2.2 El-Gamal on elliptic curves algorithm. For this reason, the security of the El-Gamal
The El-Gamal encryption system is based on the difficulty system over elliptic curves depends on, among other factors,
of the computation of discrete logarithms in finite fields. In the size of n, which is, according to Hasse’s theorem [4],
elliptic curves, retrieving n knowing P and [n]P is as difficult close to the cardinality p of the base field Fp of the chosen
as a discrete logarithm over a finite field[9], which makes it curve. The Baby-Step Giant-Step algorithm is presented in
possible to use this construction for cryptography. Algorithm 4.

The encryption system is then very similar to the classic Algorithm 4 Baby-Step Giant-Step
El-Gamal system : it is the same system, but the field is √
replaced by an elliptic curve, and exponentiation by scalar m← n
multiplication. The system needs an invertible function f for j from 0 to m do
to translate a message m to its associated point M . Compute G[j] and store the pair (j, G[j]) in a hashtable
end for
Protocol El-Gamal encryption with elliptic curves Compute G[−m]
γ←H
1: Alice has a private key x (an integer), and a public key for i from 0 to m do
(E, G, H), where G is a generator of E and H = [x]G. if γ is the second component of some pair (j, G[j]) in
2: Bob chooses randomly an integer k. the hashtable then
3: Bob computes M = f (m), C1 = [k]G, C2 = M + [k]H, return im + j
and sends both to Alice end if
4: Alice receives (C1 , C2 ), retrieves m by computing γ ← γG[−m]
f −1 (C2 + [−x]C1 ) end for

2.3 Computing the scalar multiplication 2.5 Side channel attacks

In this paper, we will focus on side-channel attacks compara-
For the computation of [n]P , the algorithm used is close to
ble to the one described in the introduction. For simplicity
the square-and-multiply algorithm used for exponentiation.
purposes, we only simulate the shooting of a laser. The ef-
It is called double-and-add, and computes [n]P in O(log n).
fect of this simulated laser will be identical to the effects of
This algorithm is presented in Alg.3.
real lasers used on debit cards: it can alter a byte of any
data at a given time, but the result of this modification will
Algorithm 3 Double-and-Add
be impossible to predict.
n = n0 + 2n1 + · · · + 2m nm
Q←0 Our goal will be to retrieve the private key from the Double-
for i from 0 to m do and-add algorithm by reducing the order of the curve, field
if ni = 1 then or generator point to be able to apply Algorithm 4 to solve
Q←Q+P the discrete logarithm problem. Once this is done, retrieving
end if the encrypted message is only applying the protocol as Alice
P ← [2]P would do.
end for
return Q
3. CHOSEN INPUT POINT ATTACK
3.1 Theory
This algorithm only works if n ≥ 0. If n is negative, we It can be noted that the addition in E does not involve the
transform [n]P into [−n](−P ), using equation 1. parameter b in the curve equation[6]. Thus, if a modification
of P creates P̃ = (x˜P , yP ), the computation of [n]P̃ will take Curve Byte Basic order Smallest Order
place on ECB-48 0 48 38
secp112r1 10 112 102
Ẽ = {(x, y) ∈ F2p | y 2 = x3 + ax + b̃} Anomalous 24 204 194
NIST P-224 26 224 216
In this group, the order of P̃ might be smaller than the order BN(2,254) 0 256 188
of P in E. In such case, computing a discrete logarithm will
be easier, and give n mod ordẼ (P̃ ) Figure 1: Table showing the smallest order of the points
generated by modifications over a single byte of the x co-
After several iterations of this trick, it will be possible to ordinate of the generator point for each test curve. The
retrieve the private key by using the Chinese Remainder column byte gives the byte that had to be modified to find
theorem. the best result, while the column order gives the base 2 log-
arithm of the order of the original generator point and the
Thus, the complete attack is : column smallest order the base 2 logarithm of the best point
found.
Attack Fault in the base point
1: while not enough values for line 8 do
2: Introduce a fault : P = (xP , yP ) → P̃ = (x˜P , yP ) 3.3 Experimentation
3: The device returns Q̃ = [n]P̃ The complexity of each complete iteration √ is the complexity
4: b̃ is computed with b̃ = y˜Q 2 − x˜Q 3 − ax˜Q of the discrete logarithm which is O( r), where r is the
5: x˜P is computed as a root of X 3 + aX + b̃ − yP2 order of P̃ in Ẽ. As a result, it is necessary to use the points
6: If possible, Q̃ = [n]P̃ is solved as a discrete logarithm where this order is the smallest possible. For this reason,
7: end while our experimentations consist mostly of an evaluation of the
8: Compute n with the Chinese Remainder theorem. order r of every possible point generated by a modification
of a single byte of the x coordinate of the generator element
of the base curve.

3.2 Implementation All experiments in this paper have been run on Intel i7 @
2.0GHz and Intel i5 @ 1.8Ghz machines with 4 cores. In the
This attack has been implemented with the perturbation
case of the Chosen Point Input Attack, the computation of
caused by a simulated laser : at the beginning of the com-
the orders of all the possible points created by perturbations
putation of [n]P , the first coordinate of P is modified ran-
of a single byte of the generator element took, for the worst
domly. As a result, line 5 is not needed in our simulation,
case (that of the BN curve over 254 bits), approximately 5
because we already have the value of x˜P .
hours, while for the curves ECB-48 and SECP-112-R1 the
computations took a few seconds.
As the simulated laser only alters one byte, there are only
256 possible outcomes. Thus, the order of P̃ in Ẽ can be
The figure 1 presents the size (in bits) of the original order of
precomputed. This represents a major gain in the complex-
the curve along with the size of the smallest order found on
ity of the attack, as this computation was one of the most
each curve (see appendix A), and the byte of the coordinate
complex part of it. The pre-computation was made using
x to modify in order to get it (indexed as 0 being the least
the free computer algebra system PARI/GP[11]. This pre-
significant byte).
computation is quite long, but is made only once for each
curve. According to its results, we can choose the byte to be
We can observe in figure 1 that, for most of the curves that
used for the attack based on the size of the order of the points
were tested, the attack is able to reduce the order of the
generated by the modifications in this byte. The computa-
point by a factor of 210 independently of the size of the
tion time needed to calculate the orders for all 256 points
curve. The exception is the curve BN(2, 254), on which the
generated by modifications over a single byte is of approxi-
attack can be seen as very effective, from the point of view
mately 30 minutes for curves over fields of 200 bits or more,
of the point orders: often, their orders are around 2190 , the
for example, the last three curves presented at Appendix A.
minimum being 2188 as shown in the table.
All algorithms described (except the pre-computation of the
orders of the points and Cornacchia’s algorithm) have been 3.4 Analysis
implemented in the C++ language using the Givaro library These results give the complexity of the attack : computing
(http://givaro.forge.imag.fr/) for arbitrary size integers, the discrete logarithms in the curves with the smallest orders
fields and operations. To make the processing of the point until the product of these orders is larger than p gives the key
orders easier, some of the needed data, such as the curve pa- by the Chinese Remainder theorem. The figure 2 gives for
rameters and modified points was also implemented in C++, each curve the complexity of a direct discrete logarithm, and
leaving only the computation of the point orders itself to be the complexity of our attack, both as security indexes (if this
made by PARI/GP scripts. Some Python and shell scripts index is i, the attack would be equivalent to a brute-force
were also written to find and calculate automatically the rel- on a 2i bits key). We see here that our attack can make a
evant data from the pre-calculated point orders. All of these great difference in the time necessary to break an El-Gamal
are available at https://ensiwiki.ensimag.fr/index.ph over elliptic curves cypher : on the BN(2,254) curve, which
p/Perturbation_sur_ECC_(Projet_de_Sp%C3%A9cialit%C3% is among recommended curves, the loss of security was of 35
A9_2015). bits.
 Curve Byte Direct logarithm Attack in Alg.6.
ECB-48 0 24 20
sepc112r1 0 56 52 Algorithm 6 Double-and-Add, corrected
Anomalous 0 102 98
n = n0 + 2n1 + · · · + 2m nm
NIST P-224 26 112 108
Q←0
BN(2,254) 4 128 95
for i from 0 to m do
if ni = 1 then
Figure 2: The base 2 logarithm of the complexity of the
Q←Q+P
chosen input point attack having pre-computed the point
end if
orders is given by the column attack. The column direct
P ← [2]P
logarithm corresponds to a brute-force attack, while byte
end for
indicates the byte that has to be attacked to obtain the best
if Q ∈ E then
results for the curve.
return Q
else
Curve Mininum Mean Maximum Mean return Error
ECB-48 46.052070106 46.6118360952 end if
sepc112r1 110.471819215 110.652386167
Anomalous 202.226933365 202.447171385
NIST P-224 222.745068969 222.849967956 But, if a laser can also be used to skip instructions, this
BN(2,254) 239.929644347 243.776578689 counter-measure is easily bypassed. Therefore, more ad-
vanced counter-measures have to be implemented.
Figure 3: This table presents the mean of the number of
bits of the pre-calculated orders of the perturbated points. First, doing the check P ∈ E at every iteration of the loop
The columns Minimum Mean and Maximum Mean show, will slow down the computation, but will be less easily by-
respectively, the minimum and the maximum of these means passed, as it will require the attacker to shoot lasers not
over the different bytes. just at the beginning and the end of the computation, but
at many very precise instants.
The best byte to modify depends on the curve, as seen in the
tables. However, to decide which one is the best byte, the
4. FAULTS IN THE CURVE PARAMETERS
attacker must have pre-computed the orders of the points 4.1 Theory
generated by modifications on every single byte of the gen- This attack is similar to the one described in section 3. But
erator point, which gives 256|x| orders to compute, where |x| here, instead of modifying the input point, we modify the
is the number of bytes of the x coordinate of the generator parameters of the curve, more precisely the a parameter,
point. Note that, as shown by the case of the BN curve, the into ã. For a given P , there is a b̃ ∈ Fp which gives P ∈ Ẽ,
best byte to attack is not necessarily the one with the point where
of lowest order, as it is necessary to apply the chinese re- Ẽ = {(x, y) ∈ Fp | y 2 = x3 + ãx + b̃}
mainder theorem to obtain the final result, and thus at least
As a result, after computation, we get Q̃ = [n]P ∈ Ẽ, which
2 points are needed. For this reason, it is preferred to choose
gives a second equation, and thus the system :
a byte that contains more than one point of reasonably low (
order. yP2 = x3P + ãxP + b̃
(5)
y˜Q 2 = x˜Q 3 + ãx˜Q + b̃
We observed that for most curves, the orders of the modi-
fied points are somewhat similar from byte to byte. In other As we have P and Q̃, this is a system which is easily solved,
words, the mean of the number of bits of the points gener- and gives the values of ã and b̃. Then, if Ẽ has a smaller
ated by modifications in a byte changes little compared to order than E, it may be possible to compute the discrete
that of another byte of the same curve. This fact is shown logarithm over this curve.
by the figure 3.
As in the previous attack, this gives n mod ordẼ (P ), where
We see, thus, that it is not stricly necessary to pre-compute ordẼ (P ) < ordE (P ). We therefore need several positive re-
the orders of every perturbated point of every byte, as the sults to compute the full value of n, with the Chinese Re-
obtained results tend to vary very little form byte to byte. mainder Theorem.
However, it remains necessary in practice to find points
whose order is sufficiently small for the discrete logarithm 4.2 Implementation
problem to be solved. As in the first attack, the modification by laser is simulated.
Thus, we do not need to compute ã with the system (5), as
3.5 Counter-measures it is the output of the modifying method.
A simple counter-measure is for the Double-and-add algo-
rithm to check whether the result is an element of E. If it is, Once again, the orders of the altered curves may be precom-
the algorithm returns normally, and if not, the algorithm re- puted, greatly reducing the attack’s complexity.
turns an error. As a result, the attacker will be unable to get
any information after modifying the value of P . Thus, the The code implementing this attack can also be found at http
corrected algorithm for Double-and-add will be as presented s://ensiwiki.ensimag.fr/index.php/Perturbation_sur_E
 Curve Byte Basic order Smallest Order Curve Mininum Mean Maximum Mean
ECB-48 0 48 40 ECB-48 46.2221736458 46.4797858687
secp112r1 3 112 103 sepc112r1 110.412740083 110.750916624
Anomalous 11 204 191 Anomalous 202.262889712 202.334902929
NIST P-224 16 224 217 NIST P-224 222.501063704 222.860444558
BN(2,254) 21 256 246 BN(2,254) 251.737034185 252.067611836

Figure 4: The smallest point order found for each curve is Figure 6: This table presents the mean of the number of
given by the column Smallest Order, considering modifica- bits of the pre-calculated orders of the original generator
tions of a single byte of the parameter a of the curve. The element over a curve whose a parameter was changed by a
column Basic order shows the order of the point in the orig- single byte. The columns Minimum Mean and Maximum
inal curve, while Byte gives the byte where the modification Mean show, respectively, the minimum and the maximum
that causes the smallest point order occurs. of these means over the different bytes.

CC_(Projet_de_Sp%C3%A9cialit%C3%A9_2015). The scripts the private key for these curves. It is still possible that there
and C++ files provided are similar to those of the previous are curves that react to this attack in a similar way to that
attack. observed in section 3 for the BN curve in the case of the first
attack, where we saw a relevant loss of security.
4.3 Experimentation
As in section 3.3, we tried on several curves to modify a byte Once again the point orders are somewhat similar no matter
of the input, but here the modified input is the parameter which byte of the curve parameter a is changed, as shown
a. In the figure 4 we show the order of the points over the by figure 6. Even when we take the incomplete results of the
new curves, in the same way as the previous attack. BN curve, this property remains the same. One could argue
that the mean might not correctly represent the variation of
In the case of this attack, the time needed to calculate the the orders. However, according to the figure 4, we can also
point orders in their new curves seem to be much higher. see that the minimum value for the order of the points is
In approximately 5 hours, our scripts only finished 25% of always somewhat close to the mean in all the cases that we
the work for the BN curve. For this reason, we decided tested.
to use these partial results for this curve. Thus, in the ta-
bles corresponding to this attack, the data given for the BN Comparing the performance of both attacks, we can con-
curve corresponds to the partial results, while in the case of clude that, at least for these curves, the first attack is much
the other curves, all orders were computed. We emphasize more efficient - not only the point orders are calculated
that, although we didn’t proceed with the computation of faster, but the decrease in the number of bits of the security
the orders for the BN curve case, it is feasible to do it even of the algorithm is also better, being of approximately 10
on simple machines such as the ones we used, because this bits in the first case and 4 bits in the second.
computation has to be done only once.
A possible reason for the greater times of computation on
the faults in the curve parameters is that the arithmetic
4.4 Analysis over an elliptic curve depends only on its parameter a, being
As before, the results give us the cost to crack the cypher independent of b. Thus, in the case of the chosen point input
using our attack, which we can compare to the cost to crack attack, even though the parameter b of the curve is changed
it using directly a discrete logarithm. by the perturbation, the performance of the arithmetic over
the new curve is the same as that of the original one. The
We observe for this attack a small decrease in the complexity same doesn’t happen in the second case, where we change
of the discrete logarithm problem comparing to the brute a directly. The difference in speed is then explained by the
force version, although this decrease corresponds only to a fact that curves recommended for cryptography are usually
few bits of security for all 5 curves tested. For this reason, made not only to be secure, but also to have reasonably fast
it seems not to be enough to be useful in practice to retrieve arithmetic, and this property is not necessarily preserved
when we inject faults in the curve parameters.
Curve Byte Direct logarithm Attack
ECB-48 0 24 21 4.5 Counter-measures
sepc112r1 2 56 53 The simple counter-measure presented in section 3.5 will also
Anomalous 23 102 96 work in this case, because the a parameter is altered, but
NIST P-224 11 112 109 not the b. Checking P ∈ E will then return false if one
BN(2,254) 1 128 124 parameter have been altered.

Figure 5: The column Attack gives the base 2 logarithm of 5. CONCLUSION

the complexity of our attack having precalculated the point We have seen that the two described attacks allow an at-
order over the modified curves, while the column Direct log- tacker to reduce the security of an elliptic-curve-based cypher,
arithm gives the complexity of a brute-force attack over the such as El-Gamal over elliptic curves. We have also seen
same curve and the column Byte the byte that gives the that some curves are far more vulnerable to this kind of at-
optimal complexity for our attack according to the tests. tack than others, even among recommended curves. Even
in these cases, the drop in the security is not enough for the 2.7.3, 2014. available from
discrete logarithm problem to be solved in reasonable time http://pari.math.u-bordeaux.fr/.
with today’s technology, although this might be the case in
the future. For this reason, in order for a curve to be consid- APPENDIX
ered secure, it is also necessary to make it pass certain tests A. CURVES
that show that it isn’t vulnerable to fault injection attacks. The curves presented here are the curves we worked with.
Among the attacks that we have evaluated in this paper, The parameters are given as (p, a, b, x, y), where p gives the
one has shown itself to be far more useful than the other in field (Fp ), a and b give the equation (y 2 = x3 + ax + b), and
both time and security drop aspects. It is important to say, x and y are the coordinates of a generator.
however, that while we have good theoretical reasons to be-
lieve that the time complexity of an attack by perturbation
over the input points will always be better than that of an
A.1 ECB-48
This curve has been found using Ellipsa’s Elliptic Curve
attack over the curve parameters, the same cannot be said
Builder2 .
for their impacts on the security of the cyphers. Thus, we
cannot discard the possibility that there exist curves over
which the faults over the curve parameters have a higher • p = 210548486455921
security drop than the chosen input point attack. • a = 81567173258700
• b = 32070683051331
In practice, such an attack by fault injection can only be ap-
• x = 193293483718178
plied if the attacker has unlimited access to the hardware,
as it requires to have it compute many values from erro- • y = 128637171164369
neous points or parameters, and as many very precise laser
shots. Furthermore, simple counter-measures can make it A.2 SECP 112-R1
even more difficult, making these kinds of attack easy to The interest of this curve lies in the fact that it is the smallest
avoid as long as the necessary precautions are taken when curve used by OpenSSL, being defined over a 112 bit field.
implementing the cypher and the appropriate studies are
made when choosing the curves. • p = 4451685225093714772084598273548427
• a = 4451685225093714772084598273548424
6. REFERENCES • b = 2061118396808653202902996166388514
[1] J. M. Basilla et al. On the solution of xˆ 2+ dyˆ 2= • x = 188281465057972534892223778713752
m. PROCEEDINGS-JAPAN ACADEMY SERIES A
MATHEMATICAL SCIENCES, 80:40–41, 2004. • y = 3419875491033170827167861896082688
[2] A. Berzati, C. Canovas, J.-G. Dumas, and L. Goubin.
Fault attacks on rsa public keys: Left-to-right A.3 Anomalous
implementations are also vulnerable. Springer, April This curve is interesting because it is the least safe of those
2009. advised by http://safecurves.cr.yp.to. We thus tried
[3] E. Brier, D. Naccache, P. Q. Nguyen, and our attacks on this one.
M. Tibouchi. Modulus fault attacks against rsa-crt
signatures. Cryptology ePrint Archive, Report • p = 176763184868488930309615830187786706104890
2011/388, 2011. http://eprint.iacr.org/. 16512983351739677143
[4] H. Hasse. Zur theorie der abstrakten elliptischen • a = 153478980553715805908905767213143188232075
funktionenkörper. Journal für die reine und 31963035637503096292
angewandte Mathematik, (175), January 1936. • b = 744438644993450597036786520456912472835066
[5] B. Holm. Constructing elliptic curves with a given 1870959593404279615
number of points. Master’s thesis, University of • x = 161909258958654290749256917043484212816575
Cambridge, 2005. 5668543894279235270
[6] M. Joye. Fault attacks on elliptic curve cryptosystems.
• y = 343694954762652492064551331656970014053548
In Crypto’Puces. Thomson Security Labs, 2009.
2973634182925459687
[7] N. Koblitz. Elliptic curve cryptosystems. Mathematics
of computation, 48(177):203–209, January 1987.
[8] National Institute for Standards and Technology.
A.4 BN(2,254)
This curve is interesting for the simplicity of its parameters.
Digital signature standard. Technical report, Federal
Information Processing Staandards Publication, 2000.
[9] A. Menezes, T. Okamoto, and S. Vanstone. Reducing • p = 167981087310158322849408041422317339098891
elliptic curve logarithm to logarithm in a finite field. 87121439069848933715426072753864723
IEEE Transactions on information theory, 39(5), • a=0
September 1993. • b=2
[10] C. Roscian, J.-M. Dutertre, and A. Tria. Injection de • x = −1
fautes laser et localisation de blocs logiques. In
• y=1
Crypto’Puces. CEA-LETI and ENSMSE, 2011.
2
[11] The PARI Group, Bordeaux. PARI/GP version www.ellipsa.eu/public/ecb/ecb.html
A.5 NIST P-224 efficient method for generating curves of an arbitrary size,
This curve is among the ones recommended by the NIST such as the Complex Multiplication method.
(National Institute for Standards and Technology) in the
report [8]. B.4 Other files
Our code is not entirely listed above, as some of it is specific
• p = 2224 − 296 + 1 to the attacks and will not be added to the library Givaro.
• a = −3 Among them, there are headers that specify classes repre-
senting an Elliptic Curve Cryptography device, an attacking
• b = 189582862855666080004086685444939264155046 device that simulates the action of a laser and useful bina-
80968679321075787234672564 ries to generate the parameters of all the curves satisfying a
• x = 192779291135662930711103080346994880268319 certain condition, for example, all curves that serve as base
34219452440156649784352033 of a point generated by a fault injection over a byte.
• y = 199268087580344709701979743708887491842059
91990603949537637343198772 B.5 Tests
Each algorithm and class mentioned above has at least some
B. CODE ORGANIZATION simple tests written in .C files in the tests folder. All of
these tests have a name finished by Test and can be compiled
As we think our code regarding computing and cryptog-
and run automatically using a provided shell script called
raphy over elliptic curves would be a useful addition to
runtests.sh.
the library Givaro3 , we present here its organization. De-
tails on the implementation can be found in the library
documentation, generated by doxygen4 . It is located at
doc/html/index.html from the base directory of the source
code given in https://ensiwiki.ensimag.fr/index.php/
Perturbation_sur_ECC_(Projet_de_Sp%C3%A9cialit%C3%A9_
2015)

B.1 Number theory

The file src/NumberTheory.cpp implements algorithms from
basic number theory, such as the Extended Euclidean algo-
rithm and the Chinese Remainder algorithm for 2 equations.
In the future, implementing Cornacchia’s algorithm would
be overall useful as well.

B.2 Elliptic curves

Our code concerning computation over elliptic curves can
be found in the files include/EllipticCurve.h and incl
ude/EllipticCurvePoint.h. The former defines the class
EllipticCurve, and implements the search of a generator
and the computation of the order of the additive group.
The latter defines the class EllipticCurvePoint and imple-
ments basic operations on it : addition, unary minus, scalar
multiplication, . . . It also implements non-trivial algorithms,
such as the equivalent to the discrete logarithm, using the
baby-step giant-step algorithm, and the computation of the
point’s order, with an optional parameter to enforce a time
limit to the computation. Finally, this file also includes the
code for the simulated laser altering, that is, random mod-
ifications and fixed modifications over a given byte of the x
coordinate of the point, or the a parameter of its curve.

B.3 Curve Generation

The file src/PrimeCurveGenerator.cpp contains methods
that returns elliptic curves : one of them creates a curve
given its order and the field, using Algorithm 1, while the
others are pre-calculated, among them NIST5 -advised curves.
All these curves are presented in Appendix A. A possible fu-
ture improvement would be the implementation of a more
3
http://givaro.forge.imag.fr
4
www.stack.nl/~dimitri/doxygen
5
National Institute of Standards and Technology, http://
csrc.nist.gov