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.

-
Note that it is more common to use ECIES to encrypt data using EC. ECIES is basically static Diffie-Hellman key agreement followed by symmetric encryption using the resulting key. – Maarten Bodewes Feb 22 '15 at 15:57

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$ of order $N$ just the same as for EC-DDH as system parameters.
• You need a public known function $f : m \mapsto P_m$, which maps messages $m$ to points $P_m$ on $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_R [1,N-1]$ randomly, publish the point $Y=x P$ as public key.
• Encryption: choose random $k\in_R [1,N-1]$ , 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 point $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$ coordinate. This would look something like this:

• function $\hat{x}(P)$ denotes the x coordinate of a point.
• Encryption: choose random $k\in_R [1,N-1]$ , then calculate $C=kP$ and $c=\hat{x}(kY)$. The ciphertext is the point $C$ and the product $d=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$.
-
You're using $\mathbb{F}_q$ to denote the field from which the ECC points' coordinates are chosen. Private keys are chosen from 1..N-1, where N is the order of the ECC group, not from $\mathbb{F}_q$. – Brock Hansen Apr 23 '14 at 0:05
@BrockHansen Changed the description of the private key "generation". Could you check if the math notation is good enough? – Maarten Bodewes Feb 22 '15 at 16:08
@MaartenBodewes Now it should be fine. – DrLecter Feb 22 '15 at 17:16
@DrLecter Ah, yeah, I wondered already if the other random components would be correct. I guess they have to be limited by the order :) I'm currently trying to map a message $m$ to a point for Bouncy Castle for this question - if anybody is able to help please do. – Maarten Bodewes Feb 22 '15 at 17:24
@MaartenBodewes You could take a look at this paper (Section 2.4 shows a simple standard approach). I think I have answered such a question already here somewhere, but cannot find it anymore :/ – DrLecter Feb 22 '15 at 17:32