Cryptography Reference
In-Depth Information
8.3 Basic Countermeasures
The simplest way to prevent the Bellcore attack is to compute a signature twice and
compare the two results. However, this doubles the computation time, and it cannot
prevent permanent errors. Another way is to verify the signature with the public
exponent
e
. That is, the device returns the signature
S
only when
S
e
m
mod
N
.
However, this method is too costly if
e
is large. Furthermore, in some applications
(e.g. Java card), one does not have access to the public exponent
e
during signature
generation.
=
8.4 Shamir's Method and Variants
Most countermeasures against the Bellcore attack rely on the method first suggested
by Shamir in 1997 [372]. In chronological order, they are [18, 53, 91, 103, 201,
228, 372, 409, 429]. Shamir's method and variants compute exponentiation with
some redundancy as shown in Algorithm 8.1. A random integer
r
is first chosen
and then modular exponentiation is computed based on
r
N
. If there is an error
during the computation of the modular exponentiation, it is detected by evaluating
if
S
∗
≡
.
Z
(
mod
r
).
Algorithm 8.1:
Basic concept of Shamir's method and variants
Input
:
M
=
0
,
d
,
N
.
Output
:
M
d
mod
N
or
error
.
1
begin
2
Choose a (small) random integer
r
;
Compute
S
∗
=
M
d
mod
rN
and
Z
=
M
d
mod
r
;
3
4
if
S
∗
≡
Z
mod
r
then
5
Output
S
=
S
∗
mod
N
6
else
7
Return
error
8
end
9
end
Shamir's method is shown in Algorithm 8.2. Both exponentiations are computed
based on
pr
and
qr
respectively. Then there is a step to check an error. The disad-
vantage of Shamir's method is that it requires
d
, which is not known in CRT mode
(only
d
p
and
d
q
are known). Joye et al. proposed a variant using only
d
p
and
d
q
as
shown in Algorithm 8.3 [201].
However, the algorithm proposed by Joye et al. cannot detect an error in CRT
recombination. Aumüller et al. exploited this security flaw [18]. If one of the
S
p
,
S
q
and
i
q
values is transiently modified during the recombination step, the fault is not
detected. To thwart this attack, a countermeasure was also presented in [18]. However,
