1
$\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.

Improve this question
$\endgroup$
2
  • $\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, 2017 at 14:39
  • 1
    $\begingroup$ Your formula for $\lambda$ has numerator and denominator swapped (in both instances). $\endgroup$
    – yyyyyyy
    Mar 1, 2017 at 14:54

1 Answer 1

Reset to default
3
$\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.$$

Improve this answer
$\endgroup$
5
  • $\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, 2017 at 17:22
  • 1
    $\begingroup$ @floyd Be sure every operation is done modular $n$. $\endgroup$
    – shaun1010
    Mar 1, 2017 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, 2019 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, 2019 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, 2019 at 1:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.