Module
Fastest JS implementation of ed25519, x25519 & ristretto255. Independently audited, high-security, 0-dependency EDDSA sigs & ECDH key agreement
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567/*! noble-ed25519 - MIT License (c) Paul Miller (paulmillr.com) */
// https://ed25519.cr.yp.to// https://tools.ietf.org/html/rfc8032// https://en.wikipedia.org/wiki/EdDSA// Thanks DJB!
export const CURVE_PARAMS = { // Params: a, b a: -1n, // Equal to -121665/121666 over finite field. // Negative number is P - number, and division is modInverse(number, P) d: 37095705934669439343138083508754565189542113879843219016388785533085940283555n, // Finite field 𝔽p over which we'll do calculations P: 2n ** 255n - 19n, // Subgroup order aka prime_order n: 2n ** 252n + 27742317777372353535851937790883648493n, // Cofactor h: 8n, // Base point (x, y) aka generator point Gx: 15112221349535400772501151409588531511454012693041857206046113283949847762202n, Gy: 46316835694926478169428394003475163141307993866256225615783033603165251855960n};
type PrivKey = Uint8Array | string | bigint | number;type PubKey = Uint8Array | string | Point;type Hex = Uint8Array | string;type Signature = Uint8Array | string | SignResult;
const ENCODING_LENGTH = 32;const P = CURVE_PARAMS.P;const PRIME_ORDER = CURVE_PARAMS.n;const I = powMod(2n, (P - 1n) / 4n, P);
// Point represents default aka affine coordinates: (x, y)// Extended Point represents point in extended coordinates: (x, y, z, t=xy)class ExtendedPoint { static ZERO_POINT = new ExtendedPoint(0n, 1n, 1n, 0n); static fromPoint(p: Point): ExtendedPoint { if (p.equals(Point.ZERO_POINT)) return ExtendedPoint.ZERO_POINT; return new ExtendedPoint(p.x, p.y, 1n, mod(p.x * p.y)); }
constructor(public x: bigint, public y: bigint, public z: bigint, public t: bigint) {}
static batchAffine(points: ExtendedPoint[]): Point[] { const toInv = batchInverse(points.map(p => p.z)); return points.map((p, i) => p.toAffine(toInv[i])); }
equals(other: ExtendedPoint): boolean { const a = this; const b = other; const [T1, T2, Z1, Z2] = [a.t, b.t, a.z, b.z]; return mod(T1 * Z2) === mod(T2 * Z1); }
// http://hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html#addition-add-2008-hwcd-4 // Cost: 8M + 8add + 2*2. add(other: ExtendedPoint): ExtendedPoint { const _a = this, _b = other; const X1 = _a.x, Y1 = _a.y, Z1 = _a.z, T1 = _a.t; const X2 = _b.x, Y2 = _b.y, Z2 = _b.z, T2 = _b.t; const A = mod((Y1 - X1) * (Y2 + X2)); const B = mod((Y1 + X1) * (Y2 - X2)); const F = mod(B - A); if (F === 0n) { return this.double(); } const C = mod(Z1 * 2n * T2); const D = mod(T1 * 2n * Z2); const E = mod(D + C); const G = mod(B + A); const H = mod(D - C); const X3 = mod(E * F); const Y3 = mod(G * H); const T3 = mod(E * H); const Z3 = mod(F * G); return new ExtendedPoint(X3, Y3, Z3, T3); }
// http://hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html#doubling-dbl-2008-hwcd // Cost: 3M + 4S + 1*a + 7add + 1*2. double(): ExtendedPoint { const _a = this; const X1 = _a.x, Y1 = _a.y, Z1 = _a.z; const { a } = CURVE_PARAMS; const A = mod(X1 ** 2n); const B = mod(Y1 ** 2n); const C = mod(2n * Z1 ** 2n); const D = mod(a * A); const E = mod((X1 + Y1) ** 2n - A - B); const G = mod(D + B); const F = mod(G - C); const H = mod(D - B); const X3 = mod(E * F); const Y3 = mod(G * H); const T3 = mod(E * H); const Z3 = mod(F * G); return new ExtendedPoint(X3, Y3, Z3, T3); }
multiplyUnsafe(scalar: bigint): ExtendedPoint { if (typeof scalar !== 'number' && typeof scalar !== 'bigint') { throw new TypeError('Point#multiply: expected number or bigint'); } let n = mod(BigInt(scalar), PRIME_ORDER); if (n <= 0) { throw new Error('Point#multiply: invalid scalar, expected positive integer'); } let p = ExtendedPoint.ZERO_POINT; let d: ExtendedPoint = this; while (n > 0n) { if (n & 1n) p = p.add(d); d = d.double(); n >>= 1n; } return p; }
toAffine(invZ: bigint = modInverse(mod(this.z))): Point { const x = mod(this.x * invZ); const y = mod(this.y * invZ); return new Point(x, y); }}
export class Point { // Base point aka generator // public_key = base_point * private_key static BASE_POINT: Point = new Point(CURVE_PARAMS.Gx, CURVE_PARAMS.Gy); // Identity point aka point at infinity // point = point + zero_point static ZERO_POINT: Point = new Point(0n, 1n);
// We calculate precomputes for elliptic curve point multiplication // using windowed method. This specifies window size and // stores precomputed values. Usually only base point would be precomputed. private WINDOW_SIZE?: number; private PRECOMPUTES?: ExtendedPoint[];
constructor(public x: bigint, public y: bigint) {}
_setWindowSize(windowSize: number) { this.WINDOW_SIZE = windowSize; this.PRECOMPUTES = undefined; }
static fromHex(hash: Hex) { const { d } = CURVE_PARAMS;
// rfc8032 5.1.3 const bytes = hash instanceof Uint8Array ? hash : hexToArray(hash); const len = bytes.length - 1; const normedLast = bytes[len] & ~0x80; const isLastByteOdd = (bytes[len] & 0x80) !== 0; const normed = Uint8Array.from(Array.from(bytes.slice(0, len)).concat(normedLast)); const y = arrayToNumberLE(normed); if (y >= P) { throw new Error('Point#fromHex expects hex <= Fp'); } const sqrY = y * y; const sqrX = mod((sqrY - 1n) * modInverse(d * sqrY + 1n), P); let x = powMod(sqrX, (P + 3n) / 8n, P); if (mod(x * x - sqrX, P) !== 0n) { x = mod(x * I, P); } const isXOdd = (x & 1n) === 1n; if (isLastByteOdd !== isXOdd) { x = mod(-x, P); } return new Point(x, y); }
encode(): Uint8Array { let hex = this.y.toString(16); hex = hex.length & 1 ? `0${hex}` : hex; const u8 = new Uint8Array(ENCODING_LENGTH); for (let i = hex.length - 2, j = 0; j < ENCODING_LENGTH && i >= 0; i -= 2, j++) { u8[j] = parseInt(hex[i] + hex[i + 1], 16); } const mask = this.x & 1n ? 0x80 : 0; u8[ENCODING_LENGTH - 1] |= mask; return u8; }
/** * Converts point to compressed representation of its Y. * ECDSA uses `04${x}${y}` to represent long form and * `02${x}` / `03${x}` to represent short form, * where leading bit signifies positive or negative Y. * EDDSA (ed25519) uses short form. */ toHex(): string { const bytes = this.encode(); let hex = ''; for (let i = 0; i < bytes.length; i++) { const value = bytes[i].toString(16); hex = `${hex}${value.length > 1 ? value : `0${value}`}`; } return hex; }
// Converts to Montgomery; aka x coordinate of curve25519. // We don't have fromX25519, because we don't know sign! toX25519() { // curve25519 is birationally equivalent to ed25519 // x, y: ed25519 coordinates // u, v: x25519 coordinates // u = (1 + y) / (1 - y) // See https://blog.filippo.io/using-ed25519-keys-for-encryption const res = (1n + this.y) * modInverse(1n - this.y); return mod(res, P); }
equals(other: Point): boolean { return this.x === other.x && this.y === other.y; }
negate(): Point { return new Point(this.x, mod(-this.y, P)); }
add(other: Point): Point { if (!(other instanceof Point)) { throw new TypeError('Point#add: expected Point'); } const { d } = CURVE_PARAMS; const a = this; const b = other; const x = (a.x * b.y + b.x * a.y) * modInverse(1n + d * a.x * b.x * a.y * b.y); const y = (a.y * b.y + a.x * b.x) * modInverse(1n - d * a.x * b.x * a.y * b.y); return new Point(mod(x, P), mod(y, P)); }
subtract(other: Point) { return this.add(other.negate()); }
private precomputeWindow(W: number): ExtendedPoint[] { if (this.PRECOMPUTES) return this.PRECOMPUTES; const points: ExtendedPoint[] = new Array(2 ** W * W); let currPoint: ExtendedPoint = ExtendedPoint.fromPoint(this); const winSize = 2 ** W; for (let currWin = 0; currWin < 256 / W; currWin++) { let offset = currWin * winSize; let point: ExtendedPoint = ExtendedPoint.ZERO_POINT; for (let i = 0; i < winSize; i++) { points[offset + i] = point; point = point.add(currPoint); } currPoint = point; } let res = points; if (W !== 1) { res = ExtendedPoint.batchAffine(points).map(p => ExtendedPoint.fromPoint(p)); this.PRECOMPUTES = res; } return res; }
multiply(scalar: bigint, isAffine: false): ExtendedPoint; multiply(scalar: bigint, isAffine?: true): Point; multiply(scalar: bigint, isAffine = true): Point | ExtendedPoint { if (typeof scalar !== 'number' && typeof scalar !== 'bigint') { throw new TypeError('Point#multiply: expected number or bigint'); } let n = mod(BigInt(scalar), PRIME_ORDER); if (n <= 0) { throw new Error('Point#multiply: invalid scalar, expected positive integer'); } const W = this.WINDOW_SIZE || 1; if (256 % W) { throw new Error('Point#multiply: Invalid precomputation window, must be power of 2'); } const precomputes = this.precomputeWindow(W); const winSize = 2 ** W; let p = ExtendedPoint.ZERO_POINT; for (let byteIdx = 0; byteIdx < 256 / W; byteIdx++) { const offset = winSize * byteIdx; const masked = Number(n & BigInt(winSize - 1)); p = p.add(precomputes[offset + masked]); n >>= BigInt(W); } return isAffine ? p.toAffine() : p; }}
export class SignResult { constructor(public r: Point, public s: bigint) {}
static fromHex(hex: Hex) { hex = normalizeHash(hex); const r = Point.fromHex(hex.slice(0, 32)); const s = arrayToNumberLE(hex.slice(32)); return new SignResult(r, s); }
toHex() { const numberBytes = numberToArray(this.s).reverse(); const sBytes = new Uint8Array(ENCODING_LENGTH); sBytes.set(numberBytes); const bytes = concatTypedArrays(this.r.encode(), sBytes); let hex = ''; for (let i = 0; i < bytes.length; i++) { const value = bytes[i].toString(16); hex = `${hex}${value.length > 1 ? value : `0${value}`}`; } return hex; }}const { BASE_POINT } = Point;
let sha512: (message: Uint8Array) => Promise<Uint8Array>;
if (typeof window == 'object' && 'crypto' in window) { sha512 = async (message: Uint8Array) => { const buffer = await window.crypto.subtle.digest('SHA-512', message.buffer); return new Uint8Array(buffer); };} else if (typeof process === 'object' && 'node' in process.versions) { const req = require; const { createHash } = req('crypto'); sha512 = async (message: Uint8Array) => { const hash = createHash('sha512'); hash.update(message); return Uint8Array.from(hash.digest()); };} else { throw new Error("The environment doesn't have sha512 function");}
function concatTypedArrays(...args: Array<Uint8Array>): Uint8Array { const result = new Uint8Array(args.reduce((a, arr) => a + arr.length, 0)); for (let i = 0, pad = 0; i < args.length; i++) { const arr = args[i]; result.set(arr, pad); pad += arr.length; } return result;}
function numberToArray(num: bigint | number, padding?: number): Uint8Array { let hex = num.toString(16); if (padding) hex = hex.padStart(padding); hex = hex.length & 1 ? `0${hex}` : hex; const len = hex.length / 2; const u8 = new Uint8Array(len); for (let j = 0, i = 0; i < hex.length; i += 2, j++) { u8[j] = parseInt(hex[i] + hex[i + 1], 16); } return u8;}
// Little Endianfunction arrayToNumberLE(bytes: Uint8Array): bigint { let value = 0n; for (let i = 0; i < bytes.length; i++) { value += (BigInt(bytes[i]) & 255n) << (8n * BigInt(i)); } return value;}
// Big Endianfunction arrayToNumber(bytes: Uint8Array): bigint { let value = 0n; for (let i = bytes.length - 1, j = 0; i >= 0; i--, j++) { value += (BigInt(bytes[i]) & 255n) << (8n * BigInt(j)); } return value;}
function powMod(x: bigint, power: bigint, order: bigint) { let res = 1n; while (power > 0) { if (power & 1n) { res = mod(res * x, order); } power >>= 1n; x = mod(x * x, order); } return res;}
function hexToArray(hash: string): Uint8Array { hash = hash.length & 1 ? `0${hash}` : hash; const len = hash.length; const result = new Uint8Array(len / 2); for (let i = 0, j = 0; i < len - 1; i += 2, j++) { result[j] = parseInt(hash[i] + hash[i + 1], 16); } return result;}
function hexToNumber(hex: string): bigint { if (typeof hex !== 'string') { throw new TypeError('hexToNumber: expected string, got ' + typeof hex); } // Big Endian return BigInt(`0x${hex}`);}
async function hashNumber(...args: Array<Uint8Array>) { const messageArray = concatTypedArrays(...args); const hash = await sha512(messageArray); const value = arrayToNumberLE(hash); return mod(value, PRIME_ORDER);}
function getPrivateBytes(privateKey: bigint | number | Uint8Array) { return sha512(privateKey instanceof Uint8Array ? privateKey : numberToArray(privateKey, 64));}
function keyPrefix(privateBytes: Uint8Array) { return privateBytes.slice(ENCODING_LENGTH);}
function mod(a: bigint, b: bigint = P) { const res = a % b; return res >= 0n ? res : b + res;}
// Eucledian GCD// https://brilliant.org/wiki/extended-euclidean-algorithm/function egcd(a: bigint, b: bigint) { let [x, y, u, v] = [0n, 1n, 1n, 0n]; while (a !== 0n) { let q = b / a; let r = b % a; let m = x - u * q; let n = y - v * q; [b, a] = [a, r]; [x, y] = [u, v]; [u, v] = [m, n]; } let gcd = b; return [gcd, x, y];}
function modInverse(number: bigint, modulo: bigint = P) { if (number === 0n || modulo <= 0n) { console.log(number); throw new Error('modInverse: expected positive integers'); } let [gcd, x] = egcd(mod(number, modulo), modulo); if (gcd !== 1n) { throw new Error('modInverse: does not exist'); } return mod(x, modulo);}
function batchInverse(nums: bigint[], n: bigint = P): bigint[] { const len = nums.length; const scratch = new Array(len); let acc = 1n; for (let i = 0; i < len; i++) { if (nums[i] === 0n) continue; scratch[i] = acc; acc = mod(acc * nums[i], n); } acc = modInverse(acc, n); for (let i = len - 1; i >= 0; i--) { if (nums[i] === 0n) continue; let tmp = mod(acc * nums[i], n); nums[i] = mod(acc * scratch[i], n); acc = tmp; } return nums;}
function encodePrivate(privateBytes: Uint8Array) { const last = ENCODING_LENGTH - 1; const head = privateBytes.slice(0, ENCODING_LENGTH); head[0] &= 248; head[last] &= 127; head[last] |= 64;
return arrayToNumberLE(head);}
function normalizePrivateKey(privateKey: PrivKey): bigint { let res: bigint; if (privateKey instanceof Uint8Array) { res = arrayToNumber(privateKey); } else if (typeof privateKey === 'string') { res = hexToNumber(privateKey); } else { res = BigInt(privateKey); } return res;}
function normalizePublicKey(publicKey: PubKey): Point { return publicKey instanceof Point ? publicKey : Point.fromHex(publicKey);}
function normalizePoint(point: Point, privateKey: PrivKey): Uint8Array | string | Point { if (privateKey instanceof Uint8Array) { return point.encode(); } if (typeof privateKey === 'string') { return point.toHex(); } return point;}
function normalizeSignature(signature: Signature): SignResult { return signature instanceof SignResult ? signature : SignResult.fromHex(signature);}
function normalizeHash(hash: Hex) { return hash instanceof Uint8Array ? hash : hexToArray(hash);}
export function getPublicKey(privateKey: Uint8Array): Promise<Uint8Array>;export function getPublicKey(privateKey: string): Promise<string>;export function getPublicKey(privateKey: bigint | number): Promise<Point>;export async function getPublicKey(privateKey: PrivKey) { const multiplier = normalizePrivateKey(privateKey); const privateBytes = await getPrivateBytes(multiplier); const privateInt = encodePrivate(privateBytes); const publicKey = BASE_POINT.multiply(privateInt); const p = normalizePoint(publicKey, privateKey); return p;}
export function sign(hash: Uint8Array, privateKey: PrivKey): Promise<Uint8Array>;export function sign(hash: string, privateKey: PrivKey): Promise<string>;export async function sign(hash: Hex, privateKey: PrivKey) { const message = normalizeHash(hash); privateKey = normalizePrivateKey(privateKey); const publicKey = await getPublicKey(privateKey); const privateBytes = await getPrivateBytes(privateKey); const privatePrefix = keyPrefix(privateBytes); const r = await hashNumber(privatePrefix, message); const R = BASE_POINT.multiply(r); const h = await hashNumber(R.encode(), publicKey.encode(), message); const S = mod(r + h * encodePrivate(privateBytes), PRIME_ORDER); const signature = new SignResult(R, S).toHex(); return hash instanceof Uint8Array ? hexToArray(signature) : signature;}
export async function verify(signature: Signature, hash: Hex, publicKey: PubKey) { hash = normalizeHash(hash); publicKey = normalizePublicKey(publicKey); signature = normalizeSignature(signature); const h = await hashNumber(signature.r.encode(), publicKey.encode(), hash); const pub = ExtendedPoint.fromPoint(publicKey); const S = BASE_POINT.multiply(signature.s, false); const R = ExtendedPoint.fromPoint(signature.r).add(pub.multiplyUnsafe(h)); return S.equals(R);}
// Enable precomputes. Slows down first publicKey computation by 20ms.BASE_POINT._setWindowSize(4);
export const utils = { // generateRandomPrivateKey,
precompute(windowSize = 4, point = BASE_POINT): Point { const cached = point.equals(BASE_POINT) ? point : new Point(point.x, point.y); cached._setWindowSize(windowSize); cached.multiply(1n); return cached; }};