x25519.h File Reference

X25519 key exchange. More...

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

Go to the source code of this file.

Data Structures
union	x25519_oct258
	An X25519 unsigned 258-bit integer. More...
union	x25519_quad257
	An X25519 unsigned 257-bit integer. More...
struct	x25519_value
	An X25519 32-byte value. More...

Macros
#define	X25519_SIZE   bigint_required_size ( ( 267 /* bits */ + 7 ) / 8 )
	X25519 unsigned big integer size. More...

Functions
	FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
	FILE_SECBOOT (PERMITTED)
typedef	bigint_t (X25519_SIZE) x25519_t
	An X25519 unsigned big integer used in internal calculations. More...
void	x25519_multiply (const union x25519_oct258 *multiplicand, const union x25519_oct258 *multiplier, union x25519_quad257 *result)
	Multiply big integers modulo field prime. More...
void	x25519_invert (const union x25519_oct258 *invertend, union x25519_quad257 *result)
	Compute multiplicative inverse. More...
void	x25519_reduce (union x25519_quad257 *value)
	Reduce big integer to canonical range. More...
void	x25519_key (const struct x25519_value *base, const struct x25519_value *scalar, struct x25519_value *result)
	Calculate X25519 key. More...
int	x25519_is_zero (const struct x25519_value *value)
	Check if X25519 value is zero. More...

Variables
struct elliptic_curve	x25519_curve
	X25519 elliptic curve. More...

Detailed Description

X25519 key exchange.

Definition in file x25519.h.

Macro Definition Documentation

X25519_SIZE

#define X25519_SIZE   bigint_required_size ( ( 267 /* bits */ + 7 ) / 8 )

X25519 unsigned big integer size.

X25519 uses the finite field of integers modulo the prime p=2^255-19. The canonical representations of integers in this field therefore require only 255 bits.

For internal calculations we use big integers containing up to 267 bits, since this ends up allowing us to avoid some unnecessary (and expensive) intermediate reductions modulo p.

Definition at line 27 of file x25519.h.

Function Documentation

FILE_LICENCE()

FILE_LICENCE

(

GPL2_OR_LATER_OR_UBDL

)

FILE_SECBOOT()

FILE_SECBOOT

(

PERMITTED

)

bigint_t()

typedef bigint_t

(

X25519_SIZE

)

An X25519 unsigned big integer used in internal calculations.

Referenced by bigint_add_okx(), bigint_add_sample(), bigint_bit_is_set_okx(), bigint_bit_is_set_sample(), bigint_copy_sample(), bigint_done_sample(), bigint_grow_sample(), bigint_init_sample(), bigint_is_geq_okx(), bigint_is_geq_sample(), bigint_is_zero_okx(), bigint_is_zero_sample(), bigint_ladder_raw(), bigint_max_set_bit_okx(), bigint_max_set_bit_sample(), bigint_mod_exp_ladder(), bigint_mod_exp_okx(), bigint_mod_exp_raw(), bigint_mod_exp_sample(), bigint_mod_invert_okx(), bigint_mod_invert_raw(), bigint_mod_invert_sample(), bigint_montgomery_okx(), bigint_montgomery_raw(), bigint_montgomery_relaxed_raw(), bigint_montgomery_sample(), bigint_multiply_okx(), bigint_multiply_raw(), bigint_multiply_sample(), bigint_ntoa_raw(), bigint_reduce_okx(), bigint_reduce_raw(), bigint_reduce_sample(), bigint_shl_okx(), bigint_shl_sample(), bigint_shr_okx(), bigint_shr_sample(), bigint_shrink_sample(), bigint_subtract_okx(), bigint_subtract_sample(), bigint_swap_okx(), bigint_swap_sample(), dhe_key(), ecdsa_alloc(), ecdsa_init_values(), ecdsa_invert(), ecdsa_parse_signature(), ecdsa_prepend_signature(), ecdsa_sign_rs(), ecdsa_verify_rs(), elliptic_curve_okx(), rsa_alloc(), rsa_cipher(), rsa_init(), weierstrass_add_raw(), weierstrass_done_raw(), weierstrass_exec(), weierstrass_init_curve(), weierstrass_init_raw(), weierstrass_is_infinity(), weierstrass_multiply(), and weierstrass_verify_raw().

x25519_multiply()

void x25519_multiply	(	const union x25519_oct258 *	multiplicand,
		const union x25519_oct258 *	multiplier,
		union x25519_quad257 *	result
	)

Multiply big integers modulo field prime.

Parameters

multiplicand	Big integer to be multiplied
multiplier	Big integer to be multiplied
result	Big integer to hold result (may overlap either input)

Definition at line 427 of file x25519.c.

                                                      {
        union x25519_multiply_workspace tmp;
        union x25519_multiply_step1 *step1 = &tmp.step1;
        union x25519_multiply_step2 *step2 = &tmp.step2;
        union x25519_multiply_step3 *step3 = &tmp.step3;

        /* Step 1: perform raw multiplication
         *
         *   step1 = multiplicand * multiplier
         *
         * Both inputs are 258-bit numbers and the step 1 result is
         * therefore 258+258=516 bits.
         */
        static_assert ( sizeof ( step1->product ) >= sizeof ( step1->parts ) );
        bigint_multiply ( &multiplicand->value, &multiplier->value,
                          &step1->product );

        /* Step 2: reduce high-order 516-256=260 bits of step 1 result
         *
         * Use the identity 2^256=38 (mod p) to reduce the high-order
         * bits of the step 1 result.  We split the 516-bit result
         * from step 1 into its low-order 256 bits and high-order 260
         * bits:
         *
         *   step1 = step1(low 256 bits) + step1(high 260 bits) * 2^256
         *
         * and then perform the calculation:
         *
         *   step2 = step1                                              (mod p)
         *         = step1(low 256 bits) + step1(high 260 bits) * 2^256 (mod p)
         *         = step1(low 256 bits) + step1(high 260 bits) * 38    (mod p)
         *
         * There are 6 bits in the constant value 38.  The step 2
         * multiplication product will therefore have 260+6=266 bits,
         * and the step 2 result (after the addition) will therefore
         * have 267 bits.
         */
        static_assert ( sizeof ( step2->product ) >= sizeof ( step2->value ) );
        static_assert ( sizeof ( step2->product ) >= sizeof ( step2->parts ) );
        bigint_grow ( &step1->parts.low_256bit, &result->value );
        bigint_multiply ( &step1->parts.high_260bit, &x25519_reduce_256,
                          &step2->product );
        bigint_add ( &result->value, &step2->value );

        /* Step 3: reduce high-order 267-256=11 bits of step 2 result
         *
         * Use the identity 2^256=38 (mod p) again to reduce the
         * high-order bits of the step 2 result.  As before, we split
         * the 267-bit result from step 2 into its low-order 256 bits
         * and high-order 11 bits:
         *
         *   step2 = step2(low 256 bits) + step2(high 11 bits) * 2^256
         *
         * and then perform the calculation:
         *
         *   step3 = step2                                             (mod p)
         *         = step2(low 256 bits) + step2(high 11 bits) * 2^256 (mod p)
         *         = step2(low 256 bits) + step2(high 11 bits) * 38    (mod p)
         *
         * There are 6 bits in the constant value 38.  The step 3
         * multiplication product will therefore have 11+6=19 bits,
         * and the step 3 result (after the addition) will therefore
         * have 257 bits.
         *
         * A loose upper bound for the step 3 result (after the
         * addition) is given by:
         *
         *   step3 < ( 2^256 - 1 ) + ( 2^19 - 1 )
         *         < ( 2^257 - 2^256 - 1 ) + ( 2^19 - 1 )
         *         < ( 2^257 - 76 ) - 2^256 + 2^19 + 74
         *         < 4 * ( 2^255 - 19 ) - 2^256 + 2^19 + 74
         *         < 4p - 2^256 + 2^19 + 74
         *
         * and so the step 3 result is strictly less than 4p, and
         * therefore lies within the range [0,4p-1].
         */
        memset ( &step3->value, 0, sizeof ( step3->value ) );
        bigint_grow ( &step2->parts.low_256bit, &result->value );
        bigint_multiply ( &step2->parts.high_11bit, &x25519_reduce_256,
                          &step3->product );
        bigint_add ( &step3->value, &result->value );

        /* Step 1 calculates the product of the input operands, and
         * each subsequent step reduces the number of bits in the
         * result while preserving this value (modulo p).  The final
         * result is therefore equal to the product of the input
         * operands (modulo p), as required.
         *
         * The step 3 result lies within the range [0,4p-1] and the
         * final result is therefore a valid X25519 unsigned 257-bit
         * integer, as required.
         */
}

References bigint_add, bigint_grow, bigint_multiply, memset(), multiplier, x25519_multiply_step1::parts, x25519_multiply_step2::parts, result, static_assert, tmp, and x25519_oct258::value.

Referenced by x25519_invert(), x25519_invert_okx(), x25519_ladder(), x25519_multiply_okx(), and x25519_step().

x25519_invert()

void x25519_invert	(	const union x25519_oct258 *	invertend,
		union x25519_quad257 *	result
	)

Compute multiplicative inverse.

Parameters

invertend	Big integer to be inverted
result	Big integer to hold result (may not overlap input)

Definition at line 529 of file x25519.c.

                                                    {
        int i;

        /* Sanity check */
        assert ( invertend != &result->oct258 );

        /* Calculate inverse as x^(-1)=x^(p-2) where p is the field prime
         *
         * The field prime is p=2^255-19 and so:
         *
         *   p - 2 = 2^255 - 21
         *         = (2^255 - 1) - 2^4 - 2^2
         *
         * i.e. p-2 is a 254-bit number in which all bits are set
         * apart from bit 2 and bit 4.
         *
         * We use the square-and-multiply method to compute x^(p-2).
         */
        bigint_copy ( &invertend->value, &result->value );
        for ( i = 253 ; i >= 0 ; i-- ) {

                /* Square running total */
                x25519_multiply ( &result->oct258, &result->oct258, result );

                /* For each set bit in the exponent, multiply by invertend */
                if ( ( i != 2 ) && ( i != 4 ) ) {
                        x25519_multiply ( invertend, &result->oct258, result );
                }
        }
}

References assert(), bigint_copy, result, x25519_oct258::value, and x25519_multiply().

Referenced by x25519_invert_okx(), and x25519_ladder().

x25519_reduce()

void x25519_reduce

(

union x25519_quad257 *

value

)

Reduce big integer to canonical range.

Parameters

value

Big integer to be reduced

Definition at line 586 of file x25519.c.

                                                   {

        /* Conditionally subtract 2p
         *
         * Subtract twice the field prime, discarding the result (in
         * constant time) if the subtraction underflows.
         *
         * The input value is in the range [0,4p-1].  After this
         * conditional subtraction, the value is in the range
         * [0,2p-1].
         */
        x25519_reduce_by ( &x25519_2p, &value->value );

        /* Conditionally subtract p
         *
         * Subtract the field prime, discarding the result (in
         * constant time) if the subtraction underflows.
         *
         * The value is already in the range [0,2p-1].  After this
         * conditional subtraction, the value is in the range [0,p-1]
         * and is therefore the canonical representation.
         */
        x25519_reduce_by ( &x25519_p, &value->value );
}

References value, x25519_2p, x25519_p, and x25519_reduce_by().

Referenced by x25519_invert_okx(), x25519_ladder(), and x25519_multiply_okx().

x25519_key()

void x25519_key	(	const struct x25519_value *	base,
		const struct x25519_value *	scalar,
		struct x25519_value *	result
	)

Calculate X25519 key.

Parameters

base	Base point
scalar	Scalar multiple
result	Point to hold result (may overlap base point)

Definition at line 808 of file x25519.c.

                                                {
        struct x25519_value *tmp = result;
        union x25519_quad257 point;

        /* Reverse base point and clear high bit as required by RFC7748 */
        memcpy ( tmp, base, sizeof ( *tmp ) );
        x25519_reverse ( tmp );
        tmp->raw[0] &= 0x7f;
        bigint_init ( &point.value, tmp->raw, sizeof ( tmp->raw ) );

        /* Clamp scalar as required by RFC7748 */
        memcpy ( tmp, scalar, sizeof ( *tmp ) );
        tmp->raw[0] &= 0xf8;
        tmp->raw[31] |= 0x40;

        /* Multiply elliptic curve point */
        x25519_ladder ( &point, tmp, &point );

        /* Reverse result */
        bigint_done ( &point.value, result->raw, sizeof ( result->raw ) );
        x25519_reverse ( result );
}

References base, bigint_done, bigint_init, memcpy(), result, tmp, x25519_quad257::value, x25519_ladder(), and x25519_reverse().

Referenced by x25519_curve_multiply(), and x25519_key_okx().

x25519_is_zero()

int x25519_is_zero

(

const struct x25519_value *

value

)

Check if X25519 value is zero.

Parameters

value

Value to check

Return values

is_zero

Value is zero

Definition at line 793 of file x25519.c.

                                                        {
        x25519_t point;

        /* Check if value is zero */
        bigint_init ( &point, value->raw, sizeof ( value->raw ) );
        return bigint_is_zero ( &point );
}

References bigint_init, bigint_is_zero, and value.

Referenced by x25519_curve_is_infinity(), and x25519_key_okx().

Variable Documentation

x25519_curve

struct elliptic_curve x25519_curve

X25519 elliptic curve.

Definition at line 876 of file x25519.c.