Cryptography Reference
In-Depth Information
a chosen message attack gives a total break of the scheme and allows an adversary
to obtain the private key.
9.2.2 Elgamal Signatures
The Elgamal signature scheme is similar to the Elgamal encryption scheme. It was
introduced in 1985 and it was the first signature scheme based on the discrete loga-
rithm problem. It can be defined on more general groups but we now give the original
version, which is as follows:
Definition 9.5
The
Elgamal signature scheme
(
Gen
,
Sign
,
Ve r
) is defined by the
following algorithms:
Gen
: On input 1
t
generate a random prime
p
of length
t
and a primitive root
modulo
p
,
g
, so that
•
Z
p
=
g
. Choose a random
x
← Z
p
−
1
and compute
g
x
mod
p
. The public key is the 3-tuple
pk
y
:=
:=
(
p
,
g
,
y
)
and the private key
is
sk
.
p
and
g
may also be regarded as system parameters, in which
case the public key is simply
y
and the private key is
x
.
:=
(
p
,
g
,
x
)
•
=
(
,
,
)
∈ Z
p
, choose a
Sign
: On input a private key
sk
p
g
x
and a message
m
← Z
p
−
1
and compute
random element
k
g
k
mod
p
k
−
1
r
:=
,
s
:=
(
m
−
rx
)
mod
(
p
−
1
).
The output is then the signature
σ
=
(
r
,
s
)
.
•
Ve r
: On input a public key
pk
=
(
p
,
g
,
y
)
and a signed message
(
m
,
r
,
s
)
check
whether
-0
<
r
<
p
,
-
g
m
y
r
r
s
≡
(
mod
p
)
.
Output 1 if these conditions hold and 0 otherwise.
Let us check that the verification algorithm accepts all the signatures output by
the signing algorithm. We have
g
rx
mod
p
−
1
g
kk
−
1
y
r
r
s
g
x
r
g
k
s
(
m
−
rx
)
mod
p
−
1
g
m
≡
(
)
(
)
≡
≡
(
mod
p
)
Z
p
).
−
−
(where we can reduce all exponents modulo
p
1 because
p
1 is the order of
Z
p
leads to
a total break of this scheme because in that case the private key
x
can be computed
from the public key. This, however, is secondary here because the scheme is insecure
anyway. An existential forgery under a key-only attackmay be constructed as follows:
It is easy to see that being able to solve the DL problem in the group
