In Figure 3, the point $R$ is the sum of the points $P$ and $Q$ on the elliptic curve (and $-R$ is the additive inverse of $R$).
Why is the sum of $P$ and $Q$ not simply the point at the third curve intersection; what we call point $-R$ in Figure 3? Why must we instead consider $R$, the $x$-axis reflection of $-R$, to be the sum of $P$ and $Q$? The answer is that reflecting points in this way imparts the property of associativity on the curve's points.
And as we will see, without associativity, the elliptic curve could not function as the basis of a Diffie-Hellman style key agreement protocol.
Understanding the add() Function¶The code that renders the addition of $P$ and $Q$ graphically in Figure 3 uses the complicated-looking add() function to do the work of summing the points. Let's take a look at each line of code in that function to see what is going on.
Given two points, where $P$ is defined by the coordinates $(x_1, y_1)$ and $Q$ is defined by the coordinates $(x_2, y_2)$, the equation for the slope of a straight line drawn between them is the following:
$\displaystyle \frac{y_2 - y_1}{x_2 - x_1}$
And this maps precisely to the first line of code in the add() function.
m = (y2 - y1) / (x2 - x1)
The slope is assigned to the variable $m$, because we will need this value in subsequent computations.
Recall from above that the equation for an elliptic curve is $y^2 = x^3 + ax + b$. And recall from high school algebra that the equation for a straight line is $y = mx + B$, where $m$ is the slope of the line, and $B$ is the $y$-coordinate of the point at which the line intercepts the $y$ axis. Thus we can rewrite the curve equation as follows, substituting $mx + B$ for $y$:
$(mx + B)^2 = x^3 + ax + b$
Having reduced the curve equation to a univariate (i.e., single variable) equation, we can manipulate it algebraically into the following form, which we call a cubic polynomial equation:
$x^3 - m^2x^2 + (a - 2mB)x + (b - B^2) = 0$
(Incidentally, a cubic polynomial in which the coefficient of the first term is $1$ is also known as a monic polynomial.)
Because the line between $P$ and $Q$ (almost always) intersects the curve at a third point $-R$, it has three distinct roots; that is, values of $x$ where the line intersects the curve at $P$, $Q$ and $-R$. Moreover, a property of cubic polynomials is that the sum of their roots is equal to the negative of the division of the coefficient of the second term by the coefficient of the first term. Algebraically:
$x_1 + x_2 + x_3 = -(\displaystyle \frac{-m^2}{1})$
Since the negative of a negative is a positive, and any number $n$ divided by $1$ equals $n$, we can simplify this to the following:
$x_1 + x_2 + x_3 = m^2$
Why is all this necessary? Because it gives us a way to determine the value of the third root, which is the $x$-coordinate of the third point of intersection $-R$ on the curve, or $x_3$. Rearranging the terms in the previous equation, we can compute $x_3$ as follows:
$x_3 = m^2 - x_1 - x_2$
The equation above thus maps to line 2 of the add() function:
x3 = pow(m, 2) - x1 - x2
All that is left now is to compute the $y$-coordinate of point $R$, or $y_3$. Here again, we employ the familiar straight-line equation, plugging $y_3$ and $x_3$ into it:
$y_3 = mx_3 + B$
Since we already know the values of $x_1$ and $y_1$, we can substitute $y_1 - mx_1$ (or $y_2 - mx_2$ for that matter) for $B$ to get the following equation:
$y_3 = mx_3 + (y_1 - mx_1)$
Simplifying the equation further, we get:
$y_3 = m(x_3 - x_1) + y_1$
And now we have an equation that maps to line 3 of the add() function:
y3 = m * (x3 - x1) + y1
With these three lines of code, we have thus solved for the coordinates $(x_3, y_3)$, or the point $-R$, in the graph in Figure 3.
Finally, recall that the sum of $P$ and $Q$ is in fact the additive inverse of the third point of intersection on the curve, or $-R$. To produce $R$, we simply reverse the sign of $y_3$, and return $(x_3, -y_3)$ from the add() function:
return x3, -y3
Doubling Points¶So far, we've added two distinct points $P$ and $Q$ to get a third point $R$. But in a cryptographic implementation, we are given just a single starting point; the base point $P$.
To generate a second point (and all subsequent points on the curve) from a single base point, we add the base point to itself, as in $P + P$. This is done by drawing a straight line where the base point $P$ is tangent to the curve, and finding the second point of intersection, just like we did when we added $P + Q$ to find the third point of intersection.
Another way of saying that we are adding a point to itself is that we are doubling a point, as in $2P = P + P$.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4