3. ElGamal

Same setup as RSA. Alice would like to receive something from Bob.

3.1. Preparation Work

Alice chooses

• a prime number \(p\),

• a generator of the \(GF(p)\), which is a positive number \(\alpha \in GF(p)\),

• a secret value \(1 \leq a \leq p-2\).

Then she generates \(\beta = \alpha^a ~mod~p\).

Alice tells Bob \(p, \alpha. \beta\)

3.2. Encryption

Bob chooses a secret key \(k\) and finds out the message \(x\) and compute

\[Enc(x, k) = [\alpha^k~mod~p, x \beta^k~mod~p] = [y_1, y_2]\]

Bob tells Alice \(y_1, y_2\)

3.3. Decryption

Alice does

\[m = y_2(y_1^\alpha)^{-1}.\]

3.4. Feasibility

\[y_2(y_1^\alpha)^{-1} = x \beta^k~mod~p [\alpha^{-k\cdot a}~mod~p] = x \alpha^{ak} \alpha^{-ak}~mod~p = x~mod~p\]