Cryptography Reference
In-Depth Information
With these values, one has
y
r
r
s
y
r
g
su
y
sv
(mod
p
)
≡
y
r
g
su
y
−r
(mod
p
)
≡
g
m
(mod
p
)
,
≡
and hence the verification equivalence (15.1) is satisfied. If one uses a cryptographic
hash function
h
(i.e., one digitally signs
h
(
m
) instead of
m
), then one can still
generate signatures for hash values. Due to the one-way property of cryptographic
hash functions, however, it is not possible to compute
m
from
h
(
m
). Similar to the
multiplicative property of the RSA function, one can also solve this problem with
the use of redundancy.
In our toy example, the ElGamal
Verify
algorithm verifies that 8
≤
16 and
2
6
8
2
(mod 17). Both verification checks are positive, and hence (8
,
2)
represents a valid ElGamal signature for a message
m
with
h
(
m
)=6.
≡
16
8
·
15.2.2.4
Security Analysis
In Section 14.2.3.4, we analyzed the security of the ElGamal asymmetric encryp-
tion system. Some parts of this analysis also apply for the ElGamal DSS. More
specifically, we showed in Theorem 14.2 that breaking the ElGamal system is com-
putationally equivalent to solving the DHP. Consequently, one must select the cyclic
group and the system parameters so that the DHP is computationally intractable.
If, for exmaple,
Z
p
is used as a cyclic group (as done earlier), then
p
should be at
least 1,024 bits long. Furthermore, one should select
p
so that efficient algorithms to
compute discrete logarithms do not work. For example, it is necessary to select
p
so
that
p
1 does not have only small prime factors (otherwise the Pohlig-Hellman
algorithm [11] can be applied to efficiently compute discrete logarithms). There
are other constraints that should be kept in mind when properly implementing the
ElGamal DSS. The constraints can be found in the relevant literature (they are not
repeated in this topic).
Last but not least, we elaborate on the requirement that the ElGamal
Sign
algorithm must use a fresh and unique
k
−
∈
Z
p
for every digital signature it generates
(this requirement is analog to the one used in the ElGamal asymmetric encryption
system). If this requirement was not made, then it would be possible to retrieve the
signing key from only two valid digital signatures. Let
s
1
and
s
2
be two ElGamal
signatures for messages
m
1
and
m
2
that are generated with the same
k
:
=
k
−
1
(
h
(
m
1
)
s
1
−
xr
)) (mod(
p
−
1))
