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

  1. 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).
  2. 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).
  3. 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$.
  4. 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).
  5. 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. $$