Cryptography Reference
In-Depth Information
Algorithm 8.6:
Ciet and Joye's algorithm
Input
:
M
=
0
,
p
,
q
,
d
p
,
d
q
,
i
q
Output
:
M
d
mod
N
or a random value in
Z
/
N
Z
1
begin
2
Choose two
k
-bit random integers
r
1
and
r
2
;
Store in memory
p
∗
=
q
∗
=
q
∗
)
−
1
mod
p
∗
,
r
1
p
,
r
2
q
,
i
q
∗
=
(
N
=
pq
;
3
Compute
S
p
∗
=
M
d
p
mod
p
∗
;
4
M
d
q
mod
ϕ(
r
2
)
mod
r
2
;
s
2
=
5
M
d
q
mod
q
∗
;
Compute
S
q
∗
=
6
M
d
p
mod
ϕ(
r
1
)
mod
r
1
;
s
1
=
7
Compute
S
∗
=
S
q
∗
+
qi
q
∗
(
S
p
∗
−
S
q
∗
)
mod
p
∗
;
8
Compute
c
1
=
(
S
∗
−
s
1
+
1
)
mod
r
1
;
9
c
2
=
(
S
∗
−
s
2
+
1
)
mod
r
2
;
10
γ
=
(
r
3
c
1
+
(
2
l
−
r
3
)
c
2
)
Pick a
l
-bit random value
r
3
and compute
;
11
2
l
S
∗
)
γ
mod
N
Return
S
=
(
12
13
end
(
S
e
M
γ
able to factor
N
by computing gcd
. From their experiment, the
authors evaluated that 83 signatures perturbed according to their model are enough
to factor
N
with a success probability of about 99 %.
In order to fix this flaw, they suggested in [38] replacing the final exponentiation
to the power of
−
mod
N
,
N
)
by the masking the operation already proposed, as a variant, by
Ciet and Joye [91]:
γ
S
∗
⊕
(γ
−
S
=
(γ
·
1
)
·
r
)
mod
N
.
8.4.4 Vigilant's Algorithm and Attack
Vigilant proposed an efficient method to protect a modular exponentiation against
a fault attack and extended this result to the case of RSA-CRT [409]. The principle
of Vigilant's secure exponentiation method consists in computing
M
d
mod
N
in
Z
Nr
2
where
r
is a small random integer that is coprime with
N
. Then the base
M
is
transformed into
M
∗
such that
M
mod
N
,
M
∗
≡
.
r
mod
r
2
1
+
This implies that
M
d
mod
N
,
M
∗
d
S
∗
=
mod
Nr
2
≡
.
dr
mod
r
2
1
+
