I need an example of Elliptic ElGamal Public Key Cryptosystem. I have been trying with some values but I don't get the right solution.

I have $p=13$, the elliptic curve $E:y^2=x^3+11x+7$ and a point $P=(6,\sqrt{3}) \in E(\mathbb{F}_{13})$.

The message is $M=(0.5,12.625)\in E(\mathbb{F}_{13})$.

Alice, chooses the value $nA=5$, calculates Q$_A=n_A \cdot P=(2.5,11.125)$ and sends $Q_A$.

Bob chooses the integer $k=2$ randomly and calculates $C_1$ and $C_2$: $$C_1=k⋅P=(12,\sqrt{23})$$ $$C_2=M+k⋅Q_A=(5.5,8.875)$$

Bob sends $(C_1,C_2)$ to Alice.

Alice calculates M: $$M=C_2−n_A⋅C_1=(−2.5,−8.4455)$$ and the solution should be $ M=(0.5,12.625)$ ... Does someone know what is wrong? I think that my problem is calculating in $\mathbb{F}_{13}$, but I'm not sure.

Thank you :)

  • $\begingroup$ Please note that you usually wouldn't use ElGamal with real numbers. (I'm not even sure if it works in this case) $\endgroup$
    – SEJPM
    Commented Jan 10, 2016 at 20:13
  • 2
    $\begingroup$ $\mathbb{F}_{13}$ is a field with precisely 13 members, and those 13 members do not include $\sqrt{3}$, $0.5$ or $12.625$. You can perform Elliptic Curve operation over the field of the Reals; however in that case, $(6, \sqrt{3})$ is not a solution to the equation for curve $E$ $\endgroup$
    – poncho
    Commented Jan 10, 2016 at 20:20
  • 1
    $\begingroup$ $y^2=3$ are two points of this curve for $x=6$,I think $0.5$ and $12.625$ means $2^{-1}$ and $101*8^{-1}=10*8^{-1} \pmod {13}$ respectively. $\endgroup$ Commented Jan 10, 2016 at 20:49
  • $\begingroup$ @poncho That sounds like a notation issue to me. Since $4^2 \equiv 3 \pmod{13}$ using $\sqrt{3}=4$ sounds reasonable (defining positive as square). $(6, \pm 4)$ is on the curve. $\endgroup$ Commented Jan 10, 2016 at 22:00

1 Answer 1


In points of elliptic curve instead of $\frac {a}{b} $ you should use $a\cdot b^{-1} \pmod p$. Also: $$\sqrt3=\{i \in [0,12]|i^2=3 \pmod {13}\}=\{4,9\}$$ So $P=(6,4)$ or $P=(6,9)$ which $2\cdot P$ are $(10,8)$ and $(10,5)$ respectively. But your computation show that $2\cdot P=(12,\sqrt {23})$.

  • Also with $x=12$ we have't a solution for $y$ in your elliptic curve.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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