weierstrass.h File Reference

Weierstrass elliptic curves. More...

#include <ipxe/bigint.h>
#include <ipxe/crypto.h>

Go to the source code of this file.

Data Structures
struct	weierstrass_curve
	A Weierstrass elliptic curve. More...

Macros
#define	WEIERSTRASS_AXES   2
	Number of axes in Weierstrass curve point representation. More...
#define	WEIERSTRASS_MAX_MULTIPLE_LOG2   5 /* maximum reached is mod 20N */
	Maximum multiple of field prime encountered during calculations. More...
#define	weierstrass_size(len)
	Determine number of elements in scalar values for a Weierstrass curve. More...
#define	weierstrass_t(size)
	Define a Weierstrass projective co-ordinate type. More...
#define	WEIERSTRASS_NUM_MONT   3
	Number of cached in Montgomery form for each Weierstrass curve. More...
#define	WEIERSTRASS_NUM_CACHED
	Number of cached big integers for each Weierstrass curve. More...
#define	WEIERSTRASS_CURVE(_name, _curve, _len, _prime, _a, _b, _base, _order)
	Define a Weierstrass curve. More...

Enumerations
enum	weierstrass_multiple { WEIERSTRASS_N = 0, WEIERSTRASS_2N, WEIERSTRASS_4N, WEIERSTRASS_NUM_MULTIPLES }
	Indexes for stored multiples of the field prime. More...

Functions
	FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
int	weierstrass_is_infinity (struct weierstrass_curve *curve, const void *point)
	Check if this is the point at infinity. More...
int	weierstrass_multiply (struct weierstrass_curve *curve, const void *base, const void *scalar, void *result)
	Multiply curve point by scalar. More...
int	weierstrass_add_once (struct weierstrass_curve *curve, const void *addend, const void *augend, void *result)
	Add curve points (as a one-off operation) More...

Detailed Description

Weierstrass elliptic curves.

Definition in file weierstrass.h.

Macro Definition Documentation

WEIERSTRASS_AXES

#define WEIERSTRASS_AXES   2

Number of axes in Weierstrass curve point representation.

Definition at line 16 of file weierstrass.h.

WEIERSTRASS_MAX_MULTIPLE_LOG2

#define WEIERSTRASS_MAX_MULTIPLE_LOG2   5 /* maximum reached is mod 20N */

Maximum multiple of field prime encountered during calculations.

Calculations are performed using values modulo a small multiple of the field prime, rather than modulo the field prime itself. This allows explicit reductions after additions, subtractions, and relaxed Montgomery multiplications to be omitted entirely, provided that we keep careful track of the field prime multiple for each intermediate value.

Relaxed Montgomery multiplication will produce a result in the range t < (1+m/k)N, where m is this maximum multiple of the field prime, and k is the constant in R > kN representing the leading zero padding in the big integer representation of the field prime. We choose to set k=m so that multiplications will always produce a result in the range t < 2N.

This is expressed as the base-two logarithm of the multiple (rounded up), to simplify compile-time calculations.

Definition at line 38 of file weierstrass.h.

weierstrass_size

#define weierstrass_size

(

len

)

Value:

bigint_required_size ( (len) +                                  \
                               ( ( WEIERSTRASS_MAX_MULTIPLE_LOG2 + 7 )  \
                                 / 8 ) )

Determine number of elements in scalar values for a Weierstrass curve.

Parameters

len	Length of field prime, in bytes

Return values

size	Number of elements

Definition at line 46 of file weierstrass.h.

weierstrass_t

#define weierstrass_t

(

size

)

Value:

union {                                                         \
                bigint_t ( size ) axis[3];                              \
                struct {                                                \
                        bigint_t ( size ) x;                            \
                        bigint_t ( size ) y;                            \
                        bigint_t ( size ) z;                            \
                };                                                      \
                bigint_t ( size * 2 ) xy;                               \
                bigint_t ( size * 3 ) all;                              \
        }

Define a Weierstrass projective co-ordinate type.

Parameters

size	Number of elements in scalar values

Return values

weierstrass_t

Projective co-ordinate type

Definition at line 57 of file weierstrass.h.

WEIERSTRASS_NUM_MONT

#define WEIERSTRASS_NUM_MONT   3

Number of cached in Montgomery form for each Weierstrass curve.

Definition at line 78 of file weierstrass.h.

WEIERSTRASS_NUM_CACHED

#define WEIERSTRASS_NUM_CACHED

Value:

( WEIERSTRASS_NUM_MULTIPLES +                                   \
          1 /* fermat */ + 1 /* mont */ +                               \
          WEIERSTRASS_NUM_MONT )

Number of cached big integers for each Weierstrass curve.

Definition at line 81 of file weierstrass.h.

WEIERSTRASS_CURVE

#define WEIERSTRASS_CURVE	(		_name,
			_curve,
			_len,
			_prime,
			_a,
			_b,
			_base,
			_order
	)

Define a Weierstrass curve.

Definition at line 137 of file weierstrass.h.

Enumeration Type Documentation

weierstrass_multiple

enum weierstrass_multiple

Indexes for stored multiples of the field prime.

Enumerator
WEIERSTRASS_N
WEIERSTRASS_2N
WEIERSTRASS_4N
WEIERSTRASS_NUM_MULTIPLES

Definition at line 70 of file weierstrass.h.

                          {
        WEIERSTRASS_N = 0,
        WEIERSTRASS_2N,
        WEIERSTRASS_4N,
        WEIERSTRASS_NUM_MULTIPLES
};

Function Documentation

FILE_LICENCE()

FILE_LICENCE

(

GPL2_OR_LATER_OR_UBDL

)

weierstrass_is_infinity()

int weierstrass_is_infinity	(	struct weierstrass_curve *	curve,
		const void *	point
	)

Check if this is the point at infinity.

Parameters

point

Curve point

Return values

is_infinity

This is the point at infinity

Definition at line 918 of file weierstrass.c.

                                                  {
        unsigned int size = curve->size;
        size_t len = curve->len;
        struct {
                bigint_t ( size ) axis;
        } temp;
        size_t offset;
        int is_finite = 0;
        unsigned int i;

        /* We use all zeroes to represent the point at infinity */
        DBGC ( curve, "WEIERSTRASS %s point (", curve->name );
        for ( i = 0, offset = 0 ; i < WEIERSTRASS_AXES ; i++, offset += len ) {
                bigint_init ( &temp.axis, ( point + offset ), len );
                DBGC ( curve, "%s%s", ( i ? "," : "" ),
                       bigint_ntoa ( &temp.axis ) );
                is_finite |= ( ! bigint_is_zero ( &temp.axis ) );
        }
        DBGC ( curve, ") is%s infinity\n", ( is_finite ? " not" : "" ) );

        return ( ! is_finite );
}

References bigint_init, bigint_is_zero, bigint_ntoa, bigint_t(), DBGC, weierstrass_curve::len, len, weierstrass_curve::name, offset, size, weierstrass_curve::size, and WEIERSTRASS_AXES.

weierstrass_multiply()

int weierstrass_multiply	(	struct weierstrass_curve *	curve,
		const void *	base,
		const void *	scalar,
		void *	result
	)

Multiply curve point by scalar.

Parameters

curve	Weierstrass curve
base	Base point
scalar	Scalar multiple
result	Result point to fill in

Return values

rc	Return status code

Definition at line 951 of file weierstrass.c.

                                                              {
        unsigned int size = curve->size;
        size_t len = curve->len;
        const bigint_t ( size ) __attribute__ (( may_alias )) *one =
                ( ( const void * ) curve->one );
        struct {
                weierstrass_t ( size ) result;
                weierstrass_t ( size ) multiple;
                bigint_t ( bigint_required_size ( len ) ) scalar;
        } temp;
        int rc;

        /* Convert input to projective coordinates in Montgomery form */
        if ( ( rc = weierstrass_init ( curve, &temp.multiple, &temp.result,
                                       base ) ) != 0 ) {
                return rc;
        }

        /* Construct identity element (the point at infinity) */
        memset ( &temp.result, 0, sizeof ( temp.result ) );
        bigint_copy ( one, &temp.result.y );

        /* Initialise scalar */
        bigint_init ( &temp.scalar, scalar, len );
        DBGC ( curve, "WEIERSTRASS %s scalar %s\n",
               curve->name, bigint_ntoa ( &temp.scalar ) );

        /* Perform multiplication via Montgomery ladder */
        bigint_ladder ( &temp.result.all, &temp.multiple.all, &temp.scalar,
                        weierstrass_add_ladder, curve, NULL );

        /* Convert result back to affine co-ordinates */
        weierstrass_done ( curve, &temp.result, &temp.multiple, result );

        return 0;
}

References __attribute__, base, bigint_copy, bigint_init, bigint_ladder, bigint_ntoa, bigint_required_size, bigint_t(), DBGC, weierstrass_curve::len, len, memset(), weierstrass_curve::name, NULL, weierstrass_curve::one, rc, result, size, weierstrass_curve::size, weierstrass_add_ladder(), weierstrass_done, weierstrass_init, and weierstrass_t.

weierstrass_add_once()

int weierstrass_add_once	(	struct weierstrass_curve *	curve,
		const void *	addend,
		const void *	augend,
		void *	result
	)

Add curve points (as a one-off operation)

Parameters

curve	Weierstrass curve
addend	Curve point to add
augend	Curve point to add
result	Curve point to hold result

Return values

rc	Return status code

Definition at line 998 of file weierstrass.c.

                                          {
        unsigned int size = curve->size;
        struct {
                weierstrass_t ( size ) addend;
                weierstrass_t ( size ) augend;
                weierstrass_t ( size ) result;
        } temp;
        int rc;

        /* Convert inputs to projective coordinates in Montgomery form */
        if ( ( rc = weierstrass_init ( curve, &temp.addend, &temp.result,
                                       addend ) ) != 0 ) {
                return rc;
        }
        if ( ( rc = weierstrass_init ( curve, &temp.augend, &temp.result,
                                       augend ) ) != 0 ) {
                return rc;
        }

        /* Add curve points */
        weierstrass_add ( curve, &temp.augend, &temp.addend, &temp.result );

        /* Convert result back to affine co-ordinates */
        weierstrass_done ( curve, &temp.result, &temp.addend, result );

        return 0;
}

References rc, result, size, weierstrass_curve::size, weierstrass_add, weierstrass_done, weierstrass_init, and weierstrass_t.