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
    Jan 10 '16 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
    Jan 10 '16 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$ Jan 10 '16 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$ 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.

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.