An Elliptic Curve visualisation tool

The following applet draws the Elliptic Curve y² = x³ + ax + b, with the ability to control the coefficients a and b with sliders. (To execute the applet, it is necessary to set up Java security, as described in security setup.) To execute the applet as a local application, using Java Web Start, click here. The source of the applet is here.

I have also produced a tool to generate co-ordinates for an integer point-based elliptic curve, at Generate point-based elliptic curves.

The applet also give the ability to control the x-coordinates of two points P and Q on the curve, with the projected point R extended from PQ on to the curve and the reflection of R in the x-axis. This reflected point is the point P+Q, where + is the elliptic curve group property.

The shape of the elliptic curve can be altered by adjusting the sliders for the coefficients a and b.

The positions of P and Q can be chosen by adjusting the Px, Py, Qx, and Qy sliders. The positions are primarily determined by the Px and Qx values: the Py and Qy sliders just select whether the point is above or below the x-axis.

Pressing the Lock P & Q button makes P and Q coincide. In this case, the line PQ becomes the tangent at P, and the point P+Q becomes 2P, demonstrating scalar multiplication using the group property.

Additional points (beyond P+Q) can be added by sliding the horizontal slider n, which repeatedly adds the point P to the sum. If P and Q are unlocked, the generated points are thus P+Q, 2P+Q, 3P+Q, etc. If P and Q are locked together, the generated points are 2P, 3P, 4P, etc.

If the button Double Points is pressed, the generated points are not added to the sum. Instead, each new point is obtained by doubling the current point. That is, the new point is generated by adding the current point to itself. Geometrically, this is performed by projecting the tangent at the current point and reflecting the new point of intersection in the x-axis. If P and Q are unlocked, this produces the sequence P+Q, 2(P+Q), 4(P+Q), etc. If P and Q are locked, the sequence is 2P, 4P, 8P, 16P, etc. The doubling property allows high multiples of the initial point to be generated relatively inexpensively, while the inverse (finding the multiplier when only P and the final point are known) is very difficult. The difficulty of finding this inverse is the basis of Elliptic Curve Cryptography.

The points at which the elliptic curve crosses the x-axis are the roots of the cubic equation x³ + ax + b = 0. Calculating the roots of this equation is discussed at Solving the cubic equation.

Mathematical basis for point-addition

The two geometrical operations that can be performed on the curve are point-addition (connect, project, reflect), and point-doubling (draw tangent, project, reflect). Algebraically, point-addition is performed by calculating the point of intersection of the chord $PQ$ with the curve at $R$, and point-doubling is performed by calculating the point of intersection of the tangent at $P$ with the curve at $R$. If the coordinates of $P$, $Q$, $R$ are $(P_x,P_y), (Q_x,Q_y), (R_x,R_y)$, and the slope of the line $PQ$ is $\lambda$, then the equation of $PQ$ is:

where $y=c$ is the point at which the line crosses the $y$-axis. Since $P$ is on the line,

The slope of the elliptic curve itself can be obtained by differentiation. If $z = y^2 = x^3 +a x +b$ then $y = z^{(1/2)}$, so: $$\begin{align} \frac{dy}{dz} &= \frac{1}{2} z^{(-1/2)} = \frac{1}{2 \sqrt{z}}= \frac{1}{2 y} \\ \frac{dz}{dx} &= 3 x^2 + a \\ \frac{dy}{dx} &= \frac{dy}{dz} \cdot \frac{dz}{dx} = \frac{3 x^2 + a}{2 y} \quad \quad \text{by the chain rule} \end{align}$$

So we can also define $\lambda$ as follows:

As the line is projected to meet the elliptic curve at $R$, then $R$ is on both the line and the curve, so the following simultaneous equations are true:

Squaring the first expression for $y$ and equating it to the second gives:

This can be rearranged as:

This cubic equation in $x$ could be solved by the techniques in Solving the cubic equation, but that would be quite difficult as it requires complicated algebra using irrational functions like cube roots and cosines. But we do not have to solve the equation for all of its roots. We already have two of them, $P_x$ and $Q_x$, and only need to find $R_x$. The cubic expression can be factored in terms of its roots as:

Comparing the coefficients of $x^2$ we see that: $$ \lambda^2 = P_x + Q_x + R_x $$

from which:

Since $R$ is on the line, then:

The point-addition rule actually requires the coordinates of $\tilde{R}$, the reflection of $R$ in the $x$-axis, whose coordinates are therefore:

This is the same rule for both point-addition and point-doubling. The difference lies only in the definition of $\lambda$.

Elliptic curves over the rational numbers and integers

The formulae for calculating $\lambda$ and $\tilde{R}$ from $P$ and $Q$ involve only the rational operations of addition, subtraction, multiplication, and division. It follows that, if the coordinates of $P$ and $Q$ and the coefficients of the curve's equation are all rational, then the coordinates of $\tilde{R}$ also remain rational. So the + operation, and the scalar multiplication derived from it, preserve the rational nature of the points. Mathematically, the + operation is an abelian (commutative) group operation over $\mathbb{Q}$, the rational numbers.

Furthermore, if modular arithmetic relative to a prime modulus is used, the rational operators preserve integer coordinates and coefficients, so the + operation does so too. Mathematically, the + operation is an abelian group operation over $\mathbb{F}_m$, a prime finite field with modulus $m$. See Generate point-based elliptic curves for a tool that generates integer-valued coordinates over a prime finite field (also called a Galois field). This is the form of arithmetic used in elliptic curve cryptography.

Elliptic Curve Cryptography

Elliptic Curve Cryptography (ECC) – like many other forms of cryptography – depends on a mathematical computation that is easy in a forward direction, but extremely difficult in the reverse direction. See this tutorial for more detail.

In ECC, this computation is the scalar multiplication of a point over a prime finite field, $\mathbb{F}_m$. As in normal arithmetic, scalar multiplication is just a multiple repetition of the add operation, although in this case the add operation is the geometric point-addition described above. The basic idea is that the scalar multiplier (n), which transforms an initial point (P) into a final product point (nP), can be used as a secret key when both the final and initial points are known, because n cannot be easily deduced from the final point.

In asymmetric-key cryptography terms, n is the private key, and nP is the public key. For suitably large values of n, discovering n from nP is computationally infeasible, meaning it's very difficult and no-one knows how to do it. The applet shows how a scalar product can be achieved: scalar multiplication is just continued addition of a point to itself, so the simplest way to obtain the product is by just adding the same point to the emerging sum. But, at first sight, this does not seem to give the necessary difficulty in reversibility. If the product is generated by performing repeated additions, what prevents an attacker from performing those same additions until he reaches the final product that is being published as the public key?

It is the second mechanism demonstrated in the applet, point-doubling, that solves this problem. The 2^t P point can be reached in only t point-doublings.

But what happens if the multiplier n is not a power of two? Then we can use a combination of powers-of-two multipliers and simple additions. Computer programmers will recognise that this is the same combination that is used when representing numbers in binary. The binary representation of a number is nothing more than a simple sum of powers-of-two. For instance, the number 2564 is 2048+512+4, which is 2¹¹ + 2⁹ + 2², or 1010 0000 0100 in binary notation.

This could be obtained graphically by separately generating the points 2⁹P and 2²P by point-doubling, adding them together, then generating 2¹¹P, and finally adding this to the point previously generated (2⁹P + 2²P). But this is quite messy, as it needs an intermediate result to be saved, and duplicates calculation as 2⁹ gets recalculated on the way to calculating 2¹¹P.

Fortunately, there are several more compact and efficient ways of performing the point multiplication, based on a procedure known as double and add. In this procedure, the binary representation of the multiplier is scanned from left to right. When the first 1 bit is found, the product is set to the point P. As each subsequent bit is examined, the emerging product is doubled, and if the new bit is 1, the original point P is added in to the product.

Continuing the example of point multiplication by 2564 (binary 1010 0000 0100), we can see the sequence of operations:

Bit	Operation	Running Result
1	Set to P	P
0	Double	2P
1	Double and add P	5P
0	Double	10P
0	Double	20P
0	Double	40P
0	Double	80P
0	Double	160P
0	Double	320P
1	Double and add P	641P
0	Double	1282P
0	Double	2564P

In this example we can see that the final result is obtained with 11 point-doublings and 2 point-additions, which is much faster than the 2563 point-additions that would be needed to reverse-engineer the multiplier from the result. In a real-world cryptographic application the multiplier would be considerably higher, and probably at least 2¹⁶⁰ (about 1.5×10⁴⁸). Encryption using 160 point-doublings would only take a few microseconds on a tiny computer such as the Raspberry Pi, whereas a supercomputer such as the IBM Sequoia (BlueGene/Q) performing 1.7×10¹⁶ operations per second would require 8.8×10³¹ seconds, or about 2.8×10²⁴ years, to perform the decryption by brute force. By comparison, the age of the Universe is now believed to be about 1.4×10¹⁰ years. (These figures are extremely approximate: supercomputer speeds are measured in floating-point operations per second, but cryptographic calculations need fixed-point (integer) arithmetic. The point-addition and point-doubling calculations take more than one operation per calculation (about ten), and the large numbers required by cryptography cannot be handled by the regular hardware instructions. Software library functions to handle the arithmetic for very large numbers are needed, which slow down the calculations considerably.)

Coordinates of points for Elliptic Curve Cryptography

The coordinate points on the curves used in ECC are always expressed as binary integers, which are the same bit length as the prime modulus. In the document SEC2: Recommended Elliptic Curve Domain Parameters, curves are named by the bit lengths of their prime moduli, which are taken from the list 192, 224, 256, 384, or 521 bits, corresponding to 24, 28, 32, 48, and 65 bytes, respectively Just as the points on real-valued elliptic curves have two possible values of y for each x, which are the positive and negative square roots of x³ + ax + b points in the prime finite field also have two y values for each x. These complementary coordinates add up to the prime modulus p, so they are the analogues of positive and negative values.

Because the sum of the two y values is equal to the modulus, which is odd, one of the y-values is odd and the other is even. This allows the point to be expressed in compressed form, where the y value is reduced to a single bit, depending on whether it is odd or even. The rest of the y value can then be calculated from the x-coordinate by using the curve's equation. (Calculating a square root in modular arithmetic is a challenge, though.)

The identification of whether a point representation is compressed or not is identified in the first byte of the point's binary value. This byte is 04x if the point is uncompressed, 03x if the point is compressed and y is odd, and 02x if the point is compressed and y is even. (Check this!!)

Encrypting data with Elliptic Curve Cryptography

It would appear from the publicity surrounding ECC that it behaves like a complete cryptosystem that can be used for encrypting and decrypting data. However, it cannot be used (by itself) for bulk data encryption. The nearest that ECC comes to this is the Elliptic Curve Integrated Encryption Scheme (ECIES). This specifies a formal encryption scheme that uses ECC, but the heavy load of actually encrypting the data is performed by a symmetric encryption scheme such as Triple DES or AES. In ECIES, Elliptic Curve Cryptography is only used to generate and consume secure keys that can be used by the symmetric encryption algorithm.

Other uses of Elliptic Curve Cryptography

ECC can also be used in the Diffie-Hellman key exchange function, where it is known as the Elliptic Curve Diffie–Hellman Exchange (ECDHE), and in the digital signature algorithm, where it is known as the Elliptic Curve Digital Signature Algorithm (ECDSA).

Bitcoin, the digital currency, uses a very specific form of ECC using the specific elliptic curve secp256k1 to secure a blockchain, which is a continuously updated distributed ledger of all the currency exchange transactions. It uses the specific elliptic curve of y² = x³ + 7 with a specific prime modulus of 2²⁵⁶ − 2³² − 2⁹ − 2⁸ − 2⁷ − 2⁶ − 2⁴ − 1, along with a very specific initial point G, which is a long 256-bit binary number whose exact value need not concern us here.