Cryptography Reference
In-Depth Information
g
a
and the private
that testing membership
g
∈
G
is easy. The public key of user
A
is
h
=
key is
a
, where 1
a<r
is chosen uniformly at random.
The Elgamal scheme requires a function
F
:
G
≤
→ Z
/r
Z
. The only property required of
this function is that the output distribution of
F
restricted to
should be close to uniform
(in particular,
F
is not required to be hard to invert). In the case where
G
g
= F
p
it is usual to
define
F
:
n
(mod
r
). If
G
is the set of
points on an elliptic curve over a finite field then one could define
F
(
x,y
) by interpreting
x
(or
x
and
y
) as binary strings, letting
n
be the integer whose binary expansion is
x
(or
x
{
0
,
1
,...,p
−
1
}→{
0
,
1
,...,r
−
1
}
by
F
(
n
)
=
y
), and then computing
n
(mod
r
).
To sign a message
m
with hash
H
(
m
)
∈ Z
Z
≤
/r
one chooses a random integer 1
k<r
,
computes
s
1
=
g
k
, computes
s
2
=
k
−
1
(
H
(
m
)
−
aF
(
s
1
)) (mod
r
) and returns (
s
1
,
s
2
). To
verify the signature (
s
1
,
s
2
) on message
m
one checks whether
s
1
∈
g
,0
≤
s
2
<r
, and
h
F
(
s
1
)
s
s
1
=
g
H
(
m
)
in
G
. Elgamal signatures are the same size as naive Schnorr signatures.
A striking feature of the scheme is the way that
s
1
appears both as a group element and
as an exponent (this is why we need the function
F
). In retrospect, this is a poor design
choice for both efficiency and security. The following exercises explore these issues in
further detail. Pointcheval and Stern give a variant of Elgamal signatures (the trick is to
replace
H
(
m
)by
H
(
m
s
1
)) and prove the security in Sections 3.3.2 and 3.3.3 of [
433
].
Exercise 22.2.1
Show that the Verify algorithm succeeds if the Sign algorithm is run
correctly.
Exercise 22.2.2
Show that one can verify Elgamal signatures by computing a single three-
dimensional multi-exponentiation. Show that the check
s
1
∈
g
can therefore be omitted if
gcd(
s
2
,
#
G
)
=
1. Hence, show that the time to verify an Elgamal signature, when
F
and
H
map to
, is around twice the time of the method in Example
22.1.13
to verify a Schnorr
signature. Explain why choosing
F
and
H
to map to
l
-bit integers where
l
Z
/r
Z
≈
log
2
(
r
)
/
2
does not lead to a verification algorithm as fast as the one in Example
22.1.13
.
Exercise 22.2.3
(Elgamal [
177
]) Suppose the hash function
H
is deleted in Elgamal
signatures (i.e., we are signing messages
m
). Give a passive existential forgery in
this case (i.e., the attack only requires the public key).
∈ Z
/r
Z
F
p
with the function
F
(
n
)
Exercise 22.2.4
Consider the Elgamal signature scheme in
=
n
(mod
r
). Suppose the function
F
(
n
) computes
n
(mod
r
) for all
n
∈ N
(not just 0
≤
n<
p
) and that the check
s
1
∈
does not include any check on the size of the integer
s
1
(for example, it could simply be the check that
s
r
1
≡
g
1(mod
p
) or the implicit check of
Exercise
22.2.2
). Give a passive selective forgery attack.
Exercise 22.2.5
Consider the following variant of Elgamal signatures in a group
g
of order
r
: the signature on a message
m
for public key
h
is a pair (
s
1
,
s
2
) such that 0
≤
s
1
,
s
2
<r
,
