20
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Maarten - reinstate Monica Feb 22 '15 at 15:57
28
$\begingroup$

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)$.
$\endgroup$
  • 3
    $\begingroup$ 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$. $\endgroup$ – Brock Hansen Apr 23 '14 at 0:05
  • $\begingroup$ @BrockHansen Changed the description of the private key "generation". Could you check if the math notation is good enough? $\endgroup$ – Maarten - reinstate Monica Feb 22 '15 at 16:08
  • $\begingroup$ @MaartenBodewes Now it should be fine. $\endgroup$ – DrLecter Feb 22 '15 at 17:16
  • $\begingroup$ @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. $\endgroup$ – Maarten - reinstate Monica Feb 22 '15 at 17:24
  • 1
    $\begingroup$ @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 :/ $\endgroup$ – DrLecter Feb 22 '15 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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