sss.ts

import * as bigintConversion from "bigint-conversion";

const extendedGcd = (
	a: bigint,
	b: bigint
): { result: bigint; x: bigint; y: bigint } => {
	if (a === 0n) return { result: b, x: 0n, y: 1n };
	const { result, x: x1, y: y1 } = extendedGcd(b % a, a);
	return { result, x: y1 - (b / a) * x1, y: x1 };
};

const modulo = (a: bigint, m: bigint) => ((a % m) + m) % m;

const fastModularInverse = (a: bigint, m: bigint): bigint => {
	const { result: g, x } = extendedGcd(a, m);
	if (g != 1n) throw new Error("Inverse does not exist!");
	return modulo(x, m);
};

/**
 * Derives a new polynomial given the supplied co a
 * @param coefficients The coefficients in the order from the lowest degree term
 *     to the highest degree term
 * @returns A function that will act as a polynomial. Bear in mind: no modulo
 *     is applied
 */
const polynomial = (coefficients: bigint[]) => (x: bigint) =>
	coefficients.reduce((accum, next, i) => accum + next * x ** BigInt(i));

const concatUint8Array = (a: Uint8Array, b: Uint8Array): Uint8Array => {
	const merged = new Uint8Array(a.length + b.length);
	merged.set(a);
	merged.set(b, a.length);
	return merged;
};

const randIntInRange = (range: bigint): bigint => {
	const buf = bigintConversion.bigintToBuf(range, true) as ArrayBuffer;
	const u8a = new Uint8Array(buf).slice(1);
	const randVal = crypto.getRandomValues(u8a);
	if (!u8a[0]) {
		throw new Error("A fatal error occurred");
	}
	return bigintConversion.bufToBigint(
		concatUint8Array(
			new Uint8Array([(Math.random() * (u8a[0] - 0b10000000)) | 0]),
			randVal
		)
	);
};

/**
 * Performs a Fisher-Yates shuffle on an array in place
 * @param array The array to shuffle
 * @returns The same array, shuffled
 */
const shuffle = <T>(array: T[]): T[] => {
	for (let i = array.length - 1; i > 0; i--) {
		const j = Math.floor(Math.random() * (i + 1));
		[array[i], array[j]] = [array[j], array[i]];
	}
	return array;
};

/**
 * The literal Ed25519 curve prime. Screw it. Let's use that
 */
const prime =
	0xffffffff00000001000000000000000000000000ffffffffffffffffffffffffn;

const randomCoefficients = Array.from({ length: 4 }).map(() =>
	randIntInRange(prime)
);

const message = 0x1337n; // 4919 in DEC

const f = polynomial([message, ...randomCoefficients]);

const randomPoints = Array.from({ length: randomCoefficients.length * 2 })
	.map(() => randIntInRange(prime))
	.map((x) => [x, modulo(f(x), prime)] as [bigint, bigint]);

const recoverLagrange = (points: [bigint, bigint][], prime: bigint) =>
	points.reduce(
		(sum, [, y], i) =>
			modulo(
				sum +
					y *
						points.reduce((product, [x], j) => {
							return j !== i
								? modulo(
										x *
											fastModularInverse(
												modulo(x - points[i][0], prime),
												prime
											) *
											product,
										prime
								  )
								: product;
						}, 1n),
				prime
			),
		0n
	);

const shuffled = shuffle(
	[...randomPoints].slice(0, randomCoefficients.length + 1)
);

console.log(recoverLagrange(shuffled, prime));