How does ElGamal encryption work on elliptic curves (the Volker Müller / Koblitz method)?
EC ElGamal maps the message to a curve point M, then masks it: ciphertext is $(k \cdot G, M + k \cdot Q)$ where Q is the public key. Decryption subtracts $d \cdot (k \cdot G)$ to recover M.
Key Generation (Bob):
- Choose curve $E$, base point $G$ of order $n$
- Choose secret $d \in \{2, ..., n-2\}$
- Compute public key: $Q = d \cdot G$
- Publish: $(E, G, n, Q)$
Encryption (Alice sends point $M$ to Bob):
- Choose random ephemeral $k \in \{2, ..., n-2\}$
- Compute ephemeral key: $k_E = k \cdot G$
- Compute masking key: $k_M = k \cdot Q$ (= $k \cdot d \cdot G$)
- Compute ciphertext point: $C = M + k_M$
- Send $(k_E, C)$ to Bob
Decryption (Bob):
- Compute masking key: $k_M = d \cdot k_E$ (= $d \cdot k \cdot G$)
- Recover: $M = C - k_M$
Why it works: $C - k_M = (M + k \cdot Q) - d \cdot (k \cdot G) = M + k \cdot d \cdot G - d \cdot k \cdot G = M$
Key differences from RSA:
- Additive masking ($M + k_M$) instead of multiplicative ($m \cdot K$) — because the group operation on curves is addition
- Inherently probabilistic — random $k$ means different ciphertext each time (no OAEP needed!)
- Ciphertext is two points — doubles the message size (ciphertext expansion factor = 2)
Challenge: The message $m$ (a number) must be mapped to a curve point $M$. This is non-trivial — not every $x$ value has a corresponding point on the curve. The Koblitz method uses trial: try $x = m \cdot c + j$ for $j = 0, 1, 2, ...$ until a valid point is found.
Go deeper:
ElGamal encryption — Wikipedia — the scheme over any cyclic group; EC ElGamal is this with point addition.- Elliptic-curve cryptography — Wikipedia — EC encryption schemes and the point-encoding problem.