Notes - The ElGamal Public Key Cryptosystem

The following are notes from Introduction to Cyrptography with Coding Theory.

• ElGamal Public Key Cryptosystem
• Alice wants to send a message m to Bob
• Bob chooses a large prime p and a primitive root α
• Bob chooses a secret integer a and computes B ≡ α ^a (mod p)
• Make public (p, α, B) and is Bob's public key
• Alice
• downloads (p, α, B)
• Chooses a secret random integer k and computes r ≡ α ^k (mod p)
• Computes t ≡ B ^k m (mod p)
• sends the pair (r,t) to B
• Bob decrypts by computing tr ^-a ≡ m (mod p)
• Security
• depends on a being kept secret which is reliant on the idea that discrete logs are difficult to compute

Back to ToC