ElGamal Encryption

Cryptography · Axiom Academy

A public key cryptosystem based on the discrete logarithm problem, providing semantic security through randomization To create an ElGamal key pair, we work in a cyclic group (typically the multiplicative group of integers modulo a large prime): Choose a generator g of the multiplicative group modulo p Choose a random private key x where 1 x p-2 Compute the public key y = g x mod p To encrypt a message m (where 0 m p-1) using the recipient's public key (p, g, y): Step 1: Choose a random ephemeral key k where 1 k p-2 Step 2: Compute c 1 = g k mod p Step 3: Compute c 2 = m · y k mod p Step 4: The ciphertext is the pair (c 1 , c 2 ) To decrypt a ciphertext (c 1 , c 2 ) using the private key x: Step 1: Compute the shared secret s = c 1 x mod p Step 2: Compute the modular inverse s -1 mod p Step 3: Recover the message: m = c 2 · s -1 mod p 4. Why It Works: Mathematical Proof Let's verify that decryption correctly recovers the original message: Ciphertext c 2 = m · y k mod p ElGamal's most important property is semantic security (also called probabilistic encryption): Each encryption uses a fresh random value k The same message encrypted twice produces completely different ciphertexts An attacker cannot tell if two ciphertexts encrypt the same message This prevents patterns from revealing information about plaintexts A significant drawback of ElGamal is ciphertext expansion : Each plaintext element produces two ciphertext elements: (c 1 , c 2 )

This is the written version of the interactive lesson above. See the full Cryptography course.