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 1
$\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
Security algorithms utilizing the difficulty of the discrete logarithm problem
Attack algorithms on the discrete logarithm problem
- Shanks’ algorithm
- Pollard’s rho algorithm
- Conditions under which the discrete logarithm problem is easily solvable
Hoffstein. (2008). An Introduction to Mathematical Cryptography: p70. ↩︎