bigint.h File Reference

Big integer support. More...

#include <assert.h>
#include <bits/bigint.h>

Go to the source code of this file.

Macros
#define	bigint_t(size)
	Define a big-integer type.
#define	bigint_required_size(len)
	Determine number of elements required for a big-integer type.
#define	bigint_size(bigint)
	Determine number of elements in big-integer type.
#define	bigint_ntoa(value)
	Transcribe big integer (for debugging)
#define	bigint_init(value, data, len)
	Initialise big integer.
#define	bigint_done(value, out, len)
	Finalise big integer.
#define	bigint_add(addend, value)
	Add big integers.
#define	bigint_subtract(subtrahend, value)
	Subtract big integers.
#define	bigint_shl(value)
	Shift big integer left.
#define	bigint_shr(value)
	Shift big integer right.
#define	bigint_is_zero(value)
	Test if big integer is equal to zero.
#define	bigint_is_geq(value, reference)
	Compare big integers.
#define	bigint_set_bit(value, bit)
	Set bit in big integer.
#define	bigint_clear_bit(value, bit)
	Clear bit in big integer.
#define	bigint_bit_is_set(value, bit)
	Test if bit is set in big integer.
#define	bigint_msb_is_set(value)
	Test if most significant bit is set in big integer.
#define	bigint_max_set_bit(value)
	Find highest bit set in big integer.
#define	bigint_grow(source, dest)
	Grow big integer.
#define	bigint_shrink(source, dest)
	Shrink big integer.
#define	bigint_copy(source, dest)
	Copy big integer.
#define	bigint_swap(first, second, swap)
	Conditionally swap big integers (in constant time)
#define	bigint_multiply(multiplicand, multiplier, result)
	Multiply big integers.
#define	bigint_reduce(modulus, result)
	Reduce big integer R^2 modulo N.
#define	bigint_mod_invert(invertend, inverse)
	Compute inverse of odd big integer modulo any power of two.
#define	bigint_montgomery_relaxed(modulus, value, result)
	Perform relaxed Montgomery reduction (REDC) of a big integer.
#define	bigint_montgomery(modulus, value, result)
	Perform classic Montgomery reduction (REDC) of a big integer.
#define	bigint_ladder(result, multiple, exponent, op, ctx, tmp)
	Perform generalised exponentiation via a Montgomery ladder.
#define	bigint_mod_exp(base, modulus, exponent, result, tmp)
	Perform modular exponentiation of big integers.
#define	bigint_mod_exp_tmp_len(modulus)
	Calculate temporary working space required for moduluar exponentiation.

Typedefs
typedef void	bigint_ladder_op_t(const bigint_element_t *operand0, bigint_element_t *result0, unsigned int size, const void *ctx, void *tmp)
	A big integer Montgomery ladder commutative operation.

Functions
	FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
	FILE_SECBOOT (PERMITTED)
static	__attribute__ ((always_inline)) void bigint_set_bit_raw(bigint_element_t *value0
	Set bit in big integer.
	return (!!(value->element[index] &(1UL<< subindex)))
const char *	bigint_ntoa_raw (const bigint_element_t *value0, unsigned int size)
	Transcribe big integer (for debugging)
void	bigint_init_raw (bigint_element_t *value0, unsigned int size, const void *data, size_t len)
void	bigint_done_raw (const bigint_element_t *value0, unsigned int size, void *out, size_t len)
int	bigint_add_raw (const bigint_element_t *addend0, bigint_element_t *value0, unsigned int size)
int	bigint_subtract_raw (const bigint_element_t *subtrahend0, bigint_element_t *value0, unsigned int size)
int	bigint_shl_raw (bigint_element_t *value0, unsigned int size)
int	bigint_shr_raw (bigint_element_t *value0, unsigned int size)
int	bigint_is_zero_raw (const bigint_element_t *value0, unsigned int size)
int	bigint_is_geq_raw (const bigint_element_t *value0, const bigint_element_t *reference0, unsigned int size)
int	bigint_bit_is_set_raw (const bigint_element_t *value0, unsigned int size, unsigned int bit)
int	bigint_max_set_bit_raw (const bigint_element_t *value0, unsigned int size)
void	bigint_grow_raw (const bigint_element_t *source0, unsigned int source_size, bigint_element_t *dest0, unsigned int dest_size)
void	bigint_shrink_raw (const bigint_element_t *source0, unsigned int source_size, bigint_element_t *dest0, unsigned int dest_size)
void	bigint_swap_raw (bigint_element_t *first0, bigint_element_t *second0, unsigned int size, int swap)
	Conditionally swap big integers (in constant time)
void	bigint_multiply_one (const bigint_element_t multiplicand, const bigint_element_t multiplier, bigint_element_t *result, bigint_element_t *carry)
void	bigint_multiply_raw (const bigint_element_t *multiplicand0, unsigned int multiplicand_size, const bigint_element_t *multiplier0, unsigned int multiplier_size, bigint_element_t *result0)
	Multiply big integers.
void	bigint_reduce_raw (const bigint_element_t *modulus0, bigint_element_t *result0, unsigned int size)
	Reduce big integer R^2 modulo N.
void	bigint_mod_invert_raw (const bigint_element_t *invertend0, bigint_element_t *inverse0, unsigned int size)
	Compute inverse of odd big integer modulo any power of two.
int	bigint_montgomery_relaxed_raw (const bigint_element_t *modulus0, bigint_element_t *value0, bigint_element_t *result0, unsigned int size)
	Perform relaxed Montgomery reduction (REDC) of a big integer.
void	bigint_montgomery_raw (const bigint_element_t *modulus0, bigint_element_t *value0, bigint_element_t *result0, unsigned int size)
	Perform classic Montgomery reduction (REDC) of a big integer.
void	bigint_ladder_raw (bigint_element_t *result0, bigint_element_t *multiple0, unsigned int size, const bigint_element_t *exponent0, unsigned int exponent_size, bigint_ladder_op_t *op, const void *ctx, void *tmp)
	Perform generalised exponentiation via a Montgomery ladder.
void	bigint_mod_exp_ladder (const bigint_element_t *multiplier0, bigint_element_t *result0, unsigned int size, const void *ctx, void *tmp)
	Perform modular multiplication as part of a Montgomery ladder.
void	bigint_mod_exp_raw (const bigint_element_t *base0, const bigint_element_t *modulus0, const bigint_element_t *exponent0, bigint_element_t *result0, unsigned int size, unsigned int exponent_size, void *tmp)
	Perform modular exponentiation of big integers.

Variables
static unsigned int	size
static unsigned int unsigned int	bit
unsigned int	index = ( bit / ( 8 * sizeof ( value->element[0] ) ) )
unsigned int	subindex = ( bit % ( 8 * sizeof ( value->element[0] ) ) )
value	element [index] = ( 1UL << subindex )

Detailed Description

Big integer support.

Definition in file bigint.h.

Macro Definition Documentation

bigint_t

#define bigint_t

(

size

)

Value:

        struct {                                                        \
                bigint_element_t element[ (size) ];                  \
        }

Define a big-integer type.

Parameters

size	Number of elements

Return values

bigint_t

Big integer type

Definition at line 20 of file bigint.h.

#define bigint_t( size )                                                \
        struct {                                                        \
                bigint_element_t element[ (size) ];                     \
        }

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(), x25519_multiply_step1::bigint_t(), x25519_multiply_step2::bigint_t(), 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().

bigint_required_size

#define bigint_required_size

(

len

)

Value:

        ( (len) ? ( ( (len) + sizeof ( bigint_element_t ) - 1 ) / \
                    sizeof ( bigint_element_t ) ) : 1 )

Determine number of elements required for a big-integer type.

Parameters

len	Maximum length of big integer, in bytes

Return values

size	Number of elements

Definition at line 31 of file bigint.h.

#define bigint_required_size( len )                                     \
        ( (len) ? ( ( (len) + sizeof ( bigint_element_t ) - 1 ) /       \
                    sizeof ( bigint_element_t ) ) : 1 )

Referenced by bigint_add_okx(), bigint_bit_is_set_okx(), bigint_is_geq_okx(), bigint_is_zero_okx(), bigint_max_set_bit_okx(), bigint_mod_exp_okx(), bigint_mod_invert_okx(), bigint_montgomery_okx(), bigint_multiply_okx(), bigint_reduce_okx(), bigint_shl_okx(), bigint_shr_okx(), bigint_subtract_okx(), bigint_swap_okx(), bigint_t(), x25519_multiply_step1::bigint_t(), x25519_multiply_step2::bigint_t(), dhe_key(), ecdsa_alloc(), elliptic_curve_okx(), rsa_alloc(), and weierstrass_multiply().

bigint_size

#define bigint_size

(

bigint

)

Value:

        ( sizeof ( *(bigint) ) / sizeof ( (bigint)->element[0] ) )

Determine number of elements in big-integer type.

Parameters

bigint

Big integer

Return values

size	Number of elements

Definition at line 41 of file bigint.h.

#define bigint_size( bigint )                                           \
        ( sizeof ( *(bigint) ) / sizeof ( (bigint)->element[0] ) )

Referenced by bigint_add_okx(), bigint_is_geq_okx(), bigint_mod_exp_okx(), bigint_multiply_okx(), bigint_reduce_okx(), bigint_subtract_okx(), and weierstrass_add_ladder().

bigint_ntoa

#define bigint_ntoa

(

value

)

Value:

        ( {                                     \
        unsigned int size = bigint_size (value);                    \
        bigint_ntoa_raw ( (value)->element, size );                     \
        } )

Transcribe big integer (for debugging)

Parameters

value

Big integer to be transcribed

Return values

string

Big integer in string form (may be abbreviated)

Definition at line 50 of file bigint.h.

#define bigint_ntoa( value ) ( {                                        \
        unsigned int size = bigint_size (value);                        \
        bigint_ntoa_raw ( (value)->element, size );                     \
        } )

Referenced by bigint_add_okx(), bigint_bit_is_set_okx(), bigint_is_geq_okx(), bigint_is_zero_okx(), bigint_max_set_bit_okx(), bigint_mod_exp_okx(), bigint_mod_invert_okx(), bigint_montgomery_okx(), bigint_multiply_okx(), bigint_reduce_okx(), bigint_shl_okx(), bigint_shr_okx(), bigint_subtract_okx(), ecdsa_init_values(), ecdsa_sign_rs(), ecdsa_verify_rs(), weierstrass_add_raw(), weierstrass_done_raw(), weierstrass_exec(), weierstrass_init_curve(), weierstrass_init_raw(), weierstrass_is_infinity(), and weierstrass_multiply().

bigint_init

#define bigint_init	(		value,
			data,
			len )

Value:

        do {                            \
        unsigned int size = bigint_size (value);                    \
        assert ( (len) <= ( size * sizeof ( (value)->element[0] ) ) );       \
        bigint_init_raw ( (value)->element, size, (data), (len) );       \
        } while ( 0 )

Initialise big integer.

Parameters

value	Big integer to initialise
data	Raw data
len	Length of raw data

Definition at line 62 of file bigint.h.

#define bigint_init( value, data, len ) do {                            \
        unsigned int size = bigint_size (value);                        \
        assert ( (len) <= ( size * sizeof ( (value)->element[0] ) ) );  \
        bigint_init_raw ( (value)->element, size, (data), (len) );      \
        } while ( 0 )

Referenced by bigint_add_okx(), bigint_bit_is_set_okx(), bigint_init_sample(), bigint_is_geq_okx(), bigint_is_zero_okx(), bigint_max_set_bit_okx(), bigint_mod_exp_okx(), bigint_mod_exp_raw(), bigint_mod_invert_okx(), bigint_montgomery_okx(), bigint_multiply_okx(), bigint_reduce_okx(), bigint_shl_okx(), bigint_shr_okx(), bigint_subtract_okx(), bigint_swap_okx(), dhe_key(), ecdsa_init_values(), ecdsa_parse_signature(), ecdsa_sign_rs(), ecdsa_verify_rs(), elliptic_curve_okx(), rsa_cipher(), rsa_init(), weierstrass_init_curve(), weierstrass_init_raw(), weierstrass_is_infinity(), weierstrass_multiply(), x25519_init_constants(), x25519_invert_okx(), x25519_is_zero(), x25519_key(), x25519_ladder(), and x25519_multiply_okx().

bigint_done

#define bigint_done	(		value,
			out,
			len )

Value:

        do {                            \
        unsigned int size = bigint_size (value);                    \
        bigint_done_raw ( (value)->element, size, (out), (len) ); \
        } while ( 0 )

Finalise big integer.

Parameters

value	Big integer to finalise
out	Output buffer
len	Length of output buffer

Definition at line 75 of file bigint.h.

#define bigint_done( value, out, len ) do {                             \
        unsigned int size = bigint_size (value);                        \
        bigint_done_raw ( (value)->element, size, (out), (len) );       \
        } while ( 0 )

Referenced by bigint_add_okx(), bigint_done_sample(), bigint_mod_exp_okx(), bigint_mod_invert_okx(), bigint_montgomery_okx(), bigint_multiply_okx(), bigint_reduce_okx(), bigint_shl_okx(), bigint_shr_okx(), bigint_subtract_okx(), bigint_swap_okx(), dhe_key(), ecdsa_prepend_signature(), ecdsa_verify_rs(), elliptic_curve_okx(), rsa_cipher(), weierstrass_done_raw(), and x25519_key().

bigint_add

#define bigint_add	(		addend,
			value )

Value:

        ( {                                     \
        unsigned int size = bigint_size (addend);                        \
        bigint_add_raw ( (addend)->element, (value)->element, size );    \
        } )

Add big integers.

Parameters

addend	Big integer to add
value	Big integer to be added to

Return values

carry

Carry out

Definition at line 87 of file bigint.h.

#define bigint_add( addend, value ) ( {                                 \
        unsigned int size = bigint_size (addend);                       \
        bigint_add_raw ( (addend)->element, (value)->element, size );   \
        } )

Referenced by bigint_add_okx(), bigint_add_sample(), bigint_mod_exp_raw(), bigint_mod_invert_raw(), bigint_montgomery_relaxed_raw(), bigint_reduce_raw(), ecdsa_sign_rs(), elliptic_curve_okx(), weierstrass_exec(), weierstrass_init_curve(), x25519_add(), x25519_init_constants(), x25519_multiply(), and x25519_subtract().

bigint_subtract

#define bigint_subtract	(		subtrahend,
			value )

Value:

        ( {                     \
        unsigned int size = bigint_size (subtrahend);                    \
        bigint_subtract_raw ( (subtrahend)->element, (value)->element,       \
                              size );                                       \
        } )

Subtract big integers.

Parameters

subtrahend	Big integer to subtract
value	Big integer to be subtracted from

Return values

borrow

Borrow out

Definition at line 99 of file bigint.h.

#define bigint_subtract( subtrahend, value ) ( {                        \
        unsigned int size = bigint_size (subtrahend);                   \
        bigint_subtract_raw ( (subtrahend)->element, (value)->element,  \
                              size );                                   \
        } )

Referenced by bigint_mod_exp_raw(), bigint_montgomery_raw(), bigint_reduce_raw(), bigint_subtract_okx(), bigint_subtract_sample(), ecdsa_init_values(), ecdsa_verify_rs(), weierstrass_exec(), weierstrass_init_curve(), x25519_reduce_by(), and x25519_subtract().

bigint_shl

#define bigint_shl

(

value

)

Value:

        ( {                                             \
        unsigned int size = bigint_size (value);                    \
        bigint_shl_raw ( (value)->element, size );                      \
        } )

Shift big integer left.

Parameters

value

Big integer

Return values

out	Bit shifted out

Definition at line 111 of file bigint.h.

#define bigint_shl( value ) ( {                                         \
        unsigned int size = bigint_size (value);                        \
        bigint_shl_raw ( (value)->element, size );                      \
        } )

Referenced by bigint_reduce_raw(), bigint_shl_okx(), and bigint_shl_sample().

bigint_shr

#define bigint_shr

(

value

)

Value:

        ( {                                             \
        unsigned int size = bigint_size (value);                    \
        bigint_shr_raw ( (value)->element, size );                      \
        } )

Shift big integer right.

Parameters

value

Big integer

Return values

out	Bit shifted out

Definition at line 122 of file bigint.h.

#define bigint_shr( value ) ( {                                         \
        unsigned int size = bigint_size (value);                        \
        bigint_shr_raw ( (value)->element, size );                      \
        } )

Referenced by bigint_mod_exp_raw(), bigint_mod_invert_raw(), bigint_shr_okx(), and bigint_shr_sample().

bigint_is_zero

#define bigint_is_zero

(

value

)

Value:

        ( {                                     \
        unsigned int size = bigint_size (value);                    \
        bigint_is_zero_raw ( (value)->element, size ); } )

Test if big integer is equal to zero.

Parameters

value	Big integer
size	Number of elements

Return values

is_zero

Big integer is equal to zero

Definition at line 134 of file bigint.h.

#define bigint_is_zero( value ) ( {                                     \
        unsigned int size = bigint_size (value);                        \
        bigint_is_zero_raw ( (value)->element, size ); } )

Referenced by bigint_is_zero_okx(), bigint_is_zero_sample(), ecdsa_parse_signature(), ecdsa_sign_rs(), ecdsa_verify_rs(), weierstrass_init_raw(), weierstrass_is_infinity(), weierstrass_verify_raw(), and x25519_is_zero().

bigint_is_geq

#define bigint_is_geq	(		value,
			reference )

Value:

        ( {                             \
        unsigned int size = bigint_size (value);                    \
        bigint_is_geq_raw ( (value)->element, (reference)->element,  \
                            size ); } )

Compare big integers.

Parameters

value	Big integer
reference	Reference big integer

Return values

geq	Big integer is greater than or equal to the reference

Definition at line 145 of file bigint.h.

#define bigint_is_geq( value, reference ) ( {                           \
        unsigned int size = bigint_size (value);                        \
        bigint_is_geq_raw ( (value)->element, (reference)->element,     \
                            size ); } )

Referenced by bigint_is_geq_okx(), bigint_is_geq_sample(), bigint_montgomery_raw(), bigint_reduce_raw(), ecdsa_parse_signature(), and ecdsa_sign_rs().

bigint_set_bit

#define bigint_set_bit	(		value,
			bit )

Value:

        do {                            \
        unsigned int size = bigint_size (value);                    \
        bigint_set_bit_raw ( (value)->element, size, bit );          \
        } while ( 0 )

Set bit in big integer.

Parameters

value	Big integer
bit	Bit to set

Definition at line 156 of file bigint.h.

#define bigint_set_bit( value, bit ) do {                               \
        unsigned int size = bigint_size (value);                        \
        bigint_set_bit_raw ( (value)->element, size, bit );             \
        } while ( 0 )

Referenced by bigint_reduce_raw().

bigint_clear_bit

#define bigint_clear_bit	(		value,
			bit )

Value:

        do {                            \
        unsigned int size = bigint_size (value);                    \
        bigint_clear_bit_raw ( (value)->element, size, bit );                \
        } while ( 0 )

Clear bit in big integer.

Parameters

value	Big integer
bit	Bit to set

Definition at line 167 of file bigint.h.

#define bigint_clear_bit( value, bit ) do {                             \
        unsigned int size = bigint_size (value);                        \
        bigint_clear_bit_raw ( (value)->element, size, bit );           \
        } while ( 0 )

bigint_bit_is_set

#define bigint_bit_is_set	(		value,
			bit )

Value:

        ( {                             \
        unsigned int size = bigint_size (value);                    \
        bigint_bit_is_set_raw ( (value)->element, size, bit ); } )

Test if bit is set in big integer.

Parameters

value	Big integer
bit	Bit to test

Return values

is_set

Bit is set

Definition at line 179 of file bigint.h.

#define bigint_bit_is_set( value, bit ) ( {                             \
        unsigned int size = bigint_size (value);                        \
        bigint_bit_is_set_raw ( (value)->element, size, bit ); } )

Referenced by bigint_add_okx(), bigint_bit_is_set_okx(), bigint_bit_is_set_sample(), bigint_ladder_raw(), bigint_mod_exp_raw(), bigint_mod_invert_raw(), bigint_montgomery_relaxed_raw(), and bigint_shl_okx().

bigint_msb_is_set

#define bigint_msb_is_set

(

value

)

Value:

        ( {                                     \
        unsigned int size = bigint_size (value);                    \
        bigint_msb_is_set_raw ( (value)->element, size ); } )

Test if most significant bit is set in big integer.

Parameters

value

Big integer

Return values

is_set

Most significant bit is set

Definition at line 189 of file bigint.h.

#define bigint_msb_is_set( value ) ( {                                  \
        unsigned int size = bigint_size (value);                        \
        bigint_msb_is_set_raw ( (value)->element, size ); } )

bigint_max_set_bit

#define bigint_max_set_bit

(

value

)

Value:

        ( {                                     \
        unsigned int size = bigint_size (value);                    \
        bigint_max_set_bit_raw ( (value)->element, size ); } )

Find highest bit set in big integer.

Parameters

value

Big integer

Return values

max_bit

Highest bit set + 1 (or 0 if no bits set)

Definition at line 199 of file bigint.h.

#define bigint_max_set_bit( value ) ( {                                 \
        unsigned int size = bigint_size (value);                        \
        bigint_max_set_bit_raw ( (value)->element, size ); } )

Referenced by bigint_max_set_bit_okx(), bigint_max_set_bit_sample(), bigint_mod_exp_raw(), and bigint_reduce_raw().

bigint_grow

#define bigint_grow	(		source,
			dest )

Value:

        do {                            \
        unsigned int source_size = bigint_size (source);          \
        unsigned int dest_size = bigint_size (dest);                    \
        bigint_grow_raw ( (source)->element, source_size,             \
                          (dest)->element, dest_size );                     \
        } while ( 0 )

Grow big integer.

Parameters

source	Source big integer
dest	Destination big integer

Definition at line 209 of file bigint.h.

#define bigint_grow( source, dest ) do {                                \
        unsigned int source_size = bigint_size (source);                \
        unsigned int dest_size = bigint_size (dest);                    \
        bigint_grow_raw ( (source)->element, source_size,               \
                          (dest)->element, dest_size );                 \
        } while ( 0 )

Referenced by bigint_grow_sample(), bigint_mod_exp_raw(), ecdsa_init_values(), weierstrass_done_raw(), weierstrass_verify_raw(), and x25519_multiply().

bigint_shrink

#define bigint_shrink	(		source,
			dest )

Value:

        do {                            \
        unsigned int source_size = bigint_size (source);          \
        unsigned int dest_size = bigint_size (dest);                    \
        bigint_shrink_raw ( (source)->element, source_size,           \
                            (dest)->element, dest_size );           \
        } while ( 0 )

Shrink big integer.

Parameters

source	Source big integer
dest	Destination big integer

Definition at line 222 of file bigint.h.

#define bigint_shrink( source, dest ) do {                              \
        unsigned int source_size = bigint_size (source);                \
        unsigned int dest_size = bigint_size (dest);                    \
        bigint_shrink_raw ( (source)->element, source_size,             \
                            (dest)->element, dest_size );               \
        } while ( 0 )

Referenced by bigint_mod_exp_ladder(), and bigint_shrink_sample().

bigint_copy

#define bigint_copy	(		source,
			dest )

Value:

        do {                            \
        build_assert ( sizeof ( *(source) ) == sizeof ( *(dest) ) );        \
        bigint_shrink ( (source), (dest) );                         \
        } while ( 0 )

Copy big integer.

Parameters

source	Source big integer
dest	Destination big integer

Definition at line 235 of file bigint.h.

#define bigint_copy( source, dest ) do {                                \
        build_assert ( sizeof ( *(source) ) == sizeof ( *(dest) ) );    \
        bigint_shrink ( (source), (dest) );                             \
        } while ( 0 )

Referenced by bigint_copy_sample(), bigint_mod_exp_raw(), bigint_montgomery_relaxed_raw(), ecdsa_init_values(), ecdsa_invert(), weierstrass_done_raw(), weierstrass_exec(), weierstrass_init_curve(), weierstrass_init_raw(), weierstrass_multiply(), x25519_add(), x25519_init_constants(), x25519_invert(), x25519_ladder(), x25519_reduce_by(), and x25519_subtract().

bigint_swap

#define bigint_swap	(		first,
			second,
			swap )

Value:

        do {                            \
        unsigned int size = bigint_size (first);                    \
        bigint_swap_raw ( (first)->element, (second)->element, size,     \
                          (swap) );                                     \
        } while ( 0 )

Conditionally swap big integers (in constant time)

Parameters

first	Big integer to be conditionally swapped
second	Big integer to be conditionally swapped
swap	Swap first and second big integers

Definition at line 247 of file bigint.h.

#define bigint_swap( first, second, swap ) do {                         \
        unsigned int size = bigint_size (first);                        \
        bigint_swap_raw ( (first)->element, (second)->element, size,    \
                          (swap) );                                     \
        } while ( 0 )

Referenced by bigint_ladder_raw(), bigint_montgomery_raw(), bigint_swap_okx(), bigint_swap_sample(), x25519_reduce_by(), and x25519_step().

bigint_multiply

#define bigint_multiply	(		multiplicand,
			multiplier,
			result )

Value:

        do {    \
        unsigned int multiplicand_size = bigint_size (multiplicand); \
        unsigned int multiplier_size = bigint_size (multiplier);   \
        bigint_multiply_raw ( (multiplicand)->element,                   \
                              multiplicand_size, (multiplier)->element,        \
                              multiplier_size, (result)->element );        \
        } while ( 0 )

Multiply big integers.

Parameters

multiplicand	Big integer to be multiplied
multiplier	Big integer to be multiplied
result	Big integer to hold result

Definition at line 260 of file bigint.h.

#define bigint_multiply( multiplicand, multiplier, result ) do {        \
        unsigned int multiplicand_size = bigint_size (multiplicand);    \
        unsigned int multiplier_size = bigint_size (multiplier);        \
        bigint_multiply_raw ( (multiplicand)->element,                  \
                              multiplicand_size, (multiplier)->element, \
                              multiplier_size, (result)->element );     \
        } while ( 0 )

Referenced by bigint_mod_exp_ladder(), bigint_mod_exp_raw(), bigint_multiply_okx(), bigint_multiply_sample(), ecdsa_invert(), ecdsa_sign_rs(), ecdsa_verify_rs(), weierstrass_done_raw(), weierstrass_exec(), weierstrass_init_curve(), weierstrass_init_raw(), and x25519_multiply().

bigint_reduce

#define bigint_reduce	(		modulus,
			result )

Value:

        do {                            \
        unsigned int size = bigint_size (modulus);                       \
        bigint_reduce_raw ( (modulus)->element, (result)->element,  \
                            size );                                 \
        } while ( 0 )

Reduce big integer R^2 modulo N.

Parameters

modulus	Big integer modulus
result	Big integer to hold result

Definition at line 274 of file bigint.h.

#define bigint_reduce( modulus, result ) do {                           \
        unsigned int size = bigint_size (modulus);                      \
        bigint_reduce_raw ( (modulus)->element, (result)->element,      \
                            size );                                     \
        } while ( 0 )

Referenced by bigint_mod_exp_raw(), bigint_reduce_okx(), bigint_reduce_sample(), ecdsa_init_values(), and weierstrass_init_curve().

bigint_mod_invert

#define bigint_mod_invert	(		invertend,
			inverse )

Value:

        do {                    \
        unsigned int size = bigint_size ( inverse );                     \
        bigint_mod_invert_raw ( (invertend)->element,                    \
                                (inverse)->element, size );          \
        } while ( 0 )

Compute inverse of odd big integer modulo any power of two.

Parameters

invertend	Odd big integer to be inverted
inverse	Big integer to hold result

Definition at line 286 of file bigint.h.

#define bigint_mod_invert( invertend, inverse ) do {                    \
        unsigned int size = bigint_size ( inverse );                    \
        bigint_mod_invert_raw ( (invertend)->element,                   \
                                (inverse)->element, size );             \
        } while ( 0 )

Referenced by bigint_mod_exp_raw(), bigint_mod_invert_okx(), bigint_mod_invert_sample(), and bigint_montgomery_relaxed_raw().

bigint_montgomery_relaxed

#define bigint_montgomery_relaxed	(		modulus,
			value,
			result )

Value:

        ( {             \
        unsigned int size = bigint_size (modulus);                       \
        bigint_montgomery_relaxed_raw ( (modulus)->element,              \
                                        (value)->element,           \
                                        (result)->element, size );     \
        } )

Perform relaxed Montgomery reduction (REDC) of a big integer.

Parameters

modulus	Big integer odd modulus
value	Big integer to be reduced
result	Big integer to hold result

Return values

carry

Carry out

Definition at line 300 of file bigint.h.

#define bigint_montgomery_relaxed( modulus, value, result ) ( {         \
        unsigned int size = bigint_size (modulus);                      \
        bigint_montgomery_relaxed_raw ( (modulus)->element,             \
                                        (value)->element,               \
                                        (result)->element, size );      \
        } )

Referenced by bigint_mod_exp_raw(), bigint_montgomery_raw(), weierstrass_done_raw(), weierstrass_exec(), and weierstrass_init_raw().

bigint_montgomery

#define bigint_montgomery	(		modulus,
			value,
			result )

Value:

        do {            \
        unsigned int size = bigint_size (modulus);                       \
        bigint_montgomery_raw ( (modulus)->element, (value)->element,        \
                                (result)->element, size );             \
        } while ( 0 )

Perform classic Montgomery reduction (REDC) of a big integer.

Parameters

modulus	Big integer odd modulus
value	Big integer to be reduced
result	Big integer to hold result

Definition at line 314 of file bigint.h.

#define bigint_montgomery( modulus, value, result ) do {                \
        unsigned int size = bigint_size (modulus);                      \
        bigint_montgomery_raw ( (modulus)->element, (value)->element,   \
                                (result)->element, size );              \
        } while ( 0 )

Referenced by bigint_mod_exp_ladder(), bigint_mod_exp_raw(), bigint_montgomery_okx(), bigint_montgomery_sample(), ecdsa_init_values(), ecdsa_invert(), ecdsa_sign_rs(), ecdsa_verify_rs(), weierstrass_done_raw(), weierstrass_init_curve(), and weierstrass_verify_raw().

bigint_ladder

#define bigint_ladder	(		result,
			multiple,
			exponent,
			op,
			ctx,
			tmp )

Value:

        do {    \
        unsigned int size = bigint_size (result);                  \
        unsigned int exponent_size = bigint_size (exponent);         \
        bigint_ladder_raw ( (result)->element, (multiple)->element, \
                            size, (exponent)->element, exponent_size,        \
                            (op), (ctx), (tmp) );                       \
        } while ( 0 )

Perform generalised exponentiation via a Montgomery ladder.

Parameters

result	Big integer result (initialised to identity element)
multiple	Big integer multiple (initialised to generator)
exponent	Big integer exponent
op	Montgomery ladder commutative operation
ctx	Operation context (if needed)
tmp	Temporary working space (if needed)

Definition at line 330 of file bigint.h.

#define bigint_ladder( result, multiple, exponent, op, ctx, tmp ) do {  \
        unsigned int size = bigint_size (result);                       \
        unsigned int exponent_size = bigint_size (exponent);            \
        bigint_ladder_raw ( (result)->element, (multiple)->element,     \
                            size, (exponent)->element, exponent_size,   \
                            (op), (ctx), (tmp) );                       \
        } while ( 0 )

Referenced by bigint_mod_exp_raw(), ecdsa_invert(), weierstrass_done_raw(), and weierstrass_multiply().

bigint_mod_exp

#define bigint_mod_exp	(		base,
			modulus,
			exponent,
			result,
			tmp )

Value:

        do {    \
        unsigned int size = bigint_size (base);                              \
        unsigned int exponent_size = bigint_size (exponent);         \
        bigint_mod_exp_raw ( (base)->element, (modulus)->element,     \
                             (exponent)->element, (result)->element,        \
                             size, exponent_size, tmp );         \
        } while ( 0 )

Perform modular exponentiation of big integers.

Parameters

base	Big integer base
modulus	Big integer modulus
exponent	Big integer exponent
result	Big integer to hold result
tmp	Temporary working space

Definition at line 347 of file bigint.h.

#define bigint_mod_exp( base, modulus, exponent, result, tmp ) do {     \
        unsigned int size = bigint_size (base);                         \
        unsigned int exponent_size = bigint_size (exponent);            \
        bigint_mod_exp_raw ( (base)->element, (modulus)->element,       \
                             (exponent)->element, (result)->element,    \
                             size, exponent_size, tmp );                \
        } while ( 0 )

Referenced by bigint_mod_exp_okx(), bigint_mod_exp_sample(), dhe_key(), and rsa_cipher().

bigint_mod_exp_tmp_len

#define bigint_mod_exp_tmp_len

(

modulus

)

Value:

        ( {                             \
        unsigned int size = bigint_size (modulus);                       \
        sizeof ( struct {                                               \
                bigint_t ( size ) temp[4];                          \
        } ); } )

Calculate temporary working space required for moduluar exponentiation.

Parameters

modulus

Big integer modulus

Return values

len	Length of temporary working space

Definition at line 361 of file bigint.h.

#define bigint_mod_exp_tmp_len( modulus ) ( {                           \
        unsigned int size = bigint_size (modulus);                      \
        sizeof ( struct {                                               \
                bigint_t ( size ) temp[4];                              \
        } ); } )

Referenced by bigint_mod_exp_okx(), bigint_mod_exp_raw(), dhe_key(), and rsa_alloc().

Typedef Documentation

bigint_ladder_op_t

typedef void bigint_ladder_op_t(const bigint_element_t *operand0, bigint_element_t *result0, unsigned int size, const void *ctx, void *tmp)

A big integer Montgomery ladder commutative operation.

Parameters

operand	Element 0 of first input operand (may overlap result)
result	Element 0 of second input operand and result
size	Number of elements in operands and result
ctx	Operation context (if needed)
tmp	Temporary working space (if needed)

Definition at line 378 of file bigint.h.

Function Documentation

FILE_LICENCE()

FILE_LICENCE

(

GPL2_OR_LATER_OR_UBDL

)

FILE_SECBOOT()

FILE_SECBOOT

(

PERMITTED

)

__attribute__()

__attribute__ ( (always_inline) )

inlinestatic

Set bit in big integer.

Test if most significant bit is set in big integer.

Test if bit is set in big integer.

Clear bit in big integer.

Parameters

value0	Element 0 of big integer
size	Number of elements
bit	Bit to set
value0	Element 0 of big integer
size	Number of elements
bit	Bit to clear
value0	Element 0 of big integer
size	Number of elements
bit	Bit to test

Return values

is_set

Bit is set

Parameters

value0	Element 0 of big integer
size	Number of elements

Return values

is_set

Most significant bit is set

return()

return

(

!!

value->element[index] &(1UL<< subindex)

)

References index, subindex, and value.

bigint_ntoa_raw()

const char * bigint_ntoa_raw	(	const bigint_element_t *	value0,
		unsigned int	size )

Transcribe big integer (for debugging)

Parameters

value0	Element 0 of big integer to be transcribed
size	Number of elements

Return values

string

Big integer in string form (may be abbreviated)

Definition at line 48 of file bigint.c.

                                                   {
        const bigint_t ( size ) __attribute__ (( may_alias ))
                *value = ( ( const void * ) value0 );
        bigint_element_t element;
        static char buf[256];
        unsigned int count;
        int threshold;
        uint8_t byte;
        char *tmp;
        int i;
 
        /* Calculate abbreviation threshold, if any */
        count = ( size * sizeof ( element ) );
        threshold = count;
        if ( count >= ( ( sizeof ( buf ) - 1 /* NUL */ ) / 2 /* "xx" */ ) ) {
                threshold -= ( ( sizeof ( buf ) - 3 /* "..." */
                                 - ( BIGINT_NTOA_LSB_MIN * 2 /* "xx" */ )
                                 - 1 /* NUL */ ) / 2 /* "xx" */ );
        }
 
        /* Transcribe bytes, abbreviating with "..." if necessary */
        for ( tmp = buf, i = ( count - 1 ) ; i >= 0 ; i-- ) {
                element = value->element[ i / sizeof ( element ) ];
                byte = ( element >> ( 8 * ( i % sizeof ( element ) ) ) );
                tmp += sprintf ( tmp, "%02x", byte );
                if ( i == threshold ) {
                        tmp += sprintf ( tmp, "..." );
                        i = BIGINT_NTOA_LSB_MIN;
                }
        }
        assert ( tmp < ( buf + sizeof ( buf ) ) );
 
        return buf;
}

References __attribute__, assert, BIGINT_NTOA_LSB_MIN, bigint_t, count, element, size, sprintf, tmp, value, and value0.

bigint_init_raw()

void bigint_init_raw	(	bigint_element_t *	value0,
		unsigned int	size,
		const void *	data,
		size_t	len )

References data, len, size, and value0.

bigint_done_raw()

void bigint_done_raw	(	const bigint_element_t *	value0,
		unsigned int	size,
		void *	out,
		size_t	len )

References len, out, size, and value0.

bigint_add_raw()

int bigint_add_raw	(	const bigint_element_t *	addend0,
		bigint_element_t *	value0,
		unsigned int	size )

References size, and value0.

bigint_subtract_raw()

int bigint_subtract_raw	(	const bigint_element_t *	subtrahend0,
		bigint_element_t *	value0,
		unsigned int	size )

References size, and value0.

bigint_shl_raw()

int bigint_shl_raw	(	bigint_element_t *	value0,
		unsigned int	size )

References size, and value0.

bigint_shr_raw()

int bigint_shr_raw	(	bigint_element_t *	value0,
		unsigned int	size )

References size, and value0.

bigint_is_zero_raw()

int bigint_is_zero_raw	(	const bigint_element_t *	value0,
		unsigned int	size )

References size, and value0.

bigint_is_geq_raw()

int bigint_is_geq_raw	(	const bigint_element_t *	value0,
		const bigint_element_t *	reference0,
		unsigned int	size )

References reference0, size, and value0.

bigint_bit_is_set_raw()

int bigint_bit_is_set_raw	(	const bigint_element_t *	value0,
		unsigned int	size,
		unsigned int	bit )

References bit, size, and value0.

bigint_max_set_bit_raw()

int bigint_max_set_bit_raw	(	const bigint_element_t *	value0,
		unsigned int	size )

References size, and value0.

bigint_grow_raw()

void bigint_grow_raw	(	const bigint_element_t *	source0,
		unsigned int	source_size,
		bigint_element_t *	dest0,
		unsigned int	dest_size )

References dest0, dest_size, and source_size.

bigint_shrink_raw()

void bigint_shrink_raw	(	const bigint_element_t *	source0,
		unsigned int	source_size,
		bigint_element_t *	dest0,
		unsigned int	dest_size )

References dest0, dest_size, size, and source_size.

bigint_swap_raw()

void bigint_swap_raw	(	bigint_element_t *	first0,
		bigint_element_t *	second0,
		unsigned int	size,
		int	swap )

Conditionally swap big integers (in constant time)

Parameters

first0	Element 0 of big integer to be conditionally swapped
second0	Element 0 of big integer to be conditionally swapped
size	Number of elements in big integers
swap	Swap first and second big integers

Definition at line 92 of file bigint.c.

                                                     {
        bigint_element_t mask;
        bigint_element_t xor;
        unsigned int i;
 
        /* Construct mask */
        mask = ( ( bigint_element_t ) ( ! swap ) - 1 );
 
        /* Conditionally swap elements */
        for ( i = 0 ; i < size ; i++ ) {
                xor = ( mask & ( first0[i] ^ second0[i] ) );
                first0[i] ^= xor;
                second0[i] ^= xor;
        }
}

References size, and xor().

bigint_multiply_one()

void bigint_multiply_one	(	const bigint_element_t	multiplicand,
		const bigint_element_t	multiplier,
		bigint_element_t *	result,
		bigint_element_t *	carry )

References carry, ctx, multiplier, op, result, size, tmp, and value0.

Referenced by bigint_montgomery_relaxed_raw(), and bigint_multiply_raw().

bigint_multiply_raw()

void bigint_multiply_raw	(	const bigint_element_t *	multiplicand0,
		unsigned int	multiplicand_size,
		const bigint_element_t *	multiplier0,
		unsigned int	multiplier_size,
		bigint_element_t *	result0 )

Multiply big integers.

Parameters

multiplicand0	Element 0 of big integer to be multiplied
multiplicand_size	Number of elements in multiplicand
multiplier0	Element 0 of big integer to be multiplied
multiplier_size	Number of elements in multiplier
result0	Element 0 of big integer to hold result

Definition at line 118 of file bigint.c.

                                                       {
        unsigned int result_size = ( multiplicand_size + multiplier_size );
        const bigint_t ( multiplicand_size ) __attribute__ (( may_alias ))
                *multiplicand = ( ( const void * ) multiplicand0 );
        const bigint_t ( multiplier_size ) __attribute__ (( may_alias ))
                *multiplier = ( ( const void * ) multiplier0 );
        bigint_t ( result_size ) __attribute__ (( may_alias ))
                *result = ( ( void * ) result0 );
        bigint_element_t multiplicand_element;
        const bigint_element_t *multiplier_element;
        bigint_element_t *result_element;
        bigint_element_t carry_element;
        unsigned int i;
        unsigned int j;
 
        /* Zero required portion of result
         *
         * All elements beyond the length of the multiplier will be
         * written before they are read, and so do not need to be
         * zeroed in advance.
         */
        memset ( result, 0, sizeof ( *multiplier ) );
 
        /* Multiply integers one element at a time, adding the low
         * half of the double-element product directly into the
         * result, and maintaining a running single-element carry.
         *
         * The running carry can never overflow beyond a single
         * element.  At each step, the calculation we perform is:
         *
         *   carry:result[i+j] := ( ( multiplicand[i] * multiplier[j] )
         *                          + result[i+j] + carry )
         *
         * The maximum value (for n-bit elements) is therefore:
         *
         *   (2^n - 1)*(2^n - 1) + (2^n - 1) + (2^n - 1) = 2^(2n) - 1
         *
         * This is precisely the maximum value for a 2n-bit integer,
         * and so the carry out remains within the range of an n-bit
         * integer, i.e. a single element.
         */
        for ( i = 0 ; i < multiplicand_size ; i++ ) {
                multiplicand_element = multiplicand->element[i];
                multiplier_element = &multiplier->element[0];
                result_element = &result->element[i];
                carry_element = 0;
                for ( j = 0 ; j < multiplier_size ; j++ ) {
                        bigint_multiply_one ( multiplicand_element,
                                              *(multiplier_element++),
                                              result_element++,
                                              &carry_element );
                }
                *result_element = carry_element;
        }
}

References __attribute__, bigint_multiply_one(), bigint_t, memset(), multiplier, and result.

bigint_reduce_raw()

void bigint_reduce_raw	(	const bigint_element_t *	modulus0,
		bigint_element_t *	result0,
		unsigned int	size )

Reduce big integer R^2 modulo N.

Parameters

modulus0	Element 0 of big integer modulus
result0	Element 0 of big integer to hold result
size	Number of elements in modulus and result

Reduce the value R^2 modulo N, where R=2^n and n is the number of bits in the representation of the modulus N, including any leading zero bits.

Definition at line 189 of file bigint.c.

                                                                        {
        const bigint_t ( size ) __attribute__ (( may_alias ))
                *modulus = ( ( const void * ) modulus0 );
        bigint_t ( size ) __attribute__ (( may_alias ))
                *result = ( ( void * ) result0 );
        const unsigned int width = ( 8 * sizeof ( bigint_element_t ) );
        unsigned int shift;
        int max;
        int sign;
        int msb;
        int carry;
 
        /* We have the constants:
         *
         *    N = modulus
         *
         *    n = number of bits in the modulus (including any leading zeros)
         *
         *    R = 2^n
         *
         * Let r be the extension of the n-bit result register by a
         * separate two's complement sign bit, such that -R <= r < R,
         * and define:
         *
         *    x = r * 2^k
         *
         * as the value being reduced modulo N, where k is a
         * non-negative integer bit shift.
         *
         * We want to reduce the initial value R^2=2^(2n), which we
         * may trivially represent using r=1 and k=2n.
         *
         * We then iterate over decrementing k, maintaining the loop
         * invariant:
         *
         *    -N <= r < N
         *
         * On each iteration we must first double r, to compensate for
         * having decremented k:
         *
         *    k' = k - 1
         *
         *    r' = 2r
         *
         *    x = r * 2^k = 2r * 2^(k-1) = r' * 2^k'
         *
         * Note that doubling the n-bit result register will create a
         * value of n+1 bits: this extra bit needs to be handled
         * separately during the calculation.
         *
         * We then subtract N (if r is currently non-negative) or add
         * N (if r is currently negative) to restore the loop
         * invariant:
         *
         *      0 <= r < N    =>   r" = 2r - N    =>   -N <= r" < N
         *     -N <= r < 0    =>   r" = 2r + N    =>   -N <= r" < N
         *
         * Note that since N may use all n bits, the most significant
         * bit of the n-bit result register is not a valid two's
         * complement sign bit for r: the extra sign bit therefore
         * also needs to be handled separately.
         *
         * Once we reach k=0, we have x=r and therefore:
         *
         *    -N <= x < N
         *
         * After this last loop iteration (with k=0), we may need to
         * add a single multiple of N to ensure that x is positive,
         * i.e. lies within the range 0 <= x < N.
         *
         * Since neither the modulus nor the value R^2 are secret, we
         * may elide approximately half of the total number of
         * iterations by constructing the initial representation of
         * R^2 as r=2^m and k=2n-m (for some m such that 2^m < N).
         */
 
        /* Initialise x=R^2 */
        memset ( result, 0, sizeof ( *result ) );
        max = ( bigint_max_set_bit ( modulus ) - 2 );
        if ( max < 0 ) {
                /* Degenerate case of N=0 or N=1: return a zero result */
                return;
        }
        bigint_set_bit ( result, max );
        shift = ( ( 2 * size * width ) - max );
        sign = 0;
 
        /* Iterate as described above */
        while ( shift-- ) {
 
                /* Calculate 2r, storing extra bit separately */
                msb = bigint_shl ( result );
 
                /* Add or subtract N according to current sign */
                if ( sign ) {
                        carry = bigint_add ( modulus, result );
                } else {
                        carry = bigint_subtract ( modulus, result );
                }
 
                /* Calculate new sign of result
                 *
                 * We know the result lies in the range -N <= r < N
                 * and so the tuple (old sign, msb, carry) cannot ever
                 * take the values (0, 1, 0) or (1, 0, 0).  We can
                 * therefore treat these as don't-care inputs, which
                 * allows us to simplify the boolean expression by
                 * ignoring the old sign completely.
                 */
                assert ( ( sign == msb ) || carry );
                sign = ( msb ^ carry );
        }
 
        /* Add N to make result positive if necessary */
        if ( sign )
                bigint_add ( modulus, result );
 
        /* Sanity check */
        assert ( ! bigint_is_geq ( result, modulus ) );
}

References __attribute__, assert, bigint_add, bigint_is_geq, bigint_max_set_bit, bigint_set_bit, bigint_shl, bigint_subtract, bigint_t, carry, max, memset(), result, and size.

bigint_mod_invert_raw()

void bigint_mod_invert_raw	(	const bigint_element_t *	invertend0,
		bigint_element_t *	inverse0,
		unsigned int	size )

Compute inverse of odd big integer modulo any power of two.

Parameters

invertend0	Element 0 of odd big integer to be inverted
inverse0	Element 0 of big integer to hold result
size	Number of elements in invertend and result

Definition at line 318 of file bigint.c.

                                                                             {
        const bigint_t ( size ) __attribute__ (( may_alias ))
                *invertend = ( ( const void * ) invertend0 );
        bigint_t ( size ) __attribute__ (( may_alias ))
                *inverse = ( ( void * ) inverse0 );
        bigint_element_t accum;
        bigint_element_t bit;
        unsigned int i;
 
        /* Sanity check */
        assert ( bigint_bit_is_set ( invertend, 0 ) );
 
        /* Initialise output */
        memset ( inverse, 0xff, sizeof ( *inverse ) );
 
        /* Compute inverse modulo 2^(width)
         *
         * This method is a lightly modified version of the pseudocode
         * presented in "A New Algorithm for Inversion mod p^k (Koç,
         * 2017)".
         *
         * Each inner loop iteration calculates one bit of the
         * inverse.  The residue value is the two's complement
         * negation of the value "b" as used by Koç, to allow for
         * division by two using a logical right shift (since we have
         * no arithmetic right shift operation for big integers).
         *
         * The residue is stored in the as-yet uncalculated portion of
         * the inverse.  The size of the residue therefore decreases
         * by one element for each outer loop iteration.  Trivial
         * inspection of the algorithm shows that any higher bits
         * could not contribute to the eventual output value, and so
         * we may safely reuse storage this way.
         *
         * Due to the suffix property of inverses mod 2^k, the result
         * represents the least significant bits of the inverse modulo
         * an arbitrarily large 2^k.
         */
        for ( i = size ; i > 0 ; i-- ) {
                const bigint_t ( i ) __attribute__ (( may_alias ))
                        *addend = ( ( const void * ) invertend );
                bigint_t ( i ) __attribute__ (( may_alias ))
                        *residue = ( ( void * ) inverse );
 
                /* Calculate one element's worth of inverse bits */
                for ( accum = 0, bit = 1 ; bit ; bit <<= 1 ) {
                        if ( bigint_bit_is_set ( residue, 0 ) ) {
                                accum |= bit;
                                bigint_add ( addend, residue );
                        }
                        bigint_shr ( residue );
                }
 
                /* Store in the element no longer required to hold residue */
                inverse->element[ i - 1 ] = accum;
        }
 
        /* Correct order of inverse elements */
        for ( i = 0 ; i < ( size / 2 ) ; i++ ) {
                accum = inverse->element[i];
                inverse->element[i] = inverse->element[ size - 1 - i ];
                inverse->element[ size - 1 - i ] = accum;
        }
}

References __attribute__, assert, bigint_add, bigint_bit_is_set, bigint_shr, bigint_t, bit, memset(), and size.

bigint_montgomery_relaxed_raw()

int bigint_montgomery_relaxed_raw	(	const bigint_element_t *	modulus0,
		bigint_element_t *	value0,
		bigint_element_t *	result0,
		unsigned int	size )

Perform relaxed Montgomery reduction (REDC) of a big integer.

Parameters

modulus0	Element 0 of big integer odd modulus
value0	Element 0 of big integer to be reduced
result0	Element 0 of big integer to hold result
size	Number of elements in modulus and result

Return values

carry

Carry out

The value to be reduced will be made divisible by the size of the modulus while retaining its residue class (i.e. multiples of the modulus will be added until the low half of the value is zero).

The result may be expressed as

tR = x + mN

where x is the input value, N is the modulus, R=2^n (where n is the number of bits in the representation of the modulus, including any leading zero bits), and m is the number of multiples of the modulus added to make the result tR divisible by R.

The maximum addend is mN <= (R-1)*N (and such an m can be proven to exist since N is limited to being odd and therefore coprime to R).

Since the result of this addition is one bit larger than the input value, a carry out bit is also returned. The caller may be able to prove that the carry out is always zero, in which case it may be safely ignored.

The upper half of the output value (i.e. t) will also be copied to the result pointer. It is permissible for the result pointer to overlap the lower half of the input value.

External knowledge of constraints on the modulus and the input value may be used to prove constraints on the result. The constraint on the modulus may be generally expressed as

R > kN

for some positive integer k. The value k=1 is allowed, and simply expresses that the modulus fits within the number of bits in its own representation.

For classic Montgomery reduction, we have k=1, i.e. R > N and a separate constraint that the input value is in the range x < RN. This gives the result constraint

tR < RN + (R-1)N < 2RN - N < 2RN t < 2N

A single subtraction of the modulus may therefore be required to bring it into the range t < N.

When the input value is known to be a product of two integers A and B, with A < aN and B < bN, we get the result constraint

tR < abN^2 + (R-1)N < (ab/k)RN + RN - N < (1 + ab/k)RN t < (1 + ab/k)N

If we have k=a=b=1, i.e. R > N with A < N and B < N, then the result is in the range t < 2N and may require a single subtraction of the modulus to bring it into the range t < N so that it may be used as an input on a subsequent iteration.

If we have k=4 and a=b=2, i.e. R > 4N with A < 2N and B < 2N, then the result is in the range t < 2N and may immediately be used as an input on a subsequent iteration, without requiring a subtraction.

Larger values of k may be used to allow for larger values of a and b, which can be useful to elide intermediate reductions in a calculation chain that involves additions and subtractions between multiplications (as used in elliptic curve point addition, for example). As a general rule: each intermediate addition or subtraction will require k to be doubled.

When the input value is known to be a single integer A, with A < aN (as used when converting out of Montgomery form), we get the result constraint

tR < aN + (R-1)N < RN + (a-1)N

If we have a=1, i.e. A < N, then the constraint becomes

tR < RN t < N

and so the result is immediately in the range t < N with no subtraction of the modulus required.

For any larger value of a, the result value t=N becomes possible. Additional external knowledge may potentially be used to prove that t=N cannot occur. For example: if the caller is performing modular exponentiation with a prime modulus (or, more generally, a modulus that is coprime to the base), then there is no way for a non-zero base value to end up producing an exact multiple of the modulus. If t=N cannot be disproved, then conversion out of Montgomery form may require an additional subtraction of the modulus.

Definition at line 488 of file bigint.c.

                                                        {
        const bigint_t ( size ) __attribute__ (( may_alias ))
                *modulus = ( ( const void * ) modulus0 );
        union {
                bigint_t ( size * 2 ) full;
                struct {
                        bigint_t ( size ) low;
                        bigint_t ( size ) high;
                } __attribute__ (( packed ));
        } __attribute__ (( may_alias )) *value = ( ( void * ) value0 );
        bigint_t ( size ) __attribute__ (( may_alias ))
                *result = ( ( void * ) result0 );
        static bigint_t ( 1 ) cached;
        static bigint_t ( 1 ) negmodinv;
        bigint_element_t multiple;
        bigint_element_t carry;
        unsigned int i;
        unsigned int j;
        int overflow;
 
        /* Sanity checks */
        assert ( bigint_bit_is_set ( modulus, 0 ) );
 
        /* Calculate inverse (or use cached version) */
        if ( cached.element[0] != modulus->element[0] ) {
                bigint_mod_invert ( modulus, &negmodinv );
                negmodinv.element[0] = -negmodinv.element[0];
                cached.element[0] = modulus->element[0];
        }
 
        /* Perform multiprecision Montgomery reduction */
        for ( i = 0 ; i < size ; i++ ) {
 
                /* Determine scalar multiple for this round */
                multiple = ( value->low.element[i] * negmodinv.element[0] );
 
                /* Multiply value to make it divisible by 2^(width*i) */
                carry = 0;
                for ( j = 0 ; j < size ; j++ ) {
                        bigint_multiply_one ( multiple, modulus->element[j],
                                              &value->full.element[ i + j ],
                                              &carry );
                }
 
                /* Since value is now divisible by 2^(width*i), we
                 * know that the current low element must have been
                 * zeroed.
                 */
                assert ( value->low.element[i] == 0 );
 
                /* Store the multiplication carry out in the result,
                 * avoiding the need to immediately propagate the
                 * carry through the remaining elements.
                 */
                result->element[i] = carry;
        }
 
        /* Add the accumulated carries */
        overflow = bigint_add ( result, &value->high );
 
        /* Copy to result buffer */
        bigint_copy ( &value->high, result );
 
        return overflow;
}

References __attribute__, assert, bigint_add, bigint_bit_is_set, bigint_copy, bigint_mod_invert, bigint_multiply_one(), bigint_t, carry, high, low, result, size, value, and value0.

bigint_montgomery_raw()

void bigint_montgomery_raw	(	const bigint_element_t *	modulus0,
		bigint_element_t *	value0,
		bigint_element_t *	result0,
		unsigned int	size )

Perform classic Montgomery reduction (REDC) of a big integer.

Parameters

modulus0	Element 0 of big integer odd modulus
value0	Element 0 of big integer to be reduced
result0	Element 0 of big integer to hold result
size	Number of elements in modulus and result

Definition at line 565 of file bigint.c.

                                                 {
        const bigint_t ( size ) __attribute__ (( may_alias ))
                *modulus = ( ( const void * ) modulus0 );
        union {
                bigint_t ( size * 2 ) full;
                struct {
                        bigint_t ( size ) low;
                        bigint_t ( size ) high;
                } __attribute__ (( packed ));
        } __attribute__ (( may_alias )) *value = ( ( void * ) value0 );
        bigint_t ( size ) __attribute__ (( may_alias ))
                *result = ( ( void * ) result0 );
        int overflow;
        int underflow;
 
        /* Sanity check */
        assert ( ! bigint_is_geq ( &value->high, modulus ) );
 
        /* Perform relaxed Montgomery reduction */
        overflow = bigint_montgomery_relaxed ( modulus, &value->full, result );
 
        /* Conditionally subtract the modulus once */
        underflow = bigint_subtract ( modulus, result );
        bigint_swap ( result, &value->high, ( underflow & ~overflow ) );
 
        /* Sanity check */
        assert ( ! bigint_is_geq ( result, modulus ) );
}

References __attribute__, assert, bigint_is_geq, bigint_montgomery_relaxed, bigint_subtract, bigint_swap, bigint_t, high, low, result, size, value, and value0.

bigint_ladder_raw()

void bigint_ladder_raw	(	bigint_element_t *	result0,
		bigint_element_t *	multiple0,
		unsigned int	size,
		const bigint_element_t *	exponent0,
		unsigned int	exponent_size,
		bigint_ladder_op_t *	op,
		const void *	ctx,
		void *	tmp )

Perform generalised exponentiation via a Montgomery ladder.

Parameters

result0	Element 0 of result (initialised to identity element)
multiple0	Element 0 of multiple (initialised to generator)
size	Number of elements in result and multiple
exponent0	Element 0 of exponent
exponent_size	Number of elements in exponent
op	Montgomery ladder commutative operation
ctx	Operation context (if needed)
tmp	Temporary working space (if needed)

The Montgomery ladder may be used to perform any operation that is isomorphic to exponentiation, i.e. to compute the result

r = g^e = g * g * g * g * .... * g

for an arbitrary commutative operation "*", generator "g" and exponent "e".

The result "r" is computed in constant time (assuming that the underlying operation is constant time) in k steps, where k is the number of bits in the big integer representation of the exponent.

The result "r" must be initialised to the operation's identity element, and the multiple must be initialised to the generator "g". On exit, the multiple will contain

m = r * g = g^(e+1)

Note that the terminology used here refers to exponentiation defined as repeated multiplication, but that the ladder may equally well be used to perform any isomorphic operation (such as multiplication defined as repeated addition).

Definition at line 632 of file bigint.c.

                                                      {
        bigint_t ( size ) __attribute__ (( may_alias ))
                *result = ( ( void * ) result0 );
        bigint_t ( size ) __attribute__ (( may_alias ))
                *multiple = ( ( void * ) multiple0 );
        const bigint_t ( exponent_size ) __attribute__ (( may_alias ))
                *exponent = ( ( const void * ) exponent0 );
        const unsigned int width = ( 8 * sizeof ( bigint_element_t ) );
        unsigned int bit = ( exponent_size * width );
        int toggle = 0;
        int previous;
 
        /* We have two physical storage locations: Rres (the "result"
         * register) and Rmul (the "multiple" register).
         *
         * On entry we have:
         *
         *   Rres = g^0 = 1  (the identity element)
         *   Rmul = g        (the generator)
         *
         * For calculation purposes, define two virtual registers R[0]
         * and R[1], mapped to the underlying physical storage
         * locations via a boolean toggle state "t":
         *
         *   R[t]  -> Rres
         *   R[~t] -> Rmul
         *
         * Define the initial toggle state to be t=0, so that we have:
         *
         *   R[0] = g^0 = 1  (the identity element)
         *   R[1] = g        (the generator)
         *
         * The Montgomery ladder then iterates over each bit "b" of
         * the exponent "e" (from MSB down to LSB), computing:
         *
         *   R[1]  := R[0] * R[1],    R[0]  := R[0] * R[0]    (if b=0)
         *   R[0]  := R[1] * R[0],    R[1]  := R[1] * R[1]    (if b=1)
         *
         * i.e.
         *
         *   R[~b] := R[b] * R[~b],   R[b]  := R[b] * R[b]
         *
         * To avoid data-dependent memory access patterns, we
         * implement this as:
         *
         *   Rmul := Rres * Rmul
         *   Rres := Rres * Rres
         *
         * and update the toggle state "t" (via constant-time
         * conditional swaps) as needed to ensure that R[b] always
         * maps to Rres and R[~b] always maps to Rmul.
         */
        while ( bit-- ) {
 
                /* Update toggle state t := b
                 *
                 * If the new toggle state is not equal to the old
                 * toggle state, then we must swap R[0] and R[1] (in
                 * constant time).
                 */
                previous = toggle;
                toggle = bigint_bit_is_set ( exponent, bit );
                bigint_swap ( result, multiple, ( toggle ^ previous ) );
 
                /* Calculate Rmul = R[~b] := R[b] * R[~b] = Rres * Rmul */
                op ( result->element, multiple->element, size, ctx, tmp );
 
                /* Calculate Rres = R[b]  := R[b] * R[b]  = Rres * Rres */
                op ( result->element, result->element, size, ctx, tmp );
        }
 
        /* Reset toggle state to zero */
        bigint_swap ( result, multiple, toggle );
}

References __attribute__, bigint_bit_is_set, bigint_swap, bigint_t, bit, ctx, op, result, size, and tmp.

bigint_mod_exp_ladder()

void bigint_mod_exp_ladder	(	const bigint_element_t *	multiplier0,
		bigint_element_t *	result0,
		unsigned int	size,
		const void *	ctx,
		void *	tmp )

Perform modular multiplication as part of a Montgomery ladder.

Parameters

operand	Element 0 of first input operand (may overlap result)
result	Element 0 of second input operand and result
size	Number of elements in operands and result
ctx	Operation context (odd modulus, or NULL)
tmp	Temporary working space

Definition at line 720 of file bigint.c.

                                                          {
        const bigint_t ( size ) __attribute__ (( may_alias ))
                *multiplier = ( ( const void * ) multiplier0 );
        bigint_t ( size ) __attribute__ (( may_alias ))
                *result = ( ( void * ) result0 );
        const bigint_t ( size ) __attribute__ (( may_alias ))
                *modulus = ( ( const void * ) ctx );
        bigint_t ( size * 2 ) __attribute__ (( may_alias ))
                *product = ( ( void * ) tmp );
 
        /* Multiply and reduce */
        bigint_multiply ( result, multiplier, product );
        if ( modulus ) {
                bigint_montgomery ( modulus, product, result );
        } else {
                bigint_shrink ( product, result );
        }
}

References __attribute__, bigint_montgomery, bigint_multiply, bigint_shrink, bigint_t, ctx, multiplier, product, result, size, and tmp.

Referenced by bigint_mod_exp_raw(), ecdsa_invert(), and weierstrass_done_raw().

bigint_mod_exp_raw()

void bigint_mod_exp_raw	(	const bigint_element_t *	base0,
		const bigint_element_t *	modulus0,
		const bigint_element_t *	exponent0,
		bigint_element_t *	result0,
		unsigned int	size,
		unsigned int	exponent_size,
		void *	tmp )

Perform modular exponentiation of big integers.

Parameters

base0	Element 0 of big integer base
modulus0	Element 0 of big integer modulus
exponent0	Element 0 of big integer exponent
result0	Element 0 of big integer to hold result
size	Number of elements in base, modulus, and result
exponent_size	Number of elements in exponent
tmp	Temporary working space

Definition at line 752 of file bigint.c.

                                      {
        const bigint_t ( size ) __attribute__ (( may_alias )) *base =
                ( ( const void * ) base0 );
        const bigint_t ( size ) __attribute__ (( may_alias )) *modulus =
                ( ( const void * ) modulus0 );
        const bigint_t ( exponent_size ) __attribute__ (( may_alias ))
                *exponent = ( ( const void * ) exponent0 );
        bigint_t ( size ) __attribute__ (( may_alias )) *result =
                ( ( void * ) result0 );
        const unsigned int width = ( 8 * sizeof ( bigint_element_t ) );
        struct {
                struct {
                        bigint_t ( size ) modulus;
                        bigint_t ( size ) stash;
                };
                union {
                        bigint_t ( 2 * size ) full;
                        bigint_t ( size ) low;
                } product;
        } *temp = tmp;
        const uint8_t one[1] = { 1 };
        bigint_element_t submask;
        unsigned int subsize;
        unsigned int scale;
        unsigned int i;
 
        /* Sanity check */
        assert ( sizeof ( *temp ) == bigint_mod_exp_tmp_len ( modulus ) );
 
        /* Handle degenerate case of zero modulus */
        if ( ! bigint_max_set_bit ( modulus ) ) {
                memset ( result, 0, sizeof ( *result ) );
                return;
        }
 
        /* Factor modulus as (N * 2^scale) where N is odd */
        bigint_copy ( modulus, &temp->modulus );
        for ( scale = 0 ; ( ! bigint_bit_is_set ( &temp->modulus, 0 ) ) ;
              scale++ ) {
                bigint_shr ( &temp->modulus );
        }
        subsize = ( ( scale + width - 1 ) / width );
        submask = ( ( 1UL << ( scale % width ) ) - 1 );
        if ( ! submask )
                submask = ~submask;
 
        /* Calculate (R^2 mod N) */
        bigint_reduce ( &temp->modulus, &temp->stash );
 
        /* Initialise result = Montgomery(1, R^2 mod N) */
        bigint_grow ( &temp->stash, &temp->product.full );
        bigint_montgomery ( &temp->modulus, &temp->product.full, result );
 
        /* Convert base into Montgomery form */
        bigint_multiply ( base, &temp->stash, &temp->product.full );
        bigint_montgomery ( &temp->modulus, &temp->product.full,
                            &temp->stash );
 
        /* Calculate x1 = base^exponent modulo N */
        bigint_ladder ( result, &temp->stash, exponent, bigint_mod_exp_ladder,
                        &temp->modulus, &temp->product );
 
        /* Convert back out of Montgomery form */
        bigint_grow ( result, &temp->product.full );
        bigint_montgomery_relaxed ( &temp->modulus, &temp->product.full,
                                    result );
 
        /* Handle even moduli via Garner's algorithm */
        if ( subsize ) {
                const bigint_t ( subsize ) __attribute__ (( may_alias ))
                        *subbase = ( ( const void * ) base );
                bigint_t ( subsize ) __attribute__ (( may_alias ))
                        *submodulus = ( ( void * ) &temp->modulus );
                bigint_t ( subsize ) __attribute__ (( may_alias ))
                        *substash = ( ( void * ) &temp->stash );
                bigint_t ( subsize ) __attribute__ (( may_alias ))
                        *subresult = ( ( void * ) result );
                union {
                        bigint_t ( 2 * subsize ) full;
                        bigint_t ( subsize ) low;
                } __attribute__ (( may_alias ))
                        *subproduct = ( ( void * ) &temp->product.full );
 
                /* Calculate x2 = base^exponent modulo 2^k */
                bigint_init ( substash, one, sizeof ( one ) );
                bigint_copy ( subbase, submodulus );
                bigint_ladder ( substash, submodulus, exponent,
                                bigint_mod_exp_ladder, NULL, subproduct );
 
                /* Reconstruct N */
                bigint_copy ( modulus, &temp->modulus );
                for ( i = 0 ; i < scale ; i++ )
                        bigint_shr ( &temp->modulus );
 
                /* Calculate N^-1 modulo 2^k */
                bigint_mod_invert ( submodulus, &subproduct->low );
                bigint_copy ( &subproduct->low, submodulus );
 
                /* Calculate y = (x2 - x1) * N^-1 modulo 2^k */
                bigint_subtract ( subresult, substash );
                bigint_multiply ( substash, submodulus, &subproduct->full );
                subproduct->low.element[ subsize - 1 ] &= submask;
                bigint_grow ( &subproduct->low, &temp->stash );
 
                /* Reconstruct N */
                bigint_mod_invert ( submodulus, &subproduct->low );
                bigint_copy ( &subproduct->low, submodulus );
 
                /* Calculate x = x1 + N * y */
                bigint_multiply ( &temp->modulus, &temp->stash,
                                  &temp->product.full );
                bigint_add ( &temp->product.low, result );
        }
}

References __attribute__, assert, base, bigint_add, bigint_bit_is_set, bigint_copy, bigint_grow, bigint_init, bigint_ladder, bigint_max_set_bit, bigint_mod_exp_ladder(), bigint_mod_exp_tmp_len, bigint_mod_invert, bigint_montgomery, bigint_montgomery_relaxed, bigint_multiply, bigint_reduce, bigint_shr, bigint_subtract, bigint_t, low, memset(), NULL, product, result, size, and tmp.

Variable Documentation

size

unsigned int size

Initial value:

{
        const bigint_t ( size ) __attribute__ (( may_alias )) *value =
                ( ( const void * ) value0 )

Definition at line 391 of file bigint.h.

bit

unsigned int unsigned int bit

Initial value:

{
        bigint_t ( size ) __attribute__ (( may_alias )) *value =
                ( ( void * ) value0 )

Definition at line 392 of file bigint.h.

Referenced by __volatile__(), __volatile__(), __volatile__(), __volatile__(), _tg3_flag(), _tg3_flag_clear(), _tg3_flag_set(), arbel_bitmask_alloc(), arbel_bitmask_free(), ath5k_hw_bitswap(), b44_wait_bit(), base64_decode(), base64_encode(), bigint_bit_is_set_okx(), bigint_bit_is_set_raw(), bigint_bit_is_set_sample(), bigint_ladder_raw(), bigint_mod_invert_raw(), bigint_shl_okx(), bigint_shr_okx(), bitmap_set(), bitmap_test(), clear_bit(), cpuid_exec(), deflate_init(), des_generate(), des_permute(), gve_poll_rx(), gve_poll_tx(), hermon_bitmask_alloc(), hermon_bitmask_free(), hub_clear_changes(), i2c_recv_bit(), i2c_send_bit(), isqrt(), linda_i2c_write_bit(), mii_bit_xfer(), qib7322_i2c_write_bit(), set_bit(), spi_bit_transfer(), test_and_clear_bit(), test_and_set_bit(), vmbus_signal_monitor(), vxgetlink(), vxsetlink(), x25519_ladder(), and x25519_step().

index

unsigned int index = ( bit / ( 8 * sizeof ( value->element[0] ) ) )

Definition at line 395 of file bigint.h.

subindex

unsigned int subindex = ( bit % ( 8 * sizeof ( value->element[0] ) ) )

Definition at line 396 of file bigint.h.

Referenced by return().

element

value element[index] = ( 1UL << subindex )

Definition at line 398 of file bigint.h.

Referenced by bigint_ntoa_raw(), linda_ib_epb_mod_reg(), and linda_set_serdes_param().