The following applet draws the Elliptic Curve `y ^{2} = x^{3} + ax + b`, with the ability to control the
coefficients

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 ^{3} + ax + b = 0`. Calculating the roots of this equation is discussed at
Solving the cubic equation.

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:

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

$$\begin{align} P_y &= \lambda P_x + c \\ \text{So:} \quad c &= P_y - \lambda P_x \end{align}$$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:

$$ \lambda = \begin{cases} \dfrac{Q_y-P_y}{Q_x-P_x} \quad \text{if } P \neq Q \\ \quad \\ \dfrac{3 P_x^2+a}{2 P_y} \quad \text{if } P=Q \quad \textit{i.e.} \text{, when the line is the tangent at } P \end{cases} $$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:

$$\begin{align} y &= \lambda x + c \\ y^2 &= x^3 + a x + b \end{align}$$Squaring the first expression for $y$ and equating it to the second gives:

$$\begin{align} \lambda^2 x^2 +2 \lambda c x +c^2 = x^3 + a x + b \end{align}$$This can be rearranged as:

$$\begin{align} x^3 + a x + b - (\lambda^2 x^2 +2 \lambda c x +c^2) = 0 \\ x^3 - \lambda^2 x^2 + (a - 2 \lambda c) x + b - c^2 = 0 \end{align}$$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:

$$\begin{align} x^3 - \lambda^2 x^2 + (a - 2 \lambda c) x + b - c^2 &= (x-P_x)(x-Q_x)(x-R_x) \\&= x^3 - (P_x +Q_x +R_x)x^2 + (P_x Q_x + Q_x R_x + R_x P_x)x - P_x Q_x R_x \end{align}$$Comparing the coefficients of $x^2$ we see that: $$ \lambda^2 = P_x + Q_x + R_x $$

from which:

$$ R_x = \lambda^2 - P_x - Q_x $$Since $R$ is on the line, then:

$$\begin{align} R_y &= \lambda R_x + c \\ &= \lambda R_x + P_y - \lambda P_x \\ &= P_y + \lambda (R_x - P_x) \end{align}$$The point-addition rule actually requires the coordinates of $\tilde{R}$, the reflection of $R$ in the $x$-axis, whose coordinates are therefore:

$$ \boxed{\begin{align}\tilde{R_x} &= \lambda^2 - P_x - Q_x \\ \tilde{R_y} &= \lambda (P_x - R_x) - P_y \end{align}} $$This is the same rule for both point-addition and point-doubling. The difference lies only in the definition of $\lambda$.

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 (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

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^{11} + 2^{9} + 2^{2}, or 1010 0000 0100 in binary notation.

This *could* be obtained graphically by separately generating the points 2^{9}P
and 2^{2}P by point-doubling, adding them together, then generating 2^{11}P,
and finally adding this to the point previously generated (2^{9}P + 2^{2}P).
But this is quite messy, as it needs an intermediate result to be saved, and duplicates calculation as 2^{9}
gets recalculated on the way to calculating 2^{11}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^{160} (about 1.5×10^{48}). 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^{16} operations per second would require 8.8×10^{31} seconds,
or about 2.8×10^{24} years, to perform the decryption by brute force.
By comparison, the age of the Universe is now believed to be about 1.4×10^{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.)

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 ^{3} + ax + b`
points in the prime finite field also have two

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!!)

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.

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 ^{2} = x^{3} + 7` with a specific prime modulus of

Copyright © Peter Havercan, 2015. An Elliptic Curve visualisation tool by Peter Havercan is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.