// SPDX-License-Identifier: GPL-3.0-only
// Copyright (c) 2022, Sylvain Huet, Ambermind
// Minimacy (r) System

struct EllipticCurve=[_name, _P, _Pminus2, _A, _B, _Gopti, _N, _Nminus2, _Pprime, _Bopti, _muN, _add, _mul, _byteLength];;
struct EcKey=[_curveEK, _pubEK, _privEK, _jacobPubEK];;	// public key is a point, private key is a scalar

// http://www.hyperelliptic.org/EFD/index.html

// _muN=bigBarrett(curve._N);
// _Pprime=bigMontgomery(curve._P);
// _Bopti=\modMontgomery( curve._P, curve._Pprime) if curve._name=="secp256k1" then (\in 3)*(\in curve._B) else (\in curve._B);
// _Gopti= jacobian(_G)
// reminder: 1/x mod P = x**(P-2) mod P

// secp256k1 refers to the parameters of the elliptic curve used in Bitcoin's public-key cryptography
const _Secp256k1= [
	_name="secp256k1",
	_P      =\big 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F,
	_Pprime  =\big 0xc9bd1905155383999c46c2c295f2b761bcb223fedc24a059d838091dd2253531,
	_Pminus2=\big 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2D,
	_Bopti  =\big 0x1500005025,
	_A      =\big 0,
	_B      =\big 7,
	_N      =\big 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141,
	_Nminus2=\big 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD036413F,
	_muN    =\big 0x01000000000000000000000000000000014551231950b75fc4402da1732fc9bec0,
	_Gopti=[
		\big 0x9981e643e9089f48979f48c033fd129c231e295329bc66dbd7362e5a487e2097,
		\big 0xcf3f851fd4a582d670b6b59aac19c1368dfc5d5d1f1dc64db15ea6d2d3dbabe2,
		\big 0x01000003d1
	],
	_add=#_ecAddWeierstrass0,
	_mul=#_ecMulWeierstrass0,
	_byteLength=32
];;

const _Secp256r1=[
	_name="secp256r1",
	_P=    \big 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF,
	_Pprime=\big 0xffffffff00000002000000000000000000000001000000000000000000000001,
	_Pminus2=\big 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFD,
	_Bopti=\big 0xdc30061d04874834e5a220abf7212ed6acf005cd78843090d89cdf6229c4bddf,
	_A=\big 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC,
	_B=\big 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B,
	_N=\big 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551,
	_Nminus2=\big 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC63254F,
	_Gopti=[
		\big 0x18905f76a53755c679fb732b7762251075ba95fc5fedb60179e730d418a9143c,
		\big 0x8571ff1825885d85d2e88688dd21f3258b4ab8e4ba19e45cddf25357ce95560a,
		\big 0xfffffffeffffffffffffffffffffffff000000000000000000000001
	],
	_muN=\big 0x0100000000fffffffffffffffeffffffff43190552df1a6c21012ffd85eedf9bfe,
	_add=#_ecAddWeierstrass3,
	_mul=#_ecMulWeierstrass3,
	_byteLength=32
];;

const _Secp384r1=[
	_name="secp384r1",
	_P=    \big 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF,
	_Pprime=\big 0x14000000140000000c00000002fffffffcfffffffafffffffbfffffffe00000000000000010000000100000001,
	_Pminus2=\big 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFD,
	_Bopti=\big 0xcd08114b604fbff9b62b21f41f022094e3374bee94938ae277f2209b1920022ef729add87a4c32ec081188719d412dcc,
	_A=\big 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFC,
	_B=\big 0xB3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE8141120314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF,
	_N=\big 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52973,
	_Nminus2=\big 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52971,
	_Gopti=[
		\big 0x4d3aadc2299e1513812ff723614ede2b6454868459a30eff879c3afc541b4d6e20e378e2a0d6ce383dd0756649c0b528,
		\big 0x2b78abc25a15c5e9dd8002263969a840c6c3521968f4ffd98bade7562e83b050a1bfa8bf7bb4a9ac23043dad4b03a4fe,
		\big 0x0100000000ffffffffffffffff00000001
	],
	_muN=\big 0x01000000000000000000000000000000000000000000000000389cb27e0bc8d220a7e5f24db74f58851313e695333ad68d,
	_add=#_ecAddWeierstrass3,
	_mul=#_ecMulWeierstrass3,
	_byteLength=48
];;

const _Secp521r1= [
	_name="secp521r1",
	_P=\big 0x01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF,
	_Pprime=\big 0x01,
	_Pminus2=\big 0x01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD,
	_Bopti=\big 0x51953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00,
	_A=\big 0x01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC,
	_B=\big 0x0051953EB9618E1C9A1F929A21A0B68540EEA2DA725B99B315F3B8B489918EF109E156193951EC7E937B1652C0BD3BB1BF073573DF883D2C34F1EF451FD46B503F00,
	_N=\big 0x01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386409,
	_Nminus2=\big 0x01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386407,
	_Gopti=[
		\big 0xc6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66,
		\big 0x011839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650,
		\big 0x01
	],
	_muN=\big 0x02000000000000000000000000000000000000000000000000000000000000000005ae79787c40d069948033feb708f65a2fc44a36477663b851449048e16ec79bf7,
	_add=#_ecAddWeierstrass3,
	_mul=#_ecMulWeierstrass3,
	_byteLength=66
];;

fun ecSecp256k1()= _Secp256k1;;
fun ecSecp256r1()= _Secp256r1;;
fun ecSecp384r1()= _Secp384r1;;
fun ecSecp521r1()= _Secp521r1;;

// O is nil
// other points are [x, y]

fun _ecAddWeierstrass0(curve, p1, p2)=
	bigWeierstrassA0Add(curve._P, curve._Pprime, curve._Bopti, p1, p2);;

fun _ecMulWeierstrass0(constantTime, curve, n, p)=
	if n<>nil then bigWeierstrassA0Mul(constantTime, curve._P, curve._Pprime, curve._Bopti, n, p);;

fun _ecAddWeierstrass3(curve, p1, p2)=
	bigWeierstrassA3Add(curve._P, curve._Pprime, curve._Bopti, p1, p2);;

fun _ecMulWeierstrass3(constantTime, curve, n, p)=
	if n<>nil then bigWeierstrassA3Mul(constantTime, curve._P, curve._Pprime, curve._Bopti, n, p);;

fun _project(curve, p) = 
	if p<>nil then
	let p-> [x, y, z] in 
	\modMontgomery( curve._P, curve._Pprime)
	let z**curve._Pminus2 -> zinv in
	[\out x*zinv, \out y*zinv];;

fun _projectX(curve, p) = 
	if p<>nil then
	let p-> [x, _, z] in 
	\modMontgomery( curve._P, curve._Pprime)
	\out x*(z**curve._Pminus2);;

fun _jacobian(curve, p) = 
	if p<>nil then let p->[x, y] in \modMontgomery(curve._P, curve._Pprime) [\in x, \in y, \in 1];;

fun ecMulG(constantTime, curve, n)=	// n is an integer, p is a point. For example: 3p  = p+p+p
	_project(curve,*) call curve._mul(constantTime, curve, n, curve._Gopti);;

fun ecTest(curve, p)=
	if p==nil then true
	else let p->[x, y] in
	let \mod(curve._P) y**2 - (x**2+curve._A)*x - curve._B -> delta in	// y2=x3+ax+b
	bigIsNull(delta);;

//------------------ API
fun ecName(curve) = curve._name;;

// compute a random number modulo n
fun ecRandom(curve)= bigMod(bigRand(bigNbits(curve._N), false), curve._N);;

fun ecDump(str, p)=
	echo {str, ": "};
	if p==nil then echoLn "O"
	else let p->[x, y] in echoLn strBuild({"[\n ",  hexFromBig(x), "\n ", hexFromBig(y), "\n]"});
	p;;

fun ecStrFromPoint(curve, p) =
	let p->[x, y] in strBuild({"\$04", bigSerialize(x, curve._byteLength), bigSerialize(y, curve._byteLength)});;

fun ecPointFromStr(str) =
	let strGet(str, 0) -> header in
	let strLength(str)>>1 -> len in
	if header==0x04 then [bigDeserialize(strSlice(str, 1, len)), bigDeserialize(strTail(str, 1+len))];;

fun ecKeyDump(key)=
	let key._pubEK -> [x, y] in	(
		echoLn  "EC KEY :";
		echoLn ["curve  : ", ecName(key._curveEK)];
		echoLn ["privKey: ", hexFromBig(key._privEK)];
		echoLn ["pubKey : ", hexFromBig(x)];
		echoLn ["       : ", hexFromBig(y)];
		key
	);;

fun ecKeyCurveName(key)= key._curveEK._name;;

//------- KEY

// create an curve public key from a string curve point
fun ecKeyFromPublic(curve, pubKey)=
	let ecPointFromStr(pubKey) ->pubKey in
	[_curveEK=curve, _pubEK=pubKey, _jacobPubEK=_jacobian(curve, pubKey)];;

// create an curve key from a private key
fun ecKeyFromPrivate(curve, privKey)=
	let ecMulG(true, curve, privKey) -> pubKey in
	[_curveEK=curve, _privEK=privKey, _pubEK=pubKey, _jacobPubEK=_jacobian(curve, pubKey)];;

// create an curve key by computing a random private key
fun ecKeyCreate(curve) =
	if !randomHardware() then echoLn "> Warning: generate EC key with pure software pseudorandom generator";
	ecKeyFromPrivate(curve, ecRandom(curve));;

// get the public key to communicate to Bob
fun ecKeyPublic(key) = ecStrFromPoint(key._curveEK, key._pubEK);;
fun ecKeyPrivate(key)= key._privEK;;

fun ecKeyIsPrivate(key)= key._privEK<>nil;;

//------- ECDH

// mix Alice Key with Bob public key to generate the shared secret
fun ecEcdh(keyAlice, publicBob) =
	let keyAlice._curveEK -> curve in
	let _projectX(curve, *) call curve._mul(true, curve, keyAlice._privEK, _jacobian(curve, ecPointFromStr(publicBob))) -> x in
	bigSerialize(x, curve._byteLength);;

//------- ECDSA

// sign a message
fun ecSign(key, msg, fHash)=
	let key._curveEK -> curve in
	let ecRandom(curve) -> k in	// improve with rfc 6979 ? deterministic nonce
	let ecMulG(true, curve, k) -> R in
\modBarrett( curve._N, curve._muN)
	let bigDeserialize(call fHash(msg)) % -> h in
	let R -> [x, y] in let x % -> r in
	let (h+r*key._privEK)*(k**curve._Nminus2)	// Barrett power uses constant time exponential
	-> s in
	[r, s];;

// verify a signature
fun ecVerify(key, sign, msg, fHash)=
	if sign<>nil then
	let key._curveEK -> curve in
\modBarrett( curve._N, curve._muN)
	let sign -> [r, s] in
	let bigDeserialize(call fHash(msg)) % -> h in
	let bigExpModBarrettFast(s, curve._Nminus2, curve._N, curve._muN) -> w in	// TODO: optimize with non-constant time exponential
	let _projectX(curve, *) call curve._add(curve,
		call curve._mul(false, curve, w*h, curve._Gopti),
		call curve._mul(false, curve, w*r, key._jacobPubEK)
	) -> a in
	let a %-> rr in	// must be equal to r
	r == rr;;