📂Number Theory

ElGamal Public Key Cryptosystem Proof

Buildup

From left to right, let’s name them Alice, Bob, and Eve. Alice and Bob are the parties exchanging messages, and Eve is a passive attacker interested in the message. The orange box represents information known only to Alice, the sky-blue box represents information known only to Bob, and the black box represents public information (also known to Eve).

Alice has a message $m \in \mathbb{N}$ to receive from Bob.

Algorithm ¹

$\mathbb{F}_{p}^{ \ast } = \mathbb{F}_{p} \setminus \left\{ 0 \right\} = \left\{ 1, g , g^2 , \cdots , g^{p-2} \right\}$ Let’s say it’s a cyclic group with $(p-1)$ elements.

---

Key Setup: Publicly choose a very large prime number $p$ and $\text{ord}_{p} (g)$, which is a large prime number, as $g \in \mathbb{F}_{p}^{ \ast }$.

Alice decides on a key $1 \le a \le p-1$, known only to herself, and computes $A \equiv g^{a} \pmod{p}$ to make it public.

---

Encryption: Generate a one-time random key $k$. Bob calculates $c_{1} \equiv g^{k} \pmod{p}$ and $c_{2} \equiv m A^{k} \pmod{p}$ to transmit $(c_{1} , c_{2})$ to Alice.

---

Decryption: Using $(c_{1} , c_{2})$, Alice computes $x \equiv (c_{1}^{a} )^{-1} c_{2} \equiv m \pmod{p}$ to obtain $x = m$. It’s realistically impossible for Eve to know $a$, therefore, she can’t know $m$.

Explanation

In fact, there’s no need for the order $\text{ord}_{p} (g)$ of $g$ to be large in the system itself, but choosing a number with a large order is better to reduce the possibility of obtaining it by brute force.

Proof

Decryption

Since Alice knows $a$, and $c_{1} \equiv g^{k} \pmod{p}$ and $c_{2} \equiv m A^{k} \pmod{p}$, she can easily compute $$ \begin{align*} (c_{1}^{a} )^{-1} c_{2} & \equiv \left( g^{ak} \right)^{-1} \cdot c_{2} \\ & \equiv \left( g^{ak} \right)^{-1} \cdot \left( m A^{k} \right) \\ & \equiv \left( g^{ak} \right)^{-1} \cdot \left( m \left( g^{a} \right)^{k} \right) \\ & \equiv m \left( g^{ak} \right)^{-1} \cdot g^{ak} \\ & \equiv m \pmod{p} \end{align*} $$ without knowing $k$.

■

Encryption

Since Eve only knows $c_{1}$ and $c_{2}$, not $a$ and $k$, she cannot know the discrete logarithm problem ${g}^{x} \equiv c_{1}^{a} \pmod{p}$, and even if she did, she would need to solve it directly. Since this is very difficult, Bob can safely transmit the message $m$ to Alice.

■

See Also

• Discrete logarithm problem

Security algorithms utilizing the difficulty of the discrete logarithm problem

• Diffie-Hellman key exchange algorithm
• ElGamal public key cryptosystem

Attack algorithms on the discrete logarithm problem

• Shanks’ algorithm
• Pollard’s rho algorithm
• Conditions under which the discrete logarithm problem is easily solvable