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.