# Elliptic ElGamal Public Key Cryptosystem doubt

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 :)

• Please note that you usually wouldn't use ElGamal with real numbers. (I'm not even sure if it works in this case) – SEJPM Jan 10 '16 at 20:13
• $\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$ – poncho Jan 10 '16 at 20:20
• $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. – Meysam Ghahramani Jan 10 '16 at 20:49
• @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. – CodesInChaos Jan 10 '16 at 22:00

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.