Cryptography Reference
In-Depth Information
is at most twice as long as the message that is signed (or the hash value thereof,
respectively). As mentioned earlier, the basic ElGamal DSS is a DSS with appendix,
meaning that the signatory must transmit both the message
m
and the signature (
r, s
)
to the verifier.
In our toy example, we assume that the signatory wants to digitally sign a
message
m
with a hash value
h
(
m
)=6.TheElGamal
Sign
algorithm randomly
selects
k
=3and computes
r
2
3
(mod 17) = 8,
k
−
1
3
−
1
(mod 16) = 11,
≡
≡
and
s
14 (mod 16) = 2. Consequently, the
ElGamal signature for
h
(
m
)=6is (8
,
2), and the numbers that are actually
transmitted are 6, 8,and2.
≡
11(6
−
4
·
8) (mod 16)
≡−
15.2.2.3
Signature Verification Algorithm
Like all signature verification algorithms, the ElGamal
Verify
algorithm is determin-
istic. It takes as input a verification key (
p, g, y
), a message
m
,andanElGamal
signature (
r, s
), and it generates as output one bit saying whether (
r, s
) is a valid
ElGamal signature for
m
with respect to (
p, g, y
). The algorithm verifies the relation
1
≤
r
≤
p
−
1
and the equivalence
g
h
(
m
)
y
r
r
s
(mod
p
)
.
≡
(15.1)
The signature is valid if and only if both verification checks are positive.
Otherwise, the signature is rejected and considered to be invalid. Note that the
verification equivalence (15.1) works, because
g
xr
g
kk
−
1
(
h
(
m
)
−xr
)
(mod
p
)
y
r
r
s
≡
g
xr
g
(
h
(
m
)
−xr
)
(mod
p
)
≡
g
xr
g
−xr
g
h
(
m
)
(mod
p
)
≡
g
h
(
m
)
(mod
p
)
.
≡
1. Otherwise, it is possible
to construct a new signature from a known signature [10]. Let, for example, (
r, s
)
be the ElGamal signature of a message
m
and
m
be another message for which
Also note that it is mandatory to verify 1
≤
r
≤
p
−
