Cryptography Reference
In-Depth Information
Fumaroli and Vigilant proposed a variant based on the Montgomery ladder [149].
However, it was shown that this method could not be used to build a fault-resistant
implementation of CRT-RSA [228]. Giraud's idea was extended to a right-to-left
exponentiation algorithm by Boscher et al. [61].
Rivain proposed a double exponentiation algorithm [346]. He devised an algo-
rithm taking as input two exponents
a
and
b
and returning
M
a
M
b
(
mod
N
,
mod
N
)
.
Using this algorithm one can detect faults by setting
a
=
d
and
b
=
ϕ(
N
)
−
d
and
M
ϕ(
N
)
−
d
checking that
M
d
1mod
N
.
In conclusion, Giraud's method and variants exploit some redundancy already
present in the exponentiation algorithm. This can be a disadvantage they impose the
exponentiation algorithm.
·
≡
8.6 Embedding Method
As we have discussed in Sect.
8.3
, we can verify the signature with the public
exponent
e
.And
e
is in nearly all cases chosen as a small value (a typical value
of
e
is 2
16
+
1). However, in some applications (e.g. Java card), it is not allowed to
access the public exponent during signature generation.
In 2009, Joye suggested embedding the value of
e
in the RSA key object [198].
Such a key object is obtained from
(
p
,
q
,
d
p
,
d
q
,
i
q
)
in CRT mode and from
(
N
,
d
)
M
d
mod
N
, it is checked
whether the public exponent
e
is embedded in the representation of the RSA key.
If this is the case, the public exponent
e
is recovered. Then it is verified if
S
e
in standard mode. When computing an RSA signature
S
=
≡
in standard mode or if
S
e
in CRT mode.
The public exponent
e
is embedded in RSA modulus
N
, which is shared between
the standard and CRT RSA key objects (notice that
N
can be obtained as
p
M
(
mod
N
)
≡
M
(
mod
pq
)
q
in
CRT mode). This can be done by using the method to generate RSA modulus
N
with
a predetermined portion [197].
·
8.7 Second-Order Fault Attacks
Until recently, most of the theoretical fault attacks and countermeasures used a fault
model that assumed that the attacker was able to disturb the execution of a crypto-
graphic algorithm only once. However, this approach seems too restrictive since the
publication in 2007 of the successful experiment of an attack based on the injection
of two faults, namely a second-order fault attack, by Kim and Quisquater [226].
Kim and Quisquater introduced a second-order fault model where they were able
to practically break the (first-order) countermeasures of [91, 161]. In their model, one
fault is dedicated to the corruption of the RSA computation in order to produce an
exploitable faulty signature. The other fault is then used to render the countermeasure
ineffective.
