weierstrass.h File Reference

Weierstrass elliptic curves. More...

#include <ipxe/bigint.h>
#include <ipxe/crypto.h>
#include <ipxe/elliptic.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.
#define	WEIERSTRASS_MAX_MULT_LOG2   5 /* maximum reached is mod 20N */
	Maximum multiple of field prime encountered during calculations.
#define	weierstrass_size(len)
	Determine number of elements in scalar values for a Weierstrass curve.
#define	weierstrass_t(size)
	Define a Weierstrass projective co-ordinate type.
#define	WEIERSTRASS_NUM_MONT   3
	Number of cached in Montgomery form for each Weierstrass curve.
#define	WEIERSTRASS_NUM_CACHED
	Number of cached big integers for each Weierstrass curve.
#define	WEIERSTRASS_CURVE(_name, _curve, _len, _prime, _a, _b, _base, _order)
	Define a Weierstrass curve.

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)
	FILE_SECBOOT (PERMITTED)
int	weierstrass_is_infinity (struct elliptic_curve *curve, const void *point)
	Check if this is the point at infinity.
int	weierstrass_multiply (struct elliptic_curve *curve, const void *base, const void *scalar, void *result)
	Multiply curve point by scalar.
int	weierstrass_add_once (struct elliptic_curve *curve, const void *addend, const void *augend, void *result)
	Add curve points (as a one-off operation).
void	weierstrass_share (struct exchange_algorithm *exchange, const void *private, void *public)
int	weierstrass_agree (struct exchange_algorithm *exchange, const void *private, const void *partner, void *shared)

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 18 of file weierstrass.h.

Referenced by weierstrass_done_raw(), weierstrass_init_raw(), and weierstrass_is_infinity().

WEIERSTRASS_MAX_MULT_LOG2

#define WEIERSTRASS_MAX_MULT_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^2)/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^2 so that multiplications will always produce a result in the range t < 2N.

A lower value of k would be possible, at the cost of having to keep track of the field prime multiples used at each multiplication input (rather than keeping track only of a single global maximum). This would gain nothing in practice: any value of k below around 2^32 will end up requiring just a single extra big integer element.

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

Definition at line 46 of file weierstrass.h.

weierstrass_size

#define weierstrass_size

(

len

)

Value:

bigint_required_size ( (len) +                                  \
                       ( ( 2 * WEIERSTRASS_MAX_MULT_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 54 of file weierstrass.h.

#define weierstrass_size( len )                                         \
        bigint_required_size ( (len) +                                  \
                               ( ( 2 * WEIERSTRASS_MAX_MULT_LOG2 + 7 )  \
                                 / 8 ) )

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

type	Projective co-ordinate type

Definition at line 65 of file weierstrass.h.

#define weierstrass_t( size )                                           \
        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;                              \
        }

Referenced by weierstrass_add_ladder(), weierstrass_add_once(), weierstrass_add_raw(), weierstrass_done_raw(), weierstrass_init_raw(), weierstrass_multiply(), and weierstrass_verify_raw().

WEIERSTRASS_NUM_MONT

#define WEIERSTRASS_NUM_MONT   3

Number of cached in Montgomery form for each Weierstrass curve.

Definition at line 86 of file weierstrass.h.

Referenced by weierstrass_init_curve().

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 89 of file weierstrass.h.

#define WEIERSTRASS_NUM_CACHED                                          \
        ( WEIERSTRASS_NUM_MULTIPLES +                                   \
          1 /* fermat */ + 1 /* mont */ +                               \
          WEIERSTRASS_NUM_MONT )

WEIERSTRASS_CURVE

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

Define a Weierstrass curve.

Definition at line 148 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 78 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

)

FILE_SECBOOT()

FILE_SECBOOT

(

PERMITTED

)

weierstrass_is_infinity()

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

extern

Check if this is the point at infinity.

Parameters

curve	Elliptic curve
point	Curve point

Return values

is_infinity

This is the point at infinity

Definition at line 929 of file weierstrass.c.

                                                  {
        struct weierstrass_curve *weierstrass = curve->priv;
        unsigned int size = weierstrass->size;
        size_t len = weierstrass->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, len, weierstrass_curve::len, elliptic_curve::name, offset, elliptic_curve::priv, size, weierstrass_curve::size, and WEIERSTRASS_AXES.

weierstrass_multiply()

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

extern

Multiply curve point by scalar.

Parameters

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

Return values

rc	Return status code

Definition at line 963 of file weierstrass.c.

                                                              {
        struct weierstrass_curve *weierstrass = curve->priv;
        unsigned int size = weierstrass->size;
        size_t len = weierstrass->len;
        const bigint_t ( size ) __attribute__ (( may_alias )) *one =
                ( ( const void * ) weierstrass->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, len, weierstrass_curve::len, memset(), elliptic_curve::name, NULL, weierstrass_curve::one, elliptic_curve::priv, rc, result, size, weierstrass_curve::size, weierstrass_add_ladder(), weierstrass_done, weierstrass_init, and weierstrass_t.

weierstrass_add_once()

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

extern

Add curve points (as a one-off operation).

Parameters

curve	Elliptic 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 1011 of file weierstrass.c.

                                          {
        struct weierstrass_curve *weierstrass = curve->priv;
        unsigned int size = weierstrass->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 elliptic_curve::priv, rc, result, size, weierstrass_curve::size, weierstrass_add, weierstrass_done, weierstrass_init, and weierstrass_t.

weierstrass_share()

void weierstrass_share ( struct exchange_algorithm * exchange, const void * private, void * public )

extern

weierstrass_agree()

int weierstrass_agree ( struct exchange_algorithm * exchange, const void * private, const void * partner, void * shared )

extern

References partner.