3
$\begingroup$

I am studying elliptic curve cryptography and this question is related to the commutative property of point addition operation.

Point addition $P_3(x_3,y_3)$ of two points $P_1(x_1, y_1)$ and $P_2(x_2,y_2)$ is given by the following rules: $$x_3 = (\lambda^2 - x_1 - x_2) \bmod n$$ and $$y_3 = (\lambda (x_1 - x_3) - y_1) \bmod n$$ where $$\lambda = \frac{y_2-y_1}{x_2-x_1} \bmod n.$$

To prove that the point addition operation is commutative, I simply interchange $x_1$ by $x_2$, and $y_1$ by $y_2$, and what I get is:

$$x_3' = (\lambda^2 - x_2 - x_1) \bmod n$$ and $$y_3' = (\lambda (x_2 - x_3) - y_2) \bmod n.$$

Now it can be seen that $x_3 = x_3'$ but $y_3 \ne y_3'$; that is, I am not getting the same point $(x_3, y_3)$. But I have read everywhere that point addition is a commutative operation.

Please help me understand the problem.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ $y_3=y_3^{'}$ is equivalent to $\lambda(x_1-x_3)-y_1 = \lambda(x_2-x_3)-y_2$ or $\lambda=\frac{y_1-y_2}{x_1-x_2}$, so it's ok $\endgroup$
    – Radu Titiu
    Jan 27, 2015 at 12:23

2 Answers 2

Reset to default
3
$\begingroup$

If I am not mistaken, $y_3 = y'_3$:

$y_3 = \frac{y_2 - y_1}{x_2 - x_1}(x_1 - x_3) - y_1 = \frac{y_2 x_1 - y_2 x_3 - y_1 x_1 + y_1 x_3 - y_1 x_2 + y_1 x_1}{x_2 - x_1} = \frac{y_2 x_1 - y_2 x_3 + y_1 x_3 - y_1 x_2}{x_2 - x_1}$

$y'_3= \frac{y_1-y_2}{x_1-x_2}(x_2-x_3) - y_2 = \frac{y_1 x_2 - y_1 x_3 - y_2 x_2 + y_2 x_3 - y_2 x_1 + y_2 x_2}{x_1-x_2} = \frac{y_2 x_1 - y_2 x_3 + y_1 x_3 - y_1 x_2}{x_2 - x_1}$

Improve this answer
$\endgroup$
3
$\begingroup$

In fact you don't need algebra to see this. Only use the geometrical interpretation of the addition.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Wouldn't the geometrical interpretation be hard to illustrate (without the algebra) when using curves over finite fields? I agree that for a curve over the reals it would be a pretty simple thing to show, but over a finite field, it would be hard. $\endgroup$
    – mikeazo
    Feb 6, 2015 at 13:58
  • 1
    $\begingroup$ Just to see or understand this, geometrical interpretation over the reals is enough. The question was about the proof - which requires formulas. However, the transition from reals to integers is only a representational issue: Both are fields and only field operations and equations are used. What is to show is that you get integer results with integer input, when you use the inversion of finite fields (which works always unless you try to divide by 0)... it's possible, but it also involves some algebra. $\endgroup$
    – tylo
    Feb 6, 2015 at 16:48
  • $\begingroup$ @mikeazo. The same principal. The composition law defined purely geometrically. If $P,Q\in E$ then there is a third point $R$ ($P,Q,R$ not necessarily distinct). In order to compute $P+Q$ we get the line $L'$ through $O,R.$ The intersection point of $L'$ with $E$ is $P+Q.$ Now if we repeat the previous definition with $Q,P$ we will find the same point. I.e., $P+Q=Q+P$. $\endgroup$
    – 111
    Feb 6, 2015 at 17:11
  • 2
    $\begingroup$ I, for one, would completely accept a proof which says "addition is commutative because for any two points $P$ and $Q$, the line through $P$ and $Q$ is the same as the line through $Q$ and $P$", and all references I know of do the same. Keep the ugly formulas for implementations, where they belong. $\endgroup$
    – fkraiem
    Feb 6, 2015 at 19:21

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.