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)
	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_multiply (struct weierstrass_curve *curve, const void *base, const void *scalar, void *result)
	Multiply curve point by scalar. 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 * 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 77 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 80 of file weierstrass.h.

WEIERSTRASS_CURVE

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

Define a Weierstrass curve.

Definition at line 131 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 69 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_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 (or NULL to use generator)
scalar	Scalar multiple
result	Result point to fill in

Return values

rc	Return status code

Definition at line 770 of file weierstrass.c.

                                                              {
        unsigned int size = curve->size;
        size_t len = curve->len;
        const bigint_t ( size ) __attribute__ (( may_alias )) *prime =
                ( ( const void * ) curve->prime[0] );
        const bigint_t ( size ) __attribute__ (( may_alias )) *prime2 =
                ( ( const void * ) curve->prime[WEIERSTRASS_2N] );
        const bigint_t ( size ) __attribute__ (( may_alias )) *fermat =
                ( ( const void * ) curve->fermat );
        const bigint_t ( size ) __attribute__ (( may_alias )) *square =
                ( ( const void * ) curve->square );
        const bigint_t ( size ) __attribute__ (( may_alias )) *one =
                ( ( const void * ) curve->one );
        struct {
                union {
                        weierstrass_t ( size ) result;
                        bigint_t ( size * 2 ) product_in;
                };
                union {
                        weierstrass_t ( size ) multiple;
                        bigint_t ( size * 2 ) product_out;
                };
                bigint_t ( bigint_required_size ( len ) ) scalar;
        } temp;
        size_t offset;
        unsigned int i;
        int rc;

        /* Initialise curve, if not already done
         *
         * The least significant element of the field prime must be
         * odd, and so the least significant element of the
         * (initialised) first multiple of the field prime must be
         * non-zero.
         */
        if ( ! prime2->element[0] )
                weierstrass_init ( curve );

        /* Use generator if applicable */
        if ( ! base )
                base = curve->base;

        /* Convert input to projective coordinates in Montgomery form */
        DBGC ( curve, "WEIERSTRASS %s base (", curve->name );
        for ( i = 0, offset = 0 ; i < WEIERSTRASS_AXES ; i++, offset += len ) {
                bigint_init ( &temp.multiple.axis[i], ( base + offset ), len );
                DBGC ( curve, "%s%s", ( i ? "," : "" ),
                       bigint_ntoa ( &temp.multiple.axis[i] ) );
                bigint_multiply ( &temp.multiple.axis[i], square,
                                  &temp.product_in );
                bigint_montgomery_relaxed ( prime, &temp.product_in,
                                            &temp.multiple.axis[i] );
        }
        bigint_copy ( one, &temp.multiple.z );
        DBGC ( curve, ")\n" );

        /* Verify point is on curve */
        if ( ( rc = weierstrass_verify ( curve, &temp.multiple ) ) != 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 );

        /* Invert result Z co-ordinate (via Fermat's little theorem) */
        bigint_copy ( one, &temp.multiple.z );
        bigint_ladder ( &temp.multiple.z, &temp.result.z, fermat,
                        bigint_mod_exp_ladder, prime, &temp.product_out );

        /* Convert result back to affine co-ordinates */
        DBGC ( curve, "WEIERSTRASS %s result (", curve->name );
        for ( i = 0, offset = 0 ; i < WEIERSTRASS_AXES ; i++, offset += len ) {
                bigint_multiply ( &temp.result.axis[i], &temp.multiple.z,
                                  &temp.product_out );
                bigint_montgomery_relaxed ( prime, &temp.product_out,
                                            &temp.result.axis[i] );
                bigint_grow ( &temp.result.axis[i], &temp.product_out );
                bigint_montgomery ( prime, &temp.product_out,
                                    &temp.result.axis[i] );
                DBGC ( curve, "%s%s", ( i ? "," : "" ),
                       bigint_ntoa ( &temp.result.axis[i] ) );
                bigint_done ( &temp.result.axis[i], ( result + offset ), len );
        }
        DBGC ( curve, ")\n" );

        return 0;
}

References __attribute__, weierstrass_curve::base, base, bigint_copy, bigint_done, bigint_grow, bigint_init, bigint_ladder, bigint_mod_exp_ladder(), bigint_montgomery, bigint_montgomery_relaxed, bigint_multiply, bigint_ntoa, bigint_required_size, bigint_t(), DBGC, weierstrass_curve::fermat, len, weierstrass_curve::len, memset(), weierstrass_curve::name, NULL, offset, weierstrass_curve::one, weierstrass_curve::prime, rc, result, size, weierstrass_curve::size, weierstrass_curve::square, WEIERSTRASS_2N, weierstrass_add_ladder(), WEIERSTRASS_AXES, weierstrass_init(), weierstrass_t, and weierstrass_verify.