Public-Key Cryptography - Codes: The Guide to Secrecy from Ancient to Modern Times - page 187

Now assume that Eve can cryptanalyze the ElGamal cipher above. Then
she can obtain any message m from knowledge of p, α, α a ,α b , and mα ab .IfEve
wants to get α ab from p, α, α a ,α b , she computes ( mα ab ) m − 1 α ab (mod p ).

In other words, we have shown that cryptanalyzing ElGamal is tantamount
to cryptanalyzing Di8e-Hellman. In fact, the ElGamal cipher may be viewed
as a Di 8 e-Hellman key exchange on k = α ab , which is used to encrypt m in
step 3 of the enciphering stage. Thus, we have demonstrated that although
Di8e-Hellman is not itself a public-key cryptosystem, it is the basis for the
ElGamal public-key cryptosystem. Furthermore, ElGamal's cipher has di8culty
equivalent to the Di8e-Hellman key-exchange. Moreover, as noted on page 167,
if Eve can solve the DLP, she can solve the DHP. The converse is not known,
but the consensus is that it is true. Hence, we assume that the security of the
ElGamal cipher is based upon the DLP. Last, as with RSA, a modulus of 1024
to 2048 bits is recommended for long-term security.
Deciphering Verification : The reason Bob's deciphering stage works is
due to the fact that

≡

( α b ) − a mα ab mα ab − ab ≡ ≡ m (mod p ) .

In 1985, ElGamal developed a DSS (see [74] and [75]). It turns out that
these publications were perhaps a little hasty since he had not applied for patent
rights, thereby forfeiting his rights to those patents. Variations of ElGamal's
scheme did get patented by others such as Schnorr (see [151, pages 180 and
181]), whose identification scheme we will study in Chapter 5. The RSA DSS
studied on pages 181-183 is deterministic, whereas the following is a randomized
algorithm. Also, RSA is a DSS with message recovery, whereas ElGamal's is a
DSS with appendix.

ElGamal Signature Scheme
The goal is for Alice to sign and send a message to Bob for verification.
The message should be hashed before signing, but for the sake of simplicity,
we will not do this and leave the issue for a discussion in the analysis after the
description of the DSS.
Key Generation Stage : First Alice engages in ElGamal key generation
as described on page 185 for Bob. Thus, Alice's public key is ( p, α, y ), α being
a primitive root modulo a large random prime p (with intractable DLP in

F p )

α a (mod p ). The message to be signed is

and her private key is a , where y ≡

∈ F p .
Signing Stage : Alice performs each of the following:

m

) ∗ . 1. Select a random r ∈ ( Z / ( p − 1) Z

α r (mod p ) and γ aβ ) r − 1 (mod p 2. Compute β ≡ ≡ ( m − − 1).

3. For k =( p, α, a, y ) the signed message sig k ( m, r )=( β,γ ) is sent, along with
m , to Bob.