# Finite fields and ECC

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.

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.

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.