Elgamal

2026-03-14

Basics of Elgamal asymmetric encryption.

Elgamal

Today, I learned about elgamal encryption. It was.... fun, to say the least. It's an interesting algorithm, but also somewhat... weird? Idk.

Elgamal

Public parameters $q, \alpha$ where the latter is a primitive root of the former and the former is a prime number.
Key generation works in a similar way, get a $X_A$ and raise the primitive root to that power, calling it $Y_A$ and publishing all three as the public key.
Encryption happens as follows: Calculate $C_1 = \alpha^k \text{mod} q$ , $K = Y_A^k \text{mod} q$ , $C_2 = KM \text{mod} q$ , and transmit $(C_1, C_2)$ to the recipient.
Decryption happens as follows: Take $C_1$ and raise it to $X_A$ and then use it's modular inverse and multiply with $C_2$ .

The idea is fairly straightforward. Basically give the signer something that we can raise using our own base and that'll give us whatever he had, to invert it and use it. $k$ here is a nonce here, obviously.

Elgamal

Public parameters

q, \alpha

where the latter is a primitive root of the former and the former is a prime number.

Key generation works in a similar way, get a

X_A

and raise the primitive root to that power, calling it

Y_A

and publishing all three as the public key.

Encryption happens as follows: Calculate

C_1 = \alpha^k \text{mod} q

K = Y_A^k \text{mod} q

C_2 = KM \text{mod} q

, and transmit

(C_1, C_2)

to the recipient.

Decryption happens as follows: Take

C_1

and raise it to

X_A

and then use it's modular inverse and multiply with

C_2

The idea is fairly straightforward. Basically give the signer something that we can raise using our own base and that'll give us whatever he had, to invert it and use it.

k

here is a nonce here, obviously.