Cryptography Reference
In-Depth Information
a DSS. Contrary to the RSA public key cryptosystem, the ElGamal public key cryp-
tosystem uses different algorithms to encrypt and decrypt messages, or to digitally
sign messages and verify digital signatures, respectively. This is disadvantageous
from the developer's point of view (because he or she must implement more algo-
rithms). Furthermore, ElGamal signatures are typically twice as long as RSA sig-
natures (see Section 15.2.2.2). For both reasons, the ElGamal DSS is not as widely
deployed in practice as the RSA DSS.
In its basic form, the ElGamal DSS is with appendix. This is also true for the
many generalizations and variations of the ElGamal DSS that have been developed
and proposed in the literature (e.g., [8]). There is, however, also an ElGamal
variation that yields a DSS with message recovery [9]. Due to the names of their
developers, this DSS is sometimes also referred to as the Nyberg-Rueppel DSS.
Similar to the ElGamal asymmetric encryption system, the security of the
ElGamal DSS is based on the DLA and the intractability assumption of the DLP.
Consequently, one needs a cyclic group in which the DLP is (assumed to be)
intractable. For example, ElGamal introduced and originally proposed the DSS in
the multiplicative group
Z
p
(for a sufficiently large prime number
p
). We also use
this group to overview and discuss the ElGamal DSS next. Note, however, that there
are many other cyclic groups that can be used instead of
Z
p
. In ECC, for example,
one uses
E
(
F
q
) as introduced in Section 7.6.
15.2.2.1
Key Generation Algorithm
The ElGamal
Generate
algorithm is the same as the one employed by the ElGamal
asymmetric encryption system (see Section 14.2.3.1). For every user, it generates
a public ElGamal verification key (
p, g, y
) and a corresponding private ElGamal
signing key
x
. The modulus
p
and the generator
g
may be system parameters (i.e.,
they may be the same for all users and not be part of the verification key).
We consider a toy example to illustrate the ElGamal DSS. Let
p
=17and
g
=2be system parameters. For a particular user, the ElGamal
Generate
algorithm
randomly selects
x
=4and computes
y
2
4
(mod 17) = 16. So the private
ElGamal signing key is 4 and the corresponding public ElGamal verification key is
16.
≡
15.2.2.2
Signature Generation Algorithm
Contrary to the RSA
Sign
algorithm, the ElGamal
Sign
algorithm is probabilistic and
requires a cryptographic hash function. The cryptographic hash function, in turn, is
used to turn a message into a hash value that is then digitally signed.
