Let $E:y^2\equiv x^3+bx+c(\mathrm{m}\mathrm{o}\mathrm{d}p)$ be an elliptic curve, where $p\ge 5$ is prime. We can list the points on $E$ by letting $x=0\text{,}1\text{,}\dots \text{,}p-1$ and seeing when $x^3+bx+c$ is a square mod $p\text{.}$ Since half of the nonzero numbers are squares mod $p\text{,}$ we expect that $x^3+bx+c$ will be a square approximately half the time. When it is a nonzero square, there are two square roots: $y$ and $-y\text{.}$ Therefore, approximately half the time we get two values of $y$ and half the time we get no $y\text{.}$ Therefore, we expect around $p$ points. Including the point $\text{∞}\text{,}$ we expect a total of approximately $p+1$ points. In the 1930s, H. Hasse made this estimate more precise.

Recall the classical discrete logarithm problem: We know that $x\equiv g^k(\mathrm{m}\mathrm{o}\mathrm{d}p)$ for some $k\text{,}$ and we want to find $k\text{.}$ There is an elliptic curve version: Suppose we have points $A\text{,}B$ on an elliptic curve $E$ and we know that $B=kA(=A+A+\cdots +A)$ for some integer $k\text{.}$ We want to find $k\text{.}$ This might not look like a logarithm problem, but it is clearly the analog of the classical discrete logarithm problem. Therefore, it is called the discrete logarithm problem for elliptic curves.

There is no good general attack on the discrete logarithm problem for elliptic curves. There is an analog of the Pohlig-Hellman attack that works in some situations. Let $E$ be an elliptic curve mod a prime $p$ and let $n$ be the smallest integer such that $nA=\text{∞}\text{.}$ If $n$ has only small prime factors, then it is possible to calculate the discrete logarithm $k$ mod the prime powers dividing $n$ and then use the Chinese remainder theorem to find $k$ (see Exercise 25). The Pohlig-Hellman attack can be thwarted by choosing $E$ and $A$ so that $n$ has a large prime factor.

There is no replacement for the index calculus attack described in Section 10.2. This is because there is no good analog of “small.” You might try to use points with small coordinates in place of the “small primes,” but this doesn’t work. When you factor a number by dividing off the prime factors one by one, the quotients get smaller and smaller until you finish. On an elliptic curve, you could have a point with fairly small coordinates, subtract off a small point, and end up with a point with large coordinates (see Computer Problem 5). So there is no good way to know when you are making progress toward expressing a point in terms of the factor base of small points.

The Baby Step, Giant Step attack on discrete logarithms works for elliptic curves (Exercise 13(b)), although it requires too much memory to be practical in most situations. For other attacks, see [Blake et al.] and [Washington].

In most cryptographic systems, we must have a method for mapping our original message into a numerical value upon which we can perform mathematical operations. In order to use elliptic curves, we need a method for mapping a message onto a point on an elliptic curve. Elliptic curve cryptosystems then use elliptic curve operations on that point to yield a new point that will serve as the ciphertext.

The problem of encoding plaintext messages as points on an elliptic curve is not as simple as it was in the conventional case. In particular, there is no known polynomial time, deterministic algorithm for writing down points on an arbitrary elliptic curve $E(\mathrm{m}\mathrm{o}\mathrm{d}p)\text{.}$ However, there are fast probabilistic methods for finding points, and these can be used for encoding messages. These methods have the property that with small probability they will fail to produce a point. By appropriately choosing parameters, this probability can be made arbitrarily small, say on the order of $1/2^{30}\text{.}$

Here is one method, due to Koblitz. The idea is the following. Let $E:y^2\equiv x^3+bx+c(\mathrm{m}\mathrm{o}\mathrm{d}p)$ be the elliptic curve. The message $m$ (already represented as a number) will be embedded in the $x\text{-coordinate}$ of a point. However, the probability is only about 1/2 that $m^3+bm+c$ is a square mod $p\text{.}$ Therefore, we adjoin a few bits at the end of $m$ and adjust them until we get a number $x$ such that $x^3+bx+c$ is a square mod $p\text{.}$

More precisely, let $K$ be a large integer so that a failure rate of $1/2^K$ is acceptable when trying to encode a message as a point. Assume that $m$ satisfies $(m+1)K<p\text{.}$ The message $m$ will be represented by a number $x=mK+j\text{,}$ where $0\le j<K\text{.}$ For $j=0\text{,}1\text{,}\dots \text{,}K-1\text{,}$ compute $x^3+bx+c$ and try to calculate the square root of $x^3+bx+c(\mathrm{m}\mathrm{o}\mathrm{d}p)\text{.}$ For example, if $p\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}4)\text{,}$ the method of Section 3.9 can be used. If there is a square root $y\text{,}$ then we take $P_m=(x\text{,}y)\text{;}$ otherwise, we increment $j$ by one and try again with the new $x\text{.}$ We repeat this until either we find a square root or $j=K\text{.}$ If $j$ ever equals $K\text{,}$ then we fail to map a message to a point. Since $x^3+bx+c$ is a square approximately half of the time, we have about a $1/2^K$ chance of failure.

In order to recover the message from the point $P_m=(x\text{,}y)$ we simply calculate $m$ by

where $\lfloor x/K\rfloor$ denotes the greatest integer less than or equal to $x/K\text{.}$