Elliptic Curve (Ed25519) and Field Arithmetic Implementation. More...

#include "common.h"

Data Structures
struct	ge25519_p2
	Projective coordinate representation. More...

struct	ge25519_p3
	Extended projective coordinate representation. More...

struct	ge25519_p1p1
	Intermediate coordinate representation. More...

struct	ge25519_precomp
	Precomputed point representation. More...

struct	ge25519_cached
	Cached point representation. More...

Macros
#define	EC25519_SEED_SIZE 32ULL
	The ecc seed cize.

#define	EC25519_SIGNATURE_SIZE 64ULL
	The ecc signature size.

#define	EC25519_PUBLICKEY_SIZE 32ULL
	The ecc public key size.

#define	EC25519_PRIVATEKEY_SIZE 64ULL
	The ecc private key size.

#define	EC25519_CURVE_SIZE 32ULL
	The ecc curve size.

Typedefs
typedef QSC_SIMD_ALIGN int32_t	fe25519[10]
	The ecc fe25519 polynomial.

Functions
void	fe25519_0 (fe25519 h)
	Set a field element to zero.

void	fe25519_1 (fe25519 h)
	Set a field element to one.

void	fe25519_copy (fe25519 h, const fe25519 f)
	Copy a field element.

void	fe25519_add (fe25519 h, const fe25519 f, const fe25519 g)
	Add two field elements.

void	fe25519_cswap (fe25519 f, fe25519 g, uint32_t b)
	Conditionally swap two field elements in constant time.

void	fe25519_sub (fe25519 h, const fe25519 f, const fe25519 g)
	Subtract one field element from another.

void	fe25519_neg (fe25519 h, const fe25519 f)
	Negate a field element.

void	fe25519_cmov (fe25519 f, const fe25519 g, uint32_t b)
	Conditionally move a field element in constant time.

int32_t	fe25519_isnegative (const fe25519 f)
	Determine if a field element is negative.

int32_t	fe25519_iszero (const fe25519 f)
	Determine if a field element is zero.

void	fe25519_mul (fe25519 h, const fe25519 f, const fe25519 g)
	Multiply two field elements.

void	fe25519_mul32 (fe25519 h, const fe25519 f, uint32_t n)
	Multiply a field element by a scalar.

void	fe25519_sq (fe25519 h, const fe25519 f)
	Square a field element.

void	fe25519_sq2 (fe25519 h, const fe25519 f)
	Compute 2 * f^2.

void	fe25519_frombytes (fe25519 h, const uint8_t *s)
	Convert a 32-byte array to a field element.

void	fe25519_reduce (fe25519 h, const fe25519 f)
	Reduce a field element modulo 2^255 - 19.

void	fe25519_tobytes (uint8_t *s, const fe25519 h)
	Convert a field element to a 32-byte array.

void	fe25519_invert (fe25519 out, const fe25519 z)
	Compute the multiplicative inverse of a field element.

void	ge25519_p1p1_to_p3 (ge25519_p3 r, const ge25519_p1p1 p)
	Convert a point from P1P1 to P3 coordinates.

void	ge25519_p1p1_to_p2 (ge25519_p2 r, const ge25519_p1p1 p)
	Convert a point from P1P1 to P2 coordinates.

void	ge25519_scalarmult_base (ge25519_p3 h, const uint8_t a)
	Multiply the base point by a scalar.

void	ge25519_p3_tobytes (uint8_t s, const ge25519_p3 h)
	Compress a point in P3 coordinates to a 32-byte representation.

int32_t	ge25519_is_canonical (const uint8_t *s)
	Check if a compressed point is canonical.

int32_t	ge25519_has_small_order (const uint8_t s[32])
	Determine if a compressed point has small order.

int32_t	ge25519_frombytes_negate_vartime (ge25519_p3 h, const uint8_t s)
	Decode and conditionally negate a compressed point.

void	ge25519_p3_to_cached (ge25519_cached r, const ge25519_p3 p)
	Convert a point from P3 coordinates to a cached representation.

void	ge25519_add_cached (ge25519_p1p1 r, const ge25519_p3 p, const ge25519_cached *q)
	Add a cached point to a point.

void	ge25519_sub_precomp (ge25519_p1p1 r, const ge25519_p3 p, const ge25519_precomp *q)
	Subtract a precomputed point from a point.

void	ge25519_double_scalarmult_vartime (ge25519_p2 r, const uint8_t a, const ge25519_p3 A, const uint8_t b)
	Compute a double scalar multiplication.

void	ge25519_sub_cached (ge25519_p1p1 r, const ge25519_p3 p, const ge25519_cached *q)
	Subtract a cached point from a point.

void	ge25519_tobytes (uint8_t s, const ge25519_p2 h)
	Compress a point in P2 coordinates to a 32-byte representation.

void	sc25519_clamp (uint8_t *k)
	Clamp a secret scalar.

int32_t	ed25519_small_order (const uint8_t s[32])
	Check if a compressed point has small order.

int32_t	sc25519_is_canonical (const uint8_t s[32])
	Check if a scalar is canonical.

void	sc25519_muladd (uint8_t s[32], const uint8_t a[32], const uint8_t b[32], const uint8_t c[32])
	Compute s = a * b + c for scalars.

void	sc25519_reduce (uint8_t s[64])
	Reduce a 64-byte scalar modulo 2^255 - 19.

int32_t	qsc_sc25519_verify (const uint8_t x, const uint8_t y, const size_t n)
	Performs a constant-time comparison of two byte arrays.

Detailed Description

Elliptic Curve (Ed25519) and Field Arithmetic Implementation.

This header defines the data structures and functions for performing operations on the Ed25519 elliptic curve, which is widely used for digital signatures and key exchange protocols. It provides several coordinate representations for curve points, including:

P2: Projective coordinates (X:Y:Z)
P3: Extended coordinates (X:Y:Z:T)
P1P1: Intermediate coordinates used in addition formulas
Precomputed: A structure for precomputed values to speed up base point operations
Cached: A structure for caching repeated computations

In addition, this header defines functions for field arithmetic in the finite field defined by 2^255 - 19. Field elements are represented as arrays of 10 int32_t values in a radix-2^25.5 format. The field arithmetic functions include:

Initialization routines to set field elements to zero or one.
Copy, addition, subtraction, and negation operations.
Constant-time conditional swap and conditional move operations.
Multiplication and squaring routines.
Conversion routines between a 32-byte little-endian representation and the field element.
Exponentiation and inversion routines.

These operations form the foundation of the Ed25519 digital signature scheme and key exchange protocols and are implemented to be constant-time to mitigate timing attacks.

Reference Links:

Function Documentation

◆ ed25519_small_order()

int32_t ed25519_small_order ( const uint8_t s[32] )

Check if a compressed point has small order.

Determines whether the given 32-byte compressed point is of small order, which is insecure for cryptographic operations.

Parameters

s	[const uint8_t[32]] The 32-byte compressed point.

Returns: [int32_t] Returns non-zero if the point has small order, 0 otherwise.

◆ fe25519_0()

void fe25519_0 ( fe25519 h )

Set a field element to zero.

Sets all limbs of the field element h to 0.

Parameters

h	[fe25519] The field element to zero.

◆ fe25519_1()

void fe25519_1 ( fe25519 h )

Set a field element to one.

Initializes the field element h to the multiplicative identity (1).

Parameters

h	[fe25519] The field element to set to one.

◆ fe25519_add()

void fe25519_add	(	fe25519	h,
		const fe25519	f,
		const fe25519	g )

Add two field elements.

Computes the sum h = f + g.

Parameters

h	[fe25519] Destination field element.
f	[const fe25519] First addend.
g	[const fe25519] Second addend.

◆ fe25519_cmov()

void fe25519_cmov	(	fe25519	f,
		const fe25519	g,
		uint32_t	b )

Conditionally move a field element in constant time.

Conditionally moves the field element g into f if the condition bit b is set. This operation is performed in constant time.

Parameters

f	[fe25519] Destination field element; modified in place.
g	[const fe25519] Source field element.
b	[uint32_t] Condition bit; if set, g is moved into f.

◆ fe25519_copy()

void fe25519_copy	(	fe25519	h,
		const fe25519	f )

Copy a field element.

Copies the field element f into h.

Parameters

h	[fe25519] Destination field element.
f	[const fe25519] Source field element.

◆ fe25519_cswap()

void fe25519_cswap	(	fe25519	f,
		fe25519	g,
		uint32_t	b )

Conditionally swap two field elements in constant time.

Conditionally swaps the field elements f and g if the condition bit b is nonzero. This function operates in constant time to prevent timing attacks.

Parameters

f	[fe25519] First field element; may be swapped.
g	[fe25519] Second field element; may be swapped.
b	[uint32_t] Condition bit; if nonzero, f and g are swapped.

◆ fe25519_frombytes()

void fe25519_frombytes	(	fe25519	h,
		const uint8_t *	s )

Convert a 32-byte array to a field element.

Interprets a 32-byte little-endian array s as a field element and stores it in h.

Parameters

h	[fe25519] Destination field element.
s	[const uint8_t*] Source byte array.

◆ fe25519_invert()

void fe25519_invert	(	fe25519	out,
		const fe25519	z )

Compute the multiplicative inverse of a field element.

Computes the multiplicative inverse of z in the field and stores the result in out. If z is zero, the result is undefined.

Parameters

out	[fe25519] Destination field element for the inverse.
z	[const fe25519] Field element to invert.

◆ fe25519_isnegative()

int32_t fe25519_isnegative ( const fe25519 f )

Determine if a field element is negative.

Converts the field element f to its 32-byte representation and returns the least significant bit.

Parameters

f	[const fe25519] The field element to check.

Returns: [int32_t] Returns nonzero if f is negative; otherwise, zero.

◆ fe25519_iszero()

int32_t fe25519_iszero ( const fe25519 f )

Determine if a field element is zero.

Converts the field element f to its 32-byte representation and checks if all bytes are zero.

Parameters

f	[const fe25519] The field element to check.

Returns: [int32_t] Returns nonzero if f is zero; otherwise, zero.

◆ fe25519_mul()

void fe25519_mul	(	fe25519	h,
		const fe25519	f,
		const fe25519	g )

Multiply two field elements.

Computes the product h = f * g.

Parameters

h	[fe25519] Destination field element.
f	[const fe25519] First factor.
g	[const fe25519] Second factor.

◆ fe25519_mul32()

void fe25519_mul32	(	fe25519	h,
		const fe25519	f,
		uint32_t	n )

Multiply a field element by a scalar.

Computes h = f * n, where n is a 32-bit scalar.

Parameters

h	[fe25519] Destination field element.
f	[const fe25519] Field element to be multiplied.
n	[uint32_t] Scalar multiplier.

◆ fe25519_neg()

void fe25519_neg	(	fe25519	h,
		const fe25519	f )

Negate a field element.

Computes the negation h = -f.

Parameters

h	[fe25519] Destination field element.
f	[const fe25519] Field element to negate.

◆ fe25519_reduce()

void fe25519_reduce	(	fe25519	h,
		const fe25519	f )

Reduce a field element modulo 2^255 - 19.

Computes the canonical representative of the field element f modulo (2^255 - 19) and stores the result in h.

Parameters

h	[fe25519] Destination field element.
f	[const fe25519] Field element to reduce.

◆ fe25519_sq()

void fe25519_sq	(	fe25519	h,
		const fe25519	f )

Square a field element.

Computes the square h = f^2.

Parameters

h	[fe25519] Destination field element.
f	[const fe25519] Field element to square.

◆ fe25519_sq2()

void fe25519_sq2	(	fe25519	h,
		const fe25519	f )

Compute 2 * f^2.

Computes h = 2 * (f^2).

Parameters

h	[fe25519] Destination field element.
f	[const fe25519] Field element to square and double.

◆ fe25519_sub()

void fe25519_sub	(	fe25519	h,
		const fe25519	f,
		const fe25519	g )

Subtract one field element from another.

Computes the difference h = f - g.

Parameters

h	[fe25519] Destination field element.
f	[const fe25519] Minuend field element.
g	[const fe25519] Subtrahend field element.

Remarks: Preconditions: f and g are bounded by specific constants. Postconditions: h is bounded by specified limits.

◆ fe25519_tobytes()

void fe25519_tobytes	(	uint8_t *	s,
		const fe25519	h )

Convert a field element to a 32-byte array.

Serializes the field element h into a 32-byte little-endian representation stored in s.

Parameters

s	[uint8_t*] Destination byte array.
h	[const fe25519] Field element to serialize.

◆ ge25519_add_cached()

void ge25519_add_cached	(	ge25519_p1p1 *	r,
		const ge25519_p3 *	p,
		const ge25519_cached *	q )

Add a cached point to a point.

Computes the sum of a point in P3 coordinates and a cached point, storing the result in the P1P1 representation.

Parameters

r	[ge25519_p1p1*] Pointer to the output point in P1P1 coordinates.
p	[const ge25519_p3*] Pointer to the input point in P3 coordinates.
q	[const ge25519_cached*] Pointer to the cached point.

◆ ge25519_double_scalarmult_vartime()

void ge25519_double_scalarmult_vartime	(	ge25519_p2 *	r,
		const uint8_t *	a,
		const ge25519_p3 *	A,
		const uint8_t *	b )

Compute a double scalar multiplication.

Computes the expression r = a * A + b * B, where A is an arbitrary point and B is the base point. The result is returned in the P2 coordinate representation using a variable-time algorithm.

Parameters

r	[ge25519_p2*] Pointer to the output point in P2 coordinates.
a	[const uint8_t*] Pointer to the scalar for point A.
A	[const ge25519_p3*] Pointer to the point A in P3 coordinates.
b	[const uint8_t*] Pointer to the scalar for the base point.

◆ ge25519_frombytes_negate_vartime()

int32_t ge25519_frombytes_negate_vartime	(	ge25519_p3 *	h,
		const uint8_t *	s )

Decode and conditionally negate a compressed point.

Decodes a 32-byte compressed point into extended P3 coordinates and conditionally negates the X-coordinate to enforce a canonical representation.

Parameters

h	[ge25519_p3*] Pointer to the output point in P3 coordinates.
s	[const uint8_t*] Pointer to the 32-byte compressed point.

Returns: [int32_t] Returns 0 on success, or -1 if the decoding fails.

◆ ge25519_has_small_order()

int32_t ge25519_has_small_order ( const uint8_t s[32] )

Determine if a compressed point has small order.

Checks whether the given 32-byte compressed point has small order, which is considered insecure.

Parameters

s	[const uint8_t[32]] The 32-byte compressed point.

Returns: [int32_t] Returns 1 if the point has small order; 0 otherwise.

◆ ge25519_is_canonical()

int32_t ge25519_is_canonical ( const uint8_t * s )

Check if a compressed point is canonical.

Verifies whether the given 32-byte compressed point is in canonical form.

Parameters

s	[const uint8_t*] Pointer to the 32-byte compressed representation.

Returns: [int32_t] Returns 1 if the point is canonical; 0 otherwise.

◆ ge25519_p1p1_to_p2()

void ge25519_p1p1_to_p2	(	ge25519_p2 *	r,
		const ge25519_p1p1 *	p )

Convert a point from P1P1 to P2 coordinates.

Converts a point in the intermediate P1P1 coordinate system to the projective P2 representation.

Parameters

r	[ge25519_p2*] Pointer to the output point in P2 coordinates.
p	[const ge25519_p1p1*] Pointer to the input point in P1P1 coordinates.

◆ ge25519_p1p1_to_p3()

void ge25519_p1p1_to_p3	(	ge25519_p3 *	r,
		const ge25519_p1p1 *	p )

Convert a point from P1P1 to P3 coordinates.

Converts a point in the intermediate P1P1 coordinate system to the extended P3 representation.

Parameters

r	[ge25519_p3*] Pointer to the output point in P3 coordinates.
p	[const ge25519_p1p1*] Pointer to the input point in P1P1 coordinates.

◆ ge25519_p3_to_cached()

void ge25519_p3_to_cached	(	ge25519_cached *	r,
		const ge25519_p3 *	p )

Convert a point from P3 coordinates to a cached representation.

Converts a point in extended P3 coordinates into a cached format to accelerate point addition.

Parameters

r	[ge25519_cached*] Pointer to the output cached point.
p	[const ge25519_p3*] Pointer to the input point in P3 coordinates.

◆ ge25519_p3_tobytes()

void ge25519_p3_tobytes	(	uint8_t *	s,
		const ge25519_p3 *	h )

Compress a point in P3 coordinates to a 32-byte representation.

Converts a point in extended P3 coordinates to its compressed 32-byte form.

Parameters

s	[uint8_t*] Pointer to the output 32-byte array.
h	[const ge25519_p3*] Pointer to the input point in P3 coordinates.

◆ ge25519_scalarmult_base()

void ge25519_scalarmult_base	(	ge25519_p3 *	h,
		const uint8_t *	a )

Multiply the base point by a scalar.

Computes the scalar multiplication h = a * BasePoint, where a is a 32-byte scalar.

Parameters

h	[ge25519_p3*] Pointer to the output point in P3 coordinates.
a	[const uint8_t*] Pointer to a 32-byte scalar.

◆ ge25519_sub_cached()

void ge25519_sub_cached	(	ge25519_p1p1 *	r,
		const ge25519_p3 *	p,
		const ge25519_cached *	q )

Subtract a cached point from a point.

Computes the difference r = p - q, where p is in P3 coordinates and q is in cached form, storing the result in the P1P1 representation.

Parameters

r	[ge25519_p1p1*] Pointer to the output point in P1P1 coordinates.
p	[const ge25519_p3*] Pointer to the input point in P3 coordinates.
q	[const ge25519_cached*] Pointer to the cached point.

◆ ge25519_sub_precomp()

void ge25519_sub_precomp	(	ge25519_p1p1 *	r,
		const ge25519_p3 *	p,
		const ge25519_precomp *	q )

Subtract a precomputed point from a point.

Computes the subtraction r = p - q, where p is in P3 coordinates and q is in precomputed form, and stores the result in the P1P1 representation.

Parameters

r	[ge25519_p1p1*] Pointer to the output point in P1P1 coordinates.
p	[const ge25519_p3*] Pointer to the input point in P3 coordinates.
q	[const ge25519_precomp*] Pointer to the precomputed point.

◆ ge25519_tobytes()

void ge25519_tobytes	(	uint8_t *	s,
		const ge25519_p2 *	h )

Compress a point in P2 coordinates to a 32-byte representation.

Converts a point in the P2 coordinate representation to its compressed 32-byte form.

Parameters

s	[uint8_t*] Pointer to the output 32-byte array.
h	[const ge25519_p2*] Pointer to the input point in P2 coordinates.

◆ qsc_sc25519_verify()

int32_t qsc_sc25519_verify	(	const uint8_t *	x,
		const uint8_t *	y,
		const size_t	n )

Performs a constant-time comparison of two byte arrays.

This function compares two byte arrays, x and y, each of length n, in constant time. It computes the bitwise XOR for each corresponding byte and accumulates the result using bitwise OR. The final result is processed to return 0 if the arrays are identical, or -1 if any byte differs.

Parameters

x	[const uint8_t*] Pointer to the first byte array.
y	[const uint8_t*] Pointer to the second byte array.
n	[size_t] The number of bytes to compare.

Returns: [int32_t] Returns 0 if all n bytes of x and y are equal; returns -1 if they differ.

◆ sc25519_clamp()

void sc25519_clamp ( uint8_t * k )

Clamp a secret scalar.

Clamps the 32-byte secret scalar to ensure it conforms to the Ed25519 key format.

Parameters

k	[uint8_t*] Pointer to the 32-byte scalar to be clamped.

◆ sc25519_is_canonical()

int32_t sc25519_is_canonical ( const uint8_t s[32] )

Check if a scalar is canonical.

Verifies that the given 32-byte scalar is in its canonical form.

Parameters

s	[const uint8_t[32]] Pointer to the 32-byte scalar.

Returns: [int32_t] Returns non-zero if the scalar is canonical, 0 otherwise.

◆ sc25519_muladd()

void sc25519_muladd	(	uint8_t	s[32],
		const uint8_t	a[32],
		const uint8_t	b[32],
		const uint8_t	c[32] )

Compute s = a * b + c for scalars.

Computes the scalar multiplication of two 32-byte scalars a and b, adds a third scalar c, and stores the result in s.

Parameters

s	[uint8_t[32]] Output scalar.
a	[const uint8_t[32]] The first scalar operand.
b	[const uint8_t[32]] The second scalar operand.
c	[const uint8_t[32]] The scalar addend.

◆ sc25519_reduce()

void sc25519_reduce ( uint8_t s[64] )

Reduce a 64-byte scalar modulo 2^255 - 19.

This function takes a 64-byte little-endian representation of an integer and reduces it modulo the prime 2^255 - 19, producing a canonical form suitable for use as a field element in the Ed25519 elliptic curve. The reduction is performed by splitting the input into 24 limbs (each containing up to 21 or 26 bits), then applying a series of multiplications, additions, subtractions, and carry propagations.

The algorithm is carefully optimized to handle the non-uniform limb sizes and ensures that the final output fits within the desired bit bounds for each limb. The result is written back into the input array s, replacing its original contents.

Parameters

s	[uint8_t*] A pointer to a 64-byte array representing the scalar to be reduced.

Data Structures

Macros

Typedefs

Functions

Detailed Description

Reference Links:

Function Documentation

◆ ed25519_small_order()

◆ fe25519_0()

◆ fe25519_1()

◆ fe25519_add()

◆ fe25519_cmov()

◆ fe25519_copy()

◆ fe25519_cswap()

◆ fe25519_frombytes()

◆ fe25519_invert()

◆ fe25519_isnegative()

◆ fe25519_iszero()

◆ fe25519_mul()

◆ fe25519_mul32()

◆ fe25519_neg()

◆ fe25519_reduce()

◆ fe25519_sq()

◆ fe25519_sq2()

◆ fe25519_sub()

◆ fe25519_tobytes()

◆ ge25519_add_cached()

◆ ge25519_double_scalarmult_vartime()

◆ ge25519_frombytes_negate_vartime()

◆ ge25519_has_small_order()

◆ ge25519_is_canonical()

◆ ge25519_p1p1_to_p2()

◆ ge25519_p1p1_to_p3()

◆ ge25519_p3_to_cached()

◆ ge25519_p3_tobytes()

◆ ge25519_scalarmult_base()

◆ ge25519_sub_cached()

◆ ge25519_sub_precomp()

◆ ge25519_tobytes()

◆ qsc_sc25519_verify()

◆ sc25519_clamp()

◆ sc25519_is_canonical()

◆ sc25519_muladd()

◆ sc25519_reduce()