Elliptic Curve Elgamal

Elliptic Curve Elgamal is an elliptic curve version of Elgamal.

The main extra complication is that the plaintext must first be encoded as a point on the elliptic curve.

Setup

Choose:

• a prime $p$,
• an elliptic curve $E$ that is nonsingular modulo $p$,
• a point $P$ on $E$ modulo $p$.

Bob chooses a secret integer $a$ and publishes

$$Q=aP$$

Encryption

Suppose the message has been encoded as a point $M$ on the curve.

Alice chooses a random integer $k$ and computes

$$\begin{array}{rl}{C}_1& =kP\\ C_2& =M+kQ\end{array}$$

The ciphertext is the pair $(C_1,C_2)$.

Decryption

Bob computes

$$a{C}_1=a(kP)=k(aP)=kQ$$

and recovers the message by

$$M=C_2-a{C}_1$$

Security Idea

Security depends on the difficulty of the elliptic curve discrete logarithm problem.