5
$\begingroup$

The Arstechnica article title as "A (relatively easy to understand) primer on elliptic curve cryptography" claims this;

In fact, you can still play the billiards game on this curve and dot points together. The equation for a line on the curve still has the same properties. Moreover, the dot operation can be efficiently computed. You can visualize the line between two points as a line that wraps around at the borders until it hits a point. It's like, in our bizarro billiards game, when a ball hits the edge of the board (the max) and then is magically transported to the opposite side of the table and continues on its path until reaching a point, kind of like the game

and provides an animation (It is a GIF see on the page, can't link here).

And I've made a similar test that achieved the same;

enter image description here

The simple curve is $E\colon y^2=x^3+4x+20$ over $\mathbb{F}_{29}$ and $P=(1,5), Q=(5,7)$ and $R = P+Q = (16,2)$ is drawn on the figure.

I've followed the same step, draw a line passing through $P$ and $Q$, and continue from the opposite edge when an edge is hit!

The green lines are the borders+1 of the possible elements, the blue lines have used for (visual) check the continuation.

Now enough experience;

If the claim on the Arstechnica is theoretically correct then what is the theory?

$\endgroup$
4
  • 1
    $\begingroup$ "by continuation" can probably be removed from the question title as well, but I'm not 100% on that. $\endgroup$
    – Maarten Bodewes
    Jan 15 at 15:49
  • $\begingroup$ @MaartenBodewes yeah, couldn't find a better word for that, but we can place copies of the map, and see where it hits. $\endgroup$
    – kelalaka
    Jan 15 at 16:33
  • $\begingroup$ I can see that from continuation, but no theory; See in the image $\endgroup$
    – kelalaka
    Jan 15 at 17:29
  • $\begingroup$ A typo. "If the claim on the Arstechnica is theoretically correct, then ..." $\endgroup$
    – Patriot
    Jan 23 at 13:30
4
+100
$\begingroup$

The question asks to prove the (true) fact that, in order to perform point addition $R\gets P+Q$ graphically on an Elliptic Curve over the field $\mathbb F_p$ of equation $y^2\equiv x^3+a\,x+b\pmod p\tag{1}\label{fgr1}$ with $p$ suitably small (here $p=29$, $a=4$, $b=20$) and $4\,a^3+27\,b^2\not\equiv0\pmod p\tag{2}\label{fgr2}$ we can (except in the special case¹ of $P$ and $Q$ equal or on the same vertical line) perform the geometric construction of $R$ per the figure

figure

  • Draw on a (black) square grid of side $p$ the points of the curve (blue dots) other than the neutral².
  • Draw a red line that starts from $P$ parallel to and in the direction of $\overrightarrow{PQ}$.
  • As soon as the line hits a point of the curve other than $Q$, call it $R'$; then on the vertical (purple) line going thru $R'$, find another point of the curve and call it the result $R$ of $P+Q$.
  • If the red line hits a side, draw an horizontal or vertical (green) line from there to the opposite side; then from that intersection keep drawing the red line parallel to and in the direction of $\overrightarrow{PQ}$, and iterate to the above bullet.

After drawing the red line for a displacement of $d$ along the $x$ axis starting from $P$, and accounting for the wraparound on the sides, the pen drawing the red line has coordinates $\begin{align}x&=(x_P+d)&\bmod p\tag{3}\label{fgr3}\\ y&=\left(y_P+d\,\frac{y_Q-y_P}{x_Q-x_P}\right)&\bmod p\tag{4}\label{fgr4} \end{align}$ with the computations in $\mathbb R$. Justification: What's on the left of the $\bmod$ operator³ in $\eqref{fgr3}$ and $\eqref{fgr4}$ is the position of the pen having moven by $d$ along the $x$ axis if we did not wraparound on black edges. The $\bmod$ operators capture the effects of the wraparound.

The points on the red line with both coordinates an integer (including but not limited to any point of the curve) thus have a corresponding $d$ an integer, and verify $(y-y_P)(x_Q-x_P)\equiv(x-x_P)(y_Q-y_P)\pmod p\tag{5}\label{fgr5}$ And any $(x,y)$ matching this equation would be on the red line if we kept drawing it indefinitely; $P$ would be reached when $d=p\,(x_Q-x_P)$ (or earlier).

It follows that our graphical search procedure for $R'$ hits a point of the curve (and thus terminates), and yields a point $R'$ which coordinates $(x,y)$ involves integers that verify $\eqref{fgr1}$ and $\eqref{fgr5}$. But we have not shown yet that $R$ obtained from $R'$ is the expected point (we have not ruled out that $R'=P$ or some other unwanted point of the curve).

An intuitive argument is that when we remove the $\bmod p$ from equations, and work in the field $\mathbb R$ instead of $\mathbb F_p$, $\eqref{fgr5}$ becomes the equation of the line going thru $P$ and $Q$ in the Euclidean plane (with coordinates in $\mathbb R$). Our graphical procedure that draws the red line and finds a third point on the curve that the line intersects is thus a mere translation⁴ in field $\mathbb F_p$ of the graphical construction of point addition on the curve with the same equation in the field $\mathbb R$, and must thus "work", in the sense of yielding a commutative group law on the set of curve points and neutral.


Alternatively, we can make an analytical proof that this graphical procedure terminates and yields the same $R$ as the usual formulas for point addition on the curve of equation $\eqref{fgr1}$ with $\eqref{fgr2}$, that is when $x_P\ne x_Q$ $$\begin{align} \lambda&\gets(x_Q-x_P)^{-1}(y_Q-y_P)&\bmod p\tag{6}\label{fgr6}\\ x_R&\gets\lambda^2-x_P-x_Q&\bmod p\tag{7}\label{fgr7}\\ y_R&\gets\lambda(x_P-x_R)-y_R&\bmod p\tag{8}\label{fgr8} \end{align}$$ Note: In this, all quantities are elements of $\mathbb F_p$, or equivalently integers in range $[0,p)$. In particular, $(x_Q-x_P)^{-1}$ is a modular inverse.

Proof sketch, which mostly⁴ parallels a possible demonstration of the point addition formulas for the same equation in the field $\mathbb R$:

  • We analytically show that $\eqref{fgr1}$ and $\eqref{fgr5}$ are verified by $(x,y)\gets(x_R,(-y_R)\bmod p)$ computed per $\eqref{fgr6}$, $\eqref{fgr7}$, $\eqref{fgr8}$.
  • The condition $\eqref{fgr2}$ allows to prove $x\ne X_P$ and $x\ne X_Q$.
  • Thus the point with these coordinates $(x,y)$ is on the red line drawn indefinitely, and neither $P$ nor $Q$.
  • When we eliminate $y$ from equations $\eqref{fgr1}$ and $\eqref{fgr5}$, we get a cubic equation in $x$ in the field $\mathbb F_p$. It thus has at most 3 distinct solutions. Two of these are $x_P$ and $x_Q$, and the third is the above $x$, neither $x_P$ nor $x_Q$.
  • Since our graphic procedure start from $P$ and skips $Q$, it must reach a point with that $x$ before reaching $P$ again.
  • Hence the $R'$ of our search procedure has the $x=x_R$ of $\eqref{fgr7}$
  • Points of the curve on the same vertical line share the same $x$, thus the same $y^2\bmod p$ per the curve's equation. It follows that the $R$ graphically constructed has the coordinates $(x_R,y_R)$ of $\eqref{fgr7}$, $\eqref{fgr8}$, Q.E.D.

¹ This special case subdivides into

  • $P\ne Q$, in which case $P+Q$ is the neutral².
  • $P=Q$. One graphical construction chooses two distinct points $S$ and $S'$ on the same vertical line, both distinct from $P$, and computes $(P+S)+(P+S')$. When $S$ can be chosen on the same horizontal line as $P$, that simplifies drawing the red line for $P+S$. I know no more direct graphical analog to the "tangent" technique used for a curve in the field $\mathbb R$.

² The neutral is an extra point of the curve, not on the figure, often noted $\infty$ or $0$, such that for any point $S$, $S+\infty=S=\infty+S$.

³ The $\bmod$ operator has a canonical extension from $\mathbb Z$ to $\mathbb R$: we can define $u\bmod m$ with $u\in\mathbb R$ and $m\in\mathbb R_+^*$ as $v\in \mathbb R_+$ with $v<m$ and $(u-v)/m\in\mathbb Z$.

⁴ The only operational difference is that for the Elliptic Curve in the field $\mathbb R$ we must draw the red line in both directions, when that's optional here because we're in a finite set and the line ultimately wraparounds back to $P$.

$\endgroup$
0
$\begingroup$

An elliptic curve has degree 3. A line has degree 1. No curve contains an irreducible component of the other. (Each curve is actually irreducible and has only one component.) Bezout's theorem says the number of intersections of the 2 curves, counting multiplicities, is the product their degrees, which is 3.

Let $R$ be the 3rd point of intersection on the line $PQ$. It's not necessary that $R\neq P$ or $R\neq Q$. The group law on elliptic curves is defined as, if $P, Q$, and $R$ are in a line, then $$ P + Q + R = O $$ where $O$ is the specified point as group identity. So you can imagine that there are curves with points such that $2P + Q = O$.

$\endgroup$
3
  • $\begingroup$ Thanks, however, this question ask about formal proof of the magic of line on the crossing to the other side while keeping the same slope. I.e. the connection of the theory and the image. $\endgroup$
    – kelalaka
    Jan 20 at 13:34
  • $\begingroup$ The set of grid points on the line and its wrap-around continuation is just a normal (algebraic) line. The wrap around is just a visual artifact of the fact that the field is finite. $\endgroup$
    – Myath
    Jan 20 at 20:23
  • $\begingroup$ That is what I can see, that is why I said "what is the theory", not by words rather a formal way to show it. $\endgroup$
    – kelalaka
    Jan 21 at 12:12

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.