How does ECC go from decimals to integers?

Question

I realise that elliptical curves are tricky, but there's one aspect that no one seems to explain. I've looked, and it's towards the beginning. This is the traverse over a red curve:-

This is only three steps (n=3). For cryptography n must be large. I don't know how large but I cannot believe that all tangential and intersection points occur at coordinates with integer values. They must be decimal. After all the curve is smooth and continuous. The tangents can be all sorts of infinitely precise gradients. We know that decimal encryption can't work due to representational and rounding errors. Assume that point G is at (-2,4). There is no way that point 8G is at (3,3) exactly. And if n is very large?

I had a look at the wiki article regarding elliptic curve point multiplication, but using an example of 42.57 degrees didn't clear it up any. I think that there's a crucial step I'm missing before the explanation of Integers in ECC. So,

Q: How do traverses over elliptical curves go from decimal coordinates to integer values that can then be used for practical cryptography?

The fact that I've identified this curve as type "red" indicates my lack of ECC knowledge or general mathematics ability. Is it possible to explain simply or am I reaching beyond my grasp?

Answer 1

I think what's going on is that a lot of introductions to elliptic curves start off with the geometric description of the group laws so as to be as visual as possible (it certainly is not intuitive to me at all). And then they switch to elliptic curves over finite fields, which look very different than the continuous case over $\mathbb{R}$ even though the group laws are the same:

$$y^2 = x^3 - 2 x + 1 \text{ over } \mathbb{Z}_{89}$$

[source]

I know; that doesn't look like a curve at all. So the idea of a "curve" is really weird over a finite field. But doing all of your calculations $\bmod p$ (i.e., adding points, calculating "slopes") will always be integral.

---

Let's go through an example using the curve $E: y^2 = x^3 - 2x + 1$ over $\mathbb{F}_{89}$. Picking $x=4$ gives us $y^2 = 4^3 - 2\cdot 4 + 1 = 57 \bmod 89$. Now, in general, to take the square root modulo a prime, you have to use the Tonelli-Shanks algorithm. Understanding this involves some number theory, such as quadratic residues. Here's a Python implementation. So like "regular" square roots, you can get two answers, and it turns out that $\sqrt{57} \equiv \{71,18\} \bmod 89$. So $(4,18)$ may be the point you mean.

Let's demonstrate addition. Let $P = (P_x, P_y) = (4, 18)$ be the point we just found. I'll pick $Q = (Q_x,Q_y) = (15,63)$. (I iterated through all $x$ from $1$ to $88$ and computed $y$ as above with the modular square root, and just picked one.)

The slope is $\lambda = (Q_y - P_y)\cdot (Q_x - P_x)^{-1} = 45 \cdot 11^{-1} = 45 \cdot 81 \bmod 89 \equiv 85 \bmod 89$

($81$ is the modular inverse of $11$, $\bmod 89$.)

Now calculate $\nu = P_y - \lambda P_x = 18 - 85\cdot 4 \bmod 89 \equiv -322 \bmod 89 \equiv 34 \bmod 89$, and finally,

$$x_3 = \lambda^2 - Q_x - P_x = 85^2 - 15 - 4 \bmod 89 \equiv 86 \bmod 89$$

$$y_3 = -(\lambda x_3 + \nu) = -(85 \cdot 86 + 34) \bmod 89 \equiv 43 \bmod 89$$

So we have $P + Q = (86,43)$ on $E(\mathbb{F}_{89})$. You can check that this point is on the curve since $86^3 - 2\cdot 86 + 1 \equiv 43^2 \bmod 89$.

---

You may like exploring these ideas with Sage as well.

Answer 2

ECC goes from "decimal" (actually, real) to integer by reusing the sames equations (for the curve, point addition or doubling), applied to some finite field instead of the infinite field $(\mathbb R,+,*)$. The "curve" becomes a set of finitely many points (as nicely illustrated in that other answer). The intuition that we could keep the geometrical construction does not immediately materialize, especially for point doubling.

Update: but not all hope is lost. The last picture in this tutorial shows that, when the finite group is $(\mathbb Z_p,+,*)$, we can make a geometric construction of point addition $A+B$ when $A\ne B$. And for doubling point $A$ we can take another point $B$ and say that $2\times A=2\times A+(B-B)=(A+B)+(A-B)$ and compute the later geometrically with three point additions.

Note: Just restricting from $\mathbb R$ (reals) to the subset $\mathbb Z$ (integers) leads nowhere, because so few points on the curve fall onto integer coordinates.

---

The geometric construction in the question applies on the Cartesian plane. It lets one establish the formulas for the point addition operation, and its special case doubling, as equations between Cartesian coordinates in the field $(\mathbb R,+,*)$. That point addition is an operation on the points of curve; it is internal (result is on the curve), and commutative. We can include an additional point as identity element, and define that elements have an additive inverse by symmetry relative to the horizontal axis; all that is geometrically evident and consistent. Then algebra based on the formulas shows the surprising fact that the point addition operation is associative (reportedly, there's also a non-trivial geometrical proof; what follows is an illustration only). We have a group!

^{Credit: Thomas Cooper, who created a GNU Octave script to generate this file; Public Domain.}

Elliptic curve cryptography replaces $(\mathbb R,+,*)$ with a finite field, perhaps $(\mathbb Z_p,+,*)$. This is not performed by considering points of the curve that fall on integer points, because there are very few; for example $y^2=x^3−2x+1$ has only 3 integer solutions: $(x,y)\in\{(0,1),(0,-1),(1,0)\}$.

Rather, replacing $(\mathbb R,+,*)$ with a finite field is made by using the curve's equation in that finite field, as well as the formulas established for point addition and doubling; that yields an operation that is commutative, associative, with identity element, and an opposite for any element; again, the axioms for a group.

The resulting "curve" looks like an haphazard set of points (with symmetry along an axis inherited from that of the original curve), as nicely illustrated in that other answer. The geometric (or at least, visual) aspect of the construction vanishes, except for opposites. In particular, we can no longer visually define a tangent, or the intersection of the line joining two points of the "curve" with a third point of the "curve". And what used to be a "slope" now involves a multiplicative inverse in the finite field, which computation is performed radically differently (e.g. by the Extended Euclidean algorithm or by exponentiation) from computing the multiplicative inverse in $\mathbb R$.

Answer 3

One way to get a better grasp on the transition is to look at the explicit formulas that are derived from the image that you posted:

For $R = P \oplus Q$ on $E: y^2 = x^3 + ax + b$ we get the following formulas for point addition and doubling:

Point addition:

• $\lambda = \frac{y_Q - y_P}{x_Q - x_P}$
• $\nu = y_P - \lambda x_P$.
• $x_R = \lambda^2 -x_P-x_Q$
• $y_R = -\lambda x_R - \nu$

Point doubling:

• $\lambda = \frac{3 x_P^2 + a}{2y_P}$
• $\nu = y_P - \lambda x_P$.
• $x_R = \lambda^2 -2x_P$
• $y_R = -\lambda x_R - \nu$

And it is immediately obvious that all the operations that are performed are available in a field. Hence, if the curve parameter $a$ is in a finite field and taking two points with coordinates in that field the result must also be in it.

That explains why using our formula over a finite field still works. And, when taking the x-axis symmetry into account, it also explains why a line through two points will still end up at a third point over a finite field.

Why elliptic curve points form a group beyond the geometrical intuition is usually proven using advanced techniques from algebraic geometry. Then it is easy to show that this also holds over a finite field.

If you want to go down that rabbit hole I think about the first 50 pages of Hartshorne's book on algebraic geometry might suffice but they are far from an easy read and require knowledge of algebra.

Another interesting take on the problem is this elementary proof of the group law using only the explicit formulas. Unfortunately it is hard to read and imho not very enlightening. But it is a proof that the group law holds.