X25519 key exchange. More...

#include <stdint.h>
#include <string.h>
#include <assert.h>
#include <errno.h>
#include <ipxe/init.h>
#include <ipxe/crypto.h>
#include <ipxe/x25519.h>

Data Structures
union	x25519_multiply_step1
	X25519 multiplication step 1 result. More...
union	x25519_multiply_step2
	X25519 multiplication step 2 result. More...
union	x25519_multiply_step3
	X25519 multiplication step 3 result. More...
union	x25519_multiply_workspace
	X25519 multiplication temporary working space. More...
struct	x25519_projective
	An X25519 elliptic curve point in projective coordinates. More...
struct	x25519_step
	An X25519 Montgomery ladder step. More...

Macros
#define	X25519_REDUCE_256 38
	X25519 reduction constant.

Functions
	FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
	FILE_SECBOOT (PERMITTED)
static	bigint_t (bigint_required_size(sizeof(x25519_reduce_256_raw)))
	Reduction constant (used during multiplication)
static void	x25519_init_constants (void)
	Initialise constants.
struct init_fn x25519_init_fn	__init_fn (INIT_NORMAL)
	Initialisation function.
static void	x25519_add (const union x25519_quad257 augend, const union x25519_quad257 addend, union x25519_oct258 *result)
	Add big integers modulo field prime.
static void	x25519_subtract (const union x25519_quad257 minuend, const union x25519_quad257 subtrahend, union x25519_oct258 *result)
	Subtract big integers modulo field prime.
void	x25519_multiply (const union x25519_oct258 multiplicand, const union x25519_oct258 multiplier, union x25519_quad257 *result)
	Multiply big integers modulo field prime.
void	x25519_invert (const union x25519_oct258 invertend, union x25519_quad257 result)
	Compute multiplicative inverse.
static void	x25519_reduce_by (const x25519_t subtrahend, x25519_t value)
	Reduce big integer via conditional subtraction.
void	x25519_reduce (union x25519_quad257 *value)
	Reduce big integer to canonical range.
static void	x25519_step (const union x25519_quad257 base, int bit, struct x25519_step step)
	Compute next step of the Montgomery ladder.
static void	x25519_ladder (const union x25519_quad257 base, struct x25519_value scalar, union x25519_quad257 *result)
	Multiply X25519 elliptic curve point.
static void	x25519_reverse (struct x25519_value *value)
	Reverse X25519 value endianness.
int	x25519_is_zero (const struct x25519_value *value)
	Check if X25519 value is zero.
void	x25519_key (const struct x25519_value base, const struct x25519_value scalar, struct x25519_value *result)
	Calculate X25519 key.
static int	x25519_curve_is_infinity (const void *point)
	Check if this is the point at infinity.
static int	x25519_curve_multiply (const void base, const void scalar, void *result)
	Multiply scalar by curve point.
static int	x25519_curve_add (const void addend __unused, const void augend __unused, void *result __unused)
	Add curve points (as a one-off operation)

Variables
static const uint8_t	x25519_p_raw []
	Constant p=2^255-19 (the finite field prime)
static x25519_t	x25519_p
	Constant p=2^255-19 (the finite field prime)
static x25519_t	x25519_2p
	Constant 2p=2^256-38.
static x25519_t	x25519_4p
	Constant 4p=2^257-76.
static const uint8_t	x25519_reduce_256_raw [] = { X25519_REDUCE_256 }
	Reduction constant (used during multiplication)
static union x25519_oct258	x25519_121665
	Constant 121665 (used in the Montgomery ladder)
static struct x25519_value	x25519_generator
	Constant g=9 (the group generator)
struct elliptic_curve	x25519_curve
	X25519 elliptic curve.

Detailed Description

X25519 key exchange.

This implementation is inspired by and partially based upon the paper "Implementing Curve25519/X25519: A Tutorial on Elliptic Curve Cryptography" by Martin Kleppmann, available for download from https://www.cl.cam.ac.uk/teaching/2122/Crypto/curve25519.pdf

The underlying modular addition, subtraction, and multiplication operations are completely redesigned for substantially improved efficiency compared to the TweetNaCl implementation studied in that paper.

                           TweetNaCl            iPXE
                           ---------            ----

Storage size of each big integer 128 40 (in bytes)

Stack usage for key exchange 1144 360 (in bytes, large objects only)

Cost of big integer addition 16 5 (in number of 64-bit additions)

Cost of big integer multiplication 273 31 (in number of 64-bit multiplications)

The implementation is constant-time (provided that the underlying big integer operations are also constant-time).

Definition in file x25519.c.

Macro Definition Documentation

◆ X25519_REDUCE_256

#define X25519_REDUCE_256 38

X25519 reduction constant.

The X25519 field prime is p=2^255-19. This gives us:

          p = 2^255 - 19
      2^255 = p + 19
      2^255 = 19          (mod p)
  k * 2^255 = k * 19      (mod p)

We can therefore reduce a value modulo p by taking the high-order bits of the value from bit 255 and above, multiplying by 19, and adding this to the low-order 255 bits of the value.

This would be cumbersome to do in practice since it would require partitioning the value at a 255-bit boundary (and hence would require some shifting and masking operations). However, we can note that:

  k * 2^255 = k * 19      (mod p)

k * 2 * 2^255 = k * 2 * 19 (mod p) k * 2^256 = k * 38 (mod p)

We can therefore simplify the reduction to taking the high order bits of the value from bit 256 and above, multiplying by 38, and adding this to the low-order 256 bits of the value.

Since 256 will inevitably be a multiple of the big integer element size (typically 32 or 64 bits), this avoids the need to perform any shifting or masking operations.

Definition at line 98 of file x25519.c.

Function Documentation

◆ FILE_LICENCE()

FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL )

◆ FILE_SECBOOT()

FILE_SECBOOT ( PERMITTED )

◆ bigint_t()

bigint_t ( bigint_required_size(sizeof(x25519_reduce_256_raw)) )

static

Reduction constant (used during multiplication)

Constant 121665 (used in the Montgomery ladder)

Definition at line 296 of file x25519.c.

300 { 0x01, 0xdb, 0x41 };

References bigint_required_size, and x25519_reduce_256_raw.

◆ x25519_init_constants()

void x25519_init_constants ( void )

static

Initialise constants.

Definition at line 314 of file x25519.c.

                                           {
 
        /* Construct constant p */
        bigint_init ( &x25519_p, x25519_p_raw, sizeof ( x25519_p_raw ) );
 
        /* Construct constant 2p */
        bigint_copy ( &x25519_p, &x25519_2p );
        bigint_add ( &x25519_p, &x25519_2p );
 
        /* Construct constant 4p */
        bigint_copy ( &x25519_2p, &x25519_4p );
        bigint_add ( &x25519_2p, &x25519_4p );
 
        /* Construct reduction constant */
        bigint_init ( &x25519_reduce_256, x25519_reduce_256_raw,
                      sizeof ( x25519_reduce_256_raw ) );
 
        /* Construct constant 121665 */
        bigint_init ( &x25519_121665.value, x25519_121665_raw,
                      sizeof ( x25519_121665_raw ) );
}

References bigint_add, bigint_copy, bigint_init, x25519_121665, x25519_2p, x25519_4p, x25519_p, x25519_p_raw, and x25519_reduce_256_raw.

Referenced by __init_fn().

◆ __init_fn()

struct init_fn x25519_init_fn __init_fn ( INIT_NORMAL )

Initialisation function.

References __init_fn, INIT_NORMAL, and x25519_init_constants().

◆ x25519_add()

void x25519_add	(	const union x25519_quad257 *	augend,
		const union x25519_quad257 *	addend,
		union x25519_oct258 *	result )

inlinestatic

Add big integers modulo field prime.

Parameters

augend	Big integer to add
addend	Big integer to add
result	Big integer to hold result (may overlap augend)

Definition at line 350 of file x25519.c.

                                           {
        int copy;
 
        /* Copy augend if necessary */
        copy = ( result != &augend->oct258 );
        build_assert ( __builtin_constant_p ( copy ) );
        if ( copy ) {
                build_assert ( result != &addend->oct258 );
                bigint_copy ( &augend->oct258.value, &result->value );
        }
 
        /* Perform addition
         *
         * Both inputs are in the range [0,4p-1] and the resulting
         * sum is therefore in the range [0,8p-2].
         *
         * This range lies within the range [0,8p-1] and the result is
         * therefore a valid X25519 unsigned 258-bit integer, as
         * required.
         */
        bigint_add ( &addend->value, &result->value );
}

References bigint_add, bigint_copy, build_assert, x25519_quad257::oct258, result, x25519_oct258::value, and x25519_quad257::value.

Referenced by x25519_step().

◆ x25519_subtract()

void x25519_subtract	(	const union x25519_quad257 *	minuend,
		const union x25519_quad257 *	subtrahend,
		union x25519_oct258 *	result )

inlinestatic

Subtract big integers modulo field prime.

Parameters

minuend	Big integer from which to subtract
subtrahend	Big integer to subtract
result	Big integer to hold result (may overlap minuend)

Definition at line 383 of file x25519.c.

                                                {
        int copy;
 
        /* Copy minuend if necessary */
        copy = ( result != &minuend->oct258 );
        build_assert ( __builtin_constant_p ( copy ) );
        if ( copy ) {
                build_assert ( result != &subtrahend->oct258 );
                bigint_copy ( &minuend->oct258.value, &result->value );
        }
 
        /* Perform subtraction
         *
         * Both inputs are in the range [0,4p-1] and the resulting
         * difference is therefore in the range [1-4p,4p-1].
         *
         * This range lies partially outside the range [0,8p-1] and
         * the result is therefore not yet a valid X25519 unsigned
         * 258-bit integer.
         */
        bigint_subtract ( &subtrahend->value, &result->value );
 
        /* Add constant multiple of field prime p
         *
         * Add the constant 4p to the result.  This brings the result
         * within the range [1,8p-1] (without changing the value
         * modulo p).
         *
         * This range lies within the range [0,8p-1] and the result is
         * therefore now a valid X25519 unsigned 258-bit integer, as
         * required.
         */
        bigint_add ( &x25519_4p, &result->value );
}

References bigint_add, bigint_copy, bigint_subtract, build_assert, x25519_quad257::oct258, result, x25519_oct258::value, x25519_quad257::value, and x25519_4p.

Referenced by x25519_step().

◆ 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, 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_by()

void x25519_reduce_by	(	const x25519_t *	subtrahend,
		x25519_t *	value )

static

Reduce big integer via conditional subtraction.

Parameters

subtrahend	Big integer to subtract
value	Big integer to be subtracted from, if possible

Definition at line 567 of file x25519.c.

                                                                             {
        x25519_t tmp;
        int underflow;
 
        /* Conditionally subtract subtrahend
         *
         * Subtract the subtrahend, discarding the result (in constant
         * time) if the subtraction underflows.
         */
        bigint_copy ( value, &tmp );
        underflow = bigint_subtract ( subtrahend, value );
        bigint_swap ( value, &tmp, underflow );
}

References bigint_copy, bigint_subtract, bigint_swap, tmp, and value.

Referenced by x25519_reduce().

◆ 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_step()

void x25519_step	(	const union x25519_quad257 *	base,
		int	bit,
		struct x25519_step *	step )

static

Compute next step of the Montgomery ladder.

Parameters

base	Base point
bit	Bit value
step	Ladder step

Definition at line 618 of file x25519.c.

                                                     {
        union x25519_quad257 *a = &step->x_n.X;
        union x25519_quad257 *b = &step->x_n1.X;
        union x25519_quad257 *c = &step->x_n.Z;
        union x25519_quad257 *d = &step->x_n1.Z;
        union x25519_oct258 e;
        union x25519_quad257 f;
        union x25519_oct258 *v1_e;
        union x25519_oct258 *v2_a;
        union x25519_oct258 *v3_c;
        union x25519_oct258 *v4_b;
        union x25519_quad257 *v5_d;
        union x25519_quad257 *v6_f;
        union x25519_quad257 *v7_a;
        union x25519_quad257 *v8_c;
        union x25519_oct258 *v9_e;
        union x25519_oct258 *v10_a;
        union x25519_quad257 *v11_b;
        union x25519_oct258 *v12_c;
        union x25519_quad257 *v13_a;
        union x25519_oct258 *v14_a;
        union x25519_quad257 *v15_c;
        union x25519_quad257 *v16_a;
        union x25519_quad257 *v17_d;
        union x25519_quad257 *v18_b;
 
        /* See the referenced paper "Implementing Curve25519/X25519: A
         * Tutorial on Elliptic Curve Cryptography" for the reasoning
         * behind this calculation.
         */
 
        /* Reuse storage locations for intermediate results where possible */
        v1_e = &e;
        v2_a = container_of ( &a->value, union x25519_oct258, value );
        v3_c = container_of ( &c->value, union x25519_oct258, value );
        v4_b = container_of ( &b->value, union x25519_oct258, value );
        v5_d = d;
        v6_f = &f;
        v7_a = a;
        v8_c = c;
        v9_e = &e;
        v10_a = container_of ( &a->value, union x25519_oct258, value );
        v11_b = b;
        v12_c = container_of ( &c->value, union x25519_oct258, value );
        v13_a = a;
        v14_a = container_of ( &a->value, union x25519_oct258, value );
        v15_c = c;
        v16_a = a;
        v17_d = d;
        v18_b = b;
 
        /* Select inputs */
        bigint_swap ( &a->value, &b->value, bit );
        bigint_swap ( &c->value, &d->value, bit );
 
        /* v1 = a + c */
        x25519_add ( a, c, v1_e );
 
        /* v2 = a - c */
        x25519_subtract ( a, c, v2_a );
 
        /* v3 = b + d */
        x25519_add ( b, d, v3_c );
 
        /* v4 = b - d */
        x25519_subtract ( b, d, v4_b );
 
        /* v5 = v1^2 = (a + c)^2 = a^2 + 2ac + c^2 */
        x25519_multiply ( v1_e, v1_e, v5_d );
 
        /* v6 = v2^2 = (a - c)^2 = a^2 - 2ac + c^2 */
        x25519_multiply ( v2_a, v2_a, v6_f );
 
        /* v7 = v3 * v2 = (b + d) * (a - c) = ab - bc + ad - cd */
        x25519_multiply ( v3_c, v2_a, v7_a );
 
        /* v8 = v4 * v1 = (b - d) * (a + c) = ab + bc - ad - cd */
        x25519_multiply ( v4_b, v1_e, v8_c );
 
        /* v9 = v7 + v8 = 2 * (ab - cd) */
        x25519_add ( v7_a, v8_c, v9_e );
 
        /* v10 = v7 - v8 = 2 * (ad - bc) */
        x25519_subtract ( v7_a, v8_c, v10_a );
 
        /* v11 = v10^2 = 4 * (ad - bc)^2 */
        x25519_multiply ( v10_a, v10_a, v11_b );
 
        /* v12 = v5 - v6 = (a + c)^2 - (a - c)^2 = 4ac */
        x25519_subtract ( v5_d, v6_f, v12_c );
 
        /* v13 = v12 * 121665 = 486660ac = (A-2) * ac */
        x25519_multiply ( v12_c, &x25519_121665, v13_a );
 
        /* v14 = v13 + v5 = (A-2) * ac + a^2 + 2ac + c^2 = a^2 + A * ac + c^2 */
        x25519_add ( v13_a, v5_d, v14_a );
 
        /* v15 = v12 * v14 = 4ac * (a^2 + A * ac + c^2) */
        x25519_multiply ( v12_c, v14_a, v15_c );
 
        /* v16 = v5 * v6 = (a + c)^2 * (a - c)^2 = (a^2 - c^2)^2 */
        x25519_multiply ( &v5_d->oct258, &v6_f->oct258, v16_a );
 
        /* v17 = v11 * base = 4 * base * (ad - bc)^2 */
        x25519_multiply ( &v11_b->oct258, &base->oct258, v17_d );
 
        /* v18 = v9^2 = 4 * (ab - cd)^2 */
        x25519_multiply ( v9_e, v9_e, v18_b );
 
        /* Select outputs */
        bigint_swap ( &a->value, &b->value, bit );
        bigint_swap ( &c->value, &d->value, bit );
}

References base, bigint_swap, bit, container_of, x25519_quad257::oct258, step(), value, x25519_quad257::value, x25519_121665, x25519_add(), x25519_multiply(), and x25519_subtract().

Referenced by x25519_ladder().

◆ x25519_ladder()

void x25519_ladder	(	const union x25519_quad257 *	base,
		struct x25519_value *	scalar,
		union x25519_quad257 *	result )

static

Multiply X25519 elliptic curve point.

Parameters

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

Definition at line 740 of file x25519.c.

                                                           {
        static const uint8_t zero[] = { 0 };
        static const uint8_t one[] = { 1 };
        struct x25519_step step;
        union x25519_quad257 *tmp;
        int bit;
        int i;
 
        /* Initialise ladder */
        bigint_init ( &step.x_n.X.value, one, sizeof ( one ) );
        bigint_init ( &step.x_n.Z.value, zero, sizeof ( zero ) );
        bigint_copy ( &base->value, &step.x_n1.X.value );
        bigint_init ( &step.x_n1.Z.value, one, sizeof ( one ) );
 
        /* Use ladder */
        for ( i = 254 ; i >= 0 ; i-- ) {
                bit = ( ( scalar->raw[ i / 8 ] >> ( i % 8 ) ) & 1 );
                x25519_step ( base, bit, &step );
        }
 
        /* Convert back to affine coordinate */
        tmp = &step.x_n1.X;
        x25519_invert ( &step.x_n.Z.oct258, tmp );
        x25519_multiply ( &step.x_n.X.oct258, &tmp->oct258, result );
        x25519_reduce ( result );
}

References base, bigint_copy, bigint_init, bit, x25519_value::raw, result, step(), tmp, x25519_invert(), x25519_multiply(), x25519_reduce(), and x25519_step().

Referenced by x25519_key().

◆ x25519_reverse()

void x25519_reverse ( struct x25519_value * value )

static

Reverse X25519 value endianness.

Parameters

value Value to reverse

Definition at line 774 of file x25519.c.

                                                          {
        uint8_t *low = value->raw;
        uint8_t *high = &value->raw[ sizeof ( value->raw ) - 1 ];
        uint8_t tmp;
 
        /* Reverse bytes */
        do {
                tmp = *low;
                *low = *high;
                *high = tmp;
        } while ( ++low < --high );
}

References high, low, tmp, and value.

Referenced by x25519_key().

◆ 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().

◆ 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_curve_is_infinity()

int x25519_curve_is_infinity ( const void * point )

static

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 839 of file x25519.c.

                                                          {
 
        /* We use all zeroes for the point at infinity (as per RFC8422) */
        return x25519_is_zero ( point );
}

References x25519_is_zero().

◆ x25519_curve_multiply()

int x25519_curve_multiply	(	const void *	base,
		const void *	scalar,
		void *	result )

static

Multiply scalar by curve point.

Parameters

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

Return values

rc	Return status code

Definition at line 853 of file x25519.c.

                                                  {
 
        x25519_key ( base, scalar, result );
        return 0;
}

References base, result, and x25519_key().

◆ x25519_curve_add()

int x25519_curve_add	(	const void *addend	__unused,
		const void *augend	__unused,
		void *result	__unused )

static

Add curve points (as a one-off operation)

Parameters

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 868 of file x25519.c.

                                                      {
 
        return -ENOTTY;
}

References __unused, ENOTTY, and result.

Variable Documentation

◆ x25519_p_raw

const uint8_t x25519_p_raw[]

static

Initial value:

= {
        0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
        0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
        0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
        0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xed
}

Constant p=2^255-19 (the finite field prime)

Definition at line 276 of file x25519.c.

                                      {
        0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
        0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
        0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
        0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xed
};

Referenced by x25519_init_constants().

◆ x25519_p

x25519_t x25519_p

static

Constant p=2^255-19 (the finite field prime)

Definition at line 284 of file x25519.c.

Referenced by x25519_init_constants(), and x25519_reduce().

◆ x25519_2p

x25519_t x25519_2p

static

Constant 2p=2^256-38.

Definition at line 287 of file x25519.c.

Referenced by x25519_init_constants(), and x25519_reduce().

◆ x25519_4p

x25519_t x25519_4p

static

Constant 4p=2^257-76.

Definition at line 290 of file x25519.c.

Referenced by x25519_init_constants(), and x25519_subtract().

◆ x25519_reduce_256_raw

const uint8_t x25519_reduce_256_raw[] = { X25519_REDUCE_256 }

static

Reduction constant (used during multiplication)

Definition at line 293 of file x25519.c.

293{ X25519_REDUCE_256 };

X25519_REDUCE_256

#define X25519_REDUCE_256

X25519 reduction constant.

Definition x25519.c:98

Referenced by bigint_t(), and x25519_init_constants().

◆ x25519_121665

union x25519_oct258 x25519_121665

static

Constant 121665 (used in the Montgomery ladder)

Definition at line 303 of file x25519.c.

Referenced by x25519_init_constants(), and x25519_step().

◆ x25519_generator

struct x25519_value x25519_generator

static

Initial value:

= {
        .raw = { 9, }
}

Constant g=9 (the group generator)

Definition at line 306 of file x25519.c.

                                              {
        .raw = { 9, }
};

◆ x25519_curve

struct elliptic_curve x25519_curve

Initial value:

= {
        .name = "x25519",
        .pointsize = sizeof ( struct x25519_value ),
        .keysize = sizeof ( struct x25519_value ),
        .base = x25519_generator.raw,
        .is_infinity = x25519_curve_is_infinity,
        .multiply = x25519_curve_multiply,
        .add = x25519_curve_add,
}

X25519 elliptic curve.

Definition at line 876 of file x25519.c.

                                     {
        .name = "x25519",
        .pointsize = sizeof ( struct x25519_value ),
        .keysize = sizeof ( struct x25519_value ),
        .base = x25519_generator.raw,
        .is_infinity = x25519_curve_is_infinity,
        .multiply = x25519_curve_multiply,
        .add = x25519_curve_add,
};

Referenced by __tls_named_curve().

Data Structures

Macros

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ X25519_REDUCE_256

Function Documentation

◆ FILE_LICENCE()

◆ FILE_SECBOOT()

◆ bigint_t()

◆ x25519_init_constants()

◆ __init_fn()

◆ x25519_add()

◆ x25519_subtract()

◆ x25519_multiply()

◆ x25519_invert()

◆ x25519_reduce_by()

◆ x25519_reduce()

◆ x25519_step()

◆ x25519_ladder()

◆ x25519_reverse()

◆ x25519_is_zero()

◆ x25519_key()

◆ x25519_curve_is_infinity()

◆ x25519_curve_multiply()

◆ x25519_curve_add()

Variable Documentation

◆ x25519_p_raw

◆ x25519_p

◆ x25519_2p

◆ x25519_4p

◆ x25519_reduce_256_raw

◆ x25519_121665

◆ x25519_generator

◆ x25519_curve