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

struct EllipticCurve=[_name, _P, _A, _B, _G, _N, _cofactor, _muP, _muN, _add, _Y2, _byteLength];;
struct EcKey=[_curveEK, _pubEK, _privEK];;	// public key is a point, private key is a scalar

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

// secp256k1 refers to the parameters of the elliptic curve used in Bitcoin's public-key cryptography
fun ecSecp256k1()=
	_ecOptimize([
		_name="secp256k1",
		_P=bigFromHex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F"),
		_A=bigFromInt(0),
		_B=bigFromInt(7),
		_N=bigFromHex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141"),
		_G=[bigFromHex("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798"),
			bigFromHex("483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8")
			],
		_cofactor=1,
		_add=#_ecAddWeierstrass,
		_Y2=#_ecY2Weierstrass,
		_byteLength=32
	]);;

fun ecSecp256r1()=
	_ecOptimize([
		_name="secp256r1",
		_P=bigFromHex("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF"),
		_A=bigFromHex("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC"),
		_B=bigFromHex("5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B"),
		_N=bigFromHex("FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551"),
		_G=[bigFromHex("6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296"),
			bigFromHex("4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5")
			],
		_cofactor=1,
		_add=#_ecAddWeierstrass,
		_Y2=#_ecY2Weierstrass,
		_byteLength=32
	]);;

fun ecSecp384r1()=
	_ecOptimize([
		_name="secp384r1",
		_P=bigFromHex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF"),
		_A=bigFromHex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFC"),
		_B=bigFromHex("B3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE8141120314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF"),
		_N=bigFromHex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52973"),
		_G=[bigFromHex("AA87CA22BE8B05378EB1C71EF320AD746E1D3B628BA79B9859F741E082542A385502F25DBF55296C3A545E3872760AB7"),
			bigFromHex("3617DE4A96262C6F5D9E98BF9292DC29F8F41DBD289A147CE9DA3113B5F0B8C00A60B1CE1D7E819D7A431D7C90EA0E5F")
			],
		_cofactor=1,
		_add=#_ecAddWeierstrass,
		_Y2=#_ecY2Weierstrass,
		_byteLength=48
	]);;

fun ecSecp521r1()=
	_ecOptimize([
		_name="secp521r1",
		_P=bigFromHex("01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"),
		_A=bigFromHex("01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC"),
		_B=bigFromHex("0051953EB9618E1C9A1F929A21A0B68540EEA2DA725B99B315F3B8B489918EF109E156193951EC7E937B1652C0BD3BB1BF073573DF883D2C34F1EF451FD46B503F00"),
		_N=bigFromHex("01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386409"),
		_G=[bigFromHex("00C6858E06B70404E9CD9E3ECB662395B4429C648139053FB521F828AF606B4D3DBAA14B5E77EFE75928FE1DC127A2FFA8DE3348B3C1856A429BF97E7E31C2E5BD66"),
			bigFromHex("011839296A789A3BC0045C8A5FB42C7D1BD998F54449579B446817AFBD17273E662C97EE72995EF42640C550B9013FAD0761353C7086A272C24088BE94769FD16650")
			],
		_cofactor=1,
		_add=#_ecAddWeierstrass,
		_Y2=#_ecY2Weierstrass,
		_byteLength=66
	]);;

fun ecCurve25519()=
	_ecOptimize([
		_name="curve25519",
		_P=bigFromHex( "7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed"),
		_A=bigFromInt(486662),
		_B=bigFromInt(1),
		_N=bigFromHex( "1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED"),
		_G=[bigFromHex("9"),
			bigFromHex("20ae19a1b8a086b4e01edd2c7748d14c923d4d7e6d7c61b229e9c5a27eced3d9")
			],
		_cofactor=8,
		_add=#_ecAddMontgomery,
		_Y2=#_ecY2Montgomery,
		_byteLength=32

	]);;

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

fun _ecOptimize(curve)=
	set curve._muP=bigBarrett(curve._P);
	set curve._muN=bigBarrett(curve._N);
	curve;;

fun _ecY2Montgomery(curve, x)=	// y2=(x3+ax2+x)/b
	if x<>nil then \modBarrett( curve._P, curve._muP) ((x+curve._A)*x+1)*x/curve._B ;;

fun _ecAddMontgomery(curve, p1, p2)=
	if p1==nil then p2
	else if p2==nil then p1
	else let p1->[x1, y1] in let p2->[x2, y2] in
	\modBarrett( curve._P, curve._muP)
	if (x1<> x2)||((y1==y2) && (y1<>0)) then
	let if x1==x2 then
		// affine doubling
		(3*x1*x1+(curve._A+curve._A)*x1+1)/((curve._B+curve._B)*y1)
	else
		// affine addition
		(y2-y1)/(x2-x1)
	-> q in
	let curve._B*q*q-(curve._A+x1+x2) -> x3 in
	let q*(x1-x3)-y1 -> y3 in
	[x3, y3];;


fun _ecY2Weierstrass(curve, x)=	// y2=x3+ax+b
	if x<>nil then \modBarrett( curve._P, curve._muP) (x*x+curve._A)*x+curve._B;;

fun _ecAddWeierstrass(curve, p1, p2)=
	if p1==nil then p2
	else if p2==nil then p1
	else let p1->[x1, y1] in let p2->[x2, y2] in
	\modBarrett( curve._P, curve._muP)
	if (x1<> x2)||((y1==y2) && (y1<>0)) then
	let if x1==x2 then
		// affine doubling
		(3*x1*x1+curve._A)/(y1+y1)
	else
		// affine addition
		(y2-y1)/(x2-x1)
	-> q in
	let q*q-x1-x2 -> x3 in
	let q*(x1-x3)-y1 -> y3 in
	[x3, y3];;

fun ecMul(curve, n, p)=	// n is an integer, p is a point. For example: 3p  = p+p+p
	if n<>nil then
	let nil -> result in (
		while !bigIsNull(n) do (
			if !bigIsEven(n) then set result=call curve._add(curve, result, p);
			set p= call curve._add(curve, p, p);
			set n= bigASR1(n)
		);
		result
	);;

fun ecAdd(curve, p1, p2)=call curve._add(curve, p1, p2);;

fun ecTest(curve, p)=
	if p==nil then true
	else let p->[x, y] in
	let bigSubMod(bigMulMod(y, y, curve._P), call curve._Y2(curve, x), curve._P) -> delta in
	bigIsNull(delta);;

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))];;


//------- KEYPAIR

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;;

// create an curve public key from a string curve point
fun ecKeyFromPublic(curve, pubKey)= [_curveEK=curve, _pubEK=ecPointFromStr(pubKey)];;

// create an curve key from a private key
fun ecKeyFromPrivate(curve, privKey)=
	let ecMul(curve, privKey, curve._G) -> pubKey in
	[_curveEK=curve, _pubEK=pubKey, _privEK=privKey];;

// create an curve key by computing a random private key
fun ecCreate(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 ecKeyPub(key) = key._pubEK;;
fun ecKeyPubStr(key) = ecStrFromPoint(key._curveEK, key._pubEK);;

fun ecIsPrivate(key)= key._privEK<>nil;;
fun ecPrivate(key)= key._privEK;;
//------- ECDH

// mix Alice Key with Bob public key to generate the shared secret
fun ecEcdh(keyAlice, pubBob) = 
	ecMul(keyAlice._curveEK, keyAlice._privEK, pubBob);;

// idem with pubBob and result being binary strings
fun ecEcdhStr(keyAlice, pubBob) =
	let keyAlice._curveEK -> curve in
	let ecMul(curve, keyAlice._privEK, ecPointFromStr(pubBob)) -> [x, _] in
	bigSerialize(x, curve._byteLength);;

//------- ECDSA

// sign a message
fun ecSign(key, msg, fHash)=
	let key._curveEK -> curve in
\modBarrett( curve._N, curve._muN)
	let bigDeserialize(call fHash(msg)) % -> h in
	let ecRandom(curve) -> k in
	let ecMul(curve, k, curve._G) -> R in
	let R -> [x, y] in let x % -> r in
	let (h+r*key._privEK)/k
	-> 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 bigInv(s, curve._N) -> w in
	let ecAdd(curve, ecMul(curve, h, ecMul(curve, w, curve._G)), ecMul(curve, r, ecMul(curve, w, key._pubEK))) -> [a, b] in
	let a %-> rr in	// must be equal to r
	r == rr;;