# ElGamal with elliptic curves

I've searched some information on ECC, but so far I have only found Diffie-Hellman key-exchange implementations using ECC, but I don't want to exchange keys, I want to encrypt & decrypt data like in ElGamal. I know that ElGamal with elliptic curves should be possible (Since ElGamal is based on DH), but I have no idea how. So, could anyone tell me how to implement ElGamal using elliptic curves. I think I do not need to much background information,

1. What is the private, what is the public key?
2. How to encrypt messages? and
3. How to decrypt messages?

should be enough.

-

Your answer is in the paper Elliptic curve cryptosystems from Neal Koblitz:

• Set up an elliptic curve $E$ over a field $\mathbb{F}_q$ and a point $P$ just the same as for EC-DDH as system parameters.
• You need a public known function $f(m) \rightarrow P_m$, which maps messages $m$ to points $P_m$ in $E$. It should be invertible, and one way is to use $m$ in the curve's equation as $x$ and calculate the according $y$.
• Choose a secret key $x \in \mathbb{F}_q$ randomly, publish the point $Y=x P$ as public key
• Encryption: choose random $k\in\mathbb{F}_q$ , then calculate $C_1=kP$ and $C_2=kY$ and calculate $P_m = f(m)$. The ciphertext is the tuple $(C_1, C_2+P_m)$
• Decryption: From a ciphertext $(C,D)$ calculate $C' = xC$, and retrieve the opint $P_m$ with $P_m = D-C' = (k(xP)+P_m)-(x(kP))$. Then calculate the message $m$ with $f^{-1}(P_m)$.

Basically, the transformation from messages to points is not required. Instead of applying $f$ to the message and using the elliptic curve addition you can just generate a "shared secret" by reducing an elliptic curve point to its $x$ coodrinate. This would look something like this:

• function $\hat{x}(P)$ denotes the x coordinate of a point.
• Encryption: choose random $k\in\mathbb{F}_q$ , then calculate $C=kP$ and $c=\hat{x}(kY)$. The ciphertext is the point $C$ and the product $c \cdot m \text{ mod } q$.
• Decryption: From a point $C$ and a value $d$ calculate $c'=\hat{x}(x C)$. Retrieve the message with $m = d / c' \text{ mod } q$
-