Cryptography Reference
In-Depth Information
Factoring
Finally, using LLL again as in the linearization step, we can construct a short vector
v
orthogonal to both
x
and
y
modulo
N
. Then
v
is also orthogonal mod
N
to all
-linear combinations of
x
and
y
, in particular
x
and
y
. Therefore, taking the inner
product of (
12.6
) with
v
, we get
Z
a
,
v
≡
0
(
mod
p
)
and we can thus factor
N
as required:
gcd
(
a
,
v
,
N
)
=
p
.
Summary and Experiments
If condition (
12.9
) is satisfied, the following algorithm should heuristically find a
nontrivial factor of
N
:
1. Find an LLL-reduced basis
Z
orthogonal
(
u
1
,...,
u
)
of the lattice of vectors in
to
a
modulo
N
.
2. Find a basis
x
,
y
)
Z
orthogonal to
u
j
,1
2.
3. Find a short vector
v
orthogonal to
x
and
y
modulo
N
(for example, the first
vector of an LLL-reduced basis of the lattice formed by such orthogonal vectors).
4. Return gcd
(
of the lattice of vectors in
≤
j
≤
−
(
a
,
v
,
N
)
.
The attack is heuristic because it might be the case that
u
j
is not actually orthogonal
to
x
and
y
in
Z
for all
j
2.
Experimentally, however, success rates are very high when condition (
12.9
)is
verified. For example, for
≤
−
γ
+
δ
=
0
.
33, condition (
12.9
) says
12. Simulations
from [108] with a 1
,
024-bit balanced RSA modulus
N
find a 13 % success rate for
=
12 and a 100 % success rate for
=
13. Note by the way that a total unknown
message part of
33 is out of reach of the single-fault attack from [104], and
its Coppersmith-based multi-fault variant is totally inapplicable for such parameter
sizes, whereas this attack is computationally very easy.
γ
+
δ
=
0
.
12.4.5 Proposed Countermeasures
Since faulty signatures are invalid, a possible countermeasure is to check the signature
after generation. Since signature verification is significantly cheaper than signature
generation in cases of interest (because of a low public exponent), this is a reasonable
option, and preferable to incurring the four fold performance penalty of not using
the Chinese Remainder Theorem at all. More generally, other usual countermeasures
against RSA-CRT fault attacks, as proposed, for example, by Shamir [201, 372] or