2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Oleg Stotsky Nov 6 '18 at 7:31
  • $\begingroup$ Okay, no problem. $\endgroup$ – Oleg Stotsky Nov 6 '18 at 7:38
  • $\begingroup$ What is calculate the sign of y using the first bit of m. could you explain it in the question? $\endgroup$ – kelalaka Nov 6 '18 at 7:52
  • 1
    $\begingroup$ 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.) $\endgroup$ – Ruggero Nov 6 '18 at 16:06
1
$\begingroup$

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.

$\endgroup$

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.