diff options
Diffstat (limited to 'src/include/ipxe/bigint.h')
| -rw-r--r-- | src/include/ipxe/bigint.h | 291 |
1 files changed, 239 insertions, 52 deletions
diff --git a/src/include/ipxe/bigint.h b/src/include/ipxe/bigint.h index 3dc344dff..9c31f4540 100644 --- a/src/include/ipxe/bigint.h +++ b/src/include/ipxe/bigint.h @@ -7,6 +7,7 @@ */ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); +FILE_SECBOOT ( PERMITTED ); #include <assert.h> @@ -28,8 +29,8 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); * @ret size Number of elements */ #define bigint_required_size( len ) \ - ( ( (len) + sizeof ( bigint_element_t ) - 1 ) / \ - sizeof ( bigint_element_t ) ) + ( (len) ? ( ( (len) + sizeof ( bigint_element_t ) - 1 ) / \ + sizeof ( bigint_element_t ) ) : 1 ) /** * Determine number of elements in big-integer type @@ -41,6 +42,17 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); ( sizeof ( *(bigint) ) / sizeof ( (bigint)->element[0] ) ) /** + * Transcribe big integer (for debugging) + * + * @v value Big integer to be transcribed + * @ret string Big integer in string form (may be abbreviated) + */ +#define bigint_ntoa( value ) ( { \ + unsigned int size = bigint_size (value); \ + bigint_ntoa_raw ( (value)->element, size ); \ + } ) + +/** * Initialise big integer * * @v value Big integer to initialise @@ -70,43 +82,47 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); * * @v addend Big integer to add * @v value Big integer to be added to + * @ret carry Carry out */ -#define bigint_add( addend, value ) do { \ +#define bigint_add( addend, value ) ( { \ unsigned int size = bigint_size (addend); \ bigint_add_raw ( (addend)->element, (value)->element, size ); \ - } while ( 0 ) + } ) /** * Subtract big integers * * @v subtrahend Big integer to subtract * @v value Big integer to be subtracted from + * @ret borrow Borrow out */ -#define bigint_subtract( subtrahend, value ) do { \ +#define bigint_subtract( subtrahend, value ) ( { \ unsigned int size = bigint_size (subtrahend); \ bigint_subtract_raw ( (subtrahend)->element, (value)->element, \ size ); \ - } while ( 0 ) + } ) /** - * Rotate big integer left + * Shift big integer left * * @v value Big integer + * @ret out Bit shifted out */ -#define bigint_rol( value ) do { \ +#define bigint_shl( value ) ( { \ unsigned int size = bigint_size (value); \ - bigint_rol_raw ( (value)->element, size ); \ - } while ( 0 ) + bigint_shl_raw ( (value)->element, size ); \ + } ) /** - * Rotate big integer right + * Shift big integer right * * @v value Big integer + * @ret out Bit shifted out */ -#define bigint_ror( value ) do { \ +#define bigint_shr( value ) ( { \ unsigned int size = bigint_size (value); \ - bigint_ror_raw ( (value)->element, size ); \ - } while ( 0 ) + bigint_shr_raw ( (value)->element, size ); \ + } ) /** * Test if big integer is equal to zero @@ -132,6 +148,28 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); size ); } ) /** + * Set bit in big integer + * + * @v value Big integer + * @v bit Bit to set + */ +#define bigint_set_bit( value, bit ) do { \ + unsigned int size = bigint_size (value); \ + bigint_set_bit_raw ( (value)->element, size, bit ); \ + } while ( 0 ) + +/** + * Clear bit in big integer + * + * @v value Big integer + * @v bit Bit to set + */ +#define bigint_clear_bit( value, bit ) do { \ + unsigned int size = bigint_size (value); \ + bigint_clear_bit_raw ( (value)->element, size, bit ); \ + } while ( 0 ) + +/** * Test if bit is set in big integer * * @v value Big integer @@ -143,6 +181,16 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); bigint_bit_is_set_raw ( (value)->element, size, bit ); } ) /** + * Test if most significant bit is set in big integer + * + * @v value Big integer + * @ret is_set Most significant bit is set + */ +#define bigint_msb_is_set( value ) ( { \ + unsigned int size = bigint_size (value); \ + bigint_msb_is_set_raw ( (value)->element, size ); } ) + +/** * Find highest bit set in big integer * * @v value Big integer @@ -218,35 +266,74 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); } while ( 0 ) /** - * Perform modular multiplication of big integers + * Reduce big integer R^2 modulo N * - * @v multiplicand Big integer to be multiplied - * @v multiplier Big integer to be multiplied * @v modulus Big integer modulus * @v result Big integer to hold result - * @v tmp Temporary working space */ -#define bigint_mod_multiply( multiplicand, multiplier, modulus, \ - result, tmp ) do { \ - unsigned int size = bigint_size (multiplicand); \ - bigint_mod_multiply_raw ( (multiplicand)->element, \ - (multiplier)->element, \ - (modulus)->element, \ - (result)->element, size, tmp ); \ +#define bigint_reduce( modulus, result ) do { \ + unsigned int size = bigint_size (modulus); \ + bigint_reduce_raw ( (modulus)->element, (result)->element, \ + size ); \ } while ( 0 ) /** - * Calculate temporary working space required for moduluar multiplication + * Compute inverse of odd big integer modulo any power of two * - * @v modulus Big integer modulus - * @ret len Length of temporary working space + * @v invertend Odd big integer to be inverted + * @v inverse Big integer to hold result */ -#define bigint_mod_multiply_tmp_len( modulus ) ( { \ +#define bigint_mod_invert( invertend, inverse ) do { \ + unsigned int size = bigint_size ( inverse ); \ + bigint_mod_invert_raw ( (invertend)->element, \ + (inverse)->element, size ); \ + } while ( 0 ) + +/** + * Perform relaxed Montgomery reduction (REDC) of a big integer + * + * @v modulus Big integer odd modulus + * @v value Big integer to be reduced + * @v result Big integer to hold result + * @ret carry Carry out + */ +#define bigint_montgomery_relaxed( modulus, value, result ) ( { \ unsigned int size = bigint_size (modulus); \ - sizeof ( struct { \ - bigint_t ( size * 2 ) temp_result; \ - bigint_t ( size * 2 ) temp_modulus; \ - } ); } ) + bigint_montgomery_relaxed_raw ( (modulus)->element, \ + (value)->element, \ + (result)->element, size ); \ + } ) + +/** + * Perform classic Montgomery reduction (REDC) of a big integer + * + * @v modulus Big integer odd modulus + * @v value Big integer to be reduced + * @v result Big integer to hold result + */ +#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 ) + +/** + * Perform generalised exponentiation via a Montgomery ladder + * + * @v result Big integer result (initialised to identity element) + * @v multiple Big integer multiple (initialised to generator) + * @v exponent Big integer exponent + * @v op Montgomery ladder commutative operation + * @v ctx Operation context (if needed) + * @v tmp Temporary working space (if needed) + */ +#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 ) /** * Perform modular exponentiation of big integers @@ -269,32 +356,114 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); * Calculate temporary working space required for moduluar exponentiation * * @v modulus Big integer modulus - * @v exponent Big integer exponent * @ret len Length of temporary working space */ -#define bigint_mod_exp_tmp_len( modulus, exponent ) ( { \ +#define bigint_mod_exp_tmp_len( modulus ) ( { \ unsigned int size = bigint_size (modulus); \ - unsigned int exponent_size = bigint_size (exponent); \ - size_t mod_multiply_len = \ - bigint_mod_multiply_tmp_len (modulus); \ sizeof ( struct { \ - bigint_t ( size ) temp_base; \ - bigint_t ( exponent_size ) temp_exponent; \ - uint8_t mod_multiply[mod_multiply_len]; \ + bigint_t ( size ) temp[4]; \ } ); } ) #include <bits/bigint.h> +/** + * A big integer Montgomery ladder commutative operation + * + * @v operand Element 0 of first input operand (may overlap result) + * @v result Element 0 of second input operand and result + * @v size Number of elements in operands and result + * @v ctx Operation context (if needed) + * @v tmp Temporary working space (if needed) + */ +typedef void ( bigint_ladder_op_t ) ( const bigint_element_t *operand0, + bigint_element_t *result0, + unsigned int size, const void *ctx, + void *tmp ); + +/** + * Set bit in big integer + * + * @v value0 Element 0 of big integer + * @v size Number of elements + * @v bit Bit to set + */ +static inline __attribute__ (( always_inline )) void +bigint_set_bit_raw ( bigint_element_t *value0, unsigned int size, + unsigned int bit ) { + bigint_t ( size ) __attribute__ (( may_alias )) *value = + ( ( void * ) value0 ); + unsigned int index = ( bit / ( 8 * sizeof ( value->element[0] ) ) ); + unsigned int subindex = ( bit % ( 8 * sizeof ( value->element[0] ) ) ); + + value->element[index] |= ( 1UL << subindex ); +} + +/** + * Clear bit in big integer + * + * @v value0 Element 0 of big integer + * @v size Number of elements + * @v bit Bit to clear + */ +static inline __attribute__ (( always_inline )) void +bigint_clear_bit_raw ( bigint_element_t *value0, unsigned int size, + unsigned int bit ) { + bigint_t ( size ) __attribute__ (( may_alias )) *value = + ( ( void * ) value0 ); + unsigned int index = ( bit / ( 8 * sizeof ( value->element[0] ) ) ); + unsigned int subindex = ( bit % ( 8 * sizeof ( value->element[0] ) ) ); + + value->element[index] &= ~( 1UL << subindex ); +} + +/** + * Test if bit is set in big integer + * + * @v value0 Element 0 of big integer + * @v size Number of elements + * @v bit Bit to test + * @ret is_set Bit is set + */ +static inline __attribute__ (( always_inline )) int +bigint_bit_is_set_raw ( const bigint_element_t *value0, unsigned int size, + unsigned int bit ) { + const bigint_t ( size ) __attribute__ (( may_alias )) *value = + ( ( const void * ) value0 ); + unsigned int index = ( bit / ( 8 * sizeof ( value->element[0] ) ) ); + unsigned int subindex = ( bit % ( 8 * sizeof ( value->element[0] ) ) ); + + return ( !! ( value->element[index] & ( 1UL << subindex ) ) ); +} + +/** + * Test if most significant bit is set in big integer + * + * @v value0 Element 0 of big integer + * @v size Number of elements + * @ret is_set Most significant bit is set + */ +static inline __attribute__ (( always_inline )) int +bigint_msb_is_set_raw ( const bigint_element_t *value0, unsigned int size ) { + const bigint_t ( size ) __attribute__ (( may_alias )) *value = + ( ( const void * ) value0 ); + unsigned int index = ( size - 1 ); + unsigned int subindex = ( ( 8 * sizeof ( value->element[0] ) ) - 1 ); + + return ( !! ( value->element[index] & ( 1UL << subindex ) ) ); +} + +const char * bigint_ntoa_raw ( const bigint_element_t *value0, + unsigned int size ); 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 ); -void bigint_add_raw ( const bigint_element_t *addend0, - bigint_element_t *value0, unsigned int size ); -void bigint_subtract_raw ( const bigint_element_t *subtrahend0, - bigint_element_t *value0, unsigned int size ); -void bigint_rol_raw ( bigint_element_t *value0, unsigned int size ); -void bigint_ror_raw ( bigint_element_t *value0, unsigned int size ); +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, @@ -311,16 +480,34 @@ void bigint_shrink_raw ( const bigint_element_t *source0, unsigned int dest_size ); void bigint_swap_raw ( bigint_element_t *first0, bigint_element_t *second0, unsigned int size, int swap ); +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 ); -void bigint_mod_multiply_raw ( const bigint_element_t *multiplicand0, - const bigint_element_t *multiplier0, - const bigint_element_t *modulus0, - bigint_element_t *result0, - unsigned int size, void *tmp ); +void bigint_reduce_raw ( const bigint_element_t *modulus0, + bigint_element_t *result0, unsigned int size ); +void bigint_mod_invert_raw ( const bigint_element_t *invertend0, + bigint_element_t *inverse0, unsigned int size ); +int bigint_montgomery_relaxed_raw ( const bigint_element_t *modulus0, + bigint_element_t *value0, + bigint_element_t *result0, + unsigned int size ); +void bigint_montgomery_raw ( const bigint_element_t *modulus0, + bigint_element_t *value0, + bigint_element_t *result0, unsigned int size ); +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 ); +void bigint_mod_exp_ladder ( const bigint_element_t *multiplier0, + bigint_element_t *result0, unsigned int size, + const void *ctx, void *tmp ); void bigint_mod_exp_raw ( const bigint_element_t *base0, const bigint_element_t *modulus0, const bigint_element_t *exponent0, |