Take the 2-minute tour ×
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.

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

1 Answer 1

up vote 15 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$ 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 \mathbb{F}_q$ randomly, publish the point $Y=x P$ as public key.
  • Encryption: choose random $k\in\mathbb{F}_q$ , 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 opint $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\mathbb{F}_q$ , 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
1  
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 at 0:05

Your Answer

 
discard

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.