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 [11], 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 [12], 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 [11]

with the infective computation technique of [12] (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