Elgamal Cryptosystem

17 Dec 2021

§ Motivation

We've already discussed how to securely exchange keys, but not a cryptosystem; i.e. a system that can be used to encrypt and decrypt messages. The Elgamal cryptosystem is very similar to Diffie-Hellman, but it can be used to encrypt messages.

§ Cryptosystem Discussion

Let $\mathcal{K}$ denote the key space (all possible keys), $\mathcal{M}$ the message space, and $\mathcal{C}$ ciphertext space (encrypted message).

For a resonably secure public key cryptosystem, we would want the following properties

For any key $k \in \mathcal{K}$ and message in $m \in \mathcal{M}$ , it must be easy to compute the ciphertext $e_k(m) = e(k, m)$ (encryption is fast).
For any key $k \in \mathcal{K}$ and ciphertext in $c \in \mathcal{C}$ , it must be easy to compute $d_k(c) = d(k, c)$ (decryption is fast).
Given one or more $c_1, \dots, c_n \in \mathcal{C}$ , all encrypted using the same $k \in \mathcal{K}$ , it must be very difficult to compute any of $d_k(c_1), \dots, d_k(c_n)$ without knowledge of $k$ .
Given one or many pairs of plaintexts and corresponding ciphertexts $(m_1, c_1), \dots, (m_n, c_n)$ it must be very difficult to compute any ciphertext besides $c_1, \dots, c_n$ without knowing $k$ (khown plaintext attack resilience).
For any message $m_1, \dots, m_n \in \mathcal{M}$ chosen by an adversarial eavesdropper, even with knowledge of ciphertexts $e_k(m_1), \dots, e_k(m_n)$ , it is very difficult to decrypt any ciphertext $c$ that is not in the given list without knowing key $k$ (chosen plaintext attack resilience).

§ Elgamal Public Key Cryptosystem

Elgamal Cryptosystem

First, Alice and Bob agree on a common (large) prime $p$ , and an element $g \pmod{p}$ . These values are communicated in public.

Alice chooses a private key $a$ , and makes her public key $A \equiv_p g^a$ available to Bob.

Encryption: If Bob wants to send a message $m$ to Alice, he chooses a random value $k\pmod{p}$ and computes the two values

c_1 \equiv_p g^k \text{ and } c_2 \equiv_p mA^k

and sends the pair $(c_1, c_2)$ to Alice.

Decryption: After receiving Bob's message, she uses the Euclidean algorithm to find the modular inverse of $c_1$ modulo $p$ . Then, she raises $c_1^{-1}$ to the power of her private key $a$ , i.e. $c_1^{-a} \equiv_p g^{-ka}$ . Finally, she decodes the message by

m \equiv_p g^{-ka}c_2.