From f7a0747b3c8c313c038cb17df68a07ab19feea0b Mon Sep 17 00:00:00 2001 From: Chris Duncan Date: Sat, 29 Nov 2025 23:37:50 -0800 Subject: [PATCH] Progress on classifying secp256k1. --- src/lib/crypto/secp256k1.ts | 1135 ++++++++++++++++++----------------- 1 file changed, 569 insertions(+), 566 deletions(-) diff --git a/src/lib/crypto/secp256k1.ts b/src/lib/crypto/secp256k1.ts index e856673..254ab81 100644 --- a/src/lib/crypto/secp256k1.ts +++ b/src/lib/crypto/secp256k1.ts @@ -1,8 +1,7 @@ /*! noble-secp256k1 - MIT License (c) 2019 Paul Miller (paulmillr.com) */ -import { Point, Signature, hashes, signAsync, verifyAsync, recoverPublicKey, recoverPublicKeyAsync, getSharedSecret, getPublicKey, etc, utils } from "@noble/secp256k1" -import { randomBytes, sign, verify } from "crypto" -import { format } from "path" +import { Point, Signature, getPublicKey, hashes } from "@noble/secp256k1" +import { randomBytes } from "crypto" import { _verify } from "../wallet/verify" /** @@ -83,6 +82,11 @@ export type ECDSASignOpts = { } type Pred = (v: Bytes) => T | undefined +type KeysSecPub = { secretKey: Bytes; publicKey: Bytes } +type KeygenFn = (seed?: Bytes) => KeysSecPub + +type MaybePromise = T | Promise + export class Secp256k1 { /** * Curve params. secp256k1 is short weierstrass / koblitz curve. Equation is y² == x³ + ax + b. @@ -321,7 +325,7 @@ export class Secp256k1 { return X1Z2 === X2Z1 && Y1Z2 === Y2Z1 } is0 (): boolean { - return this.equals(I) + return this.equals(Secp256k1.I) } /** Flip point over y coordinate. */ negate (): Point { @@ -395,7 +399,7 @@ export class Secp256k1 { toAffine (): AffinePoint { const { X: x, Y: y, Z: z } = this // fast-paths for ZERO point OR Z=1 - if (this.equals(I)) return { x: 0n, y: 0n } + if (this.equals(Secp256k1.I)) return { x: 0n, y: 0n } if (z === 1n) return { x, y } const iz = Secp256k1.invert(z, Secp256k1.P) // (Z * Z^-1) must be 1, otherwise bad math @@ -476,18 +480,41 @@ export class Secp256k1 { if (![0, 1, 2, 3].includes(recovery!)) this.err('recovery id must be valid and present') } static assertSigFormat = (format?: ECDSASignatureFormat) => { - if (format != null && !ALL_SIG.includes(format)) - err(`Signature format must be one of: ${ALL_SIG.join(', ')}`) - if (format === SIG_DER) this.err('Signature format "der" is not supported: switch to noble-curves') + if (format != null && !this.ALL_SIG.includes(format)) + this.err(`Signature format must be one of: ${this.ALL_SIG.join(', ')}`) + if (format === this.SIG_DER) this.err('Signature format "der" is not supported: switch to noble-curves') } - static assertSigLength = (sig: Bytes, format: ECDSASignatureFormat = SIG_COMPACT) => { + static assertSigLength = (sig: Bytes, format: ECDSASignatureFormat = this.SIG_COMPACT) => { this.assertSigFormat(format) const SL = this.lengths.signature const RL = SL + 1 let msg = `Signature format "${format}" expects Uint8Array with length ` - if (format === SIG_COMPACT && sig.length !== SL) this.err(msg + SL) - if (format === SIG_RECOVERED && sig.length !== RL) this.err(msg + RL) + if (format === this.SIG_COMPACT && sig.length !== SL) this.err(msg + SL) + if (format === this.SIG_RECOVERED && sig.length !== RL) this.err(msg + RL) } + + /** + * Option to enable hedged signatures with improved security. + * + * * Randomly generated k is bad, because broken CSPRNG would leak private keys. + * * Deterministic k (RFC6979) is better; but is suspectible to fault attacks. + * + * We allow using technique described in RFC6979 3.6: additional k', a.k.a. adding randomness + * to deterministic sig. If CSPRNG is broken & randomness is weak, it would STILL be as secure + * as ordinary sig without ExtraEntropy. + * + * * `true` means "fetch data, from CSPRNG, incorporate it into k generation" + * * `false` means "disable extra entropy, use purely deterministic k" + * * `Uint8Array` passed means "incorporate following data into k generation" + * + * https://paulmillr.com/posts/deterministic-signatures/ + */ + // todo: better name + static SIG_COMPACT: ECDSASignatureFormat = 'compact' + static SIG_RECOVERED = 'recovered' + static SIG_DER = 'der' + static ALL_SIG = [this.SIG_COMPACT, this.SIG_RECOVERED, this.SIG_DER] as const + /** ECDSA Signature class. Supports only compact 64-byte representation, not DER. */ static Signature = class { readonly r: bigint @@ -499,10 +526,10 @@ export class Secp256k1 { if (recovery != null) this.recovery = recovery Object.freeze(this) } - static fromBytes (b: Bytes, format: ECDSASignatureFormat = SIG_COMPACT): Secp256k1['Signature'] { + static fromBytes (b: Bytes, format: ECDSASignatureFormat = Secp256k1.SIG_COMPACT): Secp256k1['Signature'] { Secp256k1.assertSigLength(b, format) let rec: number | undefined - if (format === SIG_RECOVERED) { + if (format === Secp256k1.SIG_RECOVERED) { rec = b[0] b = b.subarray(1) } @@ -516,10 +543,10 @@ export class Secp256k1 { hasHighS (): boolean { return Secp256k1.highS(this.s) } - toBytes (format: ECDSASignatureFormat = SIG_COMPACT): Bytes { + toBytes (format: ECDSASignatureFormat = Secp256k1.SIG_COMPACT): Bytes { const { r, s, recovery } = this const res = Secp256k1.concatBytes(Secp256k1.numTo32b(r), Secp256k1.numTo32b(s)) - if (format === SIG_RECOVERED) { + if (format === Secp256k1.SIG_RECOVERED) { Secp256k1.assertRecoveryBit(recovery) return Secp256k1.concatBytes(Uint8Array.of(recovery!), res) } @@ -541,27 +568,6 @@ export class Secp256k1 { } /** int2octets can't be used; pads small msgs with 0: BAD for truncation as per RFC vectors */ static bits2int_modN = (bytes: Bytes): bigint => this.modN(this.bits2int(this.abytes(bytes))) - /** - * Option to enable hedged signatures with improved security. - * - * * Randomly generated k is bad, because broken CSPRNG would leak private keys. - * * Deterministic k (RFC6979) is better; but is suspectible to fault attacks. - * - * We allow using technique described in RFC6979 3.6: additional k', a.k.a. adding randomness - * to deterministic sig. If CSPRNG is broken & randomness is weak, it would STILL be as secure - * as ordinary sig without ExtraEntropy. - * - * * `true` means "fetch data, from CSPRNG, incorporate it into k generation" - * * `false` means "disable extra entropy, use purely deterministic k" - * * `Uint8Array` passed means "incorporate following data into k generation" - * - * https://paulmillr.com/posts/deterministic-signatures/ - */ - // todo: better name - static SIG_COMPACT: ECDSASignatureFormat = 'compact' - static SIG_RECOVERED = 'recovered' - static SIG_DER = 'der' - static ALL_SIG = [this.SIG_COMPACT, this.SIG_RECOVERED, this.SIG_DER] as const static defaultSignOpts: ECDSASignOpts = { lowS: true, @@ -596,581 +602,578 @@ export class Secp256k1 { static _drbgErr = 'drbg: tried max amount of iterations' // HMAC-DRBG from NIST 800-90. Minimal, non-full-spec - used for RFC6979 signatures. static hmacDrbg = (seed: Bytes, pred: Pred): Bytes => { - let v = u8n(L) // Steps B, C of RFC6979 3.2: set hashLen - let k = u8n(L) // In our case, it's always equal to L + let v = this.u8n(this.L) // Steps B, C of RFC6979 3.2: set hashLen + let k = this.u8n(this.L) // In our case, it's always equal to L let i = 0 // Iterations counter, will throw when over max - static reset = () => { - v.fill(1) - k.fill(0) - } - // h = hmac(K || V || ...) - static h = (...b: Bytes[]) => callHash('hmacSha256')(k, concatBytes(v, ...b)) - static reseed = (seed = NULL) => { - // HMAC-DRBG reseed() function. Steps D-G - k = h(byte0, seed) // k = hmac(k || v || 0x00 || seed) - v = h() // v = hmac(k || v) - if (seed.length === 0) return - k = h(byte1, seed) // k = hmac(k || v || 0x01 || seed) - v = h() // v = hmac(k || v) - } - // HMAC-DRBG generate() function - static gen = () => { - if (i++ >= _maxDrbgIters) err(_drbgErr) - v = h() // v = hmac(k || v) - return v // this diverges from noble-curves: we don't allow arbitrary output len! + const reset = () => { + v.fill(1) + k.fill(0) + } + // h = hmac(K || V || ...) + const h = (...b: Bytes[]) => this.callHash('hmacSha256')(k, this.concatBytes(v, ...b)) + const reseed = (seed = this.NULL) => { + // HMAC-DRBG reseed() function. Steps D-G + k = h(this.byte0, seed) // k = hmac(k || v || 0x00 || seed) + v = h() // v = hmac(k || v) + if (seed.length === 0) return + k = h(this.byte1, seed) // k = hmac(k || v || 0x01 || seed) + v = h() // v = hmac(k || v) + } + // HMAC-DRBG generate() function + const gen = () => { + if (i++ >= this._maxDrbgIters) this.err(this._drbgErr) + v = h() // v = hmac(k || v) + return v // this diverges from noble-curves: we don't allow arbitrary output len! + } + reset() + reseed(seed) // Steps D-G + let res: Bytes | undefined = undefined // Step H: grind until k is in [1..n-1] + while (!(res = pred(gen()))) reseed() // test predicate until it returns ok + reset() + return res! } - reset () - reseed (seed) // Steps D-G - let res: Bytes | undefined = undefined // Step H: grind until k is in [1..n-1] -while (!(res = pred(gen()))) reseed() // test predicate until it returns ok -reset() -return res! -} -// Identical to hmacDrbg, but async: uses built-in WebCrypto -static hmacDrbgAsync = async (seed: Bytes, pred: Pred): Promise => { - let v = u8n(L) // Steps B, C of RFC6979 3.2: set hashLen - let k = u8n(L) // In our case, it's always equal to L - let i = 0 // Iterations counter, will throw when over max - static reset = () => { - v.fill(1) - k.fill(0) - } - // h = hmac(K || V || ...) - static h = (...b: Bytes[]) => hashes.hmacSha256Async(k, concatBytes(v, ...b)) - static reseed = async (seed = NULL) => { - // HMAC-DRBG reseed() function. Steps D-G - k = await h(byte0, seed) // k = hmac(K || V || 0x00 || seed) - v = await h() // v = hmac(K || V) - if (seed.length === 0) return - k = await h(byte1, seed) // k = hmac(K || V || 0x01 || seed) - v = await h() // v = hmac(K || V) - } - // HMAC-DRBG generate() function - static gen = async () => { - if (i++ >= _maxDrbgIters) err(_drbgErr) - v = await h() // v = hmac(K || V) - return v // this diverges from noble-curves: we don't allow arbitrary output len! + // Identical to hmacDrbg, but async: uses built-in WebCrypto + static hmacDrbgAsync = async (seed: Bytes, pred: Pred): Promise => { + let v = this.u8n(this.L) // Steps B, C of RFC6979 3.2: set hashLen + let k = this.u8n(this.L) // In our case, it's always equal to L + let i = 0 // Iterations counter, will throw when over max + const reset = () => { + v.fill(1) + k.fill(0) + } + // h = hmac(K || V || ...) + const h = (...b: Bytes[]) => hashes.hmacSha256Async(k, this.concatBytes(v, ...b)) + const reseed = async (seed = this.NULL) => { + // HMAC-DRBG reseed() function. Steps D-G + k = await h(this.byte0, seed) // k = hmac(K || V || 0x00 || seed) + v = await h() // v = hmac(K || V) + if (seed.length === 0) return + k = await h(this.byte1, seed) // k = hmac(K || V || 0x01 || seed) + v = await h() // v = hmac(K || V) + } + // HMAC-DRBG generate() function + const gen = async () => { + if (i++ >= this._maxDrbgIters) this.err(this._drbgErr) + v = await h() // v = hmac(K || V) + return v // this diverges from noble-curves: we don't allow arbitrary output len! + } + reset() + await reseed(seed) // Steps D-G + let res: Bytes | undefined = undefined // Step H: grind until k is in [1..n-1] + while (!(res = pred(await gen()))) await reseed() // test predicate until it returns ok + reset() + return res! } - reset() - await reseed(seed) // Steps D-G - let res: Bytes | undefined = undefined // Step H: grind until k is in [1..n-1] - while (!(res = pred(await gen()))) await reseed() // test predicate until it returns ok - reset() - return res! -} -// RFC6979 signature generation, preparation step. -// Follows [SEC1](https://secg.org/sec1-v2.pdf) 4.1.2 & RFC6979. -static _sign = ( - messageHash: Bytes, - secretKey: Bytes, - opts: ECDSASignOpts, - hmacDrbg: (seed: Bytes, pred: Pred) => T -): T => { - let { lowS, extraEntropy } = opts // generates low-s sigs by default - // RFC6979 3.2: we skip step A - static int2octets = numTo32b // int to octets - static h1i = bits2int_modN(messageHash) // msg bigint - static h1o = int2octets(h1i) // msg octets - static d = secretKeyToScalar(secretKey) // validate private key, convert to bigint - static seedArgs = [int2octets(d), h1o] // Step D of RFC6979 3.2 - /** RFC6979 3.6: additional k' (optional). See {@link ECDSAExtraEntropy}. */ - if (extraEntropy != null && extraEntropy !== false) { - // K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1) || k') - // gen random bytes OR pass as-is - const e = extraEntropy === true ? randomBytes(L) : extraEntropy - seedArgs.push(abytes(e, undefined, 'extraEntropy')) // check for being bytes - } - static seed = concatBytes(...seedArgs) - static m = h1i // convert msg to bigint - // Converts signature params into point w r/s, checks result for validity. - // To transform k => Signature: - // q = k⋅G - // r = q.x mod n - // s = k^-1(m + rd) mod n - // Can use scalar blinding b^-1(bm + bdr) where b ∈ [1,q−1] according to - // https://tches.iacr.org/index.php/TCHES/article/view/7337/6509. We've decided against it: - // a) dependency on CSPRNG b) 15% slowdown c) doesn't really help since bigints are not CT - static k2sig = (kBytes: Bytes): Bytes | undefined => { - // RFC 6979 Section 3.2, step 3: k = bits2int(T) - // Important: all mod() calls here must be done over N - const k = bits2int(kBytes) - if (!(1n <= k && k < N)) return // Valid scalars (including k) must be in 1..N-1 - const ik = invert(k, N) // k^-1 mod n - const q = G.multiply(k).toAffine() // q = k⋅G - const r = modN(q.x) // r = q.x mod n - if (r === 0n) return - const s = modN(ik * modN(m + r * d)) // s = k^-1(m + rd) mod n - if (s === 0n) return - let recovery = (q.x === r ? 0 : 2) | Number(q.y & 1n) // recovery bit (2 or 3, when q.x > n) - let normS = s // normalized S - if (lowS && highS(s)) { - // if lowS was passed, ensure s is always - normS = modN(-s) // in the bottom half of CURVE.n - recovery ^= 1 + // RFC6979 signature generation, preparation step. + // Follows [SEC1](https://secg.org/sec1-v2.pdf) 4.1.2 & RFC6979. + static _sign = ( + messageHash: Bytes, + secretKey: Bytes, + opts: ECDSASignOpts, + hmacDrbg: (seed: Bytes, pred: Pred) => T + ): T => { + let { lowS, extraEntropy } = opts // generates low-s sigs by default + // RFC6979 3.2: we skip step A + const int2octets = numTo32b // int to octets + const h1i = bits2int_modN(messageHash) // msg bigint + const h1o = int2octets(h1i) // msg octets + const d = secretKeyToScalar(secretKey) // validate private key, convert to bigint + const seedArgs = [int2octets(d), h1o] // Step D of RFC6979 3.2 + /** RFC6979 3.6: additional k' (optional). See {@link ECDSAExtraEntropy}. */ + if (extraEntropy != null && extraEntropy !== false) { + // K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1) || k') + // gen random bytes OR pass as-is + const e = extraEntropy === true ? randomBytes(L) : extraEntropy + seedArgs.push(abytes(e, undefined, 'extraEntropy')) // check for being bytes } - const sig = new Signature(r, normS, recovery) as RecoveredSignature // use normS, not s - return sig.toBytes(opts.format) + const seed = concatBytes(...seedArgs) + const m = h1i // convert msg to bigint + // Converts signature params into point w r/s, checks result for validity. + // To transform k => Signature: + // q = k⋅G + // r = q.x mod n + // s = k^-1(m + rd) mod n + // Can use scalar blinding b^-1(bm + bdr) where b ∈ [1,q−1] according to + // https://tches.iacr.org/index.php/TCHES/article/view/7337/6509. We've decided against it: + // a) dependency on CSPRNG b) 15% slowdown c) doesn't really help since bigints are not CT + const k2sig = (kBytes: Bytes): Bytes | undefined => { + // RFC 6979 Section 3.2, step 3: k = bits2int(T) + // Important: all mod() calls here must be done over N + const k = bits2int(kBytes) + if (!(1n <= k && k < N)) return // Valid scalars (including k) must be in 1..N-1 + const ik = invert(k, N) // k^-1 mod n + const q = G.multiply(k).toAffine() // q = k⋅G + const r = modN(q.x) // r = q.x mod n + if (r === 0n) return + const s = modN(ik * modN(m + r * d)) // s = k^-1(m + rd) mod n + if (s === 0n) return + let recovery = (q.x === r ? 0 : 2) | Number(q.y & 1n) // recovery bit (2 or 3, when q.x > n) + let normS = s // normalized S + if (lowS && highS(s)) { + // if lowS was passed, ensure s is always + normS = modN(-s) // in the bottom half of CURVE.n + recovery ^= 1 + } + const sig = new Signature(r, normS, recovery) as RecoveredSignature // use normS, not s + return sig.toBytes(opts.format) + } + return hmacDrbg(seed, k2sig) } - return hmacDrbg(seed, k2sig) -} -// Follows [SEC1](https://secg.org/sec1-v2.pdf) 4.1.4. -static _verify = (sig: Bytes, messageHash: Bytes, publicKey: Bytes, opts: ECDSAVerifyOpts = {}) => { - static { lowS, format } = opts - if (sig instanceof Signature) err('Signature must be in Uint8Array, use .toBytes()') - assertSigLength(sig, format) - abytes(publicKey, undefined, 'publicKey') - try { - const { r, s } = Signature.fromBytes(sig, format) - const h = bits2int_modN(messageHash) // Truncate hash - const P = Point.fromBytes(publicKey) // Validate public key - if (lowS && highS(s)) return false // lowS bans sig.s >= CURVE.n/2 - const is = invert(s, N) // s^-1 - const u1 = modN(h * is) // u1 = hs^-1 mod n - const u2 = modN(r * is) // u2 = rs^-1 mod n - const R = doubleScalarMulUns(P, u1, u2).toAffine() // R = u1⋅G + u2⋅P - // Stop if R is identity / zero point. Check is done inside `doubleScalarMulUns` - const v = modN(R.x) // R.x must be in N's field, not P's - return v === r // mod(R.x, n) == r - } catch (error) { - return false + // Follows [SEC1](https://secg.org/sec1-v2.pdf) 4.1.4. + static _verify = (sig: Bytes, messageHash: Bytes, publicKey: Bytes, opts: ECDSAVerifyOpts = {}) => { + const { lowS, format } = opts + if (sig instanceof Signature) err('Signature must be in Uint8Array, use .toBytes()') + assertSigLength(sig, format) + abytes(publicKey, undefined, 'publicKey') + try { + const { r, s } = Signature.fromBytes(sig, format) + const h = bits2int_modN(messageHash) // Truncate hash + const P = Point.fromBytes(publicKey) // Validate public key + if (lowS && highS(s)) return false // lowS bans sig.s >= CURVE.n/2 + const is = invert(s, N) // s^-1 + const u1 = modN(h * is) // u1 = hs^-1 mod n + const u2 = modN(r * is) // u2 = rs^-1 mod n + const R = doubleScalarMulUns(P, u1, u2).toAffine() // R = u1⋅G + u2⋅P + // Stop if R is identity / zero point. Check is done inside `doubleScalarMulUns` + const v = modN(R.x) // R.x must be in N's field, not P's + return v === r // mod(R.x, n) == r + } catch (error) { + return false + } } -} -static setDefaults = (opts: ECDSASignOpts): Required => { - static res: ECDSASignOpts = {} - Object.keys(defaultSignOpts).forEach((k: string) => { - // @ts-ignore - res[k] = opts[k] ?? defaultSignOpts[k] - }) - return res as Required -} + static setDefaults = (opts: ECDSASignOpts): Required => { + const res: ECDSASignOpts = {} + Object.keys(defaultSignOpts).forEach((k: string) => { + // @ts-ignore + res[k] = opts[k] ?? defaultSignOpts[k] + }) + return res as Required + } -/** - * Sign a message using secp256k1. Sync: uses `hashes.sha256` and `hashes.hmacSha256`. - * Prehashes message with sha256, disable using `prehash: false`. - * @param opts - see {@link ECDSASignOpts} for details. Enabling {@link ECDSAExtraEntropy} will improve security. - * @example - * ```js - * const msg = new TextEncoder().encode('hello noble'); - * sign(msg, secretKey); - * sign(keccak256(msg), secretKey, { prehash: false }); - * sign(msg, secretKey, { extraEntropy: true }); - * sign(msg, secretKey, { format: 'recovered' }); - * ``` - */ -static sign = (message: Bytes, secretKey: Bytes, opts: ECDSASignOpts = {}): Bytes => { - opts = setDefaults(opts) - message = prepMsg(message, opts, false) as Bytes - return _sign(message, secretKey, opts, hmacDrbg) -} + /** + * Sign a message using secp256k1. Sync: uses `hashes.sha256` and `hashes.hmacSha256`. + * Prehashes message with sha256, disable using `prehash: false`. + * @param opts - see {@link ECDSASignOpts} for details. Enabling {@link ECDSAExtraEntropy} will improve security. + * @example + * ```js + * const msg = new TextEncoder().encode('hello noble'); + * sign(msg, secretKey); + * sign(keccak256(msg), secretKey, { prehash: false }); + * sign(msg, secretKey, { extraEntropy: true }); + * sign(msg, secretKey, { format: 'recovered' }); + * ``` + */ + static sign = (message: Bytes, secretKey: Bytes, opts: ECDSASignOpts = {}): Bytes => { + opts = setDefaults(opts) + message = prepMsg(message, opts, false) as Bytes + return _sign(message, secretKey, opts, hmacDrbg) + } -/** - * Sign a message using secp256k1. Async: uses built-in WebCrypto hashes. - * Prehashes message with sha256, disable using `prehash: false`. - * @param opts - see {@link ECDSASignOpts} for details. Enabling {@link ECDSAExtraEntropy} will improve security. - * @example - * ```js - * const msg = new TextEncoder().encode('hello noble'); - * await signAsync(msg, secretKey); - * await signAsync(keccak256(msg), secretKey, { prehash: false }); - * await signAsync(msg, secretKey, { extraEntropy: true }); - * await signAsync(msg, secretKey, { format: 'recovered' }); - * ``` - */ -static signAsync = async ( - message: Bytes, - secretKey: Bytes, - opts: ECDSASignOpts = {} -): Promise => { - opts = setDefaults(opts) - message = await prepMsg(message, opts, true) - return _sign(message, secretKey, opts, hmacDrbgAsync) -} + /** + * Sign a message using secp256k1. Async: uses built-in WebCrypto hashes. + * Prehashes message with sha256, disable using `prehash: false`. + * @param opts - see {@link ECDSASignOpts} for details. Enabling {@link ECDSAExtraEntropy} will improve security. + * @example + * ```js + * const msg = new TextEncoder().encode('hello noble'); + * await signAsync(msg, secretKey); + * await signAsync(keccak256(msg), secretKey, { prehash: false }); + * await signAsync(msg, secretKey, { extraEntropy: true }); + * await signAsync(msg, secretKey, { format: 'recovered' }); + * ``` + */ + static signAsync = async ( + message: Bytes, + secretKey: Bytes, + opts: ECDSASignOpts = {} + ): Promise => { + opts = setDefaults(opts) + message = await prepMsg(message, opts, true) + return _sign(message, secretKey, opts, hmacDrbgAsync) + } -/** - * Verify a signature using secp256k1. Sync: uses `hashes.sha256` and `hashes.hmacSha256`. - * @param signature - default is 64-byte 'compact' format, also see {@link ECDSASignatureFormat} - * @param message - message which was signed. Keep in mind `prehash` from opts. - * @param publicKey - public key which - * @param opts - see {@link ECDSAVerifyOpts} for details. - * @example - * ```js - * const msg = new TextEncoder().encode('hello noble'); - * verify(sig, msg, publicKey); - * verify(sig, keccak256(msg), publicKey, { prehash: false }); - * verify(sig, msg, publicKey, { lowS: false }); - * verify(sigr, msg, publicKey, { format: 'recovered' }); - * ``` - */ -static verify = ( - signature: Bytes, - message: Bytes, - publicKey: Bytes, - opts: ECDSAVerifyOpts = {} -): boolean => { - opts = setDefaults(opts) - message = prepMsg(message, opts, false) as Bytes - return _verify(signature, message, publicKey, opts) -} + /** + * Verify a signature using secp256k1. Sync: uses `hashes.sha256` and `hashes.hmacSha256`. + * @param signature - default is 64-byte 'compact' format, also see {@link ECDSASignatureFormat} + * @param message - message which was signed. Keep in mind `prehash` from opts. + * @param publicKey - public key which + * @param opts - see {@link ECDSAVerifyOpts} for details. + * @example + * ```js + * const msg = new TextEncoder().encode('hello noble'); + * verify(sig, msg, publicKey); + * verify(sig, keccak256(msg), publicKey, { prehash: false }); + * verify(sig, msg, publicKey, { lowS: false }); + * verify(sigr, msg, publicKey, { format: 'recovered' }); + * ``` + */ + static verify = ( + signature: Bytes, + message: Bytes, + publicKey: Bytes, + opts: ECDSAVerifyOpts = {} + ): boolean => { + opts = setDefaults(opts) + message = prepMsg(message, opts, false) as Bytes + return _verify(signature, message, publicKey, opts) + } -/** - * Verify a signature using secp256k1. Async: uses built-in WebCrypto hashes. - * @param signature - default is 64-byte 'compact' format, also see {@link ECDSASignatureFormat} - * @param message - message which was signed. Keep in mind `prehash` from opts. - * @param publicKey - public key which - * @param opts - see {@link ECDSAVerifyOpts} for details. - * @example - * ```js - * const msg = new TextEncoder().encode('hello noble'); - * verify(sig, msg, publicKey); - * verify(sig, keccak256(msg), publicKey, { prehash: false }); - * verify(sig, msg, publicKey, { lowS: false }); - * verify(sigr, msg, publicKey, { format: 'recovered' }); - * ``` - */ -static verifyAsync = async ( - sig: Bytes, - message: Bytes, - publicKey: Bytes, - opts: ECDSAVerifyOpts = {} -): Promise => { - opts = setDefaults(opts) - message = await prepMsg(message, opts, true) - return _verify(sig, message, publicKey, opts) -} + /** + * Verify a signature using secp256k1. Async: uses built-in WebCrypto hashes. + * @param signature - default is 64-byte 'compact' format, also see {@link ECDSASignatureFormat} + * @param message - message which was signed. Keep in mind `prehash` from opts. + * @param publicKey - public key which + * @param opts - see {@link ECDSAVerifyOpts} for details. + * @example + * ```js + * const msg = new TextEncoder().encode('hello noble'); + * verify(sig, msg, publicKey); + * verify(sig, keccak256(msg), publicKey, { prehash: false }); + * verify(sig, msg, publicKey, { lowS: false }); + * verify(sigr, msg, publicKey, { format: 'recovered' }); + * ``` + */ + static verifyAsync = async ( + sig: Bytes, + message: Bytes, + publicKey: Bytes, + opts: ECDSAVerifyOpts = {} + ): Promise => { + opts = setDefaults(opts) + message = await prepMsg(message, opts, true) + return _verify(sig, message, publicKey, opts) + } -static _recover = (signature: Bytes, messageHash: Bytes) => { - static sig = Signature.fromBytes(signature, 'recovered') - static { r, s, recovery } = sig - // 0 or 1 recovery id determines sign of "y" coordinate. - // 2 or 3 means q.x was >N. - assertRecoveryBit(recovery) - static h = bits2int_modN(abytes(messageHash, L)) // Truncate hash - static radj = recovery === 2 || recovery === 3 ? r + N : r - FpIsValidNot0(radj) // ensure q.x is still a field element - static head = getPrefix(big(recovery!)) // head is 0x02 or 0x03 - static Rb = concatBytes(head, numTo32b(radj)) // concat head + r - static R = Point.fromBytes(Rb) - static ir = invert(radj, N) // r^-1 - static u1 = modN(-h * ir) // -hr^-1 - static u2 = modN(s * ir) // sr^-1 - static point = doubleScalarMulUns(R, u1, u2) // (sr^-1)R-(hr^-1)G = -(hr^-1)G + (sr^-1) - return point.toBytes() -} + static _recover = (signature: Bytes, messageHash: Bytes) => { + const sig = Signature.fromBytes(signature, 'recovered') + const { r, s, recovery } = sig + // 0 or 1 recovery id determines sign of "y" coordinate. + // 2 or 3 means q.x was >N. + assertRecoveryBit(recovery) + const h = bits2int_modN(abytes(messageHash, L)) // Truncate hash + const radj = recovery === 2 || recovery === 3 ? r + N : r + FpIsValidNot0(radj) // ensure q.x is still a field element + const head = getPrefix(big(recovery!)) // head is 0x02 or 0x03 + const Rb = concatBytes(head, numTo32b(radj)) // concat head + r + const R = Point.fromBytes(Rb) + const ir = invert(radj, N) // r^-1 + const u1 = modN(-h * ir) // -hr^-1 + const u2 = modN(s * ir) // sr^-1 + const point = doubleScalarMulUns(R, u1, u2) // (sr^-1)R-(hr^-1)G = -(hr^-1)G + (sr^-1) + return point.toBytes() + } -/** - * ECDSA public key recovery. Requires msg hash and recovery id. - * Follows [SEC1](https://secg.org/sec1-v2.pdf) 4.1.6. - */ -static recoverPublicKey = (signature: Bytes, message: Bytes, opts: ECDSARecoverOpts = {}): Bytes => { - message = prepMsg(message, setDefaults(opts), false) as Bytes - return _recover(signature, message) -} + /** + * ECDSA public key recovery. Requires msg hash and recovery id. + * Follows [SEC1](https://secg.org/sec1-v2.pdf) 4.1.6. + */ + static recoverPublicKey = (signature: Bytes, message: Bytes, opts: ECDSARecoverOpts = {}): Bytes => { + message = prepMsg(message, setDefaults(opts), false) as Bytes + return _recover(signature, message) + } -static recoverPublicKeyAsync = async ( - signature: Bytes, - message: Bytes, - opts: ECDSARecoverOpts = {} -): Promise => { - message = await prepMsg(message, setDefaults(opts), true) - return _recover(signature, message) -} + static recoverPublicKeyAsync = async ( + signature: Bytes, + message: Bytes, + opts: ECDSARecoverOpts = {} + ): Promise => { + message = await prepMsg(message, setDefaults(opts), true) + return _recover(signature, message) + } -/** - * Elliptic Curve Diffie-Hellman (ECDH) on secp256k1. - * Result is **NOT hashed**. Use hash or KDF on it if you need. - * @param isCompressed 33-byte (true) or 65-byte (false) output - * @returns public key C - */ -static getSharedSecret = (secretKeyA: Bytes, publicKeyB: Bytes, isCompressed = true): Bytes => { - return Point.fromBytes(publicKeyB).multiply(secretKeyToScalar(secretKeyA)).toBytes(isCompressed) -} + /** + * Elliptic Curve Diffie-Hellman (ECDH) on secp256k1. + * Result is **NOT hashed**. Use hash or KDF on it if you need. + * @param isCompressed 33-byte (true) or 65-byte (false) output + * @returns public key C + */ + static getSharedSecret = (secretKeyA: Bytes, publicKeyB: Bytes, isCompressed = true): Bytes => { + return Point.fromBytes(publicKeyB).multiply(secretKeyToScalar(secretKeyA)).toBytes(isCompressed) + } -// FIPS 186 B.4.1 compliant key generation produces private keys -// with modulo bias being neglible. takes >N+16 bytes, returns (hash mod n-1)+1 -static randomSecretKey = (seed = randomBytes(lengths.seed)) => { - abytes(seed) - if (seed.length < lengths.seed || seed.length > 1024) err('expected 40-1024b') - static num = M(bytesToNumBE(seed), N - 1n) - return numTo32b(num + 1n) -} + // FIPS 186 B.4.1 compliant key generation produces private keys + // with modulo bias being neglible. takes >N+16 bytes, returns (hash mod n-1)+1 + static randomSecretKey = (seed = randomBytes(lengths.seed)) => { + abytes(seed) + if (seed.length < lengths.seed || seed.length > 1024) err('expected 40-1024b') + const num = M(bytesToNumBE(seed), N - 1n) + return numTo32b(num + 1n) + } -type KeysSecPub = { secretKey: Bytes; publicKey: Bytes } -type KeygenFn = (seed?: Bytes) => KeysSecPub -static createKeygen = (getPublicKey: (secretKey: Bytes) => Bytes) => (seed?: Bytes): KeysSecPub => { - static secretKey = randomSecretKey(seed) - return { secretKey, publicKey: getPublicKey(secretKey) } -} -static keygen: KeygenFn = createKeygen(getPublicKey) + static createKeygen = (getPublicKey: (secretKey: Bytes) => Bytes) => (seed?: Bytes): KeysSecPub => { + const secretKey = this.randomSecretKey(seed) + return { secretKey, publicKey: getPublicKey(secretKey) } + } + static keygen: KeygenFn = this.createKeygen(getPublicKey) -/** Math, hex, byte helpers. Not in `utils` because utils share API with noble-curves. */ -static etc = { - hexToBytes: hexToBytes as (hex: string) => Bytes, - bytesToHex: bytesToHex as (bytes: Bytes) => string, - concatBytes: concatBytes as (...arrs: Bytes[]) => Bytes, - bytesToNumberBE: bytesToNumBE as (a: Bytes) => bigint, - numberToBytesBE: numTo32b as (n: bigint) => Bytes, - mod: M as (a: bigint, md?: bigint) => bigint, - invert: invert as (num: bigint, md?: bigint) => bigint, // math utilities - randomBytes: randomBytes as (len?: number) => Bytes, - secretKeyToScalar: secretKeyToScalar as typeof secretKeyToScalar, - abytes: abytes as typeof abytes, -} + /** Math, hex, byte helpers. Not in `utils` because utils share API with noble-curves. */ + static etc = { + hexToBytes: this.hexToBytes as (hex: string) => Bytes, + bytesToHex: this.bytesToHex as (bytes: Bytes) => string, + concatBytes: this.concatBytes as (...arrs: Bytes[]) => Bytes, + bytesToNumberBE: this.bytesToNumBE as (a: Bytes) => bigint, + numberToBytesBE: this.numTo32b as (n: bigint) => Bytes, + mod: this.M as (a: bigint, md?: bigint) => bigint, + invert: this.invert as (num: bigint, md?: bigint) => bigint, // math utilities + randomBytes: randomBytes as (len?: number) => Bytes, + secretKeyToScalar: this.secretKeyToScalar as typeof this.secretKeyToScalar, + abytes: this.abytes as typeof this.abytes, + } -/** Curve-specific utilities for private keys. */ -static utils = { - isValidSecretKey: isValidSecretKey as typeof isValidSecretKey, - isValidPublicKey: isValidPublicKey as typeof isValidPublicKey, - randomSecretKey: randomSecretKey as () => Bytes, -} + /** Curve-specific utilities for private keys. */ + static utils = { + isValidSecretKey: this.isValidSecretKey as typeof this.isValidSecretKey, + isValidPublicKey: this.isValidPublicKey as typeof this.isValidPublicKey, + randomSecretKey: this.randomSecretKey as () => Bytes, + } -// Schnorr signatures are superior to ECDSA from above. Below is Schnorr-specific BIP0340 code. -// https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki -static getTag = (tag: string) => Uint8Array.from('BIP0340/' + tag, (c) => c.charCodeAt(0)) -static T_AUX = 'aux' -static T_NONCE = 'nonce' -static T_CHALLENGE = 'challenge' -static taggedHash = (tag: string, ...messages: Bytes[]): Bytes => { - static fn = callHash('sha256') - static tagH = fn(getTag(tag)) - return fn(concatBytes(tagH, tagH, ...messages)) -} -static taggedHashAsync = async (tag: string, ...messages: Bytes[]): Promise => { - static fn = hashes.sha256Async - static tagH = await fn(getTag(tag)) - return await fn(concatBytes(tagH, tagH, ...messages)) -} + // Schnorr signatures are superior to ECDSA from above. Below is Schnorr-specific BIP0340 code. + // https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki + static getTag = (tag: string) => Uint8Array.from('BIP0340/' + tag, (c) => c.charCodeAt(0)) + static T_AUX = 'aux' + static T_NONCE = 'nonce' + static T_CHALLENGE = 'challenge' + static taggedHash = (tag: string, ...messages: Bytes[]): Bytes => { + const fn = callHash('sha256') + const tagH = fn(getTag(tag)) + return fn(concatBytes(tagH, tagH, ...messages)) + } + static taggedHashAsync = async (tag: string, ...messages: Bytes[]): Promise => { + const fn = hashes.sha256Async + const tagH = await fn(getTag(tag)) + return await fn(concatBytes(tagH, tagH, ...messages)) + } -// ECDSA compact points are 33-byte. Schnorr is 32: we strip first byte 0x02 or 0x03 -// Calculate point, scalar and bytes -static extpubSchnorr = (priv: Bytes) => { - static d_ = secretKeyToScalar(priv) - static p = G.multiply(d_) // P = d'⋅G; 0 < d' < n check is done inside - static { x, y } = p.assertValidity().toAffine() // validate Point is not at infinity - static d = isEven(y) ? d_ : modN(-d_) - static px = numTo32b(x) - return { d, px } -} + // ECDSA compact points are 33-byte. Schnorr is 32: we strip first byte 0x02 or 0x03 + // Calculate point, scalar and bytes + static extpubSchnorr = (priv: Bytes) => { + const d_ = secretKeyToScalar(priv) + const p = G.multiply(d_) // P = d'⋅G; 0 < d' < n check is done inside + const { x, y } = p.assertValidity().toAffine() // validate Point is not at infinity + const d = isEven(y) ? d_ : modN(-d_) + const px = numTo32b(x) + return { d, px } + } -static bytesModN = (bytes: Bytes) => modN(bytesToNumBE(bytes)) -static challenge = (...args: Bytes[]): bigint => bytesModN(taggedHash(T_CHALLENGE, ...args)) -static challengeAsync = async (...args: Bytes[]): Promise => - bytesModN(await taggedHashAsync(T_CHALLENGE, ...args)) + static bytesModN = (bytes: Bytes) => modN(bytesToNumBE(bytes)) + static challenge = (...args: Bytes[]): bigint => bytesModN(taggedHash(T_CHALLENGE, ...args)) + static challengeAsync = async (...args: Bytes[]): Promise => + bytesModN(await taggedHashAsync(T_CHALLENGE, ...args)) -/** - * Schnorr public key is just `x` coordinate of Point as per BIP340. - */ -static pubSchnorr = (secretKey: Bytes): Bytes => { - return extpubSchnorr(secretKey).px // d'=int(sk). Fail if d'=0 or d'≥n. Ret bytes(d'⋅G) -} + /** + * Schnorr public key is just `x` coordinate of Point as per BIP340. + */ + static pubSchnorr = (secretKey: Bytes): Bytes => { + return extpubSchnorr(secretKey).px // d'=int(sk). Fail if d'=0 or d'≥n. Ret bytes(d'⋅G) + } -static keygenSchnorr: KeygenFn = createKeygen(pubSchnorr) + static keygenSchnorr: KeygenFn = createKeygen(pubSchnorr) -// Common preparation fn for both sync and async signing -static prepSigSchnorr = (message: Bytes, secretKey: Bytes, auxRand: Bytes) => { - static { px, d } = extpubSchnorr(secretKey) - return { m: abytes(message), px, d, a: abytes(auxRand, L) } -} + // Common preparation fn for both sync and async signing + static prepSigSchnorr = (message: Bytes, secretKey: Bytes, auxRand: Bytes) => { + const { px, d } = extpubSchnorr(secretKey) + return { m: abytes(message), px, d, a: abytes(auxRand, L) } + } -static extractK = (rand: Bytes) => { - static k_ = bytesModN(rand) // Let k' = int(rand) mod n - if (k_ === 0n) err('sign failed: k is zero') // Fail if k' = 0. - static { px, d } = extpubSchnorr(numTo32b(k_)) // Let R = k'⋅G. - return { rx: px, k: d } -} + static extractK = (rand: Bytes) => { + const k_ = bytesModN(rand) // Let k' = int(rand) mod n + if (k_ === 0n) err('sign failed: k is zero') // Fail if k' = 0. + const { px, d } = extpubSchnorr(numTo32b(k_)) // Let R = k'⋅G. + return { rx: px, k: d } + } -// Common signature creation helper -static createSigSchnorr = (k: bigint, px: Bytes, e: bigint, d: bigint): Bytes => { - return concatBytes(px, numTo32b(modN(k + e * d))) -} + // Common signature creation helper + static createSigSchnorr = (k: bigint, px: Bytes, e: bigint, d: bigint): Bytes => { + return concatBytes(px, numTo32b(modN(k + e * d))) + } -static E_INVSIG = 'invalid signature produced' -/** - * Creates Schnorr signature as per BIP340. Verifies itself before returning anything. - * auxRand is optional and is not the sole source of k generation: bad CSPRNG won't be dangerous. - */ -static signSchnorr = (message: Bytes, secretKey: Bytes, auxRand: Bytes = randomBytes(L)): Bytes => { - static { m, px, d, a } = prepSigSchnorr(message, secretKey, auxRand) - static aux = taggedHash(T_AUX, a) - // Let t be the byte-wise xor of bytes(d) and hash/aux(a) - static t = numTo32b(d ^ bytesToNumBE(aux)) - // Let rand = hash/nonce(t || bytes(P) || m) - static rand = taggedHash(T_NONCE, t, px, m) - static { rx, k } = extractK(rand) - // Let e = int(hash/challenge(bytes(R) || bytes(P) || m)) mod n. - static e = challenge(rx, px, m) - static sig = createSigSchnorr(k, rx, e, d) - // If Verify(bytes(P), m, sig) (see below) returns failure, abort - if (!verifySchnorr(sig, m, px)) err(E_INVSIG) - return sig -} + static E_INVSIG = 'invalid signature produced' + /** + * Creates Schnorr signature as per BIP340. Verifies itself before returning anything. + * auxRand is optional and is not the sole source of k generation: bad CSPRNG won't be dangerous. + */ + static signSchnorr = (message: Bytes, secretKey: Bytes, auxRand: Bytes = randomBytes(L)): Bytes => { + const { m, px, d, a } = prepSigSchnorr(message, secretKey, auxRand) + const aux = taggedHash(T_AUX, a) + // Let t be the byte-wise xor of bytes(d) and hash/aux(a) + const t = numTo32b(d ^ bytesToNumBE(aux)) + // Let rand = hash/nonce(t || bytes(P) || m) + const rand = taggedHash(T_NONCE, t, px, m) + const { rx, k } = extractK(rand) + // Let e = int(hash/challenge(bytes(R) || bytes(P) || m)) mod n. + const e = challenge(rx, px, m) + const sig = createSigSchnorr(k, rx, e, d) + // If Verify(bytes(P), m, sig) (see below) returns failure, abort + if (!verifySchnorr(sig, m, px)) err(E_INVSIG) + return sig + } -static signSchnorrAsync = async ( - message: Bytes, - secretKey: Bytes, - auxRand: Bytes = randomBytes(L) -): Promise => { - static { m, px, d, a } = prepSigSchnorr(message, secretKey, auxRand) - static aux = await taggedHashAsync(T_AUX, a) - // Let t be the byte-wise xor of bytes(d) and hash/aux(a) - static t = numTo32b(d ^ bytesToNumBE(aux)) - // Let rand = hash/nonce(t || bytes(P) || m) - static rand = await taggedHashAsync(T_NONCE, t, px, m) - static { rx, k } = extractK(rand) - // Let e = int(hash/challenge(bytes(R) || bytes(P) || m)) mod n. - static e = await challengeAsync(rx, px, m) - static sig = createSigSchnorr(k, rx, e, d) - // If Verify(bytes(P), m, sig) (see below) returns failure, abort - if (!(await verifySchnorrAsync(sig, m, px))) err(E_INVSIG) - return sig -} + static signSchnorrAsync = async ( + message: Bytes, + secretKey: Bytes, + auxRand: Bytes = randomBytes(L) + ): Promise => { + const { m, px, d, a } = prepSigSchnorr(message, secretKey, auxRand) + const aux = await taggedHashAsync(T_AUX, a) + // Let t be the byte-wise xor of bytes(d) and hash/aux(a) + const t = numTo32b(d ^ bytesToNumBE(aux)) + // Let rand = hash/nonce(t || bytes(P) || m) + const rand = await taggedHashAsync(T_NONCE, t, px, m) + const { rx, k } = extractK(rand) + // Let e = int(hash/challenge(bytes(R) || bytes(P) || m)) mod n. + const e = await challengeAsync(rx, px, m) + const sig = createSigSchnorr(k, rx, e, d) + // If Verify(bytes(P), m, sig) (see below) returns failure, abort + if (!(await verifySchnorrAsync(sig, m, px))) err(E_INVSIG) + return sig + } -// const finishVerif = (P_: Point, r: bigint, s: bigint, e: bigint) => {}; + // const finishVerif = (P_: Point, r: bigint, s: bigint, e: bigint) => {}; -type MaybePromise = T | Promise -static callSyncAsyncFn = (res: MaybePromise, later: (res2: T) => O) => { - return res instanceof Promise ? res.then(later) : later(res) -} + static callSyncAsyncFn = (res: MaybePromise, later: (res2: T) => O) => { + return res instanceof Promise ? res.then(later) : later(res) + } -static _verifSchnorr = ( - signature: Bytes, - message: Bytes, - publicKey: Bytes, - challengeFn: (...args: Bytes[]) => bigint | Promise -): boolean | Promise => { - static sig = abytes(signature, L2, 'signature') - static msg = abytes(message, undefined, 'message') - static pub = abytes(publicKey, L, 'publicKey') - try { - // lift_x from BIP340. Convert 32-byte x coordinate to elliptic curve point. - // Fail if x ≥ p. Let c = x³ + 7 mod p. - const x = bytesToNumBE(pub) - const y = lift_x(x) // Let y = c^(p+1)/4 mod p. - const y_ = isEven(y) ? y : M(-y) - // Return the unique point P such that x(P) = x and - // y(P) = y if y mod 2 = 0 or y(P) = p-y otherwise. - const P_ = new Point(x, y_, 1n).assertValidity() - const px = numTo32b(P_.toAffine().x) - // P = lift_x(int(pk)); fail if that fails - const r = sliceBytesNumBE(sig, 0, L) // Let r = int(sig[0:32]); fail if r ≥ p. - arange(r, 1n, P) - const s = sliceBytesNumBE(sig, L, L2) // Let s = int(sig[32:64]); fail if s ≥ n. - arange(s, 1n, N) - const i = concatBytes(numTo32b(r), px, msg) - // int(challenge(bytes(r)||bytes(P)||m))%n - return callSyncAsyncFn(challengeFn(i), (e) => { - const { x, y } = doubleScalarMulUns(P_, s, modN(-e)).toAffine() // R = s⋅G - e⋅P - if (!isEven(y) || x !== r) return false // -eP == (n-e)P - return true // Fail if is_infinite(R) / not has_even_y(R) / x(R) ≠ r. - }) - } catch (error) { - return false + static _verifSchnorr = ( + signature: Bytes, + message: Bytes, + publicKey: Bytes, + challengeFn: (...args: Bytes[]) => bigint | Promise + ): boolean | Promise => { + const sig = this.abytes(signature, this.L2, 'signature') + const msg = this.abytes(message, undefined, 'message') + const pub = this.abytes(publicKey, this.L, 'publicKey') + try { + // lift_x from BIP340. Convert 32-byte x coordinate to elliptic curve point. + // Fail if x ≥ p. Let c = x³ + 7 mod p. + const x = this.bytesToNumBE(pub) + const y = this.lift_x(x) // Let y = c^(p+1)/4 mod p. + const y_ = this.isEven(y) ? y : this.M(-y) + // Return the unique point P such that x(P) = x and + // y(P) = y if y mod 2 = 0 or y(P) = p-y otherwise. + const P_ = new Point(x, y_, 1n).assertValidity() + const px = this.numTo32b(P_.toAffine().x) + // P = lift_x(int(pk)); fail if that fails + const r = this.sliceBytesNumBE(sig, 0, this.L) // Let r = int(sig[0:32]); fail if r ≥ p. + this.arange(r, 1n, this.P) + const s = this.sliceBytesNumBE(sig, this.L, this.L2) // Let s = int(sig[32:64]); fail if s ≥ n. + this.arange(s, 1n, this.N) + const i = this.concatBytes(this.numTo32b(r), px, msg) + // int(challenge(bytes(r)||bytes(P)||m))%n + return this.callSyncAsyncFn(challengeFn(i), (e) => { + const { x, y } = this.doubleScalarMulUns(P_, s, this.modN(-e)).toAffine() // R = s⋅G - e⋅P + if (!this.isEven(y) || x !== r) return false // -eP == (n-e)P + return true // Fail if is_infinite(R) / not has_even_y(R) / x(R) ≠ r. + }) + } catch (error) { + return false + } } -} -/** - * Verifies Schnorr signature. - * Will swallow errors & return false except for initial type validation of arguments. - */ -static verifySchnorr = (s: Bytes, m: Bytes, p: Bytes): boolean => - _verifSchnorr(s, m, p, challenge) as boolean -static verifySchnorrAsync = async (s: Bytes, m: Bytes, p: Bytes): Promise => - _verifSchnorr(s, m, p, challengeAsync) as Promise + /** + * Verifies Schnorr signature. + * Will swallow errors & return false except for initial type validation of arguments. + */ + static verifySchnorr = (s: Bytes, m: Bytes, p: Bytes): boolean => + this._verifSchnorr(s, m, p, this.challenge) as boolean + static verifySchnorrAsync = async (s: Bytes, m: Bytes, p: Bytes): Promise => + this._verifSchnorr(s, m, p, this.challengeAsync) as Promise -static schnorr: { - keygen: typeof keygenSchnorr, - getPublicKey: typeof pubSchnorr - sign: typeof signSchnorr - verify: typeof verifySchnorr - signAsync: typeof signSchnorrAsync, - verifyAsync: typeof verifySchnorrAsync -} = { - keygen: keygenSchnorr, - getPublicKey: pubSchnorr, - sign: signSchnorr, - verify: verifySchnorr, - signAsync: signSchnorrAsync, - verifyAsync: verifySchnorrAsync, -} + static schnorr: { + keygen: typeof Secp256k1.keygenSchnorr, + getPublicKey: typeof Secp256k1.pubSchnorr + sign: typeof Secp256k1.signSchnorr + verify: typeof Secp256k1.verifySchnorr + signAsync: typeof Secp256k1.signSchnorrAsync, + verifyAsync: typeof Secp256k1.verifySchnorrAsync + } = { + keygen: this.keygenSchnorr, + getPublicKey: this.pubSchnorr, + sign: this.signSchnorr, + verify: this.verifySchnorr, + signAsync: this.signSchnorrAsync, + verifyAsync: this.verifySchnorrAsync, + } -// ## Precomputes -// -------------- + // ## Precomputes + // -------------- -static W = 8 // W is window size -static scalarBits = 256 -static pwindows = Math.ceil(scalarBits / W) + 1 // 33 for W=8, NOT 32 - see wNAF loop -static pwindowSize = 2 ** (W - 1) // 128 for W=8 -static precompute = () => { - static points: Point[] = [] - let p = G - let b = p - for (let w = 0; w < pwindows; w++) { - b = p - points.push(b) - for (let i = 1; i < pwindowSize; i++) { - b = b.add(p) + static W = 8 // W is window size + static scalarBits = 256 + static pwindows = Math.ceil(this.scalarBits / this.W) + 1 // 33 for W=8, NOT 32 - see wNAF loop + static pwindowSize = 2 ** (this.W - 1) // 128 for W=8 + static precompute = () => { + const points: Point[] = [] + let p = this.G + let b = p + for (let w = 0; w < this.pwindows; w++) { + b = p points.push(b) - } // i=1, bc we skip 0 - p = b.double() + for (let i = 1; i < this.pwindowSize; i++) { + b = b.add(p) + points.push(b) + } // i=1, bc we skip 0 + p = b.double() + } + return points + } + static Gpows: Point[] | undefined = undefined // precomputes for base point G + // const-time negate + static ctneg = (cnd: boolean, p: Point) => { + const n = p.negate() + return cnd ? n : p } - return points -} -let Gpows: Point[] | undefined = undefined // precomputes for base point G -// const-time negate -static ctneg = (cnd: boolean, p: Point) => { - static n = p.negate() - return cnd ? n : p -} -/** - * Precomputes give 12x faster getPublicKey(), 10x sign(), 2x verify() by - * caching multiples of G (base point). Cache is stored in 32MB of RAM. - * Any time `G.multiply` is done, precomputes are used. - * Not used for getSharedSecret, which instead multiplies random pubkey `P.multiply`. - * - * w-ary non-adjacent form (wNAF) precomputation method is 10% slower than windowed method, - * but takes 2x less RAM. RAM reduction is possible by utilizing `.subtract`. - * - * !! Precomputes can be disabled by commenting-out call of the wNAF() inside Point#multiply(). - */ -static wNAF = (n: bigint): { p: Point; f: Point } => { - static comp = Gpows || (Gpows = precompute()) - let p = I - let f = G // f must be G, or could become I in the end - static pow_2_w = 2 ** W // 256 for W=8 - static maxNum = pow_2_w // 256 for W=8 - static mask = big(pow_2_w - 1) // 255 for W=8 == mask 0b11111111 - static shiftBy = big(W) // 8 for W=8 - for (let w = 0; w < pwindows; w++) { - let wbits = Number(n & mask) // extract W bits. - n >>= shiftBy // shift number by W bits. - // We use negative indexes to reduce size of precomputed table by 2x. - // Instead of needing precomputes 0..256, we only calculate them for 0..128. - // If an index > 128 is found, we do (256-index) - where 256 is next window. - // Naive: index +127 => 127, +224 => 224 - // Optimized: index +127 => 127, +224 => 256-32 - if (wbits > pwindowSize) { - wbits -= maxNum - n += 1n - } - const off = w * pwindowSize - const offF = off // offsets, evaluate both - const offP = off + Math.abs(wbits) - 1 - const isEven = w % 2 !== 0 // conditions, evaluate both - const isNeg = wbits < 0 - if (wbits === 0) { - // off == I: can't add it. Adding random offF instead. - f = f.add(ctneg(isEven, comp[offF])) // bits are 0: add garbage to fake point - } else { - p = p.add(ctneg(isNeg, comp[offP])) // bits are 1: add to result point + /** + * Precomputes give 12x faster getPublicKey(), 10x sign(), 2x verify() by + * caching multiples of G (base point). Cache is stored in 32MB of RAM. + * Any time `G.multiply` is done, precomputes are used. + * Not used for getSharedSecret, which instead multiplies random pubkey `P.multiply`. + * + * w-ary non-adjacent form (wNAF) precomputation method is 10% slower than windowed method, + * but takes 2x less RAM. RAM reduction is possible by utilizing `.subtract`. + * + * !! Precomputes can be disabled by commenting-out call of the wNAF() inside Point#multiply(). + */ + static wNAF = (n: bigint): { p: Point; f: Point } => { + const comp = this.Gpows || (this.Gpows = this.precompute()) + let p = this.I + let f = this.G // f must be G, or could become I in the end + const pow_2_w = 2 ** this.W // 256 for W=8 + const maxNum = pow_2_w // 256 for W=8 + const mask = this.big(pow_2_w - 1) // 255 for W=8 == mask 0b11111111 + const shiftBy = this.big(this.W) // 8 for W=8 + for (let w = 0; w < this.pwindows; w++) { + let wbits = Number(n & mask) // extract W bits. + n >>= shiftBy // shift number by W bits. + // We use negative indexes to reduce size of precomputed table by 2x. + // Instead of needing precomputes 0..256, we only calculate them for 0..128. + // If an index > 128 is found, we do (256-index) - where 256 is next window. + // Naive: index +127 => 127, +224 => 224 + // Optimized: index +127 => 127, +224 => 256-32 + if (wbits > this.pwindowSize) { + wbits -= maxNum + n += 1n + } + const off = w * this.pwindowSize + const offF = off // offsets, evaluate both + const offP = off + Math.abs(wbits) - 1 + const isEven = w % 2 !== 0 // conditions, evaluate both + const isNeg = wbits < 0 + if (wbits === 0) { + // off == I: can't add it. Adding random offF instead. + f = f.add(this.ctneg(isEven, comp[offF])) // bits are 0: add garbage to fake point + } else { + p = p.add(this.ctneg(isNeg, comp[offP])) // bits are 1: add to result point + } } + if (n !== 0n) this.err('invalid wnaf') + return { p, f } // return both real and fake points for JIT } - if (n !== 0n) err('invalid wnaf') - return { p, f } // return both real and fake points for JIT -} } // !! Remove the export below to easily use in REPL / browser console -- 2.47.3