Elliptic Curve Point Arithmetic and Validation

Elliptic curve cryptography replaces the multiplicative group of a finite field with the group of points on a curve over that field. The security assumption is the same — the discrete logarithm is hard — but the group is different, and the different structure buys a much shorter key for the same security. What follows is the arithmetic that makes the group work, and the validation that keeps a hostile peer from using malformed points against it.

The group law on a short Weierstrass curve

Over a prime field $\mathbb{F}_p$ with $p > 3$, a short Weierstrass curve is the set of solutions to

$$y^2 = x^3 + ax + b \pmod p$$

together with a point at infinity $\mathcal{O}$ that acts as the identity. The curve must be nonsingular: $4a^3 + 27b^2 \not\equiv 0 \pmod p$, otherwise it degenerates into a curve with a cusp or a node and the group law fails to be a group.

Addition is defined geometrically. For two distinct points $P = (x_1, y_1)$ and $Q = (x_2, y_2)$ with $x_1 \ne x_2$, the line through them meets the curve at a third point, and its reflection in the x-axis is $P + Q$. Algebraically, with slope $\lambda = (y_2 - y_1)/(x_2 - x_1)$:

$$x_3 = \lambda^2 - x_1 - x_2, \qquad y_3 = \lambda(x_1 - x_3) - y_1$$

Doubling is the limiting case where $Q \to P$: the line becomes the tangent, and the slope is $\lambda = (3x_1^2 + a)/(2y_1)$. Negation is reflection: $-P = (x_1, -y_1 \bmod p)$. The identity is the point at infinity, and $P + (-P) = \mathcal{O}$.

The inversions are the expensive part. A field inversion costs a full exponentiation by $p - 2$ by Fermat’s little theorem, hundreds of multiplications, where a field multiplication costs one. Projective coordinates remove the inversions from the inner loop by representing a point as $(X : Y : Z)$ with $x = X/Z$ and $y = Y/Z$; the group law becomes a sequence of multiplications with a single inversion at the end to convert back. For a scalar multiplication with hundreds of steps, that converts hundreds of inversions into one.

def point_add(P, Q, a, p):
    if P is None: return Q
    if Q is None: return P
    x1, y1 = P; x2, y2 = Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return None                     # P + (-P) = identity, including order-two doubling
    if P == Q:
        lam = (3*x1*x1 + a) * pow(2*y1, -1, p) % p
    else:
        lam = (y2 - y1) * pow(x2 - x1, -1, p) % p
    x3 = (lam*lam - x1 - x2) % p
    y3 = (lam*(x1 - x3) - y1) % p
    return (x3, y3)

This version is correct and unusable: pow(..., -1, p) performs the inversion on every call, and the branches on point equality depend on secret data when the inputs are secret. It is the reference for the algebra, not for an implementation.

Scalar multiplication and the ladder

A scalar multiplication $kP$ uses the same double-and-add structure as modular exponentiation, because the group operation is written additively. The naive loop doubles the accumulator and adds $P$ when the bit of $k$ is set. It leaks the Hamming weight of $k$ through timing and through the sequence of group operations, and it is the elliptic curve analogue of the branch that Kocher’s attack exploited.

The Montgomery ladder fixes this. At each bit it computes both $R_0 + R_1$ and $2R_0$ or $2R_1$, and selects between the results based on the bit without branching. The number of operations is fixed at one addition and one doubling per bit regardless of the bit value, so the timing is independent of the scalar. The ladder requires a differential addition formula, which computes $P + Q$ given $P$, $Q$, and $P - Q$; that is what makes the constant-time selection possible, because the difference is maintained as an invariant across the loop.

The ladder is defined for Montgomery-form curves, $By^2 = x^3 + Ax^2 + x$, which is why X25519 is specified on such a curve. The x-coordinate-only arithmetic of the Montgomery form means the ladder never needs the y-coordinate, and the differential addition works entirely in x. On short Weierstrass curves the equivalent is a fixed-window or a signed-digit recoding with masked selection; the structure differs but the goal is the same.

The cost is one addition plus one doubling per bit, so a 255-bit scalar multiplication is about 510 group operations. Each group operation in projective coordinates is on the order of ten field multiplications, so the total is a few thousand field multiplications over a 255-bit field — roughly an order of magnitude fewer limb operations than a 2048-bit modular exponentiation. That is the arithmetic source of the key-size advantage, quantified in Key Size Equivalence Across RSA, Diffie-Hellman, and Curves.

Point validation: what a hostile peer can send

A protocol that receives a point from the network must decide what to do with it before performing any secret operation. The failures divide into three groups.

Not on the curve. A point $(x, y)$ that does not satisfy the curve equation is not a group element, and arithmetic on it produces results outside the group. Some implementations compute the curve equation check with the same arithmetic path used for the operation and skip the check for speed. That is a defect: the check is one field squaring and one multiplication, and its absence has broken real implementations.

On the curve, wrong subgroup. As with finite-field Diffie-Hellman, a curve group can have order $n = h \cdot q$ with a small cofactor $h$. A point of small order lies on the curve and satisfies the equation but generates a tiny subgroup. Sending such a point to a peer that multiplies by its secret confines the result to that subgroup, and repeated queries with different small-order points recover the secret by CRT. The defence is to multiply the received point by $h$ and reject the identity, or to check that $qP = \mathcal{O}$.

The point at infinity and degenerate coordinates. The identity is a valid group element but never a valid public key, since it carries no information and produces a shared secret of $\mathcal{O}$. Coordinates outside $[0, p-1]$ are likewise invalid and must be rejected rather than reduced, because reduction maps distinct encodings onto the same point and enables signature malleability.

def validate(P, a, b, p, q, h):
    if P is None:
        raise ValueError("identity is not a public key")
    x, y = P
    if not (0 <= x < p and 0 <= y < p):
        raise ValueError("coordinate out of range")
    if (y*y - (x*x*x + a*x + b)) % p != 0:
        raise ValueError("point not on curve")
    if h != 1 and scalar_mul(h, P, a, p) is None:
        raise ValueError("point in small subgroup")
    return P

For curves with cofactor 1 — the NIST prime curves among them — the subgroup check is unnecessary because the whole group has prime order. For Curve25519 the cofactor is 8, and the standard defence is different: X25519 is defined so that the scalar is clamped, forced to a multiple of the cofactor, which projects any input into the prime-order subgroup automatically. Clamping is why X25519 implementations do not perform an explicit subgroup check, and why they must clamp rather than accept an arbitrary scalar.

Complete formulas and the exceptional cases

The addition law above has exceptional inputs: $P = Q$ requires the doubling formula, and $P = -Q$ produces the identity through a division by zero. A branch on those cases is both a correctness hazard and a timing leak, since the branch is taken based on whether the inputs are equal, and in a scalar multiplication the inputs are secret-dependent.

Complete formulas eliminate the exceptions. The unified formulas of Brier and Joye, and the complete formulas for prime-order curves, compute the correct result for all input pairs including the identity and the doubling case, using a fixed sequence of field operations. The cost is a handful of extra multiplications per addition. For a protocol that performs thousands of additions per operation, that is a few percent, and it removes an entire class of bugs: the exceptional case that an implementation forgot to handle.

Twisted Edwards curves, of the form $-x^2 + y^2 = 1 + dx^2y^2$, admit particularly efficient complete formulas, and their addition law is unified by construction. Ed25519 uses such a curve, and the choice is partly about this: the addition formula is complete, so there is no exceptional case to branch on, and the implementation can be both simpler and constant-time.

Choosing a curve is choosing a group order

The group law is efficient, but the security of a specific curve depends on its order. A curve whose order is smooth is broken by Pohlig-Hellman regardless of its field size, for the same reason a smooth-order finite-field group is broken; the analysis is in Discrete Logarithms and Why Group Order Decides Their Difficulty. The order must have a large prime factor, and the curve must not be one of the special classes — anomalous, supersingular, or pairing-friendly — for which faster algorithms exist.

Generating a curve and then verifying that it has no such weakness is the subject of curve generation standards. The alternative, deriving the curve from a nothing-up-my-sleeve seed so that the parameters cannot hide a trapdoor, is what Curve25519 does. The trust model differs: a standardised curve with a published seed can be verified by anyone, but only if they bother to run the verification.