Cryptography Reference
In-Depth Information
Theorem 12.1
(Herrmann-May [179])
Let N be a sufficiently large composite inte-
ger with a divisor p
N
β
. Let f
≥
∈ Z[
x
,
y
]
be a bivariate linear polynomial. Assume
N
γ
N
δ
.
that f
(
x
0
,
y
0
)
=
0
mod p for some
(
x
0
,
y
0
)
such that
|
x
0
|≤
and
|
y
0
|≤
Then for any
ε>
0
, under the condition
3
/
2
γ
+
δ
≤
3
β
−
2
+
2
(
1
−
β)
−
ε
(12.4)
one can find linearly independent polynomials h
1
,
h
2
∈ Z[
x
,
y
]
such that h
1
(
x
0
,
y
0
)
ε
−
1
.
=
h
2
(
x
0
,
y
0
)
=
0
over
Z
, in time polynomial in
log
N and
In our case,
N
is a (presumably balanced) RSA modulus, so
β
=
1
/
2 and condition
(
12.4
) becomes
√
2
−
1
γ
+
δ<
≈
0
.
207
.
(12.5)
2
Under that condition, we obtain two linearly independent polynomials
h
1
,
h
2
∈
Z[
x
is a root of both.
Suppose further that
h
1
,
,
y
]
such that
(
x
0
,
y
0
)
h
2
are in fact
algebraically
independent. It is then easy
to compute the finite list of their common roots, e.g. by taking the resultant with
respect to
y
and solving for
x
, and thus to find
(
x
0
,
y
0
)
. Once
(
x
0
,
y
0
)
is computed,
one can proceed as in the Bellcore attack to factor
N
:
gcd
f
N
=
(
x
0
,
y
0
)
mod
N
,
p
.
The algebraic independence assumption makes the attack heuristic, but the exper-
imental validation carried out in [104] suggests that it works well for
γ
+
δ
not too
large. For example, with a 2
048-bit modulus and 160-bit hash function, a 158-bit
long nonce
r
is recovered in less than a minute with a single fault. The total fraction
of unknown message bits is then
,
155.
However, condition (
12.5
) is quite restrictive, especially when
N
is small. Indeed,
for a 1
γ
+
δ
=
(
158
+
160
)/
2
,
048
≈
0
.
024-bit modulus with a 160-bit hash function, the theoretical maximum nonce
size that can be recovered is 58 bits, and the algorithm is only manageable in practice
for much smaller sizes. As a result, the attack performs worse than exhaustive search
for
r
for this modulus size.
To tackle larger unknown message parts, it is necessary to take advantage of sev-
eral faulty signatures. This Coppersmith-based attack admits a natural extension to
multiple faults [104, Sect. 2.4], but the lattice dimensions involved grow exponen-
tially with the number of faulty signatures, so that the extension is only practical for
a very small number of faults, and does not extend the scope of the single-fault attack
by a large margin.
,
