<< Предыдущая стр. 2(из 2 стр.)ОГЛАВЛЕНИЕ
exploited by the attacker.
Only those acquisitions for which r is a weak mask may be relevant to an at-
tacker. In this case, the intermediate variables are unmasked after some steps of
our algorithm. Clearly, the expected number of acquisitions to mount a diп¬Ђeren-
tial side-channel attack against our algorithm grows inversely proportional with
the probability that r be a weak mask. Since the probability of picking a weak
mask is negligible, diп¬Ђerential side-channel attacks are infeasible in practice.

Fault attacks The resistance of our algorithm against fault attacks is based
on the relationship R2 (R0 , R1 ) = (xОє , xОє+1 ) for some Оє в€€ N. If an error occurs
on a temporary result or during one of the group operations at any time during
the computation, the mutual coherence of R0 , R1 , and R2 is deп¬Ѓnitively lost.
As a consequence, the result of the last multiplication R2 R0 is just some perfect
random number to an attacker that cannot be exploited as such, at least if we
assume the input was not blinded with a weak mask. Again, as weak masks are
extremely unlikely in practice, any such error will be caught by our countermea-
sure.
However, as in , Fig. 4 algorithm fails to thwart exponent or loop counter
disturbance as it does preserve the former relationship. Such faults hence have
to be handled by other techniques. As pointed out in , avoiding conditional
branching is safer since modifying the result of a comparison or the value of a
loop counter by tampering with the associated register is easy. On the contrary,
in order to by-pass an instruction, the attacker would have to increment the
program counter. Such a precise modiп¬Ѓcation is hardly feasible in practice. For
that reason, we propose combining the on-the-п¬‚y checksum computation of 
with the infective computation technique of  (Fig. 5). Let Оі = CKS вЉ• CKSref
be the diп¬Ђerence between the re-computed checksum CKS and the reference
checksum value CKSref . The most signiп¬Ѓcant bits of R2 are xored with Оі before
the last multiplication. Hence, the п¬Ѓnal result will be spoiled whenever Оі = 0
i.e. whenever the exponent or the loop counter has been tampered with.

3.2 Eп¬ѓciency Analysis

Time Montgomery ladder (Fig. 3) requires t multiplications and t squarings.
Our algorithm (Fig. 4) requires t more squarings for computing the compen-
sative factor. The inversion and the two multiplications involved in the masking
and unmasking process can be neglected with respect to the cost of the overall
computation. Let M denote the cost of a multiplication. The cost of a squaring
can be approximated to 0.8M . Each step of our algorithm costs 2.6M compared
to 1.8M for Montgomery ladder, that is a 44.44% time complexity increase.

Storage Compared to Montgomery ladder, our algorithm requires one more
register R2 for the compensative factor, that is a 50% storage increase.
Note however that many cryptographic co-processors cannot store the result
of some operations вЂ“ as the modular multiplication or squaring вЂ“ at the address
of the operands. With such architectures, three registers for the standard Mont-
gomery ladder and four registers for our algorithm are needed, corresponding to
a 33% storage increase.

4 Conclusion

This paper presents an algorithm for computing exponentiations in п¬Ѓnite abelian
groups, especially relevant in the RSA and ECC setting, that is intrinsically
resistant to all known simple and diп¬Ђerential side-channel analysis and fault
attacks, while requiring roughly at most 50% more time and storage compared
to traditional balanced implementations.
Our countermeasure is especially suited when only the parameters needed
for the computation itself are known, which is extremely valuable as additional
parameters are rarely available to the cryptographic device. In particular, neither
the group order nor the public exponent are required.

Acknowledgment

The authors would like to thank Jean Creignou for many helpful remarks on the
preliminary version of this paper.

A Proof of Theorem 1

Lemma 1 (CauchyвЂ™s Lemma). Any п¬Ѓnite group whose order is divisible by a
prime number p contains an element of order p.
Deп¬Ѓnition 2. Let G be a п¬Ѓnite abelian group and p be a prime number. Let
Gp denote the subgroup of all elements of G whose order is a power of p. Any
element x в€€ Gp is called a p-torsion element of G.
Lemma 2. Let G be a п¬Ѓnite abelian group. We have

Gв€ј Gp .
=
p | |G|

n
Proof. Let |G| = i=1 pОІi where pi,iв€€{1,...,n} are prime numbers.
i
Let us show that the homomorphism П€ deп¬Ѓned as
n
П€
Gpi в€’в†’ G
i=1
n
(x1 , . . . , xn ) в€’в†’ xi
i=1

is an isomorphism. First, we show that П€ is a monomorphism.
Let x and y be in the abelian group G. Let | x | = a be the order of x and
| y | = b the order of y in G. First, observe that if a and b are coprime, then
xy = 1 в‡’ x = y = 1. This is a consequence of BВґzoutвЂ™s identity. Since a and b
e
are coprime, there exists integers u and v such that au + bv = 1. We have

xy = 1 в‡’ (xy)au = 1 (1)

and as xa = 1, we have (xy)au = xau y au = y au . Then, since y b = 1, we get

(xy)au = y au = y au y bv = y au+bv = y . (2)

From (1) and (2), we have y = 1. In the same way, we show xy = 1 в‡’ x = 1.
n
Now let us suppose that П€(x1 , . . . , xn ) = i=1 xi = 1. Clearly the order of x1
n n
and the order of i=2 xi are coprime, and as we have shown above, x1 Г— i=2 xi =
1 в‡’ x1 = 1 and n xi = 1. In particular x1 = 1. Then, by induction on the
i=2
n
relation i=2 xi = 1, we get the expected result
n
П€(x1 , . . . , xn ) = xi = 1 в‡’ x1 = . . . = xn = 1 .
i=1

Now let us show that П€ is an epimorphism.
n
For all y в€€ G, | y | divides |G|. Hence, | y | = i=1 pОіi where Оіi в‰¤ ОІi for
i
Оі
all i в€€ {1, . . . , n}. Let ui = j=i pj j for i в€€ {1, . . . , n}. Then, y ui в€€ Gpi since
| y ui | = pОіi . Moreover, the ui,iв€€{1,...,n} are coprime as there exists no integer
i
dividing all ui . According to BВґzoutвЂ™s identity, there exists a1 , . . . , an such that
e
n n ui ai
i=1 ai ui = 1. Hence, for all y в€€ G, y = i=1 xi with xi = y в€€ Gpi .
n
pОІi where pi,i=1...n are prime
Lemma 3. Let G be a group with |G| = i
i=1
numbers. Then, |Gpi | = pОІi .
i
Proof. Necessarily, |Gpi | is a power of pi , say pОіi . Indeed, from CauchyвЂ™s Lemma,
i
if |Gpi | were divisible by some prime number p = pi , it would contain an element
of order p, which is contradictory with the deп¬Ѓnition of Gpi . Then, since G в€ј =
ОІi Оіi
p | |G| Gp , we have i pi = i pi , so Оіi = ОІi for all i.

We have WG = G2 and, from lemma 3, |G2 | = 2ОІ . Finally,
|WG | 1
Pr {r в€€ WG } = =.
|G| О±
rв†ђG

References
1. Kocher, P.C.: Timing Attacks on Implementations of Diп¬ѓe-Hellman, RSA, DSS,
and Other Systems. In: CRYPTO. Volume 1109 of Lecture Notes in Computer
Science. (1996) 104вЂ“113
2. Boneh, D., DeMillo, R.A., Lipton, R.J.: On the Importance of Checking Cryp-
tographic Protocols for Faults. Lecture Notes in Computer Science 1233 (1997)
37вЂ“51
3. Kocher, P., Jaп¬Ђe, J., Jun, B.: Diп¬Ђerential Power Analysis. Lecture Notes in Com-
puter Science 1666 (1999) 388вЂ“397
4. Montgomery, P.L.: Speeding the Pollard and elliptic curve methods of factorization.
Mathematics of Computation 48(177) (January 1987) 243264
5. Coron, J.S.: Resistance Against Diп¬Ђerential Power Analysis for Elliptic Curve
Cryptosystems. In C.K. KoВё, Paar, C., eds.: Cryptographic Hardware and Embed-
Вё c
ded Systems вЂ” CHES 2002. Volume 1717 of Lecture Notes in Computer Science.
(1999) 292вЂ“302
6. Goubin, L.: A reп¬Ѓned power analysis attack on elliptic curve cryptosystems. In
Springer-Verlag, ed.: Public Key Cryptography PKC 2003. Volume 2567 of Lecture
Notes in Computer Science. (2003) 199211
7. Dupuy, W., Kunz-Jacques, S.: Resistance of Randomized Projective Coordinates
Against Power Analysis. In B.S. Kaliski Jr., c.K., Paar, C., eds.: Cryptographic
Hardware and Embedded Systems вЂ” CHES 2005. Volume 3659 of Lecture Notes
in Computer Science. (2005) 1вЂ“12
8. Joye, M., Yen, S.M.: The Montgomery Powering Ladder. In B.S. Kaliski Jr., c.K.,
Paar, C., eds.: Cryptographic Hardware and Embedded Systems вЂ” CHES 2002.
Volume 2523 of Lecture Notes in Computer Science. (2002) 291вЂ“302
9. Trichina, E., Bellezza, A.: Implementation of elliptic curve cryptography with
built-in counter measures against side channel attacks. In B.S. Kaliski Jr., c.K.,
Paar, C., eds.: Cryptographic Hardware and Embedded Systems вЂ” CHES 2002.
Volume 2523 of Lecture Notes in Computer Science. (2002) 98вЂ“113
10. Pohlig, S.C., Hellman, M.E.: An improved algorithm for computing logarithms
over GF(p) and its cryptographic signiп¬Ѓcance. IEEE Transactions on Information
Theory 24 (1978) 106вЂ“110
11. Giraud, C.: Fault Resistant RSA Implementation. In Breveglieri, L., Koren, I.,
eds.: 2nd Workshop on Fault Diagnosis and Tolerance in Cryptography вЂ” FDTC
2005. (2005) 142вЂ“151
12. Ciet, M., Joye, M.: Practical Fault Countermeasures for Chinese Remaindering
Based RSA. In Breveglieri, L., Koren, I., eds.: 2nd Workshop on Fault Diagnosis
and Tolerance in Cryptography вЂ” FDTC 2005. (2005) 124вЂ“131

 << Предыдущая стр. 2(из 2 стр.)ОГЛАВЛЕНИЕ