Closed paulmillr closed 1 year ago
Point.fromHex
2x speed-up:
const pow2 = (x: bigint, e: bigint): bigint => {
let res = x;
while (e-- > 0n) { res *= res; res %= P; }
return res;
}
const sqrt = (x: bigint): bigint => {
const b2 = (x * x * x) % P; // x^3, 11
const b3 = (b2 * b2 * x) % P; // x^7
const b6 = (pow2(b3, 3n) * b3) % P;
const b9 = (pow2(b6, 3n) * b3) % P;
const b11 = (pow2(b9, 2n) * b2) % P;
const b22 = (pow2(b11, 11n) * b11) % P;
const b44 = (pow2(b22, 22n) * b22) % P;
const b88 = (pow2(b44, 44n) * b44) % P;
const b176 = (pow2(b88, 88n) * b88) % P;
const b220 = (pow2(b176, 44n) * b44) % P;
const b223 = (pow2(b220, 3n) * b3) % P;
const t1 = (pow2(b223, 23n) * b22) % P;
const t2 = (pow2(t1, 6n) * b2) % P;
const rt = pow2(t2, 2n);
const xc = (rt * rt) % P;
return xc === x ? rt : err();
}
20% faster verify / getSharedSecret / recoverPublicKey:
dbl() {
const { x: X1, y: Y1, z: Z1 } = this; // The "dbl-1998-cmo-2" doubling formulas
const w = (a * Z1 * Z1) + mod(3n * X1 * X1); // 1998 Cohen–Miyaji–Ono
const s = mod(Y1 * Z1); // Cost: 6M + 5S + 1*a + 4add + 1*2+1*3+1*4 + 3*8
const ss = mod(s * s);
const sss = mod(ss * s);
const R = mod(Y1 * s);
const B = mod(X1 * R);
const h = mod((w * w) - mod(8n * B));
const X3 = mod(2n * h * s);
const Y3 = mod(w * mod(4n * B - h) - 8n * mod(R * R));
const Z3 = mod(8n * sss);
return new Point(X3, Y3, Z3);
}
10% faster operations:
const invBatch = (nums: bigint[], p = P): bigint[] => { // batch invert list of bigints
const scratch = new Array(nums.length);
const lastMul = nums.reduce((acc, num, i) => {
if (num === 0n) return acc; // Walk from first to last
scratch[i] = acc; // multiply them by each other mod p
return mod(acc * num, p);
}, 1n);
// Invert last element
const inverted = inv(lastMul, p);
nums.reduceRight((acc, num, i) => { // Walk from last to first
if (num === 0n) return acc; // multiply them by inverted each other mod p
scratch[i] = mod(acc * scratch[i], p);
return mod(acc * num, p);
}, inverted);
return scratch;
};
const normZ = (points: Point[]) => {
const izs = invBatch(points.map(p => p.z));
return points.map((p, i) => p.aff(izs[i])).map(ap => new Point(ap.x, ap.y));
}
// apply normZ in the end of wNAF()
DER encoding
features
const DER = { // asn.1 DER encoding utils
Err: class DERErr extends Error { constructor(m = '') { super(m); } },
_parseInt(data: Uint8Array): { d: bigint; l: Uint8Array } {
const { Err: E } = DER;
if (data.length < 2 || data[0] !== 0x02) throw new E('Invalid signature integer tag');
const len = data[1];
const res = data.subarray(2, len + 2);
if (!len || res.length !== len) throw new E('Invalid signature integer: wrong length');
if (res[0] === 0x00 && res[1] <= 0x7f)
throw new E('Invalid signature integer: trailing length');
// ^ Weird condition: not about length, but about first bytes of number.
return { d: b2n(res), l: data.subarray(len + 2) }; // d is data, l is left
},
toSig(hex: Hex): Signature { // parse DER signature
const { Err: E } = DER;
const data = toU8(hex);
let l = data.length;
if (l < 2 || data[0] != 0x30) throw new E('Invalid signature tag');
if (data[1] !== l - 2) throw new E('Invalid signature: incorrect length');
const { d: r, l: sBytes } = DER._parseInt(data.subarray(2));
const { d: s, l: rBytesLeft } = DER._parseInt(sBytes);
if (rBytesLeft.length) throw new E('Invalid signature: left bytes after parsing');
return new Signature(r, s);
},
fromSig(sig: Signature): Uint8Array {
return h2b(DER.hexFromSig(sig))
},
hexFromSig(sig: Signature): string {
const slice = (s: string): string => Number.parseInt(s[0], 16) >= 8 ? '00' + s : s; // slice DER
const h = (num: number | bigint) => {
const hex = num.toString(16); return hex.length & 1 ? `0${hex}` : hex;
};
const s = slice(h(sig.s)), r = slice(h(sig.r));
const shl = s.length / 2, rhl = r.length / 2;
const sl = h(shl), rl = h(rhl);
return `30${h(rhl + shl + 4)}02${rl}${r}02${sl}${s}`;
},
};
Just leaving a few snippets that could be copy-pasted