11
$\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$
  • $\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 '17 at 3:18
  • $\begingroup$ ... especially not a blog post as bad as the one you linked. $\endgroup$ – fkraiem Dec 16 '17 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$ – Cédric Van Rompay Dec 18 '17 at 9:24
16
$\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$
  • 3
    $\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 '17 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 '17 at 9:19
9
$\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, privacy policy and cookie policy

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