Finite field arithmetic

A set of low-level APIs to perform computations over the edwards25519 curve, only useful to implement custom constructions.

Points are represented as their Y coordinate.

Example

Perform a secure two-party computation of f(x) = p(x)^k. x is the input sent to the second party by the first party after blinding it using a random invertible scalar r, and k is a secret key only known by the second party. p(x) is a hash-to-curve function.

// -------- First party -------- Send blinded p(x)
unsigned char x[crypto_core_ed25519_UNIFORMBYTES];
randombytes_buf(x, sizeof x);

// Compute px = p(x), an EC point representative for x
unsigned char px[crypto_core_ed25519_BYTES];
crypto_core_ed25519_from_uniform(px, x);

// Compute a = p(x) * g^r
unsigned char r[crypto_core_ed25519_SCALARBYTES];
unsigned char gr[crypto_core_ed25519_BYTES];
unsigned char a[crypto_core_ed25519_BYTES];
crypto_core_ed25519_scalar_random(r);
crypto_scalarmult_ed25519_base_noclamp(gr, r);
crypto_core_ed25519_add(a, px, gr);

// -------- Second party -------- Send g^k and a^k
unsigned char k[crypto_core_ed25519_SCALARBYTES];
randombytes_buf(k, sizeof k);

// Compute v = g^k
unsigned char v[crypto_core_ed25519_BYTES];
crypto_scalarmult_ed25519_base(v, k);

// Compute b = a^k
unsigned char b[crypto_core_ed25519_BYTES];
if (crypto_scalarmult_ed25519(b, k, a) != 0) {
    return -1;
}

// -------- First party -------- Unblind f(x)
// Compute vir = v^(-r)
unsigned char ir[crypto_core_ed25519_SCALARBYTES];
unsigned char vir[crypto_core_ed25519_BYTES];
crypto_core_ed25519_scalar_negate(ir, r);
crypto_scalarmult_ed25519_noclamp(vir, ir, v);

// Compute f(x) = b * v^(-r) = (p(x) * g^r)^k * (g^k)^(-r)
//              = (p(x) * g)^k * g^(-k) = p(x)^k
unsigned char fx[crypto_core_ed25519_BYTES];
crypto_core_ed25519_add(fx, b, vir);

Point validation

int crypto_core_ed25519_is_valid_point(const unsigned char *p);

The crypto_core_ed25519_is_valid_point() function checks that p represents a point on the edwards25519 curve, in canonical form, on the main subgroup, and that the point doesn’t have a small order.

It returns 1 on success, and 0 if the checks didn’t pass.

In versions <= 1.0.20, this function incorrectly accepted some points not on the main subgroup (points in mixed-order subgroups like 2L, 4L, 8L). Consider using Ristretto255 instead, which eliminates cofactor-related issues entirely: if a point decodes, it’s safe.

If you can’t upgrade or switch to Ristretto255, use this workaround:

int is_on_main_subgroup(const unsigned char p[crypto_core_ed25519_BYTES])
{
    static const unsigned char L_1[crypto_core_ed25519_SCALARBYTES] = {
        0xec, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58,
        0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10
    };
    static const unsigned char ID[crypto_core_ed25519_BYTES] = {
        0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
    };
    unsigned char t[crypto_core_ed25519_BYTES];
    unsigned char r[crypto_core_ed25519_BYTES];
    if (crypto_scalarmult_ed25519_noclamp(t, L_1, p) != 0 ||
        crypto_core_ed25519_add(r, t, p) != 0) {
        return 0;
    }
    return sodium_memcmp(r, ID, sizeof ID) == 0;
}

Random group element

void crypto_core_ed25519_random(unsigned char *p);

Fills p with the representation of a random group element.

Elligator 2 map

int crypto_core_ed25519_from_uniform(unsigned char *p, const unsigned char *r);

The crypto_core_ed25519_from_uniform() function maps a 32 bytes vector r to a point, and stores its compressed representation into p.

The point is guaranteed to be on the main subgroup.

This function directly exposes the Elligator 2 map, uses the high bit to set the sign of the X coordinate, and the resulting point is multiplied by the cofactor.

Scalar multiplication

int crypto_scalarmult_ed25519(unsigned char *q, const unsigned char *n,
                              const unsigned char *p);

The crypto_scalarmult_ed25519() function multiplies a point p by a scalar n and puts the Y coordinate of the resulting point into q.

q should not be used as a shared key prior to hashing.

The function returns 0 on success, or -1 if n is 0 or if p is not on the curve, not on the main subgroup, is a point of small order, or is not provided in canonical form.

Note that n is “clamped” (the 3 low bits are cleared to make it a multiple of the cofactor, bit 254 is set and bit 255 is cleared to respect the original design).

int crypto_scalarmult_ed25519_base(unsigned char *q, const unsigned char *n);

The crypto_scalarmult_ed25519_base() function multiplies the base point (x, 4/5) by a scalar n (clamped) and puts the Y coordinate of the resulting point into q.

The function returns -1 if n is 0, and 0 otherwise.

Scalar multiplication without clamping

In order to prevent attacks using small subgroups, the scalarmult functions above clear lower bits of the scalar. This may be undesirable to build protocols that require n to be invertible.

The noclamp variants of these functions do not clear these bits, and do not set the high bit either. These variants expect a scalar in the ]0..L[ range.

int crypto_scalarmult_ed25519_noclamp(unsigned char *q, const unsigned char *n,
                                      const unsigned char *p);

The function verifies that p is on the prime-order subgroup before performing the multiplication, and return -1 if this is not the case or n is 0. It returns 0 on success.

int crypto_scalarmult_ed25519_base_noclamp(unsigned char *q, const unsigned char *n);

The function returns 0 on success, or -1 if n is 0.

Point addition/subtraction

int crypto_core_ed25519_add(unsigned char *r,
                            const unsigned char *p, const unsigned char *q);

The crypto_core_ed25519_add() function adds the point p to the point q and stores the resulting point into r.

The function returns 0 on success, or -1 if p and/or q are not valid points.

int crypto_core_ed25519_sub(unsigned char *r,
                            const unsigned char *p, const unsigned char *q);

The crypto_core_ed25519_sub() function subtracts the point q from the point p and stores the resulting point into r.

The function returns 0 on success, or -1 if p and/or q are not valid points.

Scalar arithmetic over L

The crypto_core_ed25519_scalar_*() function set operates over scalars in the [0..L[ interval, L being the order of the main subgroup (2^252 + 27742317777372353535851937790883648493).

Non-reduced inputs are expected to be within that interval.

A random scalar can be obtained using the crypto_core_ed25519_scalar_random() function introduced in libsodium 1.0.17:

void crypto_core_ed25519_scalar_random(unsigned char *r);

crypto_core_ed25519_scalar_random() fills r with a crypto_core_ed25519_SCALARBYTES bytes representation of the scalar in the ]0..L[ interval.

A scalar in the [0..L[ interval can also be obtained by reducing a possibly larger value:

void crypto_core_ed25519_scalar_reduce(unsigned char *r, const unsigned char *s);

The crypto_core_ed25519_scalar_reduce() function reduces s to s mod L and puts the crypto_core_ed25519_SCALARBYTES integer into r.

Note that s is much larger than r (64 bytes vs 32 bytes). Bits of s can be left to 0, but the interval s is sampled from should be at least 317 bits to ensure almost uniformity of r over L.

int crypto_core_ed25519_scalar_invert(unsigned char *recip, const unsigned char *s);

The crypto_core_ed25519_scalar_invert() function computes the multiplicative inverse of s over L, and puts it into recip.

void crypto_core_ed25519_scalar_negate(unsigned char *neg, const unsigned char *s);

The crypto_core_ed25519_scalar_negate() function returns neg so that s + neg = 0 (mod L).

void crypto_core_ed25519_scalar_complement(unsigned char *comp, const unsigned char *s);

The crypto_core_ed25519_scalar_complement() function returns comp so that s + comp = 1 (mod L).

void crypto_core_ed25519_scalar_add(unsigned char *z,
                                    const unsigned char *x, const unsigned char *y);

The crypto_core_ed25519_scalar_add() function stores x + y (mod L) into z.

void crypto_core_ed25519_scalar_sub(unsigned char *z,
                                    const unsigned char *x, const unsigned char *y);

The crypto_core_ed25519_scalar_sub() function stores x - y (mod L) into z.

void crypto_core_ed25519_scalar_mul(unsigned char *z,
                                    const unsigned char *x, const unsigned char *y);

The crypto_core_ed25519_scalar_mul() function stores x * y (mod L) into z.

Constants

• crypto_scalarmult_ed25519_BYTES

• crypto_scalarmult_ed25519_SCALARBYTES

• crypto_core_ed25519_BYTES

• crypto_core_ed25519_UNIFORMBYTES

• crypto_core_ed25519_SCALARBYTES

• crypto_core_ed25519_NONREDUCEDSCALARBYTES

Note

These functions were introduced in libsodium 1.0.16, 1.0.17 and 1.0.18.

For a complete example using these functions, see the SPAKE2+EE implementation for libsodium.

crypto_core_ed25519_from_uniform() exposes the Elligator 2 map, using the high bit for the sign of the X coordinate.