4.2 ElGamal

The ElGamal Cryptosystem is based on the Discrete Logarithm problem. that means the difficulty of computing a if β = α^a(mod p) is known, where p is prime.

In the presented form only numbers can be encrypted; texts must previously be coded suitable.

The ElGamal Cryptosystem consists of three steps

1. Gernerating the key:
• Choose a large prime Primzahl p (see 2.3.2), such that (p - 1) / 2 is prime, too^* (see 2.3.1).
  N is the number of bits of p.
• Choose the base α < p.
• Choose the private key a < p.
• Compute β = α^a(mod p)
• Publish p, α and β as public key.



2. Encryption of a message:
• Split the plaintext into blocks of N - 1 bits (fill them up if necessary).
• Choose a secret random number k with  gcd(k, p - 1) = 1 (see 2.1)
• Compute for every block x the ciphertext
  
      e (x, k) = (y₁, y₂),   where
      y₁ = α^k(mod p)   and   y₂ = β^kx (mod p).
  y₁ and y₂ are blocks of the length N of ciphertext.



3. Decryption:
• Split the ciphertext in blocks of N bits
• For two successive blocks y₁ and y₂ solve
      y₁^a x = y₂ (mod p)
  for x. Thus
      d (y₁, y₂) = x = y₂ (y₁^a )^-1 (mod p)
  is the wanted block of plaintext.

^* For the special case, that (p - 1) / 2 is also a prime, there is a known algorithm to compute the Discrete Logarithm problem.


4.2 ElGamal: Sample applet for small numbers


source

4.3 Elliptic Curves