Cryptography Reference
In-Depth Information
8.2 Fault Attacks Against RSA-CRT
RSA-CRT (RSA with CRT mode), first introduced by Quisquater and Couvreur
[330], uses the Chinese remainder theorem to speed up the computation of an RSA
decryption or a signature and reduces the size of the data stored in memory. In terms
of binary operations, this implementation is four times faster than RSA standard
mode. This is why the CRT implementation of RSA is widely deployed in embedded
systems.
Here we describe RSA-CRT using Garner's reconstruction method [154]. Let
N
=
p
·
q be RSA modulus and let
ϕ(
N
) = (
p
1
)(
q
1
)
, where p and q are large
primes. We select a random integer e
,
1
<
e
<ϕ(
N
)
, such that gcd( e
,ϕ(
N
)
)=1.
Then we compute d such that e
·
d
1mod
ϕ(
N
)
. In the CRT mode, we compute
q 1
d p =
d mod
(
p
1
)
, d q
=
d mod
(
q
1
)
, and i q
=
mod p . The public key is
(
N
,
.
The RSA signature on a message M is computed as follows:
e
)
and the private key is
(
p
,
q
,
d p ,
d q ,
i q )
d p
d q
S p = μ(
)
,
S q = μ(
)
,
M
mod p
M
mod q
=
(
S p ,
S q ) =
S q +
(
i q (
S p
S q )
),
S
CRT
q
mod p
where
μ( · )
is an appropriate padding function. Without loss of generality we use M
instead of
μ(
M
)
in the subsequent sections to simplify the explanation. Therefore we
M d mod N . The signature is performed by computing two exponentiations
modulo p and q ( S p ,
let S
=
S q ) followed by a CRT recombination (CRT
(
S p ,
S q )
). This
recombination relies on the Chinese remainder theorem.
Boneh et al. showed that if an error occurs in only one of the exponentiations (that
is, during computation of S p or S q , but not during both), then the factorization of
N is possible with the correct and faulty signatures, S and S [56] (it is also referred
to as the Bellcore attack as the authors were Bellcore researchers). For example,
suppose that an error occurs during computation of S p . Then a faulty
S p will be used
S
( S p ,
in the CRT recombination and
=
CRT
S q )
will be returned. With the correct
S , the secret prime q can be computed by computing
signature S and the faulty one
S
q
=
gcd
((
S
)
mod N
,
N
).
It was shown that the attack is possible with only one execution of the algorithm [199].
That is, with only faulty signature the secret prime number q could be recovered by
computing
(( S e
q
=
gcd
M
)
mod N
,
N
).
Search WWH ::




Custom Search