Cryptography Reference
In-Depth Information
Therefore a consistency check of the result
S
∗
can be performed modulo
r
2
from
d
and
r
. If the verification
S
∗
dr
mod
r
2
=
1
+
is successful, then the final result
S
∗
mod
N
is returned.
The application to RSA-CRT depicted in Algorithm 8.7 is derived from Shamir's
method [372]. The principle is to perform both half exponentiations modulo
pr
2
and
qr
2
. Therefore it is possible to perform a final consistency check after recombination,
guaranteeing that no error occurred during the computations of
S
p
or
S
q
and during
the recombination.
Coron et al. presented two weaknesses of Vigilant's algorithm and some modifi-
cations [103]. The weakness comes from the fact that the integrity of the modulus
computation, the
p
S
=
−
1 computation, and the
q
−
1 computation are not checked.
8.4.5 Summary of Shamir's Method and Variants
Although many countermeasures based on Shamir's method have been proposed,
almost all of them were shown not to be secure enough. For example, the methods
of [18, 53, 91] have been cryptanalyzed in [38, 410, 432] respectively.
All methods based on Shamir's cannot guarantee detecting all errors with 100 %
certainty, because there always exists a probability that
S
∗
≡
Z
mod
r
in the presence
of errors. However, with proper selection of the size of
r
(for example, 16, 32, or 64
bits), this probability becomes negligible. These methods impact the performance
in terms of both running time and memory requirement. In certain variants, extra
personalization process is also required.
Infective computation can be used to avoid conditional checks. Therefore, it can
be combined with other techniques. For example, Giraud's method and variants in
the next section (such as Shamir's method and variants).
8.5 Giraud's Method and Variants
In 2005, Giraud [161] proposed a SPA-(Simple Power Analysis-) and FA-(Fault
Attack-)resistant modular exponentiation based on the Montgomery ladder [205,
294]. Then he presented a variant of it as shown in Algorithm 8.9, where
k
is a
32-bit random number [162]. He used the fact that temporary variables
(
S
[
0
]
,
S
[
1
]
)
)
M
α
,
M
α
+
1
are of the form
at each step of the algorithm as shown in Algorithm
8.8. Both values are used to compute the next temporary couple. So if an error
occurs on a temporary result
S
(
)
[
]
[
]
, or even if a multiplication or a squaring
operation is disturbed at any moment of the computation, then the coherence between
S
0
or
S
1
[
0
]
and
S
[
1
]
is lost. Therefore, the last computed couple
(
S
[
0
]
,
S
[
1
]
)
is not of the
M
d
M
d
+
1
form of
. The error can thus be detected by checking the coherence
between the last two temporary results,
S
(
,
)
[
0
]
and
S
[
1
]
, i.e., by testing if
M
·
S
[
0
]≡
