# Decoding a message on elliptic curve

Let's say I have an elliptic curve $$E$$ $$y^2=x^3 + 486662x^2 + x$$ over a prime field $$GF(2^{255} - 19)$$. My algorithm for computing $$E(m)$$ is as follows:

• I take the bits 1 through 32 of the message and plug that for $$x$$ in the equation.
• I then calculate the result, store it as $$x$$,
• and calculate the sign of $$y$$ using the first bit of $$m$$.

Let $$e$$ be the encryption key, then we can set the encrypted value of $$m$$ equal to $$Enc(m) = E(m)^e.$$

My question is how can I decode the message if I know the encryption key? Is it always possible?

• Hey there. My algorithm for computing $E(m)$ is as follows: I take the the bits 1 through 32 of the message and plug that for $x$ in equation. I then calculate the result, store it as $x$, and calculate the sign of $y$ using the first bit of $m$. – Oleg Stotsky Nov 6 '18 at 7:31
• Okay, no problem. – Oleg Stotsky Nov 6 '18 at 7:38
• What is calculate the sign of y using the first bit of m. could you explain it in the question? – kelalaka Nov 6 '18 at 7:52
• The main issue I see is that about half of the $x$ won't generate a valid x-coordinate of a point on that curve (i.e. when you "plug that for $x$ in the equation" you will get a non-square number, which has no square roots.) – Ruggero Nov 6 '18 at 16:06

if your $$e$$ is coprime to $$p-1$$ where $$p=2^{255}-19$$ you can calculate the $$e$$-th of an integer modulo $$p$$ which means you can recover $$E(m)$$ given $$E(m)^e$$. In fact, if the condition holds, there exist $$u,v \in \mathbb{Z}$$ such that $$eu+(p-1)v=1$$ (Bezout's identity). Now, we are looking for an integer $$x$$ such that $$x \equiv a^{1/e} \pmod p$$ i.e. $$x^e \equiv a \pmod p$$. It is easy to find it: $$a^u \equiv x^{eu} \equiv x^{1-(p-1)v} \equiv x\times (x^{p-1})^{(-v)}\equiv x \pmod p$$ because $$x^{p-1} \equiv 1 \pmod p$$ according to Fermat's little theorem.