Elliptic curve point arithmetic

How it works

An elliptic curve over a prime field $\mathbb{F}_p$ ($p > 3$) is the set of solutions of $y^2 = x^3 + ax + b$, together with a point at infinity $\mathcal{O}$, where the discriminant condition $4a^3 + 27b^2 \not\equiv 0 \pmod p$ rules out singular curves. The points form an abelian group with $\mathcal{O}$ as neutral element and $-(x, y) = (x, -y)$.

To add two points, draw the line through them; it meets the curve in a third point, and the sum is that point reflected in the $x$-axis. With the slope $\lambda = (y_2 - y_1)/(x_2 - x_1)$ (or $\lambda = (3x_1^2 + a)/(2y_1)$ for the tangent when doubling), the sum is $x_3 = \lambda^2 - x_1 - x_2$ and $y_3 = \lambda(x_1 - x_3) - y_1$. Over $\mathbb{F}_p$ every division is a multiplication by a modular inverse. A vertical line ($P + (-P)$, or doubling a point with $y = 0$) gives $\mathcal{O}$.

Scalar multiplication $kP$ uses double and add over the bits of $k$, the analogue of square and multiply. Going back from $kP$ to $k$ is the elliptic curve discrete logarithm problem, the basis of ECDH, ECDSA and EdDSA. On well chosen curves the best known attacks take about $\sqrt{n}$ steps for a group of order $n$, so a 256-bit curve gives about 128 bits of security.