Cryptography Reference
In-Depth Information
mod
N
(see Algorithm 8.9). If this test fails, the signature is not returned.
1
Infective computation can also be used here as well to avoid an explicit check.
S
[
1
]
Algorithm 8.8:
SPA-SE-resistant modular exponentiation
Input
:
M
=
0
,
d
=
(
d
n
−
1
,...,
d
0
)
2
odd
,
k
,
N
Output
:
M
d
−
1
N
,
M
d
mod
k
·
mod
k
·
N
1
begin
2
S
[
0
]←−
M
;
2
S
[
1
]←−
S
[
0
]
mod
k
·
N
;
3
for
if
ro
mn
−
2
t
o
1
do
4
S
[
d
i
]←
S
[
d
i
]·
S
[
d
i
]
mod
k
·
N
;
5
2
S
[
d
i
]←
S
[
d
i
]
mod
k
·
N
;
6
end
7
S
[
1
]←
S
[
1
]·
S
[
0
]
mod
k
·
N
;
8
2
S
[
0
]←
S
[
0
]
mod
k
·
N
;
9
if
(Loop Counter i not disturbed)
&
(Exponent d not disturbed)
then
10
Return (
S
[
0
]
,
S
[
1
]
)
11
12
else
13
Return error
14
end
15
end
Algorithm 8.9:
Giraud's SPA and FA-resistant CRT-RSA
Input
:
M
=
0
,
p
,
q
,
d
p
,
d
q
,
i
q
,
N
Output
:
M
d
mod
N
1
begin
2
Pick a 32-bit random number
k
;
(
S
p
,
S
p
)
←−
Algorithm
8.8
with
M
,
d
p
,
p
,
k
as inputs;
3
S
q
,
(
S
q
)
←−
Algorithm
8.8
with
M
,
d
q
,
q
,
k
as inputs;
4
S
∗
←
CRT
bli nded
(
S
p
,
S
q
);
5
S
←
CRT
bli nded
(
S
p
,
S
q
);
6
S
∗
←
S
∗
mod
M
·
(
p
·
q
)
;
7
if
(S
∗
=
S)
&
(Parameters p
,
q
,
i
q
not modified)
then
8
9
Return (
S
)
10
else
11
Return error
12
end
13
end
1
The original version of [161] does not have a blinded modulus. That is, every modular computation
is done with modulus
N
instead of
k
·
N
. Therefore the original version is vulnerable to a relative
doubling attack [431]. The CRT recombination with blinded moduli is also used in the modified
version to counter other specific SPA attacks (cf. [311]).