From 7c2e68cc87a552c153e13517b0d0d6827f48e95b Mon Sep 17 00:00:00 2001 From: Michael Brown Date: Wed, 27 Nov 2024 12:51:04 +0000 Subject: [crypto] Eliminate temporary working space for bigint_mod_invert() With a slight modification to the algorithm to ignore bits of the residue that can never contribute to the result, it is possible to reuse the as-yet uncalculated portions of the inverse to hold the residue. This removes the requirement for additional temporary working space. Signed-off-by: Michael Brown --- src/include/ipxe/bigint.h | 24 +++++------------------- 1 file changed, 5 insertions(+), 19 deletions(-) (limited to 'src/include') diff --git a/src/include/ipxe/bigint.h b/src/include/ipxe/bigint.h index 330d7deec..e55c536c7 100644 --- a/src/include/ipxe/bigint.h +++ b/src/include/ipxe/bigint.h @@ -242,30 +242,17 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); } while ( 0 ) /** - * Compute inverse of odd big integer modulo its own size + * Compute inverse of odd big integer modulo any power of two * * @v invertend Odd big integer to be inverted * @v inverse Big integer to hold result - * @v tmp Temporary working space */ -#define bigint_mod_invert( invertend, inverse, tmp ) do { \ - unsigned int size = bigint_size (invertend); \ +#define bigint_mod_invert( invertend, inverse ) do { \ + unsigned int size = bigint_size ( invertend ); \ bigint_mod_invert_raw ( (invertend)->element, \ - (inverse)->element, size, tmp ); \ + (inverse)->element, size ); \ } while ( 0 ) -/** - * Calculate temporary working space required for modular inversion - * - * @v invertend Odd big integer to be inverted - * @ret len Length of temporary working space - */ -#define bigint_mod_invert_tmp_len( invertend ) ( { \ - unsigned int size = bigint_size (invertend); \ - sizeof ( struct { \ - bigint_t ( size ) temp_residue; \ - } ); } ) - /** * Perform modular multiplication of big integers * @@ -408,8 +395,7 @@ void bigint_multiply_raw ( const bigint_element_t *multiplicand0, void bigint_reduce_raw ( bigint_element_t *modulus0, bigint_element_t *value0, unsigned int size ); void bigint_mod_invert_raw ( const bigint_element_t *invertend0, - bigint_element_t *inverse0, - unsigned int size, void *tmp ); + bigint_element_t *inverse0, unsigned int size ); void bigint_mod_multiply_raw ( const bigint_element_t *multiplicand0, const bigint_element_t *multiplier0, const bigint_element_t *modulus0, -- cgit v1.2.3-55-g7522