// SPDX-License-Identifier: GPL-3.0-only
// Copyright (c) 2022, Sylvain Huet, Ambermind
// Minimacy (r) System
use core.crypto.primal;;

fun _randomN(N)= bigRand(bigNbits(N)-1, false);;

fun _joinKey(N, x, y)=
	let (7+bigNbits(N))/8 -> nbytes in
	strConcat(bigSerialize(x, 1), bigSerialize(y, nbytes));;

fun _splitKey(key)=
	[bigDeserialize(strLeft(key, 1)), bigDeserialize(strTail(key, 1))];;

fun _computeY(N, x, polynomial)=
\mod( N)
	if polynomial==nil then 0
	else head(polynomial)+x*_computeY(N, x, tail(polynomial));;

fun _computeKeys(N, n, polynomial)=
	if n>0 then
	let bigFromInt(n) -> x in
	let _computeY(N, x, polynomial) -> y in
	let _joinKey(N, x, y) -> key in
	key::_computeKeys(N, n-1, polynomial);;

fun _computePolynomial(N, nb)=
	if nb>0 then _randomN(N) ::_computePolynomial(N, nb-1);;

fun _lagrangeProduct(N, x, y, i, j)=
	if j>=arrayLength(x) then y[i]
	else if j==i then _lagrangeProduct(N, x, y, i, j+1)
	else let _lagrangeProduct(N, x, y, i, j+1) -> p in
	\mod( N) p*((x[j])/(x[j] - x[i]));;

fun _lagrangeSum(N, x, y, i)=
	if i>=arrayLength(x) then bigFromInt(0)
	else
	let _lagrangeProduct(N, x, y, i, 0) -> p in
	let _lagrangeSum(N, x, y, i+1) -> S in
	\mod( N) S+p;;

fun _shamirCheck(N, S, nbNeeded, keys, testList)=
	if nbNeeded==0 then (S<>shamirSolve(N, testList))
	else if keys<>nil then
	if _shamirCheck(N, S, nbNeeded-1, tail(keys), head(keys)::testList) then true
	else _shamirCheck(N, S, nbNeeded, tail(keys), testList);;

//----------- API
// the secret may come from another source. Else this function can generate it
fun shamirMakeSecret(nbits)= bigSerialize(bigRand(nbits, true), nil);;

// the finite field may come from another source. Else this function selects a finite Field Z/NZ with N primal and one bit greater than S
fun shamirFiniteField(S)= bigPrimal(1+bigNbits(bigDeserialize(S)), 16);;

// for a given secret S and a finite field Z/NZ:
// - compute nbKeys keys so that any set of exactly nbNeeded of them can recover the secret
// - check every combinations of nbNeeded keys, to prevent from a degenerated polynomial or a wrong finite field (when N not primal)
// - returns the list of keys or nil
fun shamirFromSecret(N, S, nbNeeded, nbKeys)=
	if range(nbKeys, 1, 255) then
	if range(nbNeeded, 1, nbKeys) then
	let bigDeserialize(S) -> a0 in
	let a0::_computePolynomial(N, nbNeeded-1) -> polynomial in
	let _computeKeys(N, nbKeys, polynomial) -> keys in
	if !_shamirCheck(N, S, nbNeeded, keys, nil) then keys;;

// recover the secret S from a list of keys in a finite field Z/NZ
// keys should contain nbNeeded keys from the keys generated by function shamirFromSecret
// https://en.wikipedia.org/wiki/Lagrange_polynomial#Definition
fun shamirSolve(N, keys)=
	let arrayFromList(listMap(keys, lambda(k)= let _splitKey(k) ->[x, y] in x)) -> x in
	let arrayFromList(listMap(keys, lambda(k)= let _splitKey(k) ->[x, y] in y)) -> y in
	let _lagrangeSum(N, x, y, 0) -> S in
	bigSerialize(S, nil);;

/*
fun shamirTest()=
	for i=0;i<20 do
	let shamirMakeSecret (127) -> S in
	let shamirFiniteField (S) -> N in
	let shamirFromSecret (N, S, 4, 6) -> keys in
	(
		echoLn "done:";
		echoLn hexFromStr (S);
		echoLn hexFromBig (N);
		for k in keys do echoLn hexFromStr (k);
	);;
fun main()=shamirTest();;
*/