Cryptography Reference
In-Depth Information
Algorithm 8.2:
Shamir's CRT-RSA
Input
:
M
=
0
,
d
,
p
,
q
,
i
q
.
Output
:
M
d
mod
N
or
error
.
1
begin
2
Choose a (small) random integer
r
;
Compute
S
p
=
M
d
and
S
q
M
d
mod
(
pr
)
=
mod
(
qr
)
;
3
Compute
S
p
=
S
p
mod
p
and
S
q
=
S
q
mod
q
;
4
S
q
mod
r
then
6
Output
S
=
CRT
(
S
p
,
S
q
)
7
else
8
Return
error
9
end
10
end
if
S
p
≡
5
Algorithm 8.3:
Joye et al.'s CRT-RSA
Input
:
M
=
0
,
p
,
q
,
d
p
,
d
q
,
i
q
Output
:
M
d
mod
N
or
error
1
begin
2
Choose a (small) random integer
r
1
and
r
2
;
Compute
S
p
=
M
d
p
M
d
p
mod
ϕ(
r
1
)
mod
r
1
;
mod
(
pr
1
),
s
1
=
3
S
q
M
d
q
M
d
q
mod
ϕ(
r
2
)
mod
r
2
;
=
mod
(
pr
2
),
s
2
=
4
S
p
mod
p
and
S
q
=
S
q
mod
q
;
Compute
S
p
=
5
if
S
p
≡
s
1
mod
r
1
and S
q
≡
s
2
mod
r
2
then
6
7
Output
S
=
CRT
(
S
p
,
S
q
)
8
else
9
Return
error
10
end
11
end
Yen et al. showed that this countermeasure introduced another vulnerability [432].
That is, the modified algorithm can be attacked by injecting a permanent fault during
the CRT recombination.
8.4.1 Infective Computation
Yen and Joye introduced the concept of infective computation in 2000 [427] (see also
[429]). The principle is that, if an error changes the result of one of the exponentiations
(i.e.,
S
p
or
S
q
), then it will also infect the result of the other one. Hence, even if
S
,
S
≡
(
)
≡
(
)
S
mod
q
S
mod
p
and the faulty signature will not be exploitable with
the classical gcd computation.
Moreover, the authors proposed using infective computation-based methods to
avoid conditional checks. In Shamir's method, there is a conditional branch. Yen et
