Socket
Socket
Sign inDemoInstall

@noble/curves

Package Overview
Dependencies
Maintainers
1
Versions
34
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

@noble/curves - npm Package Compare versions

Comparing version 0.5.0 to 0.5.1

11

lib/abstract/hash-to-curve.d.ts

@@ -9,3 +9,3 @@ /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */

k: number;
expand: boolean;
expand?: 'xmd' | 'xof';
hash: CHash;

@@ -16,2 +16,11 @@ };

export declare function expand_message_xmd(msg: Uint8Array, DST: Uint8Array, lenInBytes: number, H: CHash): Uint8Array;
export declare function expand_message_xof(msg: Uint8Array, DST: Uint8Array, lenInBytes: number, k: number, H: CHash): Uint8Array;
/**
* Hashes arbitrary-length byte strings to a list of one or more elements of a finite field F
* https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-11#section-5.3
* @param msg a byte string containing the message to hash
* @param count the number of elements of F to output
* @param options `{DST: string, p: bigint, m: number, k: number, expand: 'xmd' | 'xof', hash: H}`
* @returns [u_0, ..., u_(count - 1)], a list of field elements.
*/
export declare function hash_to_field(msg: Uint8Array, count: number, options: htfOpts): bigint[][];

@@ -18,0 +27,0 @@ export declare function isogenyMap<T, F extends mod.Field<T>>(field: F, map: [T[], T[], T[], T[]]): (x: T, y: T) => {

42

lib/abstract/hash-to-curve.js
"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
exports.isogenyMap = exports.hash_to_field = exports.expand_message_xmd = exports.stringToBytes = exports.validateHTFOpts = void 0;
exports.isogenyMap = exports.hash_to_field = exports.expand_message_xof = exports.expand_message_xmd = exports.stringToBytes = exports.validateHTFOpts = void 0;
/*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */

@@ -16,3 +16,3 @@ const utils_js_1 = require("./utils.js");

throw new Error('Invalid htf/k');
if (typeof opts.expand !== 'boolean')
if (opts.expand !== 'xmd' && opts.expand !== 'xof' && opts.expand !== undefined)
throw new Error('Invalid htf/expand');

@@ -85,9 +85,28 @@ if (typeof opts.hash !== 'function' || !Number.isSafeInteger(opts.hash.outputLen))

exports.expand_message_xmd = expand_message_xmd;
// hashes arbitrary-length byte strings to a list of one or more elements of a finite field F
// https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-11#section-5.3
// Inputs:
// msg - a byte string containing the message to hash.
// count - the number of elements of F to output.
// Outputs:
// [u_0, ..., u_(count - 1)], a list of field elements.
function expand_message_xof(msg, DST, lenInBytes, k, H) {
// https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-16#section-5.3.3
// DST = H('H2C-OVERSIZE-DST-' || a_very_long_DST, Math.ceil((lenInBytes * k) / 8));
if (DST.length > 255) {
const dkLen = Math.ceil((2 * k) / 8);
DST = H.create({ dkLen }).update(stringToBytes('H2C-OVERSIZE-DST-')).update(DST).digest();
}
if (lenInBytes > 65535 || DST.length > 255)
throw new Error('expand_message_xof: invalid lenInBytes');
return (H.create({ dkLen: lenInBytes })
.update(msg)
.update(i2osp(lenInBytes, 2))
// 2. DST_prime = DST || I2OSP(len(DST), 1)
.update(DST)
.update(i2osp(DST.length, 1))
.digest());
}
exports.expand_message_xof = expand_message_xof;
/**
* Hashes arbitrary-length byte strings to a list of one or more elements of a finite field F
* https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-11#section-5.3
* @param msg a byte string containing the message to hash
* @param count the number of elements of F to output
* @param options `{DST: string, p: bigint, m: number, k: number, expand: 'xmd' | 'xof', hash: H}`
* @returns [u_0, ..., u_(count - 1)], a list of field elements.
*/
function hash_to_field(msg, count, options) {

@@ -101,5 +120,8 @@ // if options is provided but incomplete, fill any missing fields with the

let pseudo_random_bytes = msg;
if (options.expand) {
if (options.expand === 'xmd') {
pseudo_random_bytes = expand_message_xmd(msg, DST, len_in_bytes, options.hash);
}
else if (options.expand === 'xof') {
pseudo_random_bytes = expand_message_xof(msg, DST, len_in_bytes, options.k, options.hash);
}
const u = new Array(count);

@@ -106,0 +128,0 @@ for (let i = 0; i < count; i++) {

25

lib/abstract/modular.d.ts

@@ -11,14 +11,4 @@ export declare function mod(a: bigint, b: bigint): bigint;

export declare function invert(number: bigint, modulo: bigint): bigint;
/**
* Calculates Legendre symbol (a | p), which denotes the value of a^((p-1)/2) (mod p).
* * (a | p) ≡ 1 if a is a square (mod p)
* * (a | p) ≡ -1 if a is not a square (mod p)
* * (a | p) ≡ 0 if a ≡ 0 (mod p)
*/
export declare function legendre(num: bigint, fieldPrime: bigint): bigint;
/**
* Calculates square root of a number in a finite field.
* √a mod P
*/
export declare function sqrt(number: bigint, modulo: bigint): bigint;
export declare function tonelliShanks(P: bigint): <T>(Fp: Field<T>, n: T) => T;
export declare function FpSqrt(P: bigint): <T>(Fp: Field<T>, n: T) => T;
export declare const isNegativeLE: (num: bigint, modulo: bigint) => boolean;

@@ -61,6 +51,7 @@ export interface Field<T> {

export declare function FpDiv<T>(f: Field<T>, lhs: T, rhs: T | bigint): T;
export declare function Fp(ORDER: bigint, bitLen?: number, isLE?: boolean, redef?: Partial<Field<bigint>>): Readonly<Field<bigint>>;
export declare function FpSqrt<T>(Fp: Field<T>): {
sqrt: (x: T) => T;
isSquare: (x: T) => boolean;
};
export declare function FpIsSquare<T>(f: Field<T>): (x: T) => boolean;
declare type FpField = Field<bigint> & Required<Pick<Field<bigint>, 'isOdd'>>;
export declare function Fp(ORDER: bigint, bitLen?: number, isLE?: boolean, redef?: Partial<Field<bigint>>): Readonly<FpField>;
export declare function FpSqrtOdd<T>(Fp: Field<T>, elm: T): T;
export declare function FpSqrtEven<T>(Fp: Field<T>, elm: T): T;
export {};

283

lib/abstract/modular.js
"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
exports.FpSqrt = exports.Fp = exports.FpDiv = exports.FpInvertBatch = exports.FpPow = exports.validateField = exports.isNegativeLE = exports.sqrt = exports.legendre = exports.invert = exports.pow2 = exports.pow = exports.mod = void 0;
exports.FpSqrtEven = exports.FpSqrtOdd = exports.Fp = exports.FpIsSquare = exports.FpDiv = exports.FpInvertBatch = exports.FpPow = exports.validateField = exports.isNegativeLE = exports.FpSqrt = exports.tonelliShanks = exports.invert = exports.pow2 = exports.pow = exports.mod = void 0;
/*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
// TODO: remove circular imports
const utils = require("./utils.js");

@@ -10,3 +11,3 @@ // Utilities for modular arithmetics and finite fields

// prettier-ignore
const _4n = BigInt(4), _5n = BigInt(5), _7n = BigInt(7), _8n = BigInt(8);
const _4n = BigInt(4), _5n = BigInt(5), _8n = BigInt(8);
// prettier-ignore

@@ -77,22 +78,63 @@ const _9n = BigInt(9), _16n = BigInt(16);

exports.invert = invert;
/**
* Calculates Legendre symbol (a | p), which denotes the value of a^((p-1)/2) (mod p).
* * (a | p) ≡ 1 if a is a square (mod p)
* * (a | p) ≡ -1 if a is not a square (mod p)
* * (a | p) ≡ 0 if a ≡ 0 (mod p)
*/
function legendre(num, fieldPrime) {
return pow(num, (fieldPrime - _1n) / _2n, fieldPrime);
// Tonelli-Shanks algorithm
// https://eprint.iacr.org/2012/685.pdf (page 12)
function tonelliShanks(P) {
// Legendre constant: used to calculate Legendre symbol (a | p),
// which denotes the value of a^((p-1)/2) (mod p).
// (a | p) ≡ 1 if a is a square (mod p)
// (a | p) ≡ -1 if a is not a square (mod p)
// (a | p) ≡ 0 if a ≡ 0 (mod p)
const legendreC = (P - _1n) / _2n;
let Q, S, Z;
// Step 1: By factoring out powers of 2 from p - 1,
// find q and s such that p - 1 = q2s with q odd
for (Q = P - _1n, S = 0; Q % _2n === _0n; Q /= _2n, S++)
;
// Step 2: Select a non-square z such that (z | p) ≡ -1 and set c ≡ zq
for (Z = _2n; Z < P && pow(Z, legendreC, P) !== P - _1n; Z++)
;
// Fast-path
if (S === 1) {
const p1div4 = (P + _1n) / _4n;
return function tonelliFast(Fp, n) {
const root = Fp.pow(n, p1div4);
if (!Fp.equals(Fp.square(root), n))
throw new Error('Cannot find square root');
return root;
};
}
// Slow-path
const Q1div2 = (Q + _1n) / _2n;
return function tonelliSlow(Fp, n) {
// Step 0: Check that n is indeed a square: (n | p) must be ≡ 1
if (Fp.pow(n, legendreC) !== Fp.ONE)
throw new Error('Cannot find square root');
let s = S;
let c = pow(Z, Q, P);
let r = Fp.pow(n, Q1div2);
let t = Fp.pow(n, Q);
let t2 = Fp.ZERO;
while (!Fp.equals(Fp.sub(t, Fp.ONE), Fp.ZERO)) {
t2 = Fp.square(t);
let i;
for (i = 1; i < s; i++) {
// stop if t2-1 == 0
if (Fp.equals(Fp.sub(t2, Fp.ONE), Fp.ZERO))
break;
// t2 *= t2
t2 = Fp.square(t2);
}
let b = pow(c, BigInt(1 << (s - i - 1)), P);
r = Fp.mul(r, b);
c = mod(b * b, P);
t = Fp.mul(t, c);
s = i;
}
return r;
};
}
exports.legendre = legendre;
/**
* Calculates square root of a number in a finite field.
* √a mod P
*/
// TODO: rewrite as generic Fp function && remove bls versions
function sqrt(number, modulo) {
// prettier-ignore
const n = number;
const P = modulo;
const p1div4 = (P + _1n) / _4n;
exports.tonelliShanks = tonelliShanks;
function FpSqrt(P) {
// NOTE: different algorithms can give different roots, it is up to user to decide which one they want.
// For example there is FpSqrtOdd/FpSqrtEven to choice root based on oddness (used for hash-to-curve).
// P ≡ 3 (mod 4)

@@ -105,48 +147,51 @@ // √n = n^((P+1)/4)

// const NUM = 72057594037927816n;
// TODO: fix sqrtMod in secp256k1
const root = pow(n, p1div4, P);
if (mod(root * root, modulo) !== number)
throw new Error('Cannot find square root');
return root;
const p1div4 = (P + _1n) / _4n;
return function sqrt3mod4(Fp, n) {
const root = Fp.pow(n, p1div4);
// Throw if root**2 != n
if (!Fp.equals(Fp.square(root), n))
throw new Error('Cannot find square root');
return root;
};
}
// P ≡ 5 (mod 8)
// Atkin algorithm for q ≡ 5 (mod 8), https://eprint.iacr.org/2012/685.pdf (page 10)
if (P % _8n === _5n) {
const n2 = mod(n * _2n, P);
const v = pow(n2, (P - _5n) / _8n, P);
const nv = mod(n * v, P);
const i = mod(_2n * nv * v, P);
const r = mod(nv * (i - _1n), P);
return r;
const c1 = (P - _5n) / _8n;
return function sqrt5mod8(Fp, n) {
const n2 = Fp.mul(n, _2n);
const v = Fp.pow(n2, c1);
const nv = Fp.mul(n, v);
const i = Fp.mul(Fp.mul(nv, _2n), v);
const root = Fp.mul(nv, Fp.sub(i, Fp.ONE));
if (!Fp.equals(Fp.square(root), n))
throw new Error('Cannot find square root');
return root;
};
}
// P ≡ 9 (mod 16)
if (P % _16n === _9n) {
// NOTE: tonelli is too slow for bls-Fp2 calculations even on start
// Means we cannot use sqrt for constants at all!
//
// const c1 = Fp.sqrt(Fp.negate(Fp.ONE)); // 1. c1 = sqrt(-1) in F, i.e., (c1^2) == -1 in F
// const c2 = Fp.sqrt(c1); // 2. c2 = sqrt(c1) in F, i.e., (c2^2) == c1 in F
// const c3 = Fp.sqrt(Fp.negate(c1)); // 3. c3 = sqrt(-c1) in F, i.e., (c3^2) == -c1 in F
// const c4 = (P + _7n) / _16n; // 4. c4 = (q + 7) / 16 # Integer arithmetic
// sqrt = (x) => {
// let tv1 = Fp.pow(x, c4); // 1. tv1 = x^c4
// let tv2 = Fp.mul(c1, tv1); // 2. tv2 = c1 * tv1
// const tv3 = Fp.mul(c2, tv1); // 3. tv3 = c2 * tv1
// let tv4 = Fp.mul(c3, tv1); // 4. tv4 = c3 * tv1
// const e1 = Fp.equals(Fp.square(tv2), x); // 5. e1 = (tv2^2) == x
// const e2 = Fp.equals(Fp.square(tv3), x); // 6. e2 = (tv3^2) == x
// tv1 = Fp.cmov(tv1, tv2, e1); // 7. tv1 = CMOV(tv1, tv2, e1) # Select tv2 if (tv2^2) == x
// tv2 = Fp.cmov(tv4, tv3, e2); // 8. tv2 = CMOV(tv4, tv3, e2) # Select tv3 if (tv3^2) == x
// const e3 = Fp.equals(Fp.square(tv2), x); // 9. e3 = (tv2^2) == x
// return Fp.cmov(tv1, tv2, e3); // 10. z = CMOV(tv1, tv2, e3) # Select the sqrt from tv1 and tv2
// }
}
// Other cases: Tonelli-Shanks algorithm
if (legendre(n, P) !== _1n)
throw new Error('Cannot find square root');
let q, s, z;
for (q = P - _1n, s = 0; q % _2n === _0n; q /= _2n, s++)
;
if (s === 1)
return pow(n, p1div4, P);
for (z = _2n; z < P && legendre(z, P) !== P - _1n; z++)
;
let c = pow(z, q, P);
let r = pow(n, (q + _1n) / _2n, P);
let t = pow(n, q, P);
let t2 = _0n;
while (mod(t - _1n, P) !== _0n) {
t2 = mod(t * t, P);
let i;
for (i = 1; i < s; i++) {
if (mod(t2 - _1n, P) === _0n)
break;
t2 = mod(t2 * t2, P);
}
let b = pow(c, BigInt(1 << (s - i - 1)), P);
r = mod(r * b, P);
c = mod(b * b, P);
t = mod(t * c, P);
s = i;
}
return r;
return tonelliShanks(P);
}
exports.sqrt = sqrt;
exports.FpSqrt = FpSqrt;
// Little-endian check for first LE bit (last BE bit);

@@ -222,6 +267,11 @@ const isNegativeLE = (num, modulo) => (mod(num, modulo) & _1n) === _1n;

exports.FpDiv = FpDiv;
// NOTE: very fragile, always bench. Major performance points:
// - NonNormalized ops
// - Object.freeze
// - same shape of object (don't add/remove keys)
// This function returns True whenever the value x is a square in the field F.
function FpIsSquare(f) {
const legendreConst = (f.ORDER - _1n) / _2n; // Integer arithmetic
return (x) => {
const p = f.pow(x, legendreConst);
return f.equals(p, f.ZERO) || f.equals(p, f.ONE);
};
}
exports.FpIsSquare = FpIsSquare;
function Fp(ORDER, bitLen, isLE = false, redef = {}) {

@@ -233,3 +283,3 @@ if (ORDER <= _0n)

throw new Error('Field lengths over 2048 bytes are not supported');
const sqrtP = (num) => sqrt(num, ORDER);
const sqrtP = FpSqrt(ORDER);
const f = Object.freeze({

@@ -264,3 +314,3 @@ ORDER,

invert: (num) => invert(num, ORDER),
sqrt: redef.sqrt || sqrtP,
sqrt: redef.sqrt || ((n) => sqrtP(f, n)),
invertBatch: (lst) => FpInvertBatch(f, lst),

@@ -280,86 +330,15 @@ // TODO: do we really need constant cmov?

exports.Fp = Fp;
// TODO: re-use in bls/generic sqrt for field/etc?
// Something like sqrtUnsafe which always returns value, but sqrt throws exception if non-square
// From draft-irtf-cfrg-hash-to-curve-16
function FpSqrt(Fp) {
// NOTE: it requires another sqrt for constant precomputes, but no need for roots of unity,
// probably we can simply bls code using it
const q = Fp.ORDER;
const squareConst = (q - _1n) / _2n;
// is_square(x) := { True, if x^((q - 1) / 2) is 0 or 1 in F;
// { False, otherwise.
let isSquare = (x) => {
const p = Fp.pow(x, squareConst);
return Fp.equals(p, Fp.ZERO) || Fp.equals(p, Fp.ONE);
};
// Constant-time Tonelli-Shanks algorithm
let l = _0n;
for (let o = q - _1n; o % _2n === _0n; o /= _2n)
l += _1n;
const c1 = l; // 1. c1, the largest integer such that 2^c1 divides q - 1.
const c2 = (q - _1n) / _2n ** c1; // 2. c2 = (q - 1) / (2^c1) # Integer arithmetic
const c3 = (c2 - _1n) / _2n; // 3. c3 = (c2 - 1) / 2 # Integer arithmetic
// 4. c4, a non-square value in F
// 5. c5 = c4^c2 in F
let c4 = Fp.ONE;
while (isSquare(c4))
c4 = Fp.add(c4, Fp.ONE);
const c5 = Fp.pow(c4, c2);
let sqrt = (x) => {
let z = Fp.pow(x, c3); // 1. z = x^c3
let t = Fp.square(z); // 2. t = z * z
t = Fp.mul(t, x); // 3. t = t * x
z = Fp.mul(z, x); // 4. z = z * x
let b = t; // 5. b = t
let c = c5; // 6. c = c5
// 7. for i in (c1, c1 - 1, ..., 2):
for (let i = c1; i > 1; i--) {
// 8. for j in (1, 2, ..., i - 2):
// 9. b = b * b
for (let j = _1n; j < i - _1n; i++)
b = Fp.square(b);
const e = Fp.equals(b, Fp.ONE); // 10. e = b == 1
const zt = Fp.mul(z, c); // 11. zt = z * c
z = Fp.cmov(zt, z, e); // 12. z = CMOV(zt, z, e)
c = Fp.square(c); // 13. c = c * c
let tt = Fp.mul(t, c); // 14. tt = t * c
t = Fp.cmov(tt, t, e); // 15. t = CMOV(tt, t, e)
b = t; // 16. b = t
}
return z; // 17. return z
};
if (q % _4n === _3n) {
const c1 = (q + _1n) / _4n; // 1. c1 = (q + 1) / 4 # Integer arithmetic
sqrt = (x) => Fp.pow(x, c1);
}
else if (q % _8n === _5n) {
const c1 = Fp.sqrt(Fp.negate(Fp.ONE)); // 1. c1 = sqrt(-1) in F, i.e., (c1^2) == -1 in F
const c2 = (q + _3n) / _8n; // 2. c2 = (q + 3) / 8 # Integer arithmetic
sqrt = (x) => {
let tv1 = Fp.pow(x, c2); // 1. tv1 = x^c2
let tv2 = Fp.mul(tv1, c1); // 2. tv2 = tv1 * c1
let e = Fp.equals(Fp.square(tv1), x); // 3. e = (tv1^2) == x
return Fp.cmov(tv2, tv1, e); // 4. z = CMOV(tv2, tv1, e)
};
}
else if (Fp.ORDER % _16n === _9n) {
const c1 = Fp.sqrt(Fp.negate(Fp.ONE)); // 1. c1 = sqrt(-1) in F, i.e., (c1^2) == -1 in F
const c2 = Fp.sqrt(c1); // 2. c2 = sqrt(c1) in F, i.e., (c2^2) == c1 in F
const c3 = Fp.sqrt(Fp.negate(c1)); // 3. c3 = sqrt(-c1) in F, i.e., (c3^2) == -c1 in F
const c4 = (Fp.ORDER + _7n) / _16n; // 4. c4 = (q + 7) / 16 # Integer arithmetic
sqrt = (x) => {
let tv1 = Fp.pow(x, c4); // 1. tv1 = x^c4
let tv2 = Fp.mul(c1, tv1); // 2. tv2 = c1 * tv1
const tv3 = Fp.mul(c2, tv1); // 3. tv3 = c2 * tv1
let tv4 = Fp.mul(c3, tv1); // 4. tv4 = c3 * tv1
const e1 = Fp.equals(Fp.square(tv2), x); // 5. e1 = (tv2^2) == x
const e2 = Fp.equals(Fp.square(tv3), x); // 6. e2 = (tv3^2) == x
tv1 = Fp.cmov(tv1, tv2, e1); // 7. tv1 = CMOV(tv1, tv2, e1) # Select tv2 if (tv2^2) == x
tv2 = Fp.cmov(tv4, tv3, e2); // 8. tv2 = CMOV(tv4, tv3, e2) # Select tv3 if (tv3^2) == x
const e3 = Fp.equals(Fp.square(tv2), x); // 9. e3 = (tv2^2) == x
return Fp.cmov(tv1, tv2, e3); // 10. z = CMOV(tv1, tv2, e3) # Select the sqrt from tv1 and tv2
};
}
return { sqrt, isSquare };
function FpSqrtOdd(Fp, elm) {
if (!Fp.isOdd)
throw new Error(`Field doesn't have isOdd`);
const root = Fp.sqrt(elm);
return Fp.isOdd(root) ? root : Fp.negate(root);
}
exports.FpSqrt = FpSqrt;
exports.FpSqrtOdd = FpSqrtOdd;
function FpSqrtEven(Fp, elm) {
if (!Fp.isOdd)
throw new Error(`Field doesn't have isOdd`);
const root = Fp.sqrt(elm);
return Fp.isOdd(root) ? Fp.negate(root) : root;
}
exports.FpSqrtEven = FpSqrtEven;

4

lib/abstract/utils.d.ts

@@ -9,3 +9,5 @@ /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */

outputLen: number;
create(): any;
create(opts?: {
dkLen?: number;
}): any;
};

@@ -12,0 +14,0 @@ export declare type BasicCurve<T> = {

2

lib/bls12-381.d.ts
import { CurveFn } from './abstract/bls.js';
import * as mod from './abstract/modular.js';
declare const Fp: Readonly<mod.Field<bigint>>;
declare const Fp: Readonly<mod.Field<bigint> & Required<Pick<mod.Field<bigint>, "isOdd">>>;
declare type Fp = bigint;

@@ -5,0 +5,0 @@ declare type BigintTuple = [bigint, bigint];

2

lib/bls12-381.js

@@ -821,3 +821,3 @@ "use strict";

// expand_message_xmd
expand: true,
expand: 'xmd',
// Hash functions for: expand_message_xmd is appropriate for use with a

@@ -824,0 +824,0 @@ // wide range of hash functions, including SHA-2, SHA-3, BLAKE2, and others.

77

lib/ed25519.js

@@ -84,3 +84,70 @@ "use strict";

];
const Fp = (0, modular_js_1.Fp)(ED25519_P);
const Fp = (0, modular_js_1.Fp)(ED25519_P, undefined, true);
// Hash To Curve Elligator2 Map (NOTE: different from ristretto255 elligator)
// NOTE: very important part is usage of FpSqrtEven for ELL2_C1_EDWARDS, since
// SageMath returns different root first and everything falls apart
const ELL2_C1 = (Fp.ORDER + BigInt(3)) / BigInt(8); // 1. c1 = (q + 3) / 8 # Integer arithmetic
const ELL2_C2 = Fp.pow(_2n, ELL2_C1); // 2. c2 = 2^c1
const ELL2_C3 = Fp.sqrt(Fp.negate(Fp.ONE)); // 3. c3 = sqrt(-1)
const ELL2_C4 = (Fp.ORDER - BigInt(5)) / BigInt(8); // 4. c4 = (q - 5) / 8 # Integer arithmetic
const ELL2_J = BigInt(486662);
// prettier-ignore
function map_to_curve_elligator2_curve25519(u) {
let tv1 = Fp.square(u); // 1. tv1 = u^2
tv1 = Fp.mul(tv1, _2n); // 2. tv1 = 2 * tv1
let xd = Fp.add(tv1, Fp.ONE); // 3. xd = tv1 + 1 # Nonzero: -1 is square (mod p), tv1 is not
let x1n = Fp.negate(ELL2_J); // 4. x1n = -J # x1 = x1n / xd = -J / (1 + 2 * u^2)
let tv2 = Fp.square(xd); // 5. tv2 = xd^2
let gxd = Fp.mul(tv2, xd); // 6. gxd = tv2 * xd # gxd = xd^3
let gx1 = Fp.mul(tv1, ELL2_J); // 7. gx1 = J * tv1 # x1n + J * xd
gx1 = Fp.mul(gx1, x1n); // 8. gx1 = gx1 * x1n # x1n^2 + J * x1n * xd
gx1 = Fp.add(gx1, tv2); // 9. gx1 = gx1 + tv2 # x1n^2 + J * x1n * xd + xd^2
gx1 = Fp.mul(gx1, x1n); // 10. gx1 = gx1 * x1n # x1n^3 + J * x1n^2 * xd + x1n * xd^2
let tv3 = Fp.square(gxd); // 11. tv3 = gxd^2
tv2 = Fp.square(tv3); // 12. tv2 = tv3^2 # gxd^4
tv3 = Fp.mul(tv3, gxd); // 13. tv3 = tv3 * gxd # gxd^3
tv3 = Fp.mul(tv3, gx1); // 14. tv3 = tv3 * gx1 # gx1 * gxd^3
tv2 = Fp.mul(tv2, tv3); // 15. tv2 = tv2 * tv3 # gx1 * gxd^7
let y11 = Fp.pow(tv2, ELL2_C4); // 16. y11 = tv2^c4 # (gx1 * gxd^7)^((p - 5) / 8)
y11 = Fp.mul(y11, tv3); // 17. y11 = y11 * tv3 # gx1*gxd^3*(gx1*gxd^7)^((p-5)/8)
let y12 = Fp.mul(y11, ELL2_C3); // 18. y12 = y11 * c3
tv2 = Fp.square(y11); // 19. tv2 = y11^2
tv2 = Fp.mul(tv2, gxd); // 20. tv2 = tv2 * gxd
let e1 = Fp.equals(tv2, gx1); // 21. e1 = tv2 == gx1
let y1 = Fp.cmov(y12, y11, e1); // 22. y1 = CMOV(y12, y11, e1) # If g(x1) is square, this is its sqrt
let x2n = Fp.mul(x1n, tv1); // 23. x2n = x1n * tv1 # x2 = x2n / xd = 2 * u^2 * x1n / xd
let y21 = Fp.mul(y11, u); // 24. y21 = y11 * u
y21 = Fp.mul(y21, ELL2_C2); // 25. y21 = y21 * c2
let y22 = Fp.mul(y21, ELL2_C3); // 26. y22 = y21 * c3
let gx2 = Fp.mul(gx1, tv1); // 27. gx2 = gx1 * tv1 # g(x2) = gx2 / gxd = 2 * u^2 * g(x1)
tv2 = Fp.square(y21); // 28. tv2 = y21^2
tv2 = Fp.mul(tv2, gxd); // 29. tv2 = tv2 * gxd
let e2 = Fp.equals(tv2, gx2); // 30. e2 = tv2 == gx2
let y2 = Fp.cmov(y22, y21, e2); // 31. y2 = CMOV(y22, y21, e2) # If g(x2) is square, this is its sqrt
tv2 = Fp.square(y1); // 32. tv2 = y1^2
tv2 = Fp.mul(tv2, gxd); // 33. tv2 = tv2 * gxd
let e3 = Fp.equals(tv2, gx1); // 34. e3 = tv2 == gx1
let xn = Fp.cmov(x2n, x1n, e3); // 35. xn = CMOV(x2n, x1n, e3) # If e3, x = x1, else x = x2
let y = Fp.cmov(y2, y1, e3); // 36. y = CMOV(y2, y1, e3) # If e3, y = y1, else y = y2
let e4 = Fp.isOdd(y); // 37. e4 = sgn0(y) == 1 # Fix sign of y
y = Fp.cmov(y, Fp.negate(y), e3 !== e4); // 38. y = CMOV(y, -y, e3 XOR e4)
return { xMn: xn, xMd: xd, yMn: y, yMd: 1n }; // 39. return (xn, xd, y, 1)
}
const ELL2_C1_EDWARDS = (0, modular_js_1.FpSqrtEven)(Fp, Fp.negate(BigInt(486664))); // sgn0(c1) MUST equal 0
function map_to_curve_elligator2_edwards25519(u) {
const { xMn, xMd, yMn, yMd } = map_to_curve_elligator2_curve25519(u); // 1. (xMn, xMd, yMn, yMd) = map_to_curve_elligator2_curve25519(u)
let xn = Fp.mul(xMn, yMd); // 2. xn = xMn * yMd
xn = Fp.mul(xn, ELL2_C1_EDWARDS); // 3. xn = xn * c1
let xd = Fp.mul(xMd, yMn); // 4. xd = xMd * yMn # xn / xd = c1 * xM / yM
let yn = Fp.sub(xMn, xMd); // 5. yn = xMn - xMd
let yd = Fp.add(xMn, xMd); // 6. yd = xMn + xMd # (n / d - 1) / (n / d + 1) = (n - d) / (n + d)
let tv1 = Fp.mul(xd, yd); // 7. tv1 = xd * yd
let e = Fp.equals(tv1, Fp.ZERO); // 8. e = tv1 == 0
xn = Fp.cmov(xn, Fp.ZERO, e); // 9. xn = CMOV(xn, 0, e)
xd = Fp.cmov(xd, Fp.ONE, e); // 10. xd = CMOV(xd, 1, e)
yn = Fp.cmov(yn, Fp.ONE, e); // 11. yn = CMOV(yn, 1, e)
yd = Fp.cmov(yd, Fp.ONE, e); // 12. yd = CMOV(yd, 1, e)
const inv = Fp.invertBatch([xd, yd]); // batch division
return { x: Fp.mul(xn, inv[0]), y: Fp.mul(yn, inv[1]) }; // 13. return (xn, xd, yn, yd)
}
const ED25519_DEF = {

@@ -114,10 +181,6 @@ // Param: a

k: 128,
expand: true,
expand: 'xmd',
hash: sha512_1.sha512,
},
mapToCurve: (scalars) => {
throw new Error('Not supported yet');
// const { x, y } = calcElligatorRistrettoMap(scalars[0]).toAffine();
// return { x, y };
},
mapToCurve: (scalars) => map_to_curve_elligator2_edwards25519(scalars[0]),
};

@@ -124,0 +187,0 @@ exports.ed25519 = (0, edwards_js_1.twistedEdwards)(ED25519_DEF);

85

lib/ed448.js

@@ -51,2 +51,76 @@ "use strict";

}
const Fp = (0, modular_js_1.Fp)(ed448P, 456, true);
// Hash To Curve Elligator2 Map
const ELL2_C1 = (Fp.ORDER - BigInt(3)) / BigInt(4); // 1. c1 = (q - 3) / 4 # Integer arithmetic
const ELL2_J = BigInt(156326);
function map_to_curve_elligator2_curve448(u) {
let tv1 = Fp.square(u); // 1. tv1 = u^2
let e1 = Fp.equals(tv1, Fp.ONE); // 2. e1 = tv1 == 1
tv1 = Fp.cmov(tv1, Fp.ZERO, e1); // 3. tv1 = CMOV(tv1, 0, e1) # If Z * u^2 == -1, set tv1 = 0
let xd = Fp.sub(Fp.ONE, tv1); // 4. xd = 1 - tv1
let x1n = Fp.negate(ELL2_J); // 5. x1n = -J
let tv2 = Fp.square(xd); // 6. tv2 = xd^2
let gxd = Fp.mul(tv2, xd); // 7. gxd = tv2 * xd # gxd = xd^3
let gx1 = Fp.mul(tv1, Fp.negate(ELL2_J)); // 8. gx1 = -J * tv1 # x1n + J * xd
gx1 = Fp.mul(gx1, x1n); // 9. gx1 = gx1 * x1n # x1n^2 + J * x1n * xd
gx1 = Fp.add(gx1, tv2); // 10. gx1 = gx1 + tv2 # x1n^2 + J * x1n * xd + xd^2
gx1 = Fp.mul(gx1, x1n); // 11. gx1 = gx1 * x1n # x1n^3 + J * x1n^2 * xd + x1n * xd^2
let tv3 = Fp.square(gxd); // 12. tv3 = gxd^2
tv2 = Fp.mul(gx1, gxd); // 13. tv2 = gx1 * gxd # gx1 * gxd
tv3 = Fp.mul(tv3, tv2); // 14. tv3 = tv3 * tv2 # gx1 * gxd^3
let y1 = Fp.pow(tv3, ELL2_C1); // 15. y1 = tv3^c1 # (gx1 * gxd^3)^((p - 3) / 4)
y1 = Fp.mul(y1, tv2); // 16. y1 = y1 * tv2 # gx1 * gxd * (gx1 * gxd^3)^((p - 3) / 4)
let x2n = Fp.mul(x1n, Fp.negate(tv1)); // 17. x2n = -tv1 * x1n # x2 = x2n / xd = -1 * u^2 * x1n / xd
let y2 = Fp.mul(y1, u); // 18. y2 = y1 * u
y2 = Fp.cmov(y2, Fp.ZERO, e1); // 19. y2 = CMOV(y2, 0, e1)
tv2 = Fp.square(y1); // 20. tv2 = y1^2
tv2 = Fp.mul(tv2, gxd); // 21. tv2 = tv2 * gxd
let e2 = Fp.equals(tv2, gx1); // 22. e2 = tv2 == gx1
let xn = Fp.cmov(x2n, x1n, e2); // 23. xn = CMOV(x2n, x1n, e2) # If e2, x = x1, else x = x2
let y = Fp.cmov(y2, y1, e2); // 24. y = CMOV(y2, y1, e2) # If e2, y = y1, else y = y2
let e3 = Fp.isOdd(y); // 25. e3 = sgn0(y) == 1 # Fix sign of y
y = Fp.cmov(y, Fp.negate(y), e2 !== e3); // 26. y = CMOV(y, -y, e2 XOR e3)
return { xn, xd, yn: y, yd: Fp.ONE }; // 27. return (xn, xd, y, 1)
}
function map_to_curve_elligator2_edwards448(u) {
let { xn, xd, yn, yd } = map_to_curve_elligator2_curve448(u); // 1. (xn, xd, yn, yd) = map_to_curve_elligator2_curve448(u)
let xn2 = Fp.square(xn); // 2. xn2 = xn^2
let xd2 = Fp.square(xd); // 3. xd2 = xd^2
let xd4 = Fp.square(xd2); // 4. xd4 = xd2^2
let yn2 = Fp.square(yn); // 5. yn2 = yn^2
let yd2 = Fp.square(yd); // 6. yd2 = yd^2
let xEn = Fp.sub(xn2, xd2); // 7. xEn = xn2 - xd2
let tv2 = Fp.sub(xEn, xd2); // 8. tv2 = xEn - xd2
xEn = Fp.mul(xEn, xd2); // 9. xEn = xEn * xd2
xEn = Fp.mul(xEn, yd); // 10. xEn = xEn * yd
xEn = Fp.mul(xEn, yn); // 11. xEn = xEn * yn
xEn = Fp.mul(xEn, 4n); // 12. xEn = xEn * 4
tv2 = Fp.mul(tv2, xn2); // 13. tv2 = tv2 * xn2
tv2 = Fp.mul(tv2, yd2); // 14. tv2 = tv2 * yd2
let tv3 = Fp.mul(yn2, 4n); // 15. tv3 = 4 * yn2
let tv1 = Fp.add(tv3, yd2); // 16. tv1 = tv3 + yd2
tv1 = Fp.mul(tv1, xd4); // 17. tv1 = tv1 * xd4
let xEd = Fp.add(tv1, tv2); // 18. xEd = tv1 + tv2
tv2 = Fp.mul(tv2, xn); // 19. tv2 = tv2 * xn
let tv4 = Fp.mul(xn, xd4); // 20. tv4 = xn * xd4
let yEn = Fp.sub(tv3, yd2); // 21. yEn = tv3 - yd2
yEn = Fp.mul(yEn, tv4); // 22. yEn = yEn * tv4
yEn = Fp.sub(yEn, tv2); // 23. yEn = yEn - tv2
tv1 = Fp.add(xn2, xd2); // 24. tv1 = xn2 + xd2
tv1 = Fp.mul(tv1, xd2); // 25. tv1 = tv1 * xd2
tv1 = Fp.mul(tv1, xd); // 26. tv1 = tv1 * xd
tv1 = Fp.mul(tv1, yn2); // 27. tv1 = tv1 * yn2
tv1 = Fp.mul(tv1, BigInt(-2)); // 28. tv1 = -2 * tv1
let yEd = Fp.add(tv2, tv1); // 29. yEd = tv2 + tv1
tv4 = Fp.mul(tv4, yd2); // 30. tv4 = tv4 * yd2
yEd = Fp.add(yEd, tv4); // 31. yEd = yEd + tv4
tv1 = Fp.mul(xEd, yEd); // 32. tv1 = xEd * yEd
let e = Fp.equals(tv1, Fp.ZERO); // 33. e = tv1 == 0
xEn = Fp.cmov(xEn, Fp.ZERO, e); // 34. xEn = CMOV(xEn, 0, e)
xEd = Fp.cmov(xEd, Fp.ONE, e); // 35. xEd = CMOV(xEd, 1, e)
yEn = Fp.cmov(yEn, Fp.ONE, e); // 36. yEn = CMOV(yEn, 1, e)
yEd = Fp.cmov(yEd, Fp.ONE, e); // 37. yEd = CMOV(yEd, 1, e)
const inv = Fp.invertBatch([xEd, yEd]); // batch division
return { x: Fp.mul(xEn, inv[0]), y: Fp.mul(yEn, inv[1]) }; // 38. return (xEn, xEd, yEn, yEd)
}
const ED448_DEF = {

@@ -58,3 +132,3 @@ // Param: a

// Finite field 𝔽p over which we'll do calculations; 2n ** 448n - 2n ** 224n - 1n
Fp: (0, modular_js_1.Fp)(ed448P, 456),
Fp,
// Subgroup order: how many points ed448 has; 2n**446n - 13818066809895115352007386748515426880336692474882178609894547503885n

@@ -99,2 +173,11 @@ n: BigInt('181709681073901722637330951972001133588410340171829515070372549795146003961539585716195755291692375963310293709091662304773755859649779'),

},
htfDefaults: {
DST: 'edwards448_XOF:SHAKE256_ELL2_RO_',
p: Fp.ORDER,
m: 1,
k: 224,
expand: 'xof',
hash: sha3_1.shake256,
},
mapToCurve: (scalars) => map_to_curve_elligator2_edwards448(scalars[0]),
};

@@ -101,0 +184,0 @@ exports.ed448 = (0, edwards_js_1.twistedEdwards)(ED448_DEF);

39

lib/esm/abstract/hash-to-curve.js

@@ -13,3 +13,3 @@ /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */

throw new Error('Invalid htf/k');
if (typeof opts.expand !== 'boolean')
if (opts.expand !== 'xmd' && opts.expand !== 'xof' && opts.expand !== undefined)
throw new Error('Invalid htf/expand');

@@ -79,9 +79,27 @@ if (typeof opts.hash !== 'function' || !Number.isSafeInteger(opts.hash.outputLen))

}
// hashes arbitrary-length byte strings to a list of one or more elements of a finite field F
// https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-11#section-5.3
// Inputs:
// msg - a byte string containing the message to hash.
// count - the number of elements of F to output.
// Outputs:
// [u_0, ..., u_(count - 1)], a list of field elements.
export function expand_message_xof(msg, DST, lenInBytes, k, H) {
// https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-16#section-5.3.3
// DST = H('H2C-OVERSIZE-DST-' || a_very_long_DST, Math.ceil((lenInBytes * k) / 8));
if (DST.length > 255) {
const dkLen = Math.ceil((2 * k) / 8);
DST = H.create({ dkLen }).update(stringToBytes('H2C-OVERSIZE-DST-')).update(DST).digest();
}
if (lenInBytes > 65535 || DST.length > 255)
throw new Error('expand_message_xof: invalid lenInBytes');
return (H.create({ dkLen: lenInBytes })
.update(msg)
.update(i2osp(lenInBytes, 2))
// 2. DST_prime = DST || I2OSP(len(DST), 1)
.update(DST)
.update(i2osp(DST.length, 1))
.digest());
}
/**
* Hashes arbitrary-length byte strings to a list of one or more elements of a finite field F
* https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-11#section-5.3
* @param msg a byte string containing the message to hash
* @param count the number of elements of F to output
* @param options `{DST: string, p: bigint, m: number, k: number, expand: 'xmd' | 'xof', hash: H}`
* @returns [u_0, ..., u_(count - 1)], a list of field elements.
*/
export function hash_to_field(msg, count, options) {

@@ -95,5 +113,8 @@ // if options is provided but incomplete, fill any missing fields with the

let pseudo_random_bytes = msg;
if (options.expand) {
if (options.expand === 'xmd') {
pseudo_random_bytes = expand_message_xmd(msg, DST, len_in_bytes, options.hash);
}
else if (options.expand === 'xof') {
pseudo_random_bytes = expand_message_xof(msg, DST, len_in_bytes, options.k, options.hash);
}
const u = new Array(count);

@@ -100,0 +121,0 @@ for (let i = 0; i < count; i++) {

273

lib/esm/abstract/modular.js
/*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
// TODO: remove circular imports
import * as utils from './utils.js';

@@ -7,3 +8,3 @@ // Utilities for modular arithmetics and finite fields

// prettier-ignore
const _4n = BigInt(4), _5n = BigInt(5), _7n = BigInt(7), _8n = BigInt(8);
const _4n = BigInt(4), _5n = BigInt(5), _8n = BigInt(8);
// prettier-ignore

@@ -70,21 +71,62 @@ const _9n = BigInt(9), _16n = BigInt(16);

}
/**
* Calculates Legendre symbol (a | p), which denotes the value of a^((p-1)/2) (mod p).
* * (a | p) ≡ 1 if a is a square (mod p)
* * (a | p) ≡ -1 if a is not a square (mod p)
* * (a | p) ≡ 0 if a ≡ 0 (mod p)
*/
export function legendre(num, fieldPrime) {
return pow(num, (fieldPrime - _1n) / _2n, fieldPrime);
// Tonelli-Shanks algorithm
// https://eprint.iacr.org/2012/685.pdf (page 12)
export function tonelliShanks(P) {
// Legendre constant: used to calculate Legendre symbol (a | p),
// which denotes the value of a^((p-1)/2) (mod p).
// (a | p) ≡ 1 if a is a square (mod p)
// (a | p) ≡ -1 if a is not a square (mod p)
// (a | p) ≡ 0 if a ≡ 0 (mod p)
const legendreC = (P - _1n) / _2n;
let Q, S, Z;
// Step 1: By factoring out powers of 2 from p - 1,
// find q and s such that p - 1 = q2s with q odd
for (Q = P - _1n, S = 0; Q % _2n === _0n; Q /= _2n, S++)
;
// Step 2: Select a non-square z such that (z | p) ≡ -1 and set c ≡ zq
for (Z = _2n; Z < P && pow(Z, legendreC, P) !== P - _1n; Z++)
;
// Fast-path
if (S === 1) {
const p1div4 = (P + _1n) / _4n;
return function tonelliFast(Fp, n) {
const root = Fp.pow(n, p1div4);
if (!Fp.equals(Fp.square(root), n))
throw new Error('Cannot find square root');
return root;
};
}
// Slow-path
const Q1div2 = (Q + _1n) / _2n;
return function tonelliSlow(Fp, n) {
// Step 0: Check that n is indeed a square: (n | p) must be ≡ 1
if (Fp.pow(n, legendreC) !== Fp.ONE)
throw new Error('Cannot find square root');
let s = S;
let c = pow(Z, Q, P);
let r = Fp.pow(n, Q1div2);
let t = Fp.pow(n, Q);
let t2 = Fp.ZERO;
while (!Fp.equals(Fp.sub(t, Fp.ONE), Fp.ZERO)) {
t2 = Fp.square(t);
let i;
for (i = 1; i < s; i++) {
// stop if t2-1 == 0
if (Fp.equals(Fp.sub(t2, Fp.ONE), Fp.ZERO))
break;
// t2 *= t2
t2 = Fp.square(t2);
}
let b = pow(c, BigInt(1 << (s - i - 1)), P);
r = Fp.mul(r, b);
c = mod(b * b, P);
t = Fp.mul(t, c);
s = i;
}
return r;
};
}
/**
* Calculates square root of a number in a finite field.
* √a mod P
*/
// TODO: rewrite as generic Fp function && remove bls versions
export function sqrt(number, modulo) {
// prettier-ignore
const n = number;
const P = modulo;
const p1div4 = (P + _1n) / _4n;
export function FpSqrt(P) {
// NOTE: different algorithms can give different roots, it is up to user to decide which one they want.
// For example there is FpSqrtOdd/FpSqrtEven to choice root based on oddness (used for hash-to-curve).
// P ≡ 3 (mod 4)

@@ -97,46 +139,49 @@ // √n = n^((P+1)/4)

// const NUM = 72057594037927816n;
// TODO: fix sqrtMod in secp256k1
const root = pow(n, p1div4, P);
if (mod(root * root, modulo) !== number)
throw new Error('Cannot find square root');
return root;
const p1div4 = (P + _1n) / _4n;
return function sqrt3mod4(Fp, n) {
const root = Fp.pow(n, p1div4);
// Throw if root**2 != n
if (!Fp.equals(Fp.square(root), n))
throw new Error('Cannot find square root');
return root;
};
}
// P ≡ 5 (mod 8)
// Atkin algorithm for q ≡ 5 (mod 8), https://eprint.iacr.org/2012/685.pdf (page 10)
if (P % _8n === _5n) {
const n2 = mod(n * _2n, P);
const v = pow(n2, (P - _5n) / _8n, P);
const nv = mod(n * v, P);
const i = mod(_2n * nv * v, P);
const r = mod(nv * (i - _1n), P);
return r;
const c1 = (P - _5n) / _8n;
return function sqrt5mod8(Fp, n) {
const n2 = Fp.mul(n, _2n);
const v = Fp.pow(n2, c1);
const nv = Fp.mul(n, v);
const i = Fp.mul(Fp.mul(nv, _2n), v);
const root = Fp.mul(nv, Fp.sub(i, Fp.ONE));
if (!Fp.equals(Fp.square(root), n))
throw new Error('Cannot find square root');
return root;
};
}
// P ≡ 9 (mod 16)
if (P % _16n === _9n) {
// NOTE: tonelli is too slow for bls-Fp2 calculations even on start
// Means we cannot use sqrt for constants at all!
//
// const c1 = Fp.sqrt(Fp.negate(Fp.ONE)); // 1. c1 = sqrt(-1) in F, i.e., (c1^2) == -1 in F
// const c2 = Fp.sqrt(c1); // 2. c2 = sqrt(c1) in F, i.e., (c2^2) == c1 in F
// const c3 = Fp.sqrt(Fp.negate(c1)); // 3. c3 = sqrt(-c1) in F, i.e., (c3^2) == -c1 in F
// const c4 = (P + _7n) / _16n; // 4. c4 = (q + 7) / 16 # Integer arithmetic
// sqrt = (x) => {
// let tv1 = Fp.pow(x, c4); // 1. tv1 = x^c4
// let tv2 = Fp.mul(c1, tv1); // 2. tv2 = c1 * tv1
// const tv3 = Fp.mul(c2, tv1); // 3. tv3 = c2 * tv1
// let tv4 = Fp.mul(c3, tv1); // 4. tv4 = c3 * tv1
// const e1 = Fp.equals(Fp.square(tv2), x); // 5. e1 = (tv2^2) == x
// const e2 = Fp.equals(Fp.square(tv3), x); // 6. e2 = (tv3^2) == x
// tv1 = Fp.cmov(tv1, tv2, e1); // 7. tv1 = CMOV(tv1, tv2, e1) # Select tv2 if (tv2^2) == x
// tv2 = Fp.cmov(tv4, tv3, e2); // 8. tv2 = CMOV(tv4, tv3, e2) # Select tv3 if (tv3^2) == x
// const e3 = Fp.equals(Fp.square(tv2), x); // 9. e3 = (tv2^2) == x
// return Fp.cmov(tv1, tv2, e3); // 10. z = CMOV(tv1, tv2, e3) # Select the sqrt from tv1 and tv2
// }
}
// Other cases: Tonelli-Shanks algorithm
if (legendre(n, P) !== _1n)
throw new Error('Cannot find square root');
let q, s, z;
for (q = P - _1n, s = 0; q % _2n === _0n; q /= _2n, s++)
;
if (s === 1)
return pow(n, p1div4, P);
for (z = _2n; z < P && legendre(z, P) !== P - _1n; z++)
;
let c = pow(z, q, P);
let r = pow(n, (q + _1n) / _2n, P);
let t = pow(n, q, P);
let t2 = _0n;
while (mod(t - _1n, P) !== _0n) {
t2 = mod(t * t, P);
let i;
for (i = 1; i < s; i++) {
if (mod(t2 - _1n, P) === _0n)
break;
t2 = mod(t2 * t2, P);
}
let b = pow(c, BigInt(1 << (s - i - 1)), P);
r = mod(r * b, P);
c = mod(b * b, P);
t = mod(t * c, P);
s = i;
}
return r;
return tonelliShanks(P);
}

@@ -208,6 +253,10 @@ // Little-endian check for first LE bit (last BE bit);

}
// NOTE: very fragile, always bench. Major performance points:
// - NonNormalized ops
// - Object.freeze
// - same shape of object (don't add/remove keys)
// This function returns True whenever the value x is a square in the field F.
export function FpIsSquare(f) {
const legendreConst = (f.ORDER - _1n) / _2n; // Integer arithmetic
return (x) => {
const p = f.pow(x, legendreConst);
return f.equals(p, f.ZERO) || f.equals(p, f.ONE);
};
}
export function Fp(ORDER, bitLen, isLE = false, redef = {}) {

@@ -219,3 +268,3 @@ if (ORDER <= _0n)

throw new Error('Field lengths over 2048 bytes are not supported');
const sqrtP = (num) => sqrt(num, ORDER);
const sqrtP = FpSqrt(ORDER);
const f = Object.freeze({

@@ -250,3 +299,3 @@ ORDER,

invert: (num) => invert(num, ORDER),
sqrt: redef.sqrt || sqrtP,
sqrt: redef.sqrt || ((n) => sqrtP(f, n)),
invertBatch: (lst) => FpInvertBatch(f, lst),

@@ -265,85 +314,13 @@ // TODO: do we really need constant cmov?

}
// TODO: re-use in bls/generic sqrt for field/etc?
// Something like sqrtUnsafe which always returns value, but sqrt throws exception if non-square
// From draft-irtf-cfrg-hash-to-curve-16
export function FpSqrt(Fp) {
// NOTE: it requires another sqrt for constant precomputes, but no need for roots of unity,
// probably we can simply bls code using it
const q = Fp.ORDER;
const squareConst = (q - _1n) / _2n;
// is_square(x) := { True, if x^((q - 1) / 2) is 0 or 1 in F;
// { False, otherwise.
let isSquare = (x) => {
const p = Fp.pow(x, squareConst);
return Fp.equals(p, Fp.ZERO) || Fp.equals(p, Fp.ONE);
};
// Constant-time Tonelli-Shanks algorithm
let l = _0n;
for (let o = q - _1n; o % _2n === _0n; o /= _2n)
l += _1n;
const c1 = l; // 1. c1, the largest integer such that 2^c1 divides q - 1.
const c2 = (q - _1n) / _2n ** c1; // 2. c2 = (q - 1) / (2^c1) # Integer arithmetic
const c3 = (c2 - _1n) / _2n; // 3. c3 = (c2 - 1) / 2 # Integer arithmetic
// 4. c4, a non-square value in F
// 5. c5 = c4^c2 in F
let c4 = Fp.ONE;
while (isSquare(c4))
c4 = Fp.add(c4, Fp.ONE);
const c5 = Fp.pow(c4, c2);
let sqrt = (x) => {
let z = Fp.pow(x, c3); // 1. z = x^c3
let t = Fp.square(z); // 2. t = z * z
t = Fp.mul(t, x); // 3. t = t * x
z = Fp.mul(z, x); // 4. z = z * x
let b = t; // 5. b = t
let c = c5; // 6. c = c5
// 7. for i in (c1, c1 - 1, ..., 2):
for (let i = c1; i > 1; i--) {
// 8. for j in (1, 2, ..., i - 2):
// 9. b = b * b
for (let j = _1n; j < i - _1n; i++)
b = Fp.square(b);
const e = Fp.equals(b, Fp.ONE); // 10. e = b == 1
const zt = Fp.mul(z, c); // 11. zt = z * c
z = Fp.cmov(zt, z, e); // 12. z = CMOV(zt, z, e)
c = Fp.square(c); // 13. c = c * c
let tt = Fp.mul(t, c); // 14. tt = t * c
t = Fp.cmov(tt, t, e); // 15. t = CMOV(tt, t, e)
b = t; // 16. b = t
}
return z; // 17. return z
};
if (q % _4n === _3n) {
const c1 = (q + _1n) / _4n; // 1. c1 = (q + 1) / 4 # Integer arithmetic
sqrt = (x) => Fp.pow(x, c1);
}
else if (q % _8n === _5n) {
const c1 = Fp.sqrt(Fp.negate(Fp.ONE)); // 1. c1 = sqrt(-1) in F, i.e., (c1^2) == -1 in F
const c2 = (q + _3n) / _8n; // 2. c2 = (q + 3) / 8 # Integer arithmetic
sqrt = (x) => {
let tv1 = Fp.pow(x, c2); // 1. tv1 = x^c2
let tv2 = Fp.mul(tv1, c1); // 2. tv2 = tv1 * c1
let e = Fp.equals(Fp.square(tv1), x); // 3. e = (tv1^2) == x
return Fp.cmov(tv2, tv1, e); // 4. z = CMOV(tv2, tv1, e)
};
}
else if (Fp.ORDER % _16n === _9n) {
const c1 = Fp.sqrt(Fp.negate(Fp.ONE)); // 1. c1 = sqrt(-1) in F, i.e., (c1^2) == -1 in F
const c2 = Fp.sqrt(c1); // 2. c2 = sqrt(c1) in F, i.e., (c2^2) == c1 in F
const c3 = Fp.sqrt(Fp.negate(c1)); // 3. c3 = sqrt(-c1) in F, i.e., (c3^2) == -c1 in F
const c4 = (Fp.ORDER + _7n) / _16n; // 4. c4 = (q + 7) / 16 # Integer arithmetic
sqrt = (x) => {
let tv1 = Fp.pow(x, c4); // 1. tv1 = x^c4
let tv2 = Fp.mul(c1, tv1); // 2. tv2 = c1 * tv1
const tv3 = Fp.mul(c2, tv1); // 3. tv3 = c2 * tv1
let tv4 = Fp.mul(c3, tv1); // 4. tv4 = c3 * tv1
const e1 = Fp.equals(Fp.square(tv2), x); // 5. e1 = (tv2^2) == x
const e2 = Fp.equals(Fp.square(tv3), x); // 6. e2 = (tv3^2) == x
tv1 = Fp.cmov(tv1, tv2, e1); // 7. tv1 = CMOV(tv1, tv2, e1) # Select tv2 if (tv2^2) == x
tv2 = Fp.cmov(tv4, tv3, e2); // 8. tv2 = CMOV(tv4, tv3, e2) # Select tv3 if (tv3^2) == x
const e3 = Fp.equals(Fp.square(tv2), x); // 9. e3 = (tv2^2) == x
return Fp.cmov(tv1, tv2, e3); // 10. z = CMOV(tv1, tv2, e3) # Select the sqrt from tv1 and tv2
};
}
return { sqrt, isSquare };
export function FpSqrtOdd(Fp, elm) {
if (!Fp.isOdd)
throw new Error(`Field doesn't have isOdd`);
const root = Fp.sqrt(elm);
return Fp.isOdd(root) ? root : Fp.negate(root);
}
export function FpSqrtEven(Fp, elm) {
if (!Fp.isOdd)
throw new Error(`Field doesn't have isOdd`);
const root = Fp.sqrt(elm);
return Fp.isOdd(root) ? Fp.negate(root) : root;
}

2

lib/esm/bls12-381.js

@@ -818,3 +818,3 @@ /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */

// expand_message_xmd
expand: true,
expand: 'xmd',
// Hash functions for: expand_message_xmd is appropriate for use with a

@@ -821,0 +821,0 @@ // wide range of hash functions, including SHA-2, SHA-3, BLAKE2, and others.

79

lib/esm/ed25519.js

@@ -6,3 +6,3 @@ /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */

import { montgomery } from './abstract/montgomery.js';
import { mod, pow2, isNegativeLE, Fp as Field } from './abstract/modular.js';
import { mod, pow2, isNegativeLE, Fp as Field, FpSqrtEven } from './abstract/modular.js';
import { ensureBytes, equalBytes, bytesToHex, bytesToNumberLE, numberToBytesLE, } from './abstract/utils.js';

@@ -82,3 +82,70 @@ /**

];
const Fp = Field(ED25519_P);
const Fp = Field(ED25519_P, undefined, true);
// Hash To Curve Elligator2 Map (NOTE: different from ristretto255 elligator)
// NOTE: very important part is usage of FpSqrtEven for ELL2_C1_EDWARDS, since
// SageMath returns different root first and everything falls apart
const ELL2_C1 = (Fp.ORDER + BigInt(3)) / BigInt(8); // 1. c1 = (q + 3) / 8 # Integer arithmetic
const ELL2_C2 = Fp.pow(_2n, ELL2_C1); // 2. c2 = 2^c1
const ELL2_C3 = Fp.sqrt(Fp.negate(Fp.ONE)); // 3. c3 = sqrt(-1)
const ELL2_C4 = (Fp.ORDER - BigInt(5)) / BigInt(8); // 4. c4 = (q - 5) / 8 # Integer arithmetic
const ELL2_J = BigInt(486662);
// prettier-ignore
function map_to_curve_elligator2_curve25519(u) {
let tv1 = Fp.square(u); // 1. tv1 = u^2
tv1 = Fp.mul(tv1, _2n); // 2. tv1 = 2 * tv1
let xd = Fp.add(tv1, Fp.ONE); // 3. xd = tv1 + 1 # Nonzero: -1 is square (mod p), tv1 is not
let x1n = Fp.negate(ELL2_J); // 4. x1n = -J # x1 = x1n / xd = -J / (1 + 2 * u^2)
let tv2 = Fp.square(xd); // 5. tv2 = xd^2
let gxd = Fp.mul(tv2, xd); // 6. gxd = tv2 * xd # gxd = xd^3
let gx1 = Fp.mul(tv1, ELL2_J); // 7. gx1 = J * tv1 # x1n + J * xd
gx1 = Fp.mul(gx1, x1n); // 8. gx1 = gx1 * x1n # x1n^2 + J * x1n * xd
gx1 = Fp.add(gx1, tv2); // 9. gx1 = gx1 + tv2 # x1n^2 + J * x1n * xd + xd^2
gx1 = Fp.mul(gx1, x1n); // 10. gx1 = gx1 * x1n # x1n^3 + J * x1n^2 * xd + x1n * xd^2
let tv3 = Fp.square(gxd); // 11. tv3 = gxd^2
tv2 = Fp.square(tv3); // 12. tv2 = tv3^2 # gxd^4
tv3 = Fp.mul(tv3, gxd); // 13. tv3 = tv3 * gxd # gxd^3
tv3 = Fp.mul(tv3, gx1); // 14. tv3 = tv3 * gx1 # gx1 * gxd^3
tv2 = Fp.mul(tv2, tv3); // 15. tv2 = tv2 * tv3 # gx1 * gxd^7
let y11 = Fp.pow(tv2, ELL2_C4); // 16. y11 = tv2^c4 # (gx1 * gxd^7)^((p - 5) / 8)
y11 = Fp.mul(y11, tv3); // 17. y11 = y11 * tv3 # gx1*gxd^3*(gx1*gxd^7)^((p-5)/8)
let y12 = Fp.mul(y11, ELL2_C3); // 18. y12 = y11 * c3
tv2 = Fp.square(y11); // 19. tv2 = y11^2
tv2 = Fp.mul(tv2, gxd); // 20. tv2 = tv2 * gxd
let e1 = Fp.equals(tv2, gx1); // 21. e1 = tv2 == gx1
let y1 = Fp.cmov(y12, y11, e1); // 22. y1 = CMOV(y12, y11, e1) # If g(x1) is square, this is its sqrt
let x2n = Fp.mul(x1n, tv1); // 23. x2n = x1n * tv1 # x2 = x2n / xd = 2 * u^2 * x1n / xd
let y21 = Fp.mul(y11, u); // 24. y21 = y11 * u
y21 = Fp.mul(y21, ELL2_C2); // 25. y21 = y21 * c2
let y22 = Fp.mul(y21, ELL2_C3); // 26. y22 = y21 * c3
let gx2 = Fp.mul(gx1, tv1); // 27. gx2 = gx1 * tv1 # g(x2) = gx2 / gxd = 2 * u^2 * g(x1)
tv2 = Fp.square(y21); // 28. tv2 = y21^2
tv2 = Fp.mul(tv2, gxd); // 29. tv2 = tv2 * gxd
let e2 = Fp.equals(tv2, gx2); // 30. e2 = tv2 == gx2
let y2 = Fp.cmov(y22, y21, e2); // 31. y2 = CMOV(y22, y21, e2) # If g(x2) is square, this is its sqrt
tv2 = Fp.square(y1); // 32. tv2 = y1^2
tv2 = Fp.mul(tv2, gxd); // 33. tv2 = tv2 * gxd
let e3 = Fp.equals(tv2, gx1); // 34. e3 = tv2 == gx1
let xn = Fp.cmov(x2n, x1n, e3); // 35. xn = CMOV(x2n, x1n, e3) # If e3, x = x1, else x = x2
let y = Fp.cmov(y2, y1, e3); // 36. y = CMOV(y2, y1, e3) # If e3, y = y1, else y = y2
let e4 = Fp.isOdd(y); // 37. e4 = sgn0(y) == 1 # Fix sign of y
y = Fp.cmov(y, Fp.negate(y), e3 !== e4); // 38. y = CMOV(y, -y, e3 XOR e4)
return { xMn: xn, xMd: xd, yMn: y, yMd: 1n }; // 39. return (xn, xd, y, 1)
}
const ELL2_C1_EDWARDS = FpSqrtEven(Fp, Fp.negate(BigInt(486664))); // sgn0(c1) MUST equal 0
function map_to_curve_elligator2_edwards25519(u) {
const { xMn, xMd, yMn, yMd } = map_to_curve_elligator2_curve25519(u); // 1. (xMn, xMd, yMn, yMd) = map_to_curve_elligator2_curve25519(u)
let xn = Fp.mul(xMn, yMd); // 2. xn = xMn * yMd
xn = Fp.mul(xn, ELL2_C1_EDWARDS); // 3. xn = xn * c1
let xd = Fp.mul(xMd, yMn); // 4. xd = xMd * yMn # xn / xd = c1 * xM / yM
let yn = Fp.sub(xMn, xMd); // 5. yn = xMn - xMd
let yd = Fp.add(xMn, xMd); // 6. yd = xMn + xMd # (n / d - 1) / (n / d + 1) = (n - d) / (n + d)
let tv1 = Fp.mul(xd, yd); // 7. tv1 = xd * yd
let e = Fp.equals(tv1, Fp.ZERO); // 8. e = tv1 == 0
xn = Fp.cmov(xn, Fp.ZERO, e); // 9. xn = CMOV(xn, 0, e)
xd = Fp.cmov(xd, Fp.ONE, e); // 10. xd = CMOV(xd, 1, e)
yn = Fp.cmov(yn, Fp.ONE, e); // 11. yn = CMOV(yn, 1, e)
yd = Fp.cmov(yd, Fp.ONE, e); // 12. yd = CMOV(yd, 1, e)
const inv = Fp.invertBatch([xd, yd]); // batch division
return { x: Fp.mul(xn, inv[0]), y: Fp.mul(yn, inv[1]) }; // 13. return (xn, xd, yn, yd)
}
const ED25519_DEF = {

@@ -112,10 +179,6 @@ // Param: a

k: 128,
expand: true,
expand: 'xmd',
hash: sha512,
},
mapToCurve: (scalars) => {
throw new Error('Not supported yet');
// const { x, y } = calcElligatorRistrettoMap(scalars[0]).toAffine();
// return { x, y };
},
mapToCurve: (scalars) => map_to_curve_elligator2_edwards25519(scalars[0]),
};

@@ -122,0 +185,0 @@ export const ed25519 = twistedEdwards(ED25519_DEF);

87

lib/esm/ed448.js

@@ -5,3 +5,3 @@ /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */

import { twistedEdwards } from './abstract/edwards.js';
import { mod, pow2, Fp } from './abstract/modular.js';
import { mod, pow2, Fp as Field } from './abstract/modular.js';
import { montgomery } from './abstract/montgomery.js';

@@ -49,2 +49,76 @@ /**

}
const Fp = Field(ed448P, 456, true);
// Hash To Curve Elligator2 Map
const ELL2_C1 = (Fp.ORDER - BigInt(3)) / BigInt(4); // 1. c1 = (q - 3) / 4 # Integer arithmetic
const ELL2_J = BigInt(156326);
function map_to_curve_elligator2_curve448(u) {
let tv1 = Fp.square(u); // 1. tv1 = u^2
let e1 = Fp.equals(tv1, Fp.ONE); // 2. e1 = tv1 == 1
tv1 = Fp.cmov(tv1, Fp.ZERO, e1); // 3. tv1 = CMOV(tv1, 0, e1) # If Z * u^2 == -1, set tv1 = 0
let xd = Fp.sub(Fp.ONE, tv1); // 4. xd = 1 - tv1
let x1n = Fp.negate(ELL2_J); // 5. x1n = -J
let tv2 = Fp.square(xd); // 6. tv2 = xd^2
let gxd = Fp.mul(tv2, xd); // 7. gxd = tv2 * xd # gxd = xd^3
let gx1 = Fp.mul(tv1, Fp.negate(ELL2_J)); // 8. gx1 = -J * tv1 # x1n + J * xd
gx1 = Fp.mul(gx1, x1n); // 9. gx1 = gx1 * x1n # x1n^2 + J * x1n * xd
gx1 = Fp.add(gx1, tv2); // 10. gx1 = gx1 + tv2 # x1n^2 + J * x1n * xd + xd^2
gx1 = Fp.mul(gx1, x1n); // 11. gx1 = gx1 * x1n # x1n^3 + J * x1n^2 * xd + x1n * xd^2
let tv3 = Fp.square(gxd); // 12. tv3 = gxd^2
tv2 = Fp.mul(gx1, gxd); // 13. tv2 = gx1 * gxd # gx1 * gxd
tv3 = Fp.mul(tv3, tv2); // 14. tv3 = tv3 * tv2 # gx1 * gxd^3
let y1 = Fp.pow(tv3, ELL2_C1); // 15. y1 = tv3^c1 # (gx1 * gxd^3)^((p - 3) / 4)
y1 = Fp.mul(y1, tv2); // 16. y1 = y1 * tv2 # gx1 * gxd * (gx1 * gxd^3)^((p - 3) / 4)
let x2n = Fp.mul(x1n, Fp.negate(tv1)); // 17. x2n = -tv1 * x1n # x2 = x2n / xd = -1 * u^2 * x1n / xd
let y2 = Fp.mul(y1, u); // 18. y2 = y1 * u
y2 = Fp.cmov(y2, Fp.ZERO, e1); // 19. y2 = CMOV(y2, 0, e1)
tv2 = Fp.square(y1); // 20. tv2 = y1^2
tv2 = Fp.mul(tv2, gxd); // 21. tv2 = tv2 * gxd
let e2 = Fp.equals(tv2, gx1); // 22. e2 = tv2 == gx1
let xn = Fp.cmov(x2n, x1n, e2); // 23. xn = CMOV(x2n, x1n, e2) # If e2, x = x1, else x = x2
let y = Fp.cmov(y2, y1, e2); // 24. y = CMOV(y2, y1, e2) # If e2, y = y1, else y = y2
let e3 = Fp.isOdd(y); // 25. e3 = sgn0(y) == 1 # Fix sign of y
y = Fp.cmov(y, Fp.negate(y), e2 !== e3); // 26. y = CMOV(y, -y, e2 XOR e3)
return { xn, xd, yn: y, yd: Fp.ONE }; // 27. return (xn, xd, y, 1)
}
function map_to_curve_elligator2_edwards448(u) {
let { xn, xd, yn, yd } = map_to_curve_elligator2_curve448(u); // 1. (xn, xd, yn, yd) = map_to_curve_elligator2_curve448(u)
let xn2 = Fp.square(xn); // 2. xn2 = xn^2
let xd2 = Fp.square(xd); // 3. xd2 = xd^2
let xd4 = Fp.square(xd2); // 4. xd4 = xd2^2
let yn2 = Fp.square(yn); // 5. yn2 = yn^2
let yd2 = Fp.square(yd); // 6. yd2 = yd^2
let xEn = Fp.sub(xn2, xd2); // 7. xEn = xn2 - xd2
let tv2 = Fp.sub(xEn, xd2); // 8. tv2 = xEn - xd2
xEn = Fp.mul(xEn, xd2); // 9. xEn = xEn * xd2
xEn = Fp.mul(xEn, yd); // 10. xEn = xEn * yd
xEn = Fp.mul(xEn, yn); // 11. xEn = xEn * yn
xEn = Fp.mul(xEn, 4n); // 12. xEn = xEn * 4
tv2 = Fp.mul(tv2, xn2); // 13. tv2 = tv2 * xn2
tv2 = Fp.mul(tv2, yd2); // 14. tv2 = tv2 * yd2
let tv3 = Fp.mul(yn2, 4n); // 15. tv3 = 4 * yn2
let tv1 = Fp.add(tv3, yd2); // 16. tv1 = tv3 + yd2
tv1 = Fp.mul(tv1, xd4); // 17. tv1 = tv1 * xd4
let xEd = Fp.add(tv1, tv2); // 18. xEd = tv1 + tv2
tv2 = Fp.mul(tv2, xn); // 19. tv2 = tv2 * xn
let tv4 = Fp.mul(xn, xd4); // 20. tv4 = xn * xd4
let yEn = Fp.sub(tv3, yd2); // 21. yEn = tv3 - yd2
yEn = Fp.mul(yEn, tv4); // 22. yEn = yEn * tv4
yEn = Fp.sub(yEn, tv2); // 23. yEn = yEn - tv2
tv1 = Fp.add(xn2, xd2); // 24. tv1 = xn2 + xd2
tv1 = Fp.mul(tv1, xd2); // 25. tv1 = tv1 * xd2
tv1 = Fp.mul(tv1, xd); // 26. tv1 = tv1 * xd
tv1 = Fp.mul(tv1, yn2); // 27. tv1 = tv1 * yn2
tv1 = Fp.mul(tv1, BigInt(-2)); // 28. tv1 = -2 * tv1
let yEd = Fp.add(tv2, tv1); // 29. yEd = tv2 + tv1
tv4 = Fp.mul(tv4, yd2); // 30. tv4 = tv4 * yd2
yEd = Fp.add(yEd, tv4); // 31. yEd = yEd + tv4
tv1 = Fp.mul(xEd, yEd); // 32. tv1 = xEd * yEd
let e = Fp.equals(tv1, Fp.ZERO); // 33. e = tv1 == 0
xEn = Fp.cmov(xEn, Fp.ZERO, e); // 34. xEn = CMOV(xEn, 0, e)
xEd = Fp.cmov(xEd, Fp.ONE, e); // 35. xEd = CMOV(xEd, 1, e)
yEn = Fp.cmov(yEn, Fp.ONE, e); // 36. yEn = CMOV(yEn, 1, e)
yEd = Fp.cmov(yEd, Fp.ONE, e); // 37. yEd = CMOV(yEd, 1, e)
const inv = Fp.invertBatch([xEd, yEd]); // batch division
return { x: Fp.mul(xEn, inv[0]), y: Fp.mul(yEn, inv[1]) }; // 38. return (xEn, xEd, yEn, yEd)
}
const ED448_DEF = {

@@ -56,3 +130,3 @@ // Param: a

// Finite field 𝔽p over which we'll do calculations; 2n ** 448n - 2n ** 224n - 1n
Fp: Fp(ed448P, 456),
Fp,
// Subgroup order: how many points ed448 has; 2n**446n - 13818066809895115352007386748515426880336692474882178609894547503885n

@@ -97,2 +171,11 @@ n: BigInt('181709681073901722637330951972001133588410340171829515070372549795146003961539585716195755291692375963310293709091662304773755859649779'),

},
htfDefaults: {
DST: 'edwards448_XOF:SHAKE256_ELL2_RO_',
p: Fp.ORDER,
m: 1,
k: 224,
expand: 'xof',
hash: shake256,
},
mapToCurve: (scalars) => map_to_curve_elligator2_edwards448(scalars[0]),
};

@@ -99,0 +182,0 @@ export const ed448 = twistedEdwards(ED448_DEF);

2

lib/esm/p256.js

@@ -35,3 +35,3 @@ /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */

k: 128,
expand: true,
expand: 'xmd',
hash: sha256,

@@ -38,0 +38,0 @@ },

2

lib/esm/p384.js

@@ -40,3 +40,3 @@ /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */

k: 192,
expand: true,
expand: 'xmd',
hash: sha384,

@@ -43,0 +43,0 @@ },

2

lib/esm/p521.js

@@ -54,3 +54,3 @@ /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */

k: 256,
expand: true,
expand: 'xmd',
hash: sha512,

@@ -57,0 +57,0 @@ },

7

lib/esm/secp256k1.js

@@ -49,3 +49,6 @@ /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */

const t2 = (pow2(t1, _6n, P) * b2) % P;
return pow2(t2, _2n, P);
const root = pow2(t2, _2n, P);
if (!Fp.equals(Fp.square(root), y))
throw new Error('Cannot find square root');
return root;
}

@@ -138,3 +141,3 @@ const Fp = Field(secp256k1P, undefined, undefined, { sqrt: sqrtMod });

k: 128,
expand: true,
expand: 'xmd',
hash: sha256,

@@ -141,0 +144,0 @@ },

2

lib/esm/stark.js

@@ -166,2 +166,4 @@ /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */

}
// NOTE: we cannot use wNAF here, because last 4 bits will require full 248 bits multiplication
// We can add support for this to wNAF, but it will complicate wNAF.
p = p2;

@@ -168,0 +170,0 @@ for (let i = 0; i < 4; i++) {

2

lib/p256.js

@@ -38,3 +38,3 @@ "use strict";

k: 128,
expand: true,
expand: 'xmd',
hash: sha256_1.sha256,

@@ -41,0 +41,0 @@ },

2

lib/p384.js

@@ -43,3 +43,3 @@ "use strict";

k: 192,
expand: true,
expand: 'xmd',
hash: sha512_1.sha384,

@@ -46,0 +46,0 @@ },

2

lib/p521.js

@@ -57,3 +57,3 @@ "use strict";

k: 256,
expand: true,
expand: 'xmd',
hash: sha512_1.sha512,

@@ -60,0 +60,0 @@ },

7

lib/secp256k1.js

@@ -52,3 +52,6 @@ "use strict";

const t2 = ((0, modular_js_1.pow2)(t1, _6n, P) * b2) % P;
return (0, modular_js_1.pow2)(t2, _2n, P);
const root = (0, modular_js_1.pow2)(t2, _2n, P);
if (!Fp.equals(Fp.square(root), y))
throw new Error('Cannot find square root');
return root;
}

@@ -141,3 +144,3 @@ const Fp = (0, modular_js_1.Fp)(secp256k1P, undefined, undefined, { sqrt: sqrtMod });

k: 128,
expand: true,
expand: 'xmd',
hash: sha256_1.sha256,

@@ -144,0 +147,0 @@ },

2

lib/stark.d.ts

@@ -7,3 +7,3 @@ import { ProjectivePointType } from './abstract/weierstrass.js';

declare function getSharedSecret0x(privKeyA: Hex, pubKeyB: Hex): Uint8Array;
declare function sign0x(msgHash: Hex, privKey: Hex, opts: any): import("./abstract/weierstrass.js").SignatureType;
declare function sign0x(msgHash: Hex, privKey: Hex, opts?: any): import("./abstract/weierstrass.js").SignatureType;
declare function verify0x(signature: Hex, msgHash: Hex, pubKey: Hex): boolean;

@@ -10,0 +10,0 @@ declare const CURVE: Readonly<{

2

lib/stark.js

@@ -183,2 +183,4 @@ "use strict";

}
// NOTE: we cannot use wNAF here, because last 4 bits will require full 248 bits multiplication
// We can add support for this to wNAF, but it will complicate wNAF.
p = p2;

@@ -185,0 +187,0 @@ for (let i = 0; i < 4; i++) {

2

package.json
{
"name": "@noble/curves",
"version": "0.5.0",
"version": "0.5.1",
"description": "Minimal, auditable JS implementation of elliptic curve cryptography",

@@ -5,0 +5,0 @@ "files": [

71

README.md

@@ -10,4 +10,4 @@ # noble-curves

- Auditable, [fast](#speed)
- 🔍 Unique tests ensure correctness. Wycheproof vectors included
- 🔻 Tree-shaking-friendly: there is no entry point, which ensures small size of your app
- 🔍 Unique tests ensure correctness. Wycheproof vectors included

@@ -88,7 +88,8 @@ There are two parts of the package:

- [Overview](#overview)
- [abstract/edwards: Twisted Edwards curve](#abstract/edwards-twisted-edwards-curve)
- [abstract/montgomery: Montgomery curve](#abstract/montgomery-montgomery-curve)
- [abstract/weierstrass: Short Weierstrass curve](#abstract/weierstrass-short-weierstrass-curve)
- [abstract/modular](#abstract/modular)
- [abstract/utils](#abstract/utils)
- [abstract/edwards: Twisted Edwards curve](#abstractedwards-twisted-edwards-curve)
- [abstract/montgomery: Montgomery curve](#abstractmontgomery-montgomery-curve)
- [abstract/weierstrass: Short Weierstrass curve](#abstractweierstrass-short-weierstrass-curve)
- [abstract/hash-to-curve: Hashing strings to curve points](#abstracthash-to-curve-hashing-strings-to-curve-points)
- [abstract/modular](#abstractmodular)
- [abstract/utils](#abstractutils)

@@ -329,2 +330,50 @@ ### Overview

### abstract/hash-to-curve: Hashing strings to curve points
The module allows to hash arbitrary strings to elliptic curve points.
- `expand_message_xmd` [(spec)](https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-11#section-5.4.1) produces a uniformly random byte string using a cryptographic hash function H that outputs b bits..
```ts
function expand_message_xmd(
msg: Uint8Array, DST: Uint8Array, lenInBytes: number, H: CHash
): Uint8Array;
function expand_message_xof(
msg: Uint8Array, DST: Uint8Array, lenInBytes: number, k: number, H: CHash
): Uint8Array;
```
- `hash_to_field(msg, count, options)` [(spec)](https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-11#section-5.3)
hashes arbitrary-length byte strings to a list of one or more elements of a finite field F.
* `msg` a byte string containing the message to hash
* `count` the number of elements of F to output
* `options` `{DST: string, p: bigint, m: number, k: number, expand: 'xmd' | 'xof', hash: H}`
* Returns `[u_0, ..., u_(count - 1)]`, a list of field elements.
```ts
function hash_to_field(msg: Uint8Array, count: number, options: htfOpts): bigint[][];
type htfOpts = {
// DST: a domain separation tag
// defined in section 2.2.5
DST: string;
// p: the characteristic of F
// where F is a finite field of characteristic p and order q = p^m
p: bigint;
// m: the extension degree of F, m >= 1
// where F is a finite field of characteristic p and order q = p^m
m: number;
// k: the target security level for the suite in bits
// defined in section 5.1
k: number;
// option to use a message that has already been processed by
// expand_message_xmd
expand?: 'xmd' | 'xof';
// Hash functions for: expand_message_xmd is appropriate for use with a
// wide range of hash functions, including SHA-2, SHA-3, BLAKE2, and others.
// BBS+ uses blake2: https://github.com/hyperledger/aries-framework-go/issues/2247
// TODO: verify that hash is shake if expand==='xof' via types
hash: CHash;
};
```
### abstract/modular

@@ -335,3 +384,8 @@

```typescript
import { mod, invert, div, invertBatch, sqrt, Fp } from '@noble/curves/abstract/modular';
import { Fp, mod, invert, div, invertBatch, sqrt } from '@noble/curves/abstract/modular';
const fp = Fp(2n ** 255n - 19n); // Finite field over 2^255-19
fp.mul(591n, 932n);
fp.pow(481n, 11024858120n);
// Generic non-FP utils are also available
mod(21n, 10n); // 21 mod 10 == 1n; fixed version of 21 % 10

@@ -342,5 +396,2 @@ invert(17n, 10n); // invert(17) mod 10; modular multiplicative inverse

sqrt(21n, 73n); // √21 mod 73; square root
const fp = Fp(2n ** 255n - 19n); // Finite field over 2^255-19
fp.mul(591n, 932n);
fp.pow(481n, 11024858120n);
```

@@ -347,0 +398,0 @@

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc