From 839cad6d9aeb5872392f325cff6a27bf93cc79e1 Mon Sep 17 00:00:00 2001 From: Chris Duncan Date: Fri, 5 Dec 2025 13:19:03 -0800 Subject: [PATCH] Promote point addition to class static member. Start consolidating mod functions. --- src/lib/crypto/secp256k1.ts | 157 ++++++++++++++++++------------------ 1 file changed, 78 insertions(+), 79 deletions(-) diff --git a/src/lib/crypto/secp256k1.ts b/src/lib/crypto/secp256k1.ts index db1693b..e379e9e 100644 --- a/src/lib/crypto/secp256k1.ts +++ b/src/lib/crypto/secp256k1.ts @@ -18,7 +18,6 @@ type Point = { equals: (other: Point) => boolean negate: () => Point double: () => Point - add: (other: Point) => Point toAffine: () => AffinePoint assertValidity: () => Point toBytes: (isCompressed?: boolean) => Bytes @@ -116,30 +115,29 @@ export class Secp256k1 { } /** modular division */ - static M (a: bigint, b: bigint): bigint { - const r = a % b - return r >= 0n ? r : b + r + static M (a: bigint): bigint { + const r = a % this.P + return r >= 0n ? r : this.P + r } - static modP = (a: bigint) => this.M(a, this.P) /** Modular inversion using eucledian GCD (non-CT). No negative exponent for now. */ // prettier-ignore - static invert (num: bigint, md: bigint): bigint { - if (num === 0n || md <= 0n) this.err('no inverse n=' + num + ' mod=' + md) - let a = this.M(num, md), b = md, x = 0n, y = 1n, u = 1n, v = 0n + static invert (num: bigint): bigint { + if (num === 0n || this.P <= 0n) this.err('no inverse n=' + num + ' mod=' + this.P) + let a = this.M(num), b = this.P, x = 0n, y = 1n, u = 1n, v = 0n while (a !== 0n) { const q = b / a, r = b % a const m = x - u * q, n = y - v * q b = a, a = r, x = u, y = v, u = m, v = n } - return b === 1n ? this.M(x, md) : this.err('no inverse') // b is gcd at this point + return b === 1n ? this.M(x) : this.err('no inverse') // b is gcd at this point } // ## End of Helpers // ----------------- /** secp256k1 formula. Koblitz curves are subclass of weierstrass curves with a=0, making it x³+b */ - static koblitz = (x: bigint): bigint => this.modP(this.modP(x * x) * x + this.b) + static koblitz = (x: bigint): bigint => this.M(this.M(x * x) * x + this.b) static isEven = (y: bigint): boolean => (y & 1n) === 0n static getPrefix = (y: bigint) => Uint8Array.of(this.isEven(y) ? 0x02 : 0x03) /** lift_x from BIP340 calculates square root. Validates x, then validates root*root. */ @@ -156,7 +154,62 @@ export class Secp256k1 { if (e & 1n) r = (r * num) % this.P // Uses exponentiation by squaring. num = (num * num) % this.P // Not constant-time. } - return this.modP(r * r) === c ? r : this.err('sqrt invalid') // check if result is valid + return this.M(r * r) === c ? r : this.err('sqrt invalid') // check if result is valid + } + + /** + * Point addition: P+Q, complete, exception-free formula + * (Renes-Costello-Batina, algo 1 of [2015/1060](https://eprint.iacr.org/2015/1060)). + * Cost: `12M + 0S + 3*a + 3*b3 + 23add`. + */ + static Add (p: Point, q: Point): Point { + const { X: X1, Y: Y1, Z: Z1 } = p + const { X: X2, Y: Y2, Z: Z2 } = q + const P = this.P + const a = this.a + const b3 = this.M(this.b * 3n) + let X3 = 0n, Y3 = 0n, Z3 = 0n + let t0 = this.M(X1 * X2) // step 1 + let t1 = this.M(Y1 * Y2) + let t2 = this.M(Z1 * Z2) + let t3 = this.M(X1 + Y1) + let t4 = this.M(X2 + Y2) // step 5 + t3 = this.M(t3 * t4) + t4 = this.M(t0 + t1) + t3 = this.M(t3 - t4) + t4 = this.M(X1 + Z1) + let t5 = this.M(X2 + Z2) // step 10 + t4 = this.M(t4 * t5) + t5 = this.M(t0 + t2) + t4 = this.M(t4 - t5) + t5 = this.M(Y1 + Z1) + X3 = this.M(Y2 + Z2) // step 15 + t5 = this.M(t5 * X3) + X3 = this.M(t1 + t2) + t5 = this.M(t5 - X3) + Z3 = this.M(a * t4) + X3 = this.M(b3 * t2) // step 20 + Z3 = this.M(X3 + Z3) + X3 = this.M(t1 - Z3) + Z3 = this.M(t1 + Z3) + Y3 = this.M(X3 * Z3) + t1 = this.M(t0 + t0) // step 25 + t1 = this.M(t1 + t0) + t2 = this.M(a * t2) + t4 = this.M(b3 * t4) + t1 = this.M(t1 + t2) + t2 = this.M(t0 - t2) // step 30 + t2 = this.M(a * t2) + t4 = this.M(t4 + t2) + t0 = this.M(t1 * t4) + Y3 = this.M(Y3 + t0) + t0 = this.M(t5 * t4) // step 35 + X3 = this.M(t3 * X3) + X3 = this.M(X3 - t0) + t0 = this.M(t3 * t1) + Z3 = this.M(t5 * Z3) + Z3 = this.M(Z3 + t0) // step 40 + return this.Point(X3, Y3, Z3) } /** Point in 3d xyz projective coordinates. 3d takes less inversions than 2d. */ @@ -170,73 +223,19 @@ export class Secp256k1 { equals (other: Point): boolean { const { X: X1, Y: Y1, Z: Z1 } = this const { X: X2, Y: Y2, Z: Z2 } = other - const X1Z2 = secp256k1.modP(X1 * Z2) - const X2Z1 = secp256k1.modP(X2 * Z1) - const Y1Z2 = secp256k1.modP(Y1 * Z2) - const Y2Z1 = secp256k1.modP(Y2 * Z1) + const X1Z2 = secp256k1.M(X1 * Z2) + const X2Z1 = secp256k1.M(X2 * Z1) + const Y1Z2 = secp256k1.M(Y1 * Z2) + const Y2Z1 = secp256k1.M(Y2 * Z1) return X1Z2 === X2Z1 && Y1Z2 === Y2Z1 }, /** Flip point over y coordinate. */ negate (): Point { - return secp256k1.Point(X, secp256k1.modP(-Y), Z) + return secp256k1.Point(X, secp256k1.M(-Y), Z) }, /** Point doubling: P+P, complete formula. */ double (): Point { - return this.add(this) - }, - /** - * Point addition: P+Q, complete, exception-free formula - * (Renes-Costello-Batina, algo 1 of [2015/1060](https://eprint.iacr.org/2015/1060)). - * Cost: `12M + 0S + 3*a + 3*b3 + 23add`. - */ - add (other: Point): Point { - const M = (v: bigint): bigint => secp256k1.modP(v) - const { X: X1, Y: Y1, Z: Z1 } = { X, Y, Z } - const { X: X2, Y: Y2, Z: Z2 } = other - const a = 0n - const b3 = M(secp256k1.b * 3n) - let X3 = 0n, Y3 = 0n, Z3 = 0n - let t0 = M(X1 * X2) // step 1 - let t1 = M(Y1 * Y2) - let t2 = M(Z1 * Z2) - let t3 = M(X1 + Y1) - let t4 = M(X2 + Y2) // step 5 - t3 = M(t3 * t4) - t4 = M(t0 + t1) - t3 = M(t3 - t4) - t4 = M(X1 + Z1) - let t5 = M(X2 + Z2) // step 10 - t4 = M(t4 * t5) - t5 = M(t0 + t2) - t4 = M(t4 - t5) - t5 = M(Y1 + Z1) - X3 = M(Y2 + Z2) // step 15 - t5 = M(t5 * X3) - X3 = M(t1 + t2) - t5 = M(t5 - X3) - Z3 = M(a * t4) - X3 = M(b3 * t2) // step 20 - Z3 = M(X3 + Z3) - X3 = M(t1 - Z3) - Z3 = M(t1 + Z3) - Y3 = M(X3 * Z3) - t1 = M(t0 + t0) // step 25 - t1 = M(t1 + t0) - t2 = M(a * t2) - t4 = M(b3 * t4) - t1 = M(t1 + t2) - t2 = M(t0 - t2) // step 30 - t2 = M(a * t2) - t4 = M(t4 + t2) - t0 = M(t1 * t4) - Y3 = M(Y3 + t0) - t0 = M(t5 * t4) // step 35 - X3 = M(t3 * X3) - X3 = M(X3 - t0) - t0 = M(t3 * t1) - Z3 = M(t5 * Z3) - Z3 = M(Z3 + t0) // step 40 - return secp256k1.Point(X3, Y3, Z3) + return secp256k1.Add(this, this) }, /** Convert point to 2d xy affine point. (X, Y, Z) ∋ (x=X/Z, y=Y/Z) */ toAffine (): AffinePoint { @@ -244,11 +243,11 @@ export class Secp256k1 { // fast-paths for ZERO point OR Z=1 if (this.equals(secp256k1.I)) return { x: 0n, y: 0n } if (z === 1n) return { x, y } - const iz = secp256k1.invert(z, secp256k1.P) + const iz = secp256k1.invert(z) // (Z * Z^-1) must be 1, otherwise bad math - if (secp256k1.modP(z * iz) !== 1n) secp256k1.err('inverse invalid') + if (secp256k1.M(z * iz) !== 1n) secp256k1.err('inverse invalid') // x = X*Z^-1; y = Y*Z^-1 - return { x: secp256k1.modP(x * iz), y: secp256k1.modP(y * iz) } + return { x: secp256k1.M(x * iz), y: secp256k1.M(y * iz) } }, /** Checks if the point is valid and on-curve. */ assertValidity (): Point { @@ -256,7 +255,7 @@ export class Secp256k1 { secp256k1.bigintInRange(x, 1n, secp256k1.P) // must be in range 1 <= x,y < P secp256k1.bigintInRange(y, 1n, secp256k1.P) // y² == x³ + ax + b, equation sides must be equal - return secp256k1.modP(y * y) === secp256k1.koblitz(x) ? this : secp256k1.err('bad point: not on curve') + return secp256k1.M(y * y) === secp256k1.koblitz(x) ? this : secp256k1.err('bad point: not on curve') }, /** Converts point to 33/65-byte Uint8Array. */ toBytes (isCompressed = true): Bytes { @@ -283,7 +282,7 @@ export class Secp256k1 { let y = this.lift_x(x) const evenY = this.isEven(y) const evenH = this.isEven(BigInt(head)) - if (evenH !== evenY) y = this.modP(-y) + if (evenH !== evenY) y = this.M(-y) p = this.Point(x, y, 1n) } // Uncompressed 65-byte point, 0x04 prefix @@ -362,7 +361,7 @@ export class Secp256k1 { b = p points.push(b) for (let i = 1; i < this.pwindowSize; i++) { - b = b.add(p) + b = this.Add(b, p) points.push(b) } // i=1, bc we skip 0 p = b.double() @@ -401,9 +400,9 @@ export class Secp256k1 { const isNeg = wbits < 0 if (wbits === 0) { // off == I: can't add it. Adding random offF instead. - f = f.add(this.ctneg(isEven, comp[offsetF])) // bits are 0: add garbage to fake point + f = this.Add(f, this.ctneg(isEven, comp[offsetF])) // bits are 0: add garbage to fake point } else { - p = p.add(this.ctneg(isNeg, comp[offsetP])) // bits are 1: add to result point + p = this.Add(p, this.ctneg(isNeg, comp[offsetP])) // bits are 1: add to result point } } if (n !== 0n) this.err('invalid wnaf') -- 2.47.3