0
$\begingroup$

I tried to calculate the sum of two Points on an elliptic curve in a finite field. The Curve is defined as following:

$$y^2 \equiv x^3 + x \mod 257$$

So the curve parameters are $a = 1,b = 0,p = 257$.I want to add the two points $P = (1|60)$ and $Q = (15|7)$:

$$60^2 \equiv 1^3 + 1 \equiv 4 \mod 257$$ $$7^2 \equiv 15^3 + 15 \equiv 49 \mod 257$$

To add this two points, I calculate the slope $s$, $x_r$ and $y_r$:

$$s = \frac{y_q - y_p}{x_q - x_p}$$ $$x_r = s^2 - (x_p + x_q)$$ $$y_r = s(x_p - x_r) - y_p$$

for my points $P$ and $Q$ I get:

$$s = \frac{7-60}{15-1} = \frac{-53}{14} = -3.7857142857$$ $$x_r = (\frac{-53}{14})^2 - (1 + 15) = 14.3316326531 - 16 = -1.6683673469$$ $$y_r = \frac{-53}{14}(1-(-1.6683673469)) - 60 = -70.1016763848$$ $$R = (-1.6683673469|-70.1016763848)$$ However: $$x_r^3 + x_r = -6.3121837787$$ while $$y_r^2 = 4914.2450319648$$ So $R$ seems to be outside the curve. Even if I calculate everything modulo 257 I get weird results.

What I don't understand:

  • since I defined the curve on a finite field, I expected integer results
  • I expected $R$ to be part of the curve
  • the definition of $x_r$ is the difference between $s^2$ and the sum of the x-coordinates of the two added points. Why can $s^2$ be interpreted as an x-coordinate or even a length?
  • in reference to wikipedia, the addition of two points of an elliptic curve is commutative. That seems to be true for $x_r$, but why should it be true for $y_r$?

Notes:

  • I looked for an answer to this questions and all I did find were this and this. Both questions looked similar to mine but I still don't understand addition on elliptic curves.
  • I'm really new to elliptic curves, sorry if I did huge mistakes by calculating these values
$\endgroup$
2
$\begingroup$
  • You are right, when you're working on a finite field, you should get integer results. So let's look at why you aren't.

The problem lies in how you handle the fractions inside the equation, e.g. $s=\frac{y_q-y_p}{x_q-x_p}$. Elliptic curve operations make use of finite field arithmetic. Maybe it'd be easier for you to grasp if you imagined the equation to look like $s=(y_q-y_p)(x_q-x_p)^{-1}\mod p$. This means that you have to calculate the modular inverse of the denominator of your fracture and then multiply this with the nominator.

  • $R$ is indeed part of the curve. Recalculate it using the "technique" described above.

  • It's not right to see it as length. As you're reducing the result modulo a prime ($\mod p$) the information which you call "length" is lost.

  • Take two points that are part of an elliptic curve, e.g. $P$ and $Q$. Commutative means that $P + Q$ gives the same result as $Q + P$. However it does not mean that you can just switch the $x$- and $y$-coordinates

$\endgroup$
  • 3
    $\begingroup$ Thanks for the hint, I will try to calculate the modular inverse :) $\endgroup$ – Aemyl May 12 '17 at 8:46
  • $\begingroup$ about the cummutative: I didn't want to switch the $x$- and $y$-coordinates, I wondered why I should get the same result by calculating $y_r = s(x_q - x_r) - y_q$ $\endgroup$ – Aemyl May 12 '17 at 8:49
1
$\begingroup$

I don't have enough reputation to comment, so will do so here.

Re commutativity: geometrically, when you add two (unequal) points on an elliptic curve, you draw a secant line through the two points and find the point where it intersects. Then reflect this point across the x-axis to get the sum.

But two points determine a line, so it doesn't matter whether you do $P + Q$ or $Q+P$; the secant line is the same either way.

Algebraically, you correctly note that under exchange of $P$ and $Q$, $x_r$ doesn't change. The same is true for $y_r$. Swapping the points gives you $y_r = s(x_q - x_r) - y_q$. If you expand this polynomial (substitute the full expression for $s$), you'll get the same $y_r$ as before.

$\endgroup$
  • $\begingroup$ good point, I referred to the algebraic way. I understood that $y_r = s(x_q - x_r) - y_q$ gives the same result, I just wondered why it does. At least I could fix the calculation of $s$, now I get the correct results :) $\endgroup$ – Aemyl May 12 '17 at 16:34

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.