El Gamal Encryption

Here, we summarize the El Gamal cryptosystem. Consult wikipedia for more detail.

• KeyGen:
  • Choose a random prime p.
  • Choose a random generator g modulo p.
  • Choose the decryption exponent x randomly from {1, ... , p-1}.
  • Let y be g^x mod p.
  • Return the public key pk = (y, g, p) and the secret key sk = x.
• Enc(pk = (y, g, p), m), where m is a message to be encrypted:
  • Choose r randomly from {1, ..., p-1}.
  • Let s = y^r.
  • Let c₁ = g^r mod p.
  • Let c₂ = sm mod p.
  • Return the ciphertext c = (c₁, c₂).
• Dec(sk = x, c), where c is a ciphertext to be decrypted:
  • Let s = c₁^x mod p.
  • Return the recovered message m = (c₂ / s) mod p.