# 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

• 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$. – Brock Hansen Apr 23 '14 at 0:05
• @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