Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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!
share|improve this question

migrated from security.stackexchange.com Aug 28 '13 at 6:56

This question came from our site for Information security professionals.

add comment

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.