Elligator: Hiding cryptographic key exchange as random noise

The Elligator Map and Inverse Map

Elligator specifies two kinds of maps, the “map” (or “direct map” for clarity) and the “inverse map”.

The map is a function that takes a number r from an elliptic curve’s finite field (which we call a “field element”), and produces a point P = (uv) on that elliptic curve. Note that the map is not quite injective: r and −r map to the same point. Numbers that are neither equal nor opposite do map to different points though.

The inverse map is a function that takes as input an elliptic curve point P and outputs a field element r. We also call that number the “representative” because it represents a point on the curve. Note that only about half of the curve can be mapped back.

For any given point P that can be mapped, applying the inverse map then the direct map will yield the original point P.

For any representative r in the curve’s finite field, applying the direct map then the inverse map will yield either the original representative r or its opposite −r.


Elligator does not work on all elliptic curves, and will not properly hide points on all curves where it does work. The following conditions must hold:

Overall, those conditions cover a wide range of curves, including the very popular Curve25519 and Curve448. One notable exception are short Weierstraß curves that have a prime order and therefore lack a point of order two; an example of a curve with a prime order is NIST P-256.

Instantiation Parameters

An Elligator instantiation works over a specific curve, and has a couple parameters of its own. Before actually defining the maps, we need to fix those parameters.

The direct map

First, we need to define the legendre() function; it computes the Legendre symbol of a field element f:

This can be constructed using the square root checking functions needed to find the chosen non-square Z above. In a prime fields GF(p), it can be defined as: legendre(f) = f(p − 1) / 2.

The map itself takes any non-zero field element r (the representative), and outputs a point P = (uv) on the curve as follows:

Zero is a special case, which maps to the point (0, 0).

The inverse map

Unlike the direct map, the inverse map does not work for all points on the curve. It only holds for points P = (uv) such that:

Assuming those conditions hold, the representative r of P = (uv) is computed as follows:

Note: if P = (0, 0) then r = √(−0 / (Z (0 + A))) = 0.