I understand modular arithmetic(or at least I think I do!) and I've tried to read and learn about how the Math in RSA works(and I think it went pretty well). I've been reading up on ECC and it looks very interesting and I tried solving a few basic math problems that involve ECC. I understand the basics, now I'm trying to understand it on a deeper level.

I find it easier to learn where I have analogies so my understanding stands as follows at this point — ECC is not a cryptosystem as such, it is a technique, much similar to the concept of using primes in RSA. Using ECC, encryption algorithms such as El-Gamal and signing algorithms such as ECDSA can be implemented.

I understand the properties about what a group, field are : However I see this statement in quite a few places. My doubts are as follows:

  • What does it mean to say “E is an elliptic curve over $\mathbb{F}_p$, where $p$ is prime"?
  • Does the cardinality of a curve mean the number of primes that are on a curve?
  • How does real-world ECC encryption work? In a problem I had tried solving, the message was denoted as a point on the curve. However, I imagine that its infeasible/impractical to always be able to denote messages as a point on the curve.
  • Any additional reading resource suggestions would be awesome!

When an elliptic curve is said to be "over a field $K$", we mean that the curve is the set of "points" $(x,y)$, where both $x$ and $y$ are elements of $K$, such that the curve equation is fulfilled. The curve equation may have various representation, but a typical one is $y^2 = x^3 + ax + b$ for two constants $a$ and $b$ which are also elements of $K$. An additional formal point, the "point at infinity" (denoted $\mathcal{O}$), which has no $x$ and $y$ coordinates, is also part of the curve.

In cryptography we are mostly interested in finite fields. A finite field is traditionally denoted $\mathbb{F}_q$ for some integer $q$, which is the size (cardinality) of the field; it so happens that when two finite fields have the same number of elements, they are isomorphic to each other, which more or less means that they have the same structure; morally, both are "the same" field, which is why we can afford to say "the field $\mathbb{F}_q$. There exists a finite field $\mathbb{F}_q$ if and only if $q = p^f$ for a prime $p$ and an integer $f\geq 1$. When $f = 1$, i.e. the field cardinality is a prime integer $p$, then the field $\mathbb{F}_p$ is (isomorphic to) the set of integers modulo $p$.

In a finite field $\mathbb{F}_q$, there are $q^2$ pairs $(x,y)$, so the curve cannot contain more than $q^2+1$ points (including the point at infinity), which means that the curve is also a finite set of points. The cardinality of the curve is its size: the number of points it contains (again, including the point at infinity). Actually, the curve cardinality is close to $q$: if we define $t$ such that the cardinality of the curve is equal to $q+1-t$, then it can be proven that $|t| \leq 2\sqrt{q}$ (that's Hasse's theorem).

Roughly speaking, for about half of the $q$ possible values $x$ in the field $\mathbb{F}_q$, there can exist a curve point $(x,y)$, and when there is one, there usually are two. The "two" and the "half" mostly cancel out, and you end up with about $q$ points on the curve.

For practical usage of elliptic curves, we use a conventional generator which is a point $G$ on the curve. That point has an order: the order $n$ of the point $G$ is the smallest integer $n \geq 1$ such that $nG = \mathcal{O}$. There are $n$ points $kG$, for all integers $k$ from $0$ to $n-1$, and these are, collectively, a subgroup of the curve. This implies that $n$ is a divisor of the curve cardinality. We usually look for curves and generators such that $n$ is a big enough prime; if possible, we arrange for the curve cardinality to be itself prime, and then $G$ generates the whole curve (in particular, any point on the curve, except $\mathcal{O}$, can be used as generator).

For real-world encryption on the curve, well, we do not really encrypt. We use Diffie-Hellman. The DH algorithm produces a shared secret value, which happens to be a curve point. The point selection is basically random, but a shared random value is good enough because it can be used as key (after a suitable hashing) for symmetric encryption. There is a name for that combination: ECIES. But some standards just do the DH and then use their own symmetric encryption system (typical of SSL/TLS with the "ECDHE" cipher suites).

ElGamal could also be used, but it would require mapping, in a reversible way, a "message" $m$ into a curve point. This would be interpreting the message as the coordinate $x$ (in $\mathbb{F}_q$) of a curve point, and computing a matching $y$. However, only about half of the $x$ values can be the first coordinate of a curve point, so some "variability" would be needed (some bits which can be adjusted until a possible $x$ is reached), or some other trick (e.g. not using one curve but two curves which complement each other). Since the size of the message $m$ would be severely limited (no bigger than $q$), this is hardly worthwhile, and nobody does that. People use Diffie-Hellman.

The guide to elliptic curve cryptography is a good reading for a practical view on how things are done. The chapter on finite fields can be downloaded for free, so I warmly encourage you to read it first.


Here is a partial answer:

  1. $\mathbb{F}_p$ is the finite field with $p$ elements (it is isomorphic with $\mathbb{Z}/p\mathbb{Z}$.

  2. You may think to an elliptic curve as the set of solutions in $\overline{\mathbb{F}_p}$ (the algebraic closure of $\mathbb{F}_p$) of the equation $f(x,y)=0$, where $f(x,y)=y^2-ax^3-b$ (with $a,b \in \mathbb{F}_p$ and $4a^3+27b^2\neq 0$.

  3. The cardinality of the curve refers to the number of solutions of the equation $f(x,y)=0$ which lie in $\mathbb{F}_p \times \mathbb{F}_p$.

For further reading you may found all of this and much more, for example in the Handbook of Elliptic and Hyperelliptic Curve Cryptography.


Your Answer
