13
$\begingroup$

I'm a working programmer (read: a person without a maths degree) trying to get a better grasp on elliptic curves specifically in the context of elliptic curve cryptography (though to be clear, this is for personal development — I'm in no way trying to roll my own crypto).

One concept that's difficult to grasp for me is that curve points in the ECC context are often discretized over a finite field — specifically, a finite field having cardinality of the form $P^n$ for some large prime $P$. This gives points on elliptic curves a congruent behaviour under modular arithmetic whose value I can understand in this setting.

My question here is, how is the set of discrete points on elliptic curves determined for ECC applications? I'm entirely willing to do the legwork in terms of getting more math context, but I think I've got a lack of mathematical vocabulary which has made searching for papers explaining this difficult.

$\endgroup$
  • 2
    $\begingroup$ Understanding Elliptic Curves requires Mathematics Knowledge and it is taught beyond the 3rd class. This book may help you Modern Cryptography and Elliptic Curves: A Beginner's Guide on your journey. Also, you may fallow some youtube lectures about ECC. $\endgroup$ – kelalaka Aug 10 at 14:34
  • 1
    $\begingroup$ Thanks @kelalaka, I've so far been reading the Springer undergrad Rational Points on Elliptic Curves to get a better understanding of the theory; is your recommendation more grounded in applications? (If so, that's great!) $\endgroup$ – QuartzCrystal Aug 10 at 14:57
  • 1
    $\begingroup$ It is a general book on the Elliptic Curves. In Elliptic Curve Cryptography (ECC), we use special cases where the EC is defined over finite fields. If you are interested in only understanding the ECC, you might look at my recommendation. It might better suits you. $\endgroup$ – kelalaka Aug 10 at 15:03
17
$\begingroup$

How is the set of discrete points on elliptic curves determined for ECC applications?

One common method to define a point on an elliptic curve over a suitable finite field $(\Bbb F,+,\cdot)$ is that such point is one of

  • any pair of coordinates $(x,y)$ with $x$ and $y$ elements of the field that obey an equation $y^2\,=\,x^3+a\cdot x+b$, where $a$ and $b$ are suitable constant elements of the finite field;
  • an extra point called the point at infinity, noted $\infty$ (or $\mathcal O\,$), often assimilated to $(0,0)$, where $0$ is the additive neutral for the field and $b\ne0$.

That defines a finite (discrete) set: in principle, we can enumerate all the $(x,y)$ (say, with two nested loops) and for each pair test if the equation is met; then throw in the extra $\infty$. That form $(x,y)$ is a standard discrete expression of a point on the curve: Cartesian coordinates.

We can define a binary law on the curve, using the same equations¹ as for a continuous elliptic curve group law, only operating in the finite field. We'll note that new law $\boxplus$ (in order to distinguish it from the addition $+$ in the field, though $+$ is often used for both laws), such that for all points $U$, $V$, $W$ on the curve (including $\infty\,$)

  • $U\boxplus V$ is a well-defined point on the curve.
  • $(U\boxplus V)\boxplus W\,=\,U\boxplus(V\boxplus W)$ (that is: $\boxplus$ is associative).
  • $U\boxplus V\,=\,V\boxplus U$ (that is: $\boxplus$ is commutative).
  • $U\boxplus\infty\,=\,U$ (that is: $\infty$ is neutral for $\boxplus\,$).
  • There exists a point $I$ on the curve with $U+I\,=\,\infty$. That $I$ is uniquely defined, and can be noted $\boxminus U$ (that is: the inverse of $U$ is $\boxminus U\,$). $U\boxplus\,\boxminus U\,=\,\infty$ becomes $U\boxminus U\,=\,\infty$. When $U\ne\infty$, $U$ is $(x,y)$ with $x$ and $y$ in the field and meeting the curve's equation $y^2\,=\,x^3+a\cdot x+b$, and $\boxminus U$ is $(x,-y$), also meeting the curve's equation since $(-y)^2\,=\,y^2\,$. If holds $\boxminus\infty\,=\,\infty$. Thus when $\infty$ is noted $(0,0)$, it holds $\boxminus(x,y)\,=\,(x,-y)$ for all $(x,y)$ of the curve.

In the above construction, we "discretized" a continuous elliptic curve and it's addition operation $\boxplus$ by

  • changing from an infinite field to a finite field;
  • keeping the curve's equation and the addition formula.

We can define² multiplication of an integer $k$ and a point $U$ of the curve, by using repeated addition: $$k\times U\,\underset{\text{def}}=\;\begin{cases} \infty&\text{if }k=0\\ ((k-1)\times U)\boxplus U&\text{if }k>0\\ (-k)\times(\boxminus U)&\text{if }k<0 \end{cases}$$ It follows $0\times U\,=\,\infty\,$, $1\times U\,=\,U\,$, $2\times U\,=\,U\boxplus U\,$, $-1\times U\,=\,\boxminus U\,$.

It can be shown that there exists a point $G$ such that the set of all $m$ points $U$ on the curve is precisely the set of $U=k\times G$ for $k$ from $0$ to $m-1$. And when we take any point $G$ of the curve, the set of all $k\times G$ forms a group of $n$ distinct elements of the curve under the law $\boxplus$, with $n$ dividing $m$. In cryptography, we typically arrange things so that $n$ is prime, either because $m$ is prime and $n=m$ (the whole curve is used), or by choosing an appropriate $G$ of prime order $n$ (the group is a subgroup of the whole curve).

The construction as $U=k\times G$ with $k$ from $0$ to $n-1$ is another (discrete) way to express a point of the elliptic curve (sub)group, and the one used to construct a public key $U$ from a private key $k$. However, $U$ is not made public in this form, for that would reveal the private key. $U$ can be revealed as a pair $(x,y)$.

There are other common (discrete) ways to express a point of the elliptic curve. In particular, when the field is $\Bbb F_p$ (the integers modulo prime $p\,$), any point $U$ other than $\infty$ can be expressed as $x$ and the parity of $y$ (in this construction, not all $x$ yield a valid point).

Another common way is as a triplet $(x,y,z)$ of elements of the field with $z\ne0$ and $y^2\cdot z=x^3+a\cdot x\cdot z^2+b\cdot z^3$, which makes the evaluation of $\boxplus$ simpler. We can get back to the curve in Cartesian coordinates by projecting to $(x/z,\,y/z)$ when desired.


¹ These equations are: $$U\boxplus V\underset{\text{def}}=\,\begin{cases} U&\text{if }V=\infty\\ V&\text{if }U=\infty\\ \infty&\text{if }(x_U,y_U)=(x_V,-y_V)\\ \big(\lambda^2-x_U-x_V,\lambda\cdot(2\cdot x_U+x_V-\lambda^2)-y_U\big)&\text{otherwise} \end{cases}$$ with in the otherwise case $$\lambda\,\underset{\text{def}}=\;\begin{cases} (3\cdot {x_U}^2+a)/(2\cdot y_U)&\text{if }U=V\\ (y_V-y_U)/(x_V-x_U)&\text{otherwise} \end{cases}$$ Note: $/$ is division in the finite field, such that for all $r$ and $s$ in the finite field with $s\ne 0$, it holds $(r/s)\cdot s=1$. Here $1$ is the multiplicative neutral for the field; $2$ is $1+1\,$; and $3$ is $2+1\,$. When the field is the integers modulo prime $p$, the quantity $r/s$ can be computed as r*pow(s,-1,p)%p in Python starting with version 3.8 ( r*pow(s,p-2,p)%p works in more versions).


² This definition involves a number of field operations linear with $k$. For efficiency, an implementation can use $$k\times U\,=\;\begin{cases} \infty&\text{if }k=0\\ (-k)\times(\boxminus U)&\text{if }k<0\\ U&\text{if }k=1\\ ((k/2)\times U)\boxplus((k/2)\times U)&\text{if }k>1\text{ and }k\text{ is even}\\ ((k-1)\times U)\boxplus U&\text{if }k>1\text{ and }k\text{ is odd} \end{cases}$$

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I rather find the boxed operations too much messing around, maybe more beginners. Instead, usually, it is preferred like; let the capital letters denote the points on the curve as $P,Q,R$ and addition of the points defined as $P+Q = ...$. Similar to the scalar multiplication $[k]P =..$. Of course, we have seen many confuse this, too. And, we should recommend a book for the OP depending on their background. $\endgroup$ – kelalaka Aug 10 at 14:28
  • 6
    $\begingroup$ @kelalaka: I find it essential to understand the distinction between addition in the field $+$ and addition in the curve $\boxplus$. Same for multiplication in the field $\,\cdot\,$ with scalar multiplication $\times$. Hence the idea of using different notations in this answer to a newcomer's question. $\endgroup$ – fgrieu Aug 10 at 14:51
  • 3
    $\begingroup$ @kelalaka: Well, $\times$ is already quite distinct from $\,\cdot\,$ so I see less incentive to invent a notation, and rather I stick to $\times$, which I think is quite common for scalar multiplication. $\endgroup$ – fgrieu Aug 10 at 15:22
  • 3
    $\begingroup$ @Glenn Willen: I added the formulas defining $\boxplus$. I would not call them simple! The rule "To add two points, draw a line through them" works to establish these formulas when the field is $\Bbb R$, but is much less natural/useful in a general finite field. $\endgroup$ – fgrieu Aug 11 at 8:17
  • 1
    $\begingroup$ @Vivekanand V: I've moved some of our comments related to C implementation into this chatroom, for comments are not for extended discussion. $\endgroup$ – fgrieu Aug 29 at 16:59
11
$\begingroup$

The points on an elliptic curve are not discretized, they're discrete by definition.

An elliptic curve is the set of $(x,y)$ such that $y \odot y = (x \odot x \odot x) \oplus (a \odot x) \oplus b$, where $\oplus$ is something we consider to be “addition” and $\odot$ is something we consider “multiplication”, and $a$ and $b$ are two constants. You can write this equation in any algebraic structure where addition ($\oplus$) and multiplication ($\odot$) are defined, not just in the real numbers. It's customary to use the usual operators $+$ and $\cdot$ (which is often omitted) except in contexts where multiple operations are defined that could be considered addition or multiplication on the same objects, but in this answer, I'll use different notations ($\oplus$ for addition, $\odot$ for multiplication) to avoid confusion.

For cryptography, we consider this equation in a finite field $F$. (Actually a finite field plus a point at infinity but it's too early to get into this.) A field is, roughly speaking, an algebraic structure where addition, multiplication and division behave like we're used to. In this context, “finite” means just that: there are only finitely many distinct elements in the field (unlike, for example, the rationals or the reals, which are infinite fields). No real numbers are involved at all. We just write the equation between elements of $F$.

The parameters $a$ and $b$ are elements of the finite field, not real numbers. They're usually written as integers, because every field more or less contains a “primary” copy of the integers. Identify the integer $0$ with the field's neutral element for addition $\mathbf{0}$. Identify the integer $1$ with the field's neutral element for multiplication $\mathbf{1}$. Identify $2$ with $\mathbf{1} \oplus \mathbf{1}$, etc. Identify $-1$ with the additive inverse of $\mathbf{1}$ (which I'll write $\mathbf{\bar1}$), etc. So when we write an equation like $y^2 = x^3 - x + 2$, we really mean $y \odot y = (x \odot x \odot x) \oplus (\mathbf{\bar1} \odot x) \oplus (\mathbf{1} \oplus \mathbf{1})$.

In the real numbers, equations like $y^2 = x^3 + a x + b$ have been well-understood for centuries. We know how many solutions they have depending on properties of $a$ and $b$. We know how to calculate approximate values of the solutions. But in other fields, while you can write exactly the same equation if $a$ and $b$ are integers (or more precisely, use the corresponding field elements), the set of solutions may be completely different. Knowing how to solve algebraic equations in one field doesn't necessarily prepare you to solve the same equation (or more precisely, the corresponding equation).

To illustrate this, let us consider a much simpler algebraic equation: $\mathbf{1} \oplus \mathbf{1} = \mathbf{0}$. There aren't even any variables, so the only question is whether this is true or not. In the real numbers, this is obviously false. But there are fields where this is true! For example, take $F_2 = \{\mathbf0, \mathbf1\}$, the smallest possible field, with just two elements: the neutral element for addition (“zero”) $\mathbf0$, and the neutral element for multiplication (“one”) $\mathbf1$. There's only one way to make this a field: $\mathbf{1} \oplus \mathbf{1} = \mathbf{0}$. The smallest $n \gt 0$ such that adding $\mathbf1$ to itself $n$ times yields the value $\mathbf0$ is called the characteristic of the field. For the real numbers (and the rationals, and the complex numbers, and many other fields), there is no such $n$ (these fields are said to have characteristic 0). Any finite field has a finite characteristic (which is always a prime number).

You don't need to know much algebra to understand how elliptic curve cryptography works. What you do need is a bit of “sophistication”: you need to get used to the appropriate level of abstraction. You already know about the algebraic structure (fields that aren't number fields), but you're having trouble because you haven't really internalized it. I recommend an undergraduate algebra textbook, specifically chapters on algebraic structures (setoids, groups, rings, fields). Not so much for the knowledge, but for getting used to the algebraic manipulations. Your objective is to read mathematical texts that use notations like $+$, $42$, $x^3$, etc., and have an easy time understanding what mathematical object they represent.

Coming from a programming background, think of mathematical notation as using a large amount of overloading. You need to figure out how this overloading is resolved.

| improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ Bravo for "not discretized", and defining $2$. I borrowed some of that in my answer. Nitpick: "we consider this equation $y \odot y = (x \odot x \odot x) \oplus (a \odot x) \oplus b$ in a finite field plus a point at infinity": no, the point at infinity can't be any of the $x$ and $y$ of the curve's equation. The point at infinity is an extra curve point, not an extra field member. $\endgroup$ – fgrieu Aug 11 at 9:12
5
$\begingroup$

At the risk of talking like an actual mathematician, I'd like to try to clarify the matter of "infinity" here. If for fixed $a$ and $b$ (with $b \ne 0$), we look at solutions to $$ y^2\,=\,x^3+a\cdot x+b $$ they're in 1-to-1 correspondence with solutions to $$ ty^2\,=\,x^3+a\cdot xt^2+bt^3 $$ where $t = 1$, i.e., if $(x,y)$ is a solution to the first equation, then $(x, y, t)$ is a solution to the second, and vice versa. If we remove the restriction that $t$ be $1$, then each solution $(x, y)$ to the first equation corresponds to a family $$ \{ (ax, ay, a) \mid a \in \Bbb F \} $$ of solutions to the second equation, where $a$ ranges over the field in question.

This correspondence is not quite 1-to-1. Suppose some family $Q$ contains a triple $(x, y, 0)$ whose last element is $0$. Then we must have ( by the second equation) that $$ 0\cdot y^2 = x^3 + a \cdot x \cdot 0 + b \cdot 0^2 $$ i.e. that $x = 0$. So such a family must actually consist exactly of all multiples of $(0,1,0)$.

This family doesn't arise from any solution to the first equation.

For any other family, if you pick an element $(u,v,w)$, it's in the same family as $(u/w, v/w, 1)$, and so $(x, y) = (u/w, v/w)$ is a solution to the first equation. But if you try to do this with $(u, v, w) = (0, 1, 0)$, you end up dividing by $0$. On the other hand, if you do it with $(0, 1, s)$ for some very small $s$ (I'm thinking of the real numbers for now), then you end up with $(0, 1/s)$, i.e., something whose $y$-coordinate is huge. As $s \to 0$, the $y$-coordinate gets bigger and bigger. So it's tempting to call this additional solution to the "homogenized equation" a "point at infinity". (The second version of the equation is called "homogenized" because all terms of the equation have the same total degree, namely $3$).

The "families" I've described basically consist of lines through the origin in $\Bbb F^3$, and the space of all such lines is the "natural" context in which to study elliptic curves (in the sense that doing so avoids lots of case-analysis).

Apologies for the long ramble, but I figured it was better than nothing.

| improve this answer | |
$\endgroup$
  • $\begingroup$ What you called $t$ is often called $z$, right? $\endgroup$ – Aman Grewal Aug 29 at 17:28
  • 1
    $\begingroup$ It is indeed sometimes called $z$ (as a "natural" third coordinate following $x$ and $y$ alphabetically). And that also emphasizes that post-homogenization, all three variable share equal pride of place. But since I'm mostly talking about the process of homogenization, I wanted an obviously distinct name for the thing I was introducing. My second-to-last paragraph tries (badly) to make the point that post-homogenization, all three variables have equal standing. $\endgroup$ – John Aug 29 at 18:27

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.