0
$\begingroup$

I am new to elliptic curve cryptography as well as finite field theory. I am trying to understand point addition in affine coordinates.

I understand, that for an elliptic curve $ y^{2}=x^{3}+ax+b $ over $\mathbb R$ the sum of two points $P=(x_{p},y_{p})$ and $Q=(x_{q},y_{q})$ is $R=(x_{r},y_{r})$: $$x_{r}=\lambda^{2}-x_{p}-x_{q}$$ $$y_{r}=\lambda(x_{p}-x_{r})-y_{p}$$

with the slope $$\lambda=\frac{y_{q}-y_{p}}{x_{q}-x_{p}}$$

Excluding the cases: $P=Q$ (e.g. tangent slope), $P=0$ and $Q=0$ (e.g. $R=0$). If however the elliptic curve is defined over a finite field with prime size $n$: $$y^{2}=x^{3}+ax+b\pmod n$$

Can I just compute the slope for the "standard case" as follows (source: Slide 6)?

$$\lambda=\frac{y_{q}-y_{p}}{x_{q}-x_{p}} \pmod n$$

I understand that for an element in a finite field (f.e. point $P=(x_{p},y_{p})$) amongst other things an multiplicative inverse has to exist. However the formula for the slope $\lambda$ does only include coordinates of the point, not the element itself.

$\endgroup$
  • $\begingroup$ The formula for $\lambda$ w/o the $\bmod n$ is exactly the same, the modular reduction is just implicit (if this was your question), assuming you're operating over a prime field. $\endgroup$ – SEJPM Mar 1 '17 at 14:39
  • 1
    $\begingroup$ Your formula for $\lambda$ has numerator and denominator swapped (in both instances). $\endgroup$ – yyyyyyy Mar 1 '17 at 14:54
2
$\begingroup$

Your coordinates are elements of the finite field. For a point $P = (x_p, y_p)$ with $x_p,y_p \in \mathbb{F}_n$, where $\mathbf{F}_n$ is the finite field of order $n$ over which the elliptic curve is defined.

Since $n$ is prime, your slope will also be an element of the field $\mathbb{F}_n$. Even if $n$ was composite and $\gcd(x_q - x_p, n) = 1$, $\lambda$ is still an element of your field since an inverse of $(x_q - x_p)$ would still exist in this case. To compute the slope, you must find the multiplicative inverse of $(x_q-x_p)$ in your field $\mathbb{F}_n$. Then $$\lambda \equiv (y_q - y_p)\cdot(x_q - x_p)^{-1} \pmod n \text.$$

$\endgroup$
  • $\begingroup$ Thank you. So if all coordinates, such as $x_p,y_p$ are $\in \mathbf{F}_n$, then every calculation has to be done in the field $\mathbf{F}_n$? Since however $(x_q - x_p)$ are not points I can use "normal" subtraction / addition here, right? Also including the modulo operation already here is possible to calculate with smaller numbers, but not necessary? Like this: $(x_q - x_p) \pmod n$ $\endgroup$ – floyd Mar 1 '17 at 17:22
  • 1
    $\begingroup$ @floyd Be sure every operation is done modular $n$. $\endgroup$ – shaun1010 Mar 1 '17 at 20:53
  • $\begingroup$ In the above answer, how do we proceed if gcd(xq−xp,n) is not equal to 1? $\endgroup$ – Rishabh Jain Jun 2 at 14:28
  • $\begingroup$ As $n$ is a prime larger than both $x_p,x_q$ this won't happen unless $x_p=x_q$ and in that case you're trying to do a point-doubling and there's a different formula for that. $\endgroup$ – SEJPM Jun 2 at 14:38
  • 1
    $\begingroup$ @SEJPM: doubling which is a different formula or adding a point to its additive inverse which is a special case in the addition formula and gives the point at infinity aka scriptO. $\endgroup$ – dave_thompson_085 Jun 3 at 1:31

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.