15
$\begingroup$

Every introduction to elliptic curves that I've read hasn't explained this.

If you have two points P and Q on an elliptic curve, to find P+Q, you draw a straight line through the points, find the third point of intersection with the elliptic curve. To get P+Q, reflect across the x-axis. Why reflect across the x-axis?

For example, towards the bottom of this blog post they explain how to add two points on the curve, but not why you want to reflect across the x-axis.

Please ELI(someone who has taken a university crypto class that didn't cover ECC).

$\endgroup$
3
  • $\begingroup$ You really don't want to read blog posts for something as deep as this; get a good book like those of Enge or Washington. $\endgroup$
    – fkraiem
    Dec 16, 2017 at 3:18
  • $\begingroup$ ... especially not a blog post as bad as the one you linked. $\endgroup$
    – fkraiem
    Dec 16, 2017 at 3:21
  • $\begingroup$ Did you take a look at this? jiggerwit.wordpress.com/2016/10/18/… Sorry @fkraiem, it is a blog post :-/ but this one come with an arXiv paper: arxiv.org/abs/1610.05278 $\endgroup$ Dec 18, 2017 at 9:24

2 Answers 2

19
$\begingroup$

If we did not make the final reflection, point multiplication would not be associative, we would not have a group, and we thus could not define a scalar multiplication the way we do, with the property $n\cdot A+m\cdot A=(n+m)\cdot A$ .

If operation $+$ is a group law, the operation $\boxplus$ defined on that group by $A\boxplus B=-(A+B)$ (which is what removing the reflection does) is generally not associative, because $$(A\boxplus B)\boxplus C=-(-(A+B)+C)=A+B-C,$$ while $$A\boxplus(B\boxplus C)=-(A-(B+C))=-A+B+C.$$ The only groups where $\boxplus$ is associative are those with 1 or 2 elements.

Associativity of point addition on an elliptic curve in fact is a non-trivial and fragile property. Messing with how we do point addition in almost any way (changing sign as proposed, using a curve with a different equation like an astroid..) breaks that property.


Comments by entrop-x and Rosie F provide an intuitive explanation: if three points $A$, $B$, $C$ on the curve are such that "point addition of $A$ and $B$ without final reflection yields $C=A\boxplus B$", then that statement holds for all 6 permutations of $A$, $B$ and $C$, and it can be reworded as "$A$, $B$ and $C$ are collinear" without consideration of the order of the points. In a group with law $+$, the simplest relation between 3 variables with that invariance under order is: $A+B+C=0$, and then we have $A+B=-C=-(A\boxplus B)$ (where the $-$ sign designates taking the opposite for law $+$ ), hence the final reflection to change $\boxplus$ into a group law $+$.

That intuitive explanation can be extended to justify that full point multiplication is associative!

$\endgroup$
5
  • 4
    $\begingroup$ Spot on ! You can actually make it more intuitive, but your answer is clearly the clearest in rigorous terms. Intuitively, if one wouldn't flip the third point, A, B and C on the same line would be "equivalent" and we would have that A + B = C, A + C = B and B + C = A. Filling the B of the second into the first, we'd have A + A + C = C, or 2A = 0 if we assume a group law. But A and B are arbitrary. So every point is 0. $\endgroup$
    – entrop-x
    Dec 16, 2017 at 7:41
  • 1
    $\begingroup$ Alternatively: the property "the points A, B, C are collinear" is symmetric in A, B, C. As @entrop-x said, $A+B=C$ fails. But $A+B+C=0$ succeeds, as + is commutative. $A+B+C=0 \iff A+B=-C$ and the $-$ corresponds to the flip. $\endgroup$
    – Rosie F
    Dec 16, 2017 at 9:19
  • $\begingroup$ Is it accurate to put it as "a point at infinity ($\phi$) of an elliptic curve is analogous to zero in the set of $\mathbb{R}$"? $\endgroup$ Jan 14, 2023 at 5:14
  • $\begingroup$ @RomeoSierra: when $\mathbb R$ is seen as a group under ordinary addition, yes the analogy is justified: $0$ is the identity element for that group, quite like the point at infinity of an elliptic curve is the identity element for the group formed by the elliptic curve under point addition. When $\mathbb R$ is viewed as the field for coordinates of points on an (infinite) elliptic curve, there's no good analogy. $\endgroup$
    – fgrieu
    Jan 14, 2023 at 5:26
  • $\begingroup$ @fgrieu Yep. That's the way to put it accurately... $\endgroup$ Jan 17, 2023 at 12:29
11
$\begingroup$

Cryptographic operations on elliptic curves typically deal with scalar multiplication of points. That is, we pick a generator point $P$ and a random, secret integer $d$, and we add $P$ to itself $d$ times. This is easy to calculate, but it is very difficult to find out the value of $d$ given the points $P$ and $dP$.

Now consider a variant where we don't flip over the x-axis. First we calculate $2P$ by drawing a line tangent to the curve at point $P$, and call this $Q$. To calculate $3P$, we add $P + Q$, so we draw a new line that goes through $P$ and $Q$ -- but this is the exact same line, so the "third point" on the curve is $P$ itself. (There are only two intersecting points because the line is still tangent to the curve, so we consider the tangent point as two points.)

So to get a meaningful definition of scalar multiplication that is useful in cryptography, we need the flip across the x-axis to get a non-trivial cyclic group with an order larger than $2$.

$\endgroup$

Your Answer

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

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