nish/crypto/ed25519

The Ed25519 signature scheme of RFC 8032 (§5.1).

import {
  ED25519_PUBLIC_KEY_SIZE,
  ED25519_SEED_SIZE,
  ED25519_SIGNATURE_SIZE,
  ed25519PublicKey,
  ed25519Sign,
  ed25519Verify,
} from "nish/crypto/ed25519";
import { ED25519_SEED_SIZE, ed25519PublicKey, ed25519Sign, ed25519Verify } from "nish/crypto/ed25519";
import { Secret, secret, wipe } from "nish:secret";

const raw: u8[] = new Array<u8>(ED25519_SEED_SIZE)
crypto.getRandomValues(raw)                              // any 32 bytes are a seed
const seed: Secret<u8[]> = secret(raw)
const message: u8[] = [104, 105]
const pub: u8[] | null = ed25519PublicKey(seed)          // 32 bytes
const sig: u8[] | null = ed25519Sign(seed, message)      // 64 bytes, R || S
wipe(seed)
if (pub !== null && sig !== null) {
  ed25519Verify(pub, message, sig)                       // true
}

Written from the specification (RFC 8032 §5.1.1 to §5.1.7), in this module's own structure: nothing here is ported from another implementation. The field is nish/crypto/x25519's GF(2^255 - 19), imported rather than written twice, and SHA-512 is nish/crypto/sha512's. The point formulas are the extended twisted Edwards ones of Hisil, Wong, Carter and Dawson, "Twisted Edwards Curves Revisited" (ASIACRYPT 2008), for a = -1; the code is this module's.

The curve

-x^2 + y^2 = 1 + d x^2 y^2 over GF(p), d = -121665/121666. A point is held in extended coordinates (X : Y : Z : T), x = X/Z, y = Y/Z and x y = T/Z. The addition is complete — it is right for every pair of points, the identity and a point added to itself included, because -1 is a square and d is not — so no input steers it down another path. A point about to be added is first put in the "cached" form (Y + X, Y - X, 2 d T, 2 Z) the addition reads.

Bounds

f25519Mul accepts limbs below 2^27 in magnitude: a reduced element, or one sum or difference of two. Every product below is given one of those; a value two sums away from reduced (F and E in the doubling) is carried first, and so is every cached coordinate. The field functions state their own bounds (nish/crypto/x25519).

Constant time, by construction

Signing and the public key multiply the base point by a secret scalar, and that multiplication branches on and indexes by nothing the scalar reaches. The scalar is recoded into 64 signed radix-16 digits in [-8, 8]; each step doubles four times and adds the table entry for the digit, which is chosen by reading all eight entries and keeping one under a mask, and negated with a masked swap and a masked select.

The digit arithmetic and the masks use f25519Add64, f25519Sub64 and f25519Mul64, because signed overflow is undefined and a checked operation branches. The reductions mod L run a fixed 512 steps of a shift and a masked conditional subtraction over 32-bit limbs in u64, whose subtraction wraps. Every if and every loop bound is on a public quantity: a digit position, a limb number, a bit position or a length. This is discipline, checked by reading, not by a disassembly fixture as f25519Mul and the X25519 ladder are (ECC-5, docs/security/crypto-ecc.md).

Verification is variable time

Every value ed25519Verify handles is public — the key, the message and the signature — so it may branch on them: it refuses early, and compares the final encoding byte by byte. It uses the same multiplication as signing all the same.

What is refused. ed25519Verify is RFC 8032 §5.1.7 with the cofactorless equation [S]B = R + [k]A: an S of L or more, a public key whose y is not below p or that is not on the curve, and an x of zero with the sign bit set are all refused (§5.1.3). R is not decoded: [S]B - [k]A is encoded and compared with R's bytes, and since the encoding is canonical, an R that is not the canonical encoding of a point never matches.

A public key of small order is not refused, as RFC 8032 does not ask it to be: under such a key, some signatures verify for messages its owner never signed, so a protocol that needs a signature to bind one key checks the key itself.

The seed is a `Secret`

The seed is a Secret (nish:secret, docs/LANGUAGE.md "Secrets"). ed25519PublicKey and ed25519Sign take the 32-byte seed as a Secret<u8[]> and run inside expose / exposeWith; the seed's hash, the clamped scalar and the prefix, the nonce and its hash, the digits, the accumulator, the selected table entry and the formula temporaries are all wiped before they return, and so are both SHA-512 states (ECC-5).

Loop bounds are literals

As in nish/crypto/x25519, each function that indexes an array opens with an early return for a shorter one, which cannot happen but lets the compiler drop the loops' bounds checks.

Private names carry the ed25519 / Ed25519 prefix because a std/ module's private functions share the importing program's flat symbol namespace (docs/wp26-stdlib.md §3e).

Functions

ed25519PublicKey

The public key of seed (RFC 8032 §5.1.5): the encoding of a * B, as 32 plain bytes. Answers null unless seed is ED25519_SEED_SIZE bytes.

const ed25519PublicKey: (seed: Secret<u8[]>) => u8[] | null
seedSecret<u8[]>required

The private key, 32 bytes.

returnsu8[] | null

The 32-byte encoded public key, or null for a seed of the wrong length.

ed25519Sign

The Ed25519 signature of msg under seed (RFC 8032 §5.1.6), R || S, 64 bytes. Signing is deterministic: the same seed and message always give the same signature. Answers null unless seed is ED25519_SEED_SIZE bytes. The public key is derived from the seed again on every call. A message longer than 2^31 - 1 bytes panics, as in sha512: its length does not survive toI32, and the signature would be of a prefix.

const ed25519Sign: (
  seed: Secret<u8[]>,
  msg: u8[],
) => u8[] | null
seedSecret<u8[]>required

The private key, 32 bytes.

msgu8[]required

The whole message signed.

returnsu8[] | null

The 64-byte signature R || S, or null for a seed of the wrong length.

ed25519Verify

Whether sig is a valid Ed25519 signature of msg under the public key pub (RFC 8032 §5.1.7): [S]B = R + [k]A with k = SHA-512(R || A || M) mod L, checked as the encoding of [S]B + [k](-A) against R's bytes. Answers false for a key or signature of the wrong length, an S of L or more, and a key that does not decode. A message longer than 2^31 - 1 bytes panics, as in ed25519Sign: a check of a prefix would accept the signature for any longer message that shares it. Every value here is public, so the answer may be reached by branches.

const ed25519Verify: (
  pub: u8[],
  msg: u8[],
  sig: u8[],
) => boolean
pubu8[]required

The signer's 32-byte encoded public key.

msgu8[]required

The whole message.

sigu8[]required

The 64-byte signature R || S.

returnsboolean

true when the signature is valid, false for anything else.

Constants

32

ED25519_PUBLIC_KEY_SIZE: i32

The length in bytes of an encoded public key.

32

ED25519_SEED_SIZE: i32

The length in bytes of a seed (the private key), RFC 8032 §5.1.5.

64

ED25519_SIGNATURE_SIZE: i32

The length in bytes of a signature, R || S.