nistp256 point decompression

decompress.ts

/*
NOTE: arithnetic here is NOT CONSTANT TIME

This is mostly ok since we're operating on public keys.
*/

const P256_P = BigInt("0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff");
const P256_A = BigInt("0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc");
const P256_B = BigInt("0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b");
const P256_N = BigInt("0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551");
const P256_P_PLUS_ONE_OVER_4 = (P256_P + 1n) / 4n;

function BEu8toBigInt(buf: Uint8Array): bigint {
	return buf.reduce(
		(a, n, i) => a + (
			BigInt(n) << BigInt(8 * (buf.length - i - 1))
		),
		0n
	);
}

// size in bytes
function BigIntToBEu8(n: bigint, size: number): Uint8Array {
	return new Uint8Array([...Array(size)].map((_, i) => 
		Number(BigInt.asUintN(8, n >> BigInt((size - i - 1) * 8)))
	))
}

// (a^16)%n
function pow16mod(a: bigint, n: bigint): bigint {
	a = (a * a) % n;
	a = (a * a) % n;
	a = (a * a) % n;
	a = (a * a) % n;
	return a
}

// efficiently-ish compute (a^b)%n
function powmod(a: bigint, b: bigint, n: bigint): bigint {
	const a_lut = [1n];
	for (let i=0; i<15; i++) {
		a_lut.push((a_lut[i] * a) % n);
	}
	return Array.from(b.toString(16)).reduce(
		(acc, bi) => ((pow16mod(acc, n) * a_lut[parseInt(bi, 16)])) % n,
		1n
	);
}

function p256decompress(compressed: Uint8Array): Uint8Array {
	if (!(compressed[0] === 2 || compressed[0] === 3)) {
		throw new Error("not a compressed point");
	}
	if (compressed.length !== 33) {
		throw new Error("invalid compressed point length");
	}

	const x = BEu8toBigInt(compressed.slice(1));

	const y_squared = (x ** 3n + P256_A * x + P256_B) % P256_P;

	// sqrt via tonelli shanks
	let y = powmod(y_squared, P256_P_PLUS_ONE_OVER_4, P256_P);

	// check the result is valid
	if (((y * y) % P256_P) != y_squared) {
		throw new Error("invalid curve point");
	}

	// parity correction
	if ((compressed[0] ^ Number(BigInt.asUintN(1, y))) & 1) {
		y = P256_P - y;
	}

	const res = new Uint8Array(1 + 32 + 32);
	res.set([4], 0);
	res.set(BigIntToBEu8(x, 32), 1);
	res.set(BigIntToBEu8(y, 32), 1 + 32);

	return res;
}

console.log(p256decompress(new Uint8Array([3, 6, 51, 14, 4, 53, 11, 220, 220, 210, 226, 96, 98, 247, 174, 134, 146, 179, 181, 149, 85, 92, 84, 143, 219, 95, 152, 13, 43, 46, 137, 149, 188])))
console.log(p256decompress(new Uint8Array([2, 162, 161, 22, 14, 215, 20, 47, 145, 27, 220, 35, 23, 191, 119, 106, 245, 200, 208, 181, 246, 39, 153, 5, 130, 67, 253, 61, 230, 5, 234, 100, 88])))

console.log(p256decompress(new Uint8Array([3, 143, 159, 2, 99, 165, 174, 89, 69, 27, 134, 252, 39, 253, 198, 211, 113, 58, 181, 114, 70, 138, 53, 236, 116, 197, 173, 162, 102, 6, 124, 89, 208])))
console.log(p256decompress(new Uint8Array([2, 69, 244, 15, 230, 104, 128, 105, 163, 167, 150, 127, 147, 86, 80, 167, 229, 154, 55, 27, 155, 205, 38, 158, 233, 6, 0, 57, 41, 67, 103, 8, 215])))