LINEBURG






On the Implementation of a Fast Prime
Generation Algorithm

Christophe Clavier and Jean-S´bastien Coron
e
1
Gemalto, Security Labs,
La Vigie, Avenue du Jujubier, ZI Ath´lia IV,
e
F-13705 La Ciotat Cedex, France
christophe.clavier@gemalto.com
2
University of Luxembourg,
Faculty of Sciences, Technology and Communication,
6, rue Richard Coudenhove-Kalergi,
L-1359 Luxembourg
jean-sebastien.coron@uni.lu



Abstract. A side-channel analysis of a cryptographic algorithm gener-
ally concentrates on the encryption or decryption phases, rarely on the
key generation phase. In this paper, we show that, when not properly
implemented, the fast prime generation algorithm proposed by Joye and
Paillier at CHES 2006 is susceptible to side-channel analysis; its main
application is the generation of RSA key-pairs for embedded platforms
like smart-cards. Our attack assumes that some parity bit can be recov-
ered through SPA when it appears in a branch condition. Our attack can
be combined with Coppersmith™s theorem to improve its e¬ciency; we
show that for 1024-bit RSA moduli, one can recover the factorization of
roughly 1/1000 of the RSA moduli.


Key-words : Simple Power Analysis, Prime generation algorithm, Copper-
smith™s theorem.


1 Introduction
Side-channel analysis, such as Simple Power Analysis (SPA) and Di¬erential
Power Analysis (DPA) [7], generally concentrates on the encryption or decryp-
tion phases, rarely on the key generation phase. Namely encryption or decryption
o¬er more ¬‚exibility to the attacker who can provide various messages as input
and each time record a side channel leakage. In contrast, a key generation al-
gorithm doesn™t take any input (beyond a security parameter) and in general
it doesn™t help to execute it multiple times since a di¬erent key is obtained for
each new execution.
In this paper, we show that, when not properly implemented, one of the fast
prime generation algorithms proposed by Joye and Paillier at CHES 2006 [6] is
susceptible to side-channel analysis. The main application of the Joye-Paillier
algorithm is to generate RSA keys on embedded platforms like smart-cards,
where e¬ciency is of crucial importance. Prime generation usually works by
applying a primality test on randomly generated integers, until a prime is found.
The technique described in [6] consists in generating random integers that are not
divisible by the ¬rst primes pi ; then a prime appears with higher probability, and
on average fewer primality tests have to be applied, which improves e¬ciency.
A faster variant is described in [6] where a sequence of candidates is generated
from a random seed and the parity of each candidate is tested before applying
a primality test, until a prime is found. In this paper, we concentrate on an
implementation of this faster variant; we show that if n primality tests have been
applied and if the parity bits can be obtained through SPA, then we can recover
the n ’ 1 least signi¬cant bits of the output prime. Coppersmith™s theorem
[1] shows that an RSA modulus N = pq can be factored in polynomial time
given half of the least signi¬cant (or most signi¬cant) bits of p. Therefore, if the
number n of primality tests for p or q is more than half the bit-size of p, one can
recover the factorization of N e¬ciently. We provide an analysis which shows
that for certain parameters (bmin = bmax = 0) and for 1024-bit RSA moduli,
this happens for 10’3 of the generated RSA moduli.


2 The Joye-Paillier Prime Generation Algorithm

The Joye-Paillier algorithm [6] consists in generating a sequence of candidates
q that are co-prime with the ¬rst small primes pi ; a primality test T (q) is then
applied on each candidate until a prime is found. Here we concentrate on the
faster variant (from Fig. 3 in [6]). One de¬nes Π as the product of the r ¬rst
primes, excluding p1 = 2, so that Π is odd :
r
Π= pi
i=2

Let [qmin , qmax ] be the interval in which the prime integers must be generated.
One de¬nes integers bmin , bmax and v such that :

qmin ¤ (v + bmin )Π, and (v + bmax + 1)Π < qmax

The prime integers will actually be generated in the sub-interval :

[(v + bmin )Π, (v + bmax + 1)Π]

See [6] for more details on the selection of parameters bmin , bmax and v. We
denote by T (q) a primality test (for example, Miller-Rabin [8]).
Fast Prime Generation Algorithm [6] :
Parameters : Π odd, bmin , bmax , v
Output : a random prime q ∈ [qmin , qmax ]
1. Compute ← vΠ
2. Randomly choose k ∈ (Z/ΠZ)—

2
3. Randomly choose b ∈ {bmin , . . . , bmax } and set t ← bΠ
4. Set q ← k + t +
5. If (q even) then q ← Π ’ k + t +
6. If T (q) = false then
(a) Set k ← 2k mod Π
(b) Go to step 4.
7. Output q

It is easy to see that the candidate q at step 6 is odd and co-prime with all
primes in Π. Namely, we have that q = ±k mod Π and k remains always in
(Z/ΠZ)— , because 2 ∈ (Z/ΠZ)— . This implies that q is co-prime with all primes
in Π. Moreover, if q = k+t+ is even at step 4, then q = Π ’k+t+ = Π ’2k+q
must be odd since Π is odd, and therefore q is odd at step 6. Since we ensure
that each candidate q is not divisible by the ¬rst small primes, each candidate
is prime with higher probability, so one gets a faster prime generation algorithm
(see [6] for a complete analysis).


3 Our Side-Channel Attack

Our attack is based on the assumption we can recover the parity of k at step
4 thanks to the parity test performed on q at step 5. Namely, on a practical
implementation, a branch condition usually produces a di¬erent physical leakage
depending on the result of the test. Indeed by measuring power consumption,
the attacker may be able to determine if the operation q ← Π ’k +t+ has been
performed or not, which gives him the parity bit of q. Our attack is therefore a
Simple Power Attack (SPA) on the parity bit of q. In practice, this assumption
may be realistic or not, depending on the micro-processor used, the presence of
hardware countermeasures, and the way the test is implemented. We note that
SPA attacks based on analogous assumptions have been described in [3, 4].
Here we show that this sequence of parity bits enables us to recover the least
signi¬cant bits of the prime q returned as output. Our attack is based on the
following simple lemma :

Lemma 1. Let Π be an odd integer and let k0 ∈ Z Π . De¬ne Bi = 2i k0 /Π
Z
i
and the sequence ki = 2 k0 mod Π. Then, for i ≥ 1, Bi = j=1 (kj mod 2)2i’j .
i


Proof. By de¬nition, we have 2i’1 k0 = Bi’1 Π + ki’1 . Hence, we have 2i k0 =
2Bi’1 Π + 2ki’1 = (2Bi’1 + 2ki’1 /Π )Π + ki , which gives Bi = 2Bi’1 +
i
2ki’1 /Π . It follows that Bi = j=1 2kj’1 /Π 2i’j (note that B0 = 0).
Moreover, we have 2kj’1 = 2kj’1 /Π Π + kj . Taking the relation modulo
2, we get 2kj’1 /Π ≡ kj (mod 2) as Π is odd, and since 2kj’1 < 2Π, we have
2kj’1 /Π = kj mod 2. This concludes the proof.

Proposition 1. With the previous notation and letting bj = kj mod 2, we have
i
ki ≡ ’( j=1 bj 2i’j ) Π (mod 2i ).


3
Proof. This follows immediately from the previous lemma by observing that
Bi Π = 2 i k0 ’ k i .

We assume that the parameters Π, bmin , bmax and v are public and known
to the attacker. Let ki = k0 · 2i mod Π for i ≥ 0 denote the sequence of integers
k which appear at step 4, where k0 is the integer initially generated at step 2.
Let qi = ki + t + denote the corresponding integer computed at step 4. From
the parity of qi tested at step 5, one can therefore obtain the parity of ki ; this
is done by making an assumption on the parity of t + , which is constant after
step 4. Then using the previous lemma, after n + 1 primality tests the value of
kn mod 2n is obtained 3 . Then we can write :

kn = 2 n · x + x0

where 0 ¤ x0 < 2n is known and x is unknown. Therefore the prime generated
q = kn + t + or q = Π ’ kn + t + can be written :

q = 2 n · x + x0 + b · Π +

where x and b ∈ [bmin , bmax ] are integers unknown to the attacker, and the
integers n, k0 , Π and are known.
We make the following assumption : we assume that bmin = bmax = 0, so
that b = 0. We note that taking bmin = bmax = 0 is a valid parameter choice in
the Joye-Paillier algorithm. In this case, the integer q can be written :

q = 2n · x + C

where C is a known constant and x is an unknown integer.

Theorem 1 (Coppersmith [1]). Given N = pq and the high-order or low-
order 1/4 log2 N bits of p, one can recover the factorization of N in time poly-
nomial in log N .

Using Coppersmith™s theorem, one can therefore recover the factorization of
N in polynomial-time if the number n of primality tests is at least half the
bit-size of p. Let ± denote the probability that a random n0 -bit odd integer
q co-prime with Π is prime. We make the heuristic approximation that the
candidates qi behave as if they were uniformly and independently distributed.
From the analysis of [5], we obtain that a candidate qi is prime with probability :

1 Π
±= ·
n0 · ln 2 φ(Π )

where Π = 2Π and φ is Euler™s function. Therefore, letting X be the random
variable that gives the number of primality tests, we have :

Pr[X = i] = (1 ’ ±)i’1 · ±
3
We need n + 1 parity bits because we don™t use the ¬rst one.


4
which gives E[X] = 1/± and :

Pr[X ≥ i] = (1 ’ ±)i’1

To summarize, if the attack is applied for both p and q, the factorization of a
2n0 -bit RSA modulus can be recovered in polynomial-time for a fraction :
n0 /2’1
1 Π
δ 2· 1’ ·
n0 · ln 2 φ(Π )

of the generated moduli. We provide in Table 1 the corresponding fraction for
various moduli size. For a prime size of n0 bits, we take the largest r such that :
r
pi < 2n0 ’1
Π=
i=2

Then we take v = 2n0 /Π and qmin = v · Π and qmax = (v + 1) · Π, with
bmin = bmax = 0; this is a valid parameter choice for the Joye-Paillier algorithm.
Table 1 shows that for a 1024-bit RSA modulus, our side channel attack enables
8.4 · 10’4 of the RSA moduli. If the algorithm is run
to factor a fraction δ
only once inside a smart-card, this means that in practice a fraction 8.4 · 10’4
of the smart-cards could be broken.


RSA n0 r E[X] δ
512 bits 256 43 18.7 1.8 · 10’3
768 bits 384 60 26.1 1.1 · 10’3
1024 bits 512 75 33.3 8.4 · 10’4
2048 bits 1024 131 60.0 3.7 · 10’4

Table 1. RSA modulus bit-size, bit-size n0 of primes p and q, number r of primes pi
in Π, average number E[X] of primality tests, and fraction δ of weak RSA moduli.




We note that the assumption bmin = bmax = 0 could be relaxed to small
(known) values for bmin and bmax ; in this case the value b ∈ [bmin , bmax ] would
be exhaustively searched 4 .


4 Countermeasures

In this section we discuss three possible countermeasures. Our ¬rst countermea-
sure is to periodically re-generate a fresh seed k so that the attacker doesn™t
4
Alternatively, one could try to derive a variant of Coppersmith™s theorem for primes
of the form q = 2n · x + b · Π + C, with unknown x and b, and known constants Π
and C.


5
obtain enough information about the prime q. Let s > 0 be the maximum num-
ber of primality tests performed for a given seed k. The integer s should be small
enough to prevent the previous attack, but not too small to keep the same level
of e¬ciency; we propose to take s = n0 /4 where n0 is the prime bit-size. One
gets the modi¬ed algorithm :

Modi¬ed Prime Generation Algorithm :
Parameters : s, Π odd, bmin , bmax , v
Output : a random prime q ∈ [qmin , qmax ]

1. Compute ← vΠ
2. Let i ← 0.

3. Randomly choose k ∈ (Z/ΠZ)
4. Randomly choose b ∈ {bmin , . . . , bmax } and set t ← bΠ
5. Set q ← k + t +
6. If (q even) then q ← Π ’ k + t +
7. If T (q) = false then
(a) Set k ← 2k mod Π
(b) Let i ← i + 1
(c) If i < s then go to step 5, otherwise go to step 2.
8. Output q

Our second countermeasure consists in replacing the instruction k ← 2 · k
mod Π by k ← 2t · k mod Π where t is a small random integer. If k ← 2t · k
mod Π is implemented in constant time, then the attacker doesn™t know for
which integers ki = 2i · a mod Π he gets the parity bits, which prevents the
previous attack. This second countermeasure is e¬cient because the additional
running time is probably negligible compared to the primality test running time.
Our third countermeasure is to implement the test so that it doesn™t leak.
The standard way is to compute both sides of the branch and select the correct
result. This countermeasure is analogous to the square & multiply always and
double & add always countermeasures in RSA exponentiation and ECC scalar
multiplication (see [2]). The instruction :

6. If (q even) then q ← Π ’ k + t +

is then replaced by :

6. (a) Let u ← q mod 2
(b) Set A[0] ← Π ’ k + t +
(c) Set A[1] ← q
(d) Let q ← A[u]

In this case the computation of Π ’ k + t + is always performed so it is likely
more di¬cult for the attacker to recover the parity of q.

6
5 Conclusion and Open Problem

We have demonstrated that an improper implementation of the Joye-Paillier
prime generation algorithm may succumb to side-channel analysis. Our attack is
based on the assumption that a Simple Power Analysis can give us the parity bits
which appear in a branch condition. We have shown that for certain parameters
(bmin = bmax = 0) and for 1024-bit RSA moduli, a fraction 10’3 of those moduli
can be factored e¬ciently. However in practice, some of the parity bits obtained
through SPA may be erroneous. Therefore an interesting open problem is to ¬nd
an attack that works with errors; formally :
Open Problem: let β > 0, let Π be an odd integer and let k0 ∈ Z Π . De¬ne
Z
i
the sequence ki = 2 k0 mod Π and bi = ki mod 2 for i ≥ 1. Let bi = bi with
probability 1 ’ β and bi = 1 ’ bi otherwise, independently for each i ≥ 1. Given
the sequence bi for i ≥ 1, ¬nd k0 in time polynomial in log Π.

Acknowledgments : we wish to thank Marc Joye and the anonymous reviewers
for their valuable comments.


References
1. D. Coppersmith, Small solutions to polynomial equations, and low exponent vul-
nerabilities. J. of Cryptology, 10(4)233-260, 1997. Revised version of two articles
of Eurocrypt ™96.
2. J.S. Coron, Resistance against Di¬erential Power Analysis for Elliptic Curve Cryp-
tosystems. Proceedings of CHES ™99. LNCS, Springer-Verlag.
3. W. Dupuy and S. Kunz-Jacques, Resistance of Randomized Projective Coordinates
Against Power Analysis, Proceedings of CHES 2005, LNCS.
4. P.A. Fouque, S. Kunz-Jacques, G. Martinet, F. Muller, and F. Valette. Power At-
tack on Small RSA Public Exponent. Proceedings of the 8th International Work-
shop on Cryptographic Hardware and Embedded Systems (CHES ™06), LNCS 4249,
Springer-Verlag, 2006.
5. M. Joye, P. Paillier and S. Vaudenay, E¬cient Generation of Prime Numbers.
Proceedings of CHES™00, Lecture Notes in Computer Science, Springer-Verlag No
1965, pp. 340-354.
6. M. Joye and P. Paillier, Fast Generation of Prime Numbers of Portable Devices:
An Update. Proceedings of CHES 2006, LNCS 4249, pp. 160-173, 2006.
7. P. Kocher, J. Ja¬e, and B. Jun, Di¬erential power analysis, Advances in Cryptol-
ogy - CRYPTO ™99, Lecture Notes in Computer Science, vol. 1666, pp. 388“397,
Springer-Verlag, 1999.
8. G. Miller, Riemann™s Hypothesis and Tests for Primality. J. Comp. Syst. Sci. 13,
300-317, 1976.




7





Copyright Design by: Sunlight webdesign