# 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 too much background information;

1. What is the private, what is the public key?
2. How to encrypt messages?
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. Commented Feb 22, 2015 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=kP$$ and $$C'=kY$$ and calculate $$P_m = f(m)$$. The ciphertext is the tuple $$(C, C'+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)$$.
• 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$. Commented Apr 23, 2014 at 0:05
• @BrockHansen Changed the description of the private key "generation". Could you check if the math notation is good enough? Commented Feb 22, 2015 at 16:08
• @MaartenBodewes Now it should be fine. Commented Feb 22, 2015 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. Commented Feb 22, 2015 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 :/ Commented Feb 22, 2015 at 17:32