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.

$\endgroup$
  • 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 '15 at 12:23
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}$

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • 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 '15 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 '15 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 '15 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 '15 at 19:21

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.