Cryptography Reference
In-Depth Information
2
l
z
Writing these known bits as
k
0
we have, in the case of least significant bits,
k
=
k
0
+
z<r/
2
l
. Indeed, one gets a better result by writing
where 0
≤
2
l
r/
2
l
+
1
2
l
z
k
=
k
0
+
+
(22.7)
r/
2
l
+
1
r/
2
l
+
1
. Then one can re-write any of the above linear equations in the
with
−
≤
z
≤
form
z
≡
ta
−
u
(mod
r
)
for some
t,u
∈ Z
that are known. In other words, we know
t,u
MSB
l
(
at
(mod
r
))
,
=
(22.8)
which is an instance of the hidden number problem (see Section
21.7.1
).
If the values
t
in equation (
22.8
) are uniformly distributed in
Z
/r
Z
then Corollary
21.7.10
≥
log
2
(
r
)
directly implies that if
r>
2
32
consecutive bits of th
e rando
mness
k
then one can determine the private key
a
in polynomial-
time given
n
and if we can determine
l
+
log
2
(log
2
(
r
))
log
2
(
r
)
message-signature pairs. As noted in [
411
], in the practical
attack the values
t
arising are not uniformly distributed. We refer to [
411
,
412
] for the full
details. In practice, the attack works well for current values for
r
when
l
=
2
=
4, see Section
4.2 of [
411
].
Exercise 22.3.1
Show how to obtain an analogue of equation (
22.7
) when the
l
most
significant bits are known.
Bleichenbacher has described a similar attack on a specific implementation of DSA that
used a biased random generator for the values
k
.
22.4 Other signature functionalities
There are many topics that are beyond the scope of this topic. We briefly discuss two of
them now.
Online/offline signatures. The goal here is to design public key signature schemes that
possibly perform some (slow) precomputations when they are “offline” but that generate
a signature on a given message
m
extremely quickly. The typical application is smart
cards or other tokens that may have extremely constrained computing power.
The first to suggest a solution to this problem seems to have been Schnorr in his paper
[
469
] on efficient signatures for smart cards. The Schnorr signature scheme already
has this functionality: if
s
0
=
g
k
is precomputed during the idle time of the device,
then generating a signature on message
m
only requires computing
s
1
=
H
(
m
s
0
) and
s
2
=
a
s
1
(mod
r
). The computation of
s
1
and
s
2
is relatively fast since no group
operations are performed.
A simple idea due to Girault [
231
] (proposed for groups of unknown order, typically
k
+
)
∗
) is to make Schnorr signatures even faster by omitting the modular reduction in
(
Z
/N
Z
