x25519.c File Reference

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>

Go to the source code of this file.

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. More...

Functions
	FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
static	bigint_t (bigint_required_size(sizeof(x25519_reduce_256_raw)))
	Reduction constant (used during multiplication) More...
static void	x25519_init_constants (void)
	Initialise constants. More...
struct init_fn x25519_init_fn	__init_fn (INIT_NORMAL)
	Initialisation function. More...
static void	x25519_add (const union x25519_quad257 *augend, const union x25519_quad257 *addend, union x25519_oct258 *result)
	Add big integers modulo field prime. More...
static void	x25519_subtract (const union x25519_quad257 *minuend, const union x25519_quad257 *subtrahend, union x25519_oct258 *result)
	Subtract big integers modulo field prime. 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...
static void	x25519_reduce_by (const x25519_t *subtrahend, x25519_t *value)
	Reduce big integer via conditional subtraction. More...
void	x25519_reduce (union x25519_quad257 *value)
	Reduce big integer to canonical range. More...
static void	x25519_step (const union x25519_quad257 *base, int bit, struct x25519_step *step)
	Compute next step of the Montgomery ladder. More...
static void	x25519_ladder (const union x25519_quad257 *base, struct x25519_value *scalar, union x25519_quad257 *result)
	Multiply X25519 elliptic curve point. More...
static void	x25519_reverse (struct x25519_value *value)
	Reverse X25519 value endianness. More...
int	x25519_key (const struct x25519_value *base, const struct x25519_value *scalar, struct x25519_value *result)
	Calculate X25519 key. More...
static int	x25519_curve_multiply (const void *base, const void *scalar, void *result)
	Multiply scalar by curve point. More...

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

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

Function Documentation

FILE_LICENCE()

FILE_LICENCE

(

GPL2_OR_LATER_OR_UBDL

)

bigint_t()

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

                                           { 0x01, 0xdb, 0x41 };

x25519_init_constants()

static void x25519_init_constants ( void  )

static

Initialise constants.

Definition at line 313 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_oct258::value, x25519_121665, x25519_2p, x25519_4p, x25519_p, x25519_p_raw, and x25519_reduce_256_raw.

__init_fn()

struct init_fn x25519_init_fn __init_fn

(

INIT_NORMAL

)

Initialisation function.

x25519_add()

static 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 348 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()

static 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 381 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, subtrahend, x25519_oct258::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 425 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 527 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()

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

                                                                             {
        unsigned int max_bit = ( ( 8 * sizeof ( *value ) ) - 1 );
        x25519_t tmp;

        /* Conditionally subtract subtrahend
         *
         * Subtract the subtrahend, discarding the result (in constant
         * time) if the subtraction underflows.
         */
        bigint_copy ( value, &tmp );
        bigint_subtract ( subtrahend, value );
        bigint_swap ( value, &tmp, bigint_bit_is_set ( value, max_bit ) );
}

References bigint_bit_is_set, bigint_copy, bigint_subtract, bigint_swap, subtrahend, 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 584 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()

static 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 616 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 a, b, base, bigint_swap, bit, c, container_of, d, e, f, x25519_quad257::oct258, step(), value, x25519_121665, x25519_add(), x25519_multiply(), and x25519_subtract().

Referenced by x25519_ladder().

x25519_ladder()

static 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 738 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, result, scalar, step(), tmp, x25519_invert(), x25519_multiply(), x25519_reduce(), x25519_step(), and zero.

Referenced by x25519_key().

x25519_reverse()

static void x25519_reverse ( struct x25519_value *  value )

static

Reverse X25519 value endianness.

Parameters

value

Value to reverse

Definition at line 772 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_key()

int 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)

Return values

rc	Return status code

Definition at line 793 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 );

        /* Fail if result was all zeros (as required by RFC8422) */
        return ( bigint_is_zero ( &point.value ) ? -EPERM : 0 );
}

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

Referenced by x25519_curve_multiply(), and x25519_key_okx().

x25519_curve_multiply()

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

static

Multiply scalar by curve point.

Parameters

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

                                                  {

        /* Use base point if applicable */
        if ( ! base )
                base = &x25519_generator;

        return x25519_key ( base, scalar, result );
}

References base, result, scalar, x25519_generator, and x25519_key().

Variable Documentation

__attribute__

union x25519_multiply_step1 __attribute__

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

Referenced by x25519_init_constants().

x25519_p

x25519_t x25519_p

static

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

Definition at line 283 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 286 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 289 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 292 of file x25519.c.

Referenced by x25519_init_constants().

x25519_121665

union x25519_oct258 x25519_121665

static

Constant 121665 (used in the Montgomery ladder)

Definition at line 302 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 305 of file x25519.c.

Referenced by x25519_curve_multiply().

x25519_curve

struct elliptic_curve x25519_curve

Initial value:

= {
        .name = "x25519",
        .keysize = sizeof ( struct x25519_value ),
        .multiply = x25519_curve_multiply,
}

X25519 elliptic curve.

Definition at line 840 of file x25519.c.