Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
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
up vote 21 down vote accepted

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$.
share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.