Cryptography Reference
In-Depth Information
Exercise 9.3
Explain why the previous attack is very unlikely to be successful in
case the verification algorithm adds the constraints
r
<
p
and
r
1
<
p
.
Exercise 9.4
Write a Maple implementation of Elgamal signatures using the code
Exercise 9.5
Using theMaple implementation of Elgamal signatures in the previous
exercise, give an example in which the signature of a message is computed and then,
assuming that the condition 0
<
r
<
p
is not checked, construct an Elgamal signature
for a different message.
In [28], Bleichenbacher presented yet another, more dangerous, attack against
Elgamal signatures in case the parameters are not carefully chosen. This attack is
based on the Pohlig-Hellman algorithm that, as we have seen, gives an efficient
solution to the DL problem in groups of smooth order, i.e., in groups whose order is
a product of small prime factors. For this reason
p
should be chosen so that
p
1
has at least one large prime factor. However, Bleichenbacher's attack shows that this
is not sufficient as it applies in case
p
−
−
1
=
bw
with
b
smooth and a relation of
the form
g
t
b
is known. We refer to the original
paper for the details and here we merely point out that attacks like this one led to the
introduction of signature schemes that are similar to Elgamal—and hence are also
based on the DL problem—but are immune to these attacks because they work in a
subgroup of (large) prime order of
≡
cw
(
mod
p
)
with 0
<
c
<
Z
p
; we will look at a couple of these schemes in
the next section. Another drawback of Elgamal signatures, namely their relatively
large size, is also avoided by these schemes.
Exercise 9.6
Suppose that
p
≡
1
(
mod 4
)
and the Elgamal public key of a user is
(
p
,
g
,
y
)
[140]. Suppose further that
p
−
1
=
gw
and computing discrete logarithms
Z
p
of order
g
is easy (for example, using the Pohlig-Hellman
algorithm if
g
is smooth). Prove that an Elgamal signature for a message
m
(with
h
in the subgroup of
=
H
(
m
)
if a hash function
H
is used) can be forged as follows:
1. Set
t
:=
(
p
−
3
)/
2 and
r
:=
w
.
2. Find
z
such that
g
wz
y
w
≡
(
)
mod
p
.
:=
(
−
)
(
−
)
(
,
)
3. Set
s
t
h
wz
mod
p
1
and let
r
s
be the signature of
m
.
Indicate how this attack may be prevented.
9.4 The Digital Signature Algorithm
The Digital Signature Algorithm has a close precedent in Schnorr's signature scheme
which was introduced in 1989. This scheme was motivated by the desire to obtain a
version of Elgamal which produces shorter signatures and is more efficient because
the exponents in the modular exponentiations are less than
q
, where
q
is a prime
divisor of
p
−
1 of much smaller size: for example,
p
can be a 1024-bit prime and
