Elliptic-Curve Scalar Multiplication

Intuition, Vocabulary and Foundations

Scalar multiplication computes $[k]P$ without adding $P$ exactly $k$ times. Like binary exponentiation, it doubles for each scalar bit and adds selected powers. On $E:y^2=x^3+2x+2\pmod{17}$, the point $P=(5,1)$ has order $19$, so $[19]P=\mathcal O$ and subgroup scalars may be reduced modulo $19$.

Affine formulas use field inversions. Projective coordinates represent the same point by a triple such as $(X:Y:Z)$ with $x=X/Z^2$ and $y=Y/Z^3$, replacing loop inversions with multiplications and one final inversion. Exceptional cases—identity, inverse pairs, and doubling a point with $y=0$—must be defined explicitly.

Scalar multiplication is binary exponentiation in an elliptic-curve group. Correctness begins before the bit loop: validate the curve, input point, infinity representation, subgroup assumption, and every exceptional addition case.

Concept	Example	Boundary	Question answered
Infinity	$\mathcal O$ is identity and $[0]P=\mathcal O$	A sentinel must never enter coordinate arithmetic	How is the identity represented?
Inverse	$-(x,y)=(x,-y\bmod p)$	Negating both coordinates is wrong	What happens for opposite points?
Doubling	Slope $(3x^2+a)/(2y)$ when $y\ne0$	If $y=0$, doubling returns infinity	Which exceptional case replaces division?
Projective point	$(X:Y:Z)$ encodes $(X/Z^2,Y/Z^3)$	Multiple triples encode one affine point	How are inversions avoided?
Subgroup order	For $P=(5,1)$, $[19]P=\mathcal O$	Reducing by an unverified number changes meaning	When may a scalar be reduced?
Scalar bits	$13=(1101)_2$	Wrong bit order violates the invariant	Which group operations are required?

Step-by-Step Derivations and Algorithms

Left-to-right double-and-add maintains $R=[v]P$ for the processed bit prefix $v$. Reading bit $b$ changes the prefix to $2v+b$, so double $R$ and add $P$ only when $b=1$.

A width-$w$ method precomputes $[0]P$ through $[2^w-1]P$ and processes base-$2^w$ digits, trading memory for fewer online additions. The ladder maintains adjacent multiples $R_0=[v]P$ and $R_1=[v+1]P$. Each bit performs one addition and one doubling, updating to adjacent multiples for prefix $2v+b$.

Elliptic-Curve Scalar Multiplication algorithm map

flowchart TD
    A[Validate curve, point, and subgroup] --> B[Normalize sign and scalar]
    B --> C{Strategy}
    C -->|Double-and-add| D[Double and conditionally add]
    C -->|Window| E[Precompute table and process digits]
    C -->|Ladder| F[Maintain adjacent multiples]
    D --> G[Verify result on curve]
    E --> G
    F --> G

Double-and-add preserves $R=[v]P$, the ladder preserves $R_0=[v]P$ and $R_1=[v+1]P$, and a window method preserves the processed base-$2^w$ prefix. Each needs $O(\log k)$ group operations; a width-$w$ table stores $O(2^w)$ points, while projective formulas defer inversion until the end.

Implementation, Complexity and Engineering

The reference uses affine coordinates for auditability. It rejects singular curves and off-curve points, handles infinity and vertical lines, supports negative scalars, and reduces modulo a supplied subgroup order only after verifying $[r]P=\mathcal O$. The ladder's regular operation count is educational structure, not a constant-time guarantee in Python.

from math import isqrt


INFINITY = None


def is_prime(n):
    if not isinstance(n, int) or isinstance(n, bool) or n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    d = 3
    while d <= isqrt(n):
        if n % d == 0:
            return False
        d += 2
    return True


class Curve:
    def __init__(self, p, a, b):
        if not is_prime(p):
            raise ValueError("p must be prime")
        self.p, self.a, self.b = p, a % p, b % p
        if (4 * self.a**3 + 27 * self.b**2) % p == 0:
            raise ValueError("curve must be nonsingular")

    def on_curve(self, point):
        if point is INFINITY:
            return True
        if not isinstance(point, tuple) or len(point) != 2:
            return False
        x, y = point
        return (0 <= x < self.p and 0 <= y < self.p and
                (y * y - x**3 - self.a * x - self.b) % self.p == 0)

    def require(self, point):
        if not self.on_curve(point):
            raise ValueError("point is not canonical and on curve")

    def negate(self, point):
        self.require(point)
        return INFINITY if point is INFINITY else (point[0], -point[1] % self.p)

    def add(self, left, right):
        self.require(left)
        self.require(right)
        if left is INFINITY:
            return right
        if right is INFINITY:
            return left
        x1, y1 = left
        x2, y2 = right
        if x1 == x2 and (y1 + y2) % self.p == 0:
            return INFINITY
        if left == right:
            slope = (3 * x1 * x1 + self.a) * pow(2 * y1, -1, self.p) % self.p
        else:
            slope = (y2 - y1) * pow((x2 - x1) % self.p, -1, self.p) % self.p
        x3 = (slope * slope - x1 - x2) % self.p
        result = (x3, (slope * (x1 - x3) - y1) % self.p)
        self.require(result)
        return result

    def normalize(self, scalar, point, order):
        if not isinstance(scalar, int) or isinstance(scalar, bool):
            raise TypeError("scalar must be an integer")
        self.require(point)
        if scalar < 0:
            scalar, point = -scalar, self.negate(point)
        if order is not None:
            if order <= 0 or self.double_and_add(order, point) is not INFINITY:
                raise ValueError("invalid subgroup order")
            scalar %= order
        return scalar, point

    def double_and_add(self, scalar, point, order=None):
        scalar, point = self.normalize(scalar, point, order)
        result = INFINITY
        for bit in bin(scalar)[2:]:
            result = self.add(result, result)
            if bit == "1":
                result = self.add(result, point)
        return result

    def ladder(self, scalar, point, order=None):
        scalar, point = self.normalize(scalar, point, order)
        lower, upper = INFINITY, point
        for bit in bin(scalar)[2:]:
            if bit == "0":
                upper, lower = self.add(lower, upper), self.add(lower, lower)
            else:
                lower, upper = self.add(lower, upper), self.add(upper, upper)
        return lower

    def window(self, scalar, point, width=3, order=None):
        if width <= 0:
            raise ValueError("width must be positive")
        scalar, point = self.normalize(scalar, point, order)
        table = [INFINITY]
        for _ in range(1, 1 << width):
            table.append(self.add(table[-1], point))
        digits, mask = [], (1 << width) - 1
        while scalar:
            digits.append(scalar & mask)
            scalar >>= width
        result = INFINITY
        for digit in reversed(digits):
            for _ in range(width):
                result = self.add(result, result)
            result = self.add(result, table[digit])
        return result


curve = Curve(17, 2, 2)
point, order = (5, 1), 19
assert curve.double_and_add(order, point) is INFINITY
assert curve.double_and_add(2, point) == (6, 3)
assert curve.double_and_add(13, point) == (16, 4)
assert curve.double_and_add(32, point, order) == (16, 4)

for scalar in range(-40, 81):
    expected = curve.double_and_add(scalar, point)
    assert curve.ladder(scalar, point) == expected
    for width in (1, 2, 3, 4):
        assert curve.window(scalar, point, width) == expected

try:
    curve.double_and_add(3, (1, 1))
except ValueError:
    pass
else:
    raise AssertionError("off-curve point accepted")

for operation in (lambda: Curve(17, 0, 0),
                  lambda: curve.double_and_add(5, point, 18)):
    try:
        operation()
    except ValueError:
        pass
    else:
        raise AssertionError("invalid input accepted")

print("all tests passed")

Strategy	Cost and storage	Failure mode	Mitigation
Affine double-and-add	$O(\log k)$ steps with inversions	Scalar-dependent branches and costly inversion	Use for teaching or public data
Projective method	One final inversion	More complex exceptional formulas	Use reviewed formulas
Fixed window	Fewer additions, $O(2^w)$ table	Secret-dependent lookup may leak	Constant-time table selection
Ladder	One add and double per bit	High-level branch still leaks	Conditional swaps and fixed bit length
Scalar reduction	Shortens work	Wrong order changes semantics	Verify subgroup order first
Audited library	Tested production implementation	Wrappers may skip validation	Preserve parameter and point checks

Applications, Case Studies and Exercises

On the toy curve, $13=(1101)_2$ and every strategy returns $(16,4)$. A realistic comparison should count field multiplications, squarings, and inversions separately and distinguish public scalars from secret scalars, where timing and memory-access regularity matter.

Practice

Apply Elliptic-Curve Scalar Multiplication

Case study 1. Trace double-and-add, a width-two window, and the ladder for $k=13$. Success means all return $(16,4)$ and every intermediate point remains on the curve.

Case study 2. Cross-check all $0\le k\lt19$, then benchmark reproducible larger public scalars while counting additions, doublings, inversions, table entries, and scalar-dependent branches. Success means outputs agree and speed is separated from side-channel structure.

Exercises. Prove the ladder invariant; add Jacobian coordinates; test infinity, $y=0$, negative scalars, off-curve inputs, and bad subgroup orders; document what a constant-time table lookup requires from the runtime.

Use affine double-and-add for transparent public examples, projective windows for reviewed throughput code, and an audited constant-time ladder or window routine for secrets. Never reduce by an unverified order, omit point validation, or infer constant-time behavior from a regular-looking high-level loop.

Cookie Consent