// PureNoise CryptoLib (c) 1997-2004, PureNoise Ltd Vaduz <www.cryptolib.com>
// Ruptor's Elliptic Curve Cryptography implementation (strongly recommended over legacy DH, RSA or El-Gamal) definition file
// The fastest Elliptic Curve implementation in the world!
// Inspired by the famous Miracl Library (http://indigo.ie/~mscott) by Shamus Software Ltd
// Uses and recommends Shamus Standard Curves (we believe that the US ECC standards are trapdoored by the NSA)

/*!

Elliptic Curve Parameters

The elliptic curve has a form: y^2 = x^3 + A*x + B;
with fixed A = -3 it takes form y^2 = x^3 - 3*x + B;
only A = -3 curves are implemented in this library to increase performance.

const unsigned long 	ECC_PRIME[ECC_WORDS + 2];
const unsigned long 	ECC_ORDER[ECC_WORDS + 2];
const unsigned long 	ECC_A[ECC_WORDS + 2];
const unsigned long 	ECC_B[ECC_WORDS + 2];
const unsigned long 	ECC_NDASH;

ECC_PRIME, ECC_A and ECC_B are kept as hard-coded constants presented in N-residue format
with the first element representing their length ECC_WORDS and an extra 0 element at the end.
Note: as overflows are a natural part of addition and multiplication operations
(with a subsequent subtraction of the modulus in modular arithmetic)
all constants must contain a trailing zero word;
also all the resulting variables should reserve space for an extra trailing zero.
ECC_A is basically 3 converted to N-residue format.
ECC_NDASH is a multiplicative inverse modulo 2^32 of ECC_PRIME[1] constant necessary for Montgomery multiplication.

const unsigned long 	ECC_1[3] = { 1U, 1U, 0U };

ECC_1 is a constant 1 in big format ready to be added to or subtracted from big numbers.
A direct call to padd (x, ECC_1, y) or to psub (x, ECC_1, y) can be used
wherever increment or decrement of a big number is needed. Mainly used internally.

!*/

#ifndef _crypto_ecc_h_
#define _crypto_ecc_h_

#include <crypto/crypto.h>

//! \def ECC_XYZ A point shared among all the components with all its coordinates precalculated. It is safe to keep it constant although a randomly selected point is also acceptable and may be more secure in some cases. socket_open uses a random point during its dynamic key exchange. socket_init_keys uses static point ECC_XYZ.
//! \def ECC_XYZ \brief a constant randomly selected point on the curve
//! \def ECC_NDASH = -inv32 (PRIME[1]); or in other words: NDASH * PRIME[1] == 0xFFFFFFFFUL

#if (ECC_BITS == 512)

	#define ECC_PRIME			ECC_512_P
	#define ECC_ORDER			ECC_512_Q
	#define ECC_NDASH			ECC_512_N
	#define ECC_A				ECC_512_A
	#define ECC_B				ECC_512_B
	#define ECC_ONE				ECC_512_ONE
	#define ECC_XYZ				ECC_512_XYZ

#elif (ECC_BITS == 384)

	#define ECC_PRIME			ECC_384_P
	#define ECC_ORDER			ECC_384_Q
	#define ECC_NDASH			ECC_384_N
	#define ECC_A				ECC_384_A
	#define ECC_B				ECC_384_B
	#define ECC_ONE				ECC_384_ONE
	#define ECC_XYZ				ECC_384_XYZ

#elif (ECC_BITS == 256)

	#define ECC_PRIME			ECC_256_P
	#define ECC_ORDER			ECC_256_Q
	#define ECC_NDASH			ECC_256_N
	#define ECC_A				ECC_256_A
	#define ECC_B				ECC_256_B
	#define ECC_ONE				ECC_256_ONE
	#define ECC_XYZ				ECC_256_XYZ

#elif (ECC_BITS == 128)

	#define ECC_PRIME			ECC_128_P
	#define ECC_ORDER			ECC_128_Q
	#define ECC_NDASH			ECC_128_N
	#define ECC_A				ECC_128_A
	#define ECC_B				ECC_128_B
	#define ECC_ONE				ECC_128_ONE
	#define ECC_XYZ				ECC_128_XYZ

#endif

//! \brief size of asymmetric keys in 8-byte octets (8)
#define ECC_OCTETS				((ECC_BITS + 63) / 64)
//! \brief size of asymmetric keys in 32-bit words (16)
#define ECC_WORDS				(ECC_OCTETS * 2)
//! \brief size of asymmetric keys in bytes (64)
#define ECC_BYTES				(ECC_OCTETS * 8)
//! \brief size of asymmetric keys in BASE-64 characters (86)
#define ECC_BASE_16_CHARS	(BYTES_TO_BASE_16 (ECC_BYTES))
#define ECC_BASE_64_CHARS	(BYTES_TO_BASE_64 (ECC_BYTES))
#define ECC_BASE_128_CHARS	(BYTES_TO_BASE_128 (ECC_BYTES))
#define ECC_BASE_222_CHARS	(BYTES_TO_BASE_222 (ECC_BYTES))
#define ECC_BASE_252_CHARS	(BYTES_TO_BASE_252 (ECC_BYTES))
#define ECC_BASE_255_CHARS	(BYTES_TO_BASE_255 (ECC_BYTES))

// Elliptic curve point status

//! \brief if (ecc_point).marker == ECC_POINT_GENERAL, the point requires normalisation before its coordinates can be used for storage or comparison with other points; see ecc_point_norm
#define ECC_POINT_GENERAL		0
//! \brief if (ecc_point).marker == ECC_POINT_NORMALISED, the point's X coordinate and the least significant bit of Y coordinate can be used for storage or comparison with other points
#define ECC_POINT_NORMALIZED	1
//! \brief (ecc_point).marker should never be ECC_POINT_INFINITY in cryptographic calculations unless there is an error; it's only allowed in other mathematical calculations
#define ECC_POINT_INFINITY		2

//! marker takes values ECC_POINT_GENERAL, ECC_POINT_NORMALIZED and ECC_POINT_INFINITY. Only ECC_POINT_NORMALIZED point coordinates are allowed to be used as keys, for storage or transmission. Call ecc_point_norm to convert point to a normalized form, then store or transmit its X coordinate and the least significant bit of its Y coordinate.
//! \brief Elliptic Curve point structure. Uses projective (X,Y,Z) co-ordinates

typedef struct _ecc_point
{
	unsigned long		X[ECC_WORDS + 3];
	unsigned long		Y[ECC_WORDS + 3];
	unsigned long		Z[ECC_WORDS + 3];
	unsigned long		marker;	// ECC_POINT_{GENERAL|NORMALIZED|INFINITY}
}	ecc_point;

//! \brief sets the value of (big) x to n
#define big_convert(n,x) (x[0] = (n != 0), x[1] = n)
//! \brief sets the value of (big) x to 0
#define big_zero(x) { bzero (x, (x[0]+1) * sizeof (unsigned long)); }
//! \brief removes trailing zeroes from (big) x
#define big_lzero(x) { unsigned long m; for(m=x[0];m&&!x[m];m--); x[0]=m; }
//! \brief modular addition of bigs: z = x + y (mod ECC_PRIME);
#define big_modadd(x,y,z) { big_padd(x,y,z); if (big_compare(z,ECC_PRIME)>=0) big_psub(z,ECC_PRIME,z); }

//! \retval z = x + y
EXTERN void 						big_padd (const unsigned long *x,const unsigned long *y,unsigned long *z);
//! \pre x > y
//! \retval z = x - y
EXTERN void 						big_psub (const unsigned long *x,const unsigned long *y,unsigned long *z);
//! \retval z = x * y
EXTERN void 						big_pmul (const unsigned long *x, const unsigned long sn, unsigned long *z);
//! \retval z = x / y
//! \returns x % y
EXTERN unsigned long 				big_sdiv (const unsigned long *x, const unsigned long sn, unsigned long *z);
//! \retval z = x * y
EXTERN void 						big_multiply (const unsigned long *x, const unsigned long *y, unsigned long *z);
//! returns quotient only if big_divide(x,y,x)
//! returns remainder only if big_divide(x,y,y)
//! \retval z = x / y
//! \retval x = x % y
EXTERN void 						big_divide (unsigned long *x, const unsigned long *y, unsigned long *z);
//! \retval y = x converted to n-residue form
EXTERN void 						big_nres (const unsigned long *x, unsigned long *y, unsigned long *z);
//! \retval y = x converted back from n-residue form mod z; ndash = inv32 (-z[1]);
EXTERN void 						big_redc (const unsigned long *x, unsigned long *y, const unsigned long *z, const unsigned long ndash);
//! Returns remainder only if w == q, quotient only if q == r, add done only if x, y and z are distinct.
//! \brief Multiply, Add and Divide
//! \retval q = (x * y + z) / w
//! \retval r = (x * y + z) % w
EXTERN void 						big_mad (const unsigned long *x, const unsigned long *y, const unsigned long *z, const unsigned long *w, unsigned long *q, unsigned long *r);
//! Returns remainder only if w == q, quotient only if q == r, z add done only if x, y and z are distinct.
//! \brief Negative Multiply, Add and Divide
//! \retval q = (z - x * y) / w
//! \retval r = (z - x * y) % w
EXTERN void 						big_nmad (const unsigned long *x, const unsigned long *y, const unsigned long *z, const unsigned long *w, unsigned long *q, unsigned long *r);
//! \retval y = x ^ n
EXTERN void 						big_power (const unsigned long *x, unsigned long n, unsigned long *y);
//! \retval y = x ^ -1 (mod ECC_PRIME)
EXTERN unsigned long 				big_inverse (const unsigned long *x, unsigned long *y);
//! \retval w = (x ^ y) % z, using n-residues
EXTERN void 						nres_powltr (const unsigned long x, const unsigned long *y, unsigned long *w, unsigned long *z, unsigned long ndash);
//! \retval w = (x ^ y) % z, using n-residues
//! \param ndash = inv32(-z[1])
void nres_powmod (const unsigned long *x, const unsigned long *y, unsigned long *w, unsigned long *z, const unsigned long ndash);

//! Basically ecc_point_mult is similar to and replaces the exponentiation function in Diffie-Hellman key exchange algorithm.
//! \brief multiplies a fixed or variable point by a big number
//! \pre e number must be supplied in binary form, not in n-residue form
//! \pre p_in point is not required to be normalised
//! \post p_out point is not normalised and does not have to be normalised if it is an intermediate result that requires further calculations
//! \retval p_out = e * p_in
EXTERN void							ecc_point_mult (const unsigned long *e, const ecc_point *p_in, ecc_point *p_out);

//! \brief adds a point to a point
//! \pre input points are not required to be normalised
//! \post resulting pb point is not normalised and does not have to be normalised if it is an intermediate result that requires further calculations
//! \retval pb += pa
EXTERN void 						ecc_point_add (const ecc_point *pa, ecc_point *pb);

//! Point normalization is only necessary at the end of all calculations (like multiple point multiplications) to allow point compression down to only one coordinate X and the "sign" of Y. You have to call ecc_point_norm after point multiplication prior to the storage or transmission of its compressed form. Call ecc_point_set afterwards to decompress a point recovering its Y coordinate.
//! \brief normalizes a point reducing its Z coordinate to 1
//! \pre input coordinates should be in n-residue form
//! \post output coordinates remain in n-residue form
//! \returns 1 if the point was normalized successfully
//! \returns 0 if it did not need to be normalized in the first place
EXTERN int 							ecc_point_norm (ecc_point *p);

//! If ecc_point_set fails to set a newly generated point or if Y coordinate of the fixed point multiplied by the secret key is odd, either simply increment x or generate a new random one using socket_init_keys as example. Also, doing MOD ECC_PRIME for a given random x to make it fit the ECC_PRIME field is bad practice as it makes 2^ECC_BITS - ECC_PRIME numbers appear twice as often as the rest of all the possible values thus unnecessarily reducing strength of the generated keys. Therefore simply regenerate the random number or at least its top 32-64 bits until it's smaller than ECC_PRIME.
//! \brief decompresses a point restoring Y and Z coordinates from its given X coordinate and the sign bit of Y coordinate
//! \pre input coordinates should be in n-residue form
//! \pre x < ECC_PRIME
//! \pre the lowest bit of an extra word x[x[0]+1] determines the sign of the Y coordinate for p (the least significant bit of Y coordinate of the point, <crypto/socket.c> always makes sure it's 0).
//! \post output coordinates remain in n-residue form
//! \post returned point is always normalized
//! \param x if it is NULL ecc_point_set will set p to point to infinity and will return 1
//! \returns 1 (TRUE) if point was set successfully, that is if its matching Y coordinate was found
//! \returns 0 (FALSE) if there is no existing Y coordinate to match the supplied X coordinate of the point
EXTERN int 							ecc_point_set (const unsigned long *x, ecc_point *p);

EXTERN unsigned long				ECC_PRIME[ECC_WORDS + 2];
EXTERN unsigned long				ECC_ORDER[ECC_WORDS + 2];
EXTERN unsigned long				ECC_A[ECC_WORDS + 2];
EXTERN unsigned long				ECC_B[ECC_WORDS + 2];
EXTERN unsigned long				ECC_ONE[ECC_WORDS + 2];
EXTERN unsigned long				ECC_NDASH;
EXTERN const unsigned long			ECC_1[3];
EXTERN const unsigned long			ECC_2[3];
EXTERN const ecc_point				ECC_XYZ;

//! \brief Quickly copies x[0]+1 words of x to y attaching a trailing zero word after the big.
//! \pre does not do any bounds or alignment checking;
//! \param x the big to copy to y
//! \post x is copied to y
//! \retval y the big to copy x to
static __forceinline void big_copy (const unsigned long *x, unsigned long *y)
{
	if (x != y)
	{
		memcpy (y, x, (x[0] + 1) * sizeof (*x));
		y[x[0]+1] = 0;
	}
}

//! \brief compares two big numbers
//! \param x a big to compare with y
//! \param y a big to compare x with
//! \returns sign of (x - y)
static __forceinline int big_compare (const unsigned long *x, const unsigned long *y)
{
	register unsigned long m = x[0], n = y[0];
	if (x == y) return 0;
	if (m > n) return 1;
	if (m < n) return -1;
	for (; m > 0; m--) if (x[m] > y[m]) return 1; else if (x[m] < y[m]) return -1;
	return 0;
}

//! \brief z = (x * y) % ECC_PRIME
//! \pre does not do any bounds checking
//! \param x a big to multiply by y
//! \param y a big to multiply x by
//! \retval z a big to store x * y
static __forceinline void nres_ecc_modmult (const unsigned long *x, const unsigned long *y, unsigned long *z)
{
	unsigned long			w0[ECC_WORDS * 2 + 2];
	
	big_multiply (x, y, w0);
	big_redc (w0, z, ECC_PRIME, ECC_NDASH);
}

//! \brief z = (x * y) % mod
//! \pre does not do any bounds checking
//! \param x a big to multiply by y
//! \param y a big to multiply x by
//! \retval z a big to store x * y
//! \param mod a big modulus
//! \param ndash = inv32 (-mod[1])
static __forceinline void nres_modmult (const unsigned long *x, const unsigned long *y, unsigned long *z, const unsigned long *mod, const unsigned long ndash)
{
	unsigned long			w0[ECC_WORDS * 2 + 2];
	
	big_multiply (x, y, w0);
	big_redc (w0, z, mod, ndash);
}

//! \returns value of i-th bit of big
static __forceinline unsigned long big_testbit (const unsigned long *x, const unsigned long i)
{
	return (x[1 + i/(sizeof (unsigned long)*8)] & ((unsigned long) 1 << (i % (sizeof (unsigned long)*8)))) != 0;
}

//! \returns number of bits in x
static __forceinline unsigned long big_logb2 (const unsigned long *x)
{
	register unsigned long	L = x[0], xL;
	if (L)
	{
		xL = x[L];
		for (L *= sizeof (unsigned long) * 8; (signed) xL > 0; L--) xL <<= 1;
	}
	return L;
}

static __forceinline void ecc_point_copy (const ecc_point *a, ecc_point *b)
{
	if (a != b) memcpy (b, a, sizeof (ecc_point));
}


#endif	// _crypto_ecc_h_