ElGamal Signature

Introduction.

Before discussing the ElGamal signature scheme, let's first talk about the ElGamal public key scheme. ElGamal is based on the problem of Discrete Logarithms in the group (Z_p*, ●). Let p be a prime and let α be a primitive element in Z_p*. The set of all plaintexts P = Z_p*, the set of all ciphertexts C = Z_p* x Z_p*, and the set of all keys K = {(p, α, a, β) : β ≡ α^a mod p}. p, α, and β make up the public key and the private key is p, α, and a. Alice chooses a secret random number k in Z_p-1, and given m as the plaintext to be encrypted we have:

Encryption

e_k(m, k) = (y1, y2),  where

y₁ = α^k mod p and

y₂ = (m * β^k) mod p

Decryption

m = d_k(y₁, y₂) = y₂(y₁^a)^-1 mod p,  for all y₁, y₂ in Z_p* (notice the multiplicative inverse (y₁^a)^-1)

Cryptosystem Example.

Let p = 7, α = 2, a = 5, m = 6 and k = 4. Alice computes the following:

β = 2⁵ mod 7 = 4
y₁ = 2⁴ mod 7 = 2
y₂ = [6(4⁴)] mod 7 = 1536 mod 7 = 3

Alice then sends (2, 3) to Bob, and Bob decrypts the ciphertext as:

m = [3(2⁵)^-1] mod 7
  = [(3 mod 7)(32^-1 mod 7)] mod 7
  = [3 * 2] mod 7 = 6

ElGamal Signature Scheme.

The ElGamal signature scheme is as follows: Again let p be a prime and let α be a primitive element in Z_p*. The set of all plaintexts P = Z_p-1, the set of all ciphertexts C = Z_p-1 x Z_p-1, and the set of all keys K = {(p, α, a, β) : β ≡ α^a mod p}. p, α, and β make up the public key and the private key is p, α, and a. Alice chooses a secret random number k in Z_p-1, and given m as the plaintext to be signed we have:

Signing

sig_k(m, k) = (y₁, y₂),  where

y₁ = α^k mod p and

y₂ = [(m - a * y₁)(k^-1)] mod (p - 1)

Verification

ver_k(m, (y₁, y₂)) ↔ y₁^y2 * β^y1 = α^m mod p

Signature Example.

Let p = 17, α = 2, a = 4, m = 6 and k = 3. Alice computes the following signature:

β = 2⁴ mod 17 = 16
y₁ = 2³ mod 17 = 8
y₂ = [(6 - 4 * 8)(11)] mod 16 = -286 mod 16 = -14 mod 16 = 2

Alice then sends (6, 8, 2) to Bob, and Bob verifies the signature as:

2⁶ ≡ [(8²)(16⁸)] mod 17 → 2⁶ mod 17 = [(8²)(16⁸)] mod 17 = 13 It checks.

Security.

If the attacker can compute the value a = log_αβ, then ElGamal signatures can be forged. As long as p is chosen carefully and α is a primitive element modulo p, then solving the Discrete Logarithm problem in Z_p* is infeasible. Additionally, k must be secret, only used once and random. As shown above, ElGamal can also be used for encryption as well, but the messages should be relatively small in size.

Links

http://home.ecn.ab.ca/~jsavard/crypto/pk050301.htm
http://www.hack.gr/users/dij/crypto/overview/otherpk.html