From 9cbf5c4f86b45773badec2498fac22e8bc6d7dd1 Mon Sep 17 00:00:00 2001 From: Michael Brown Date: Tue, 26 Nov 2024 14:45:51 +0000 Subject: [crypto] Eliminate temporary working space for bigint_reduce() Direct modular reduction is expected to be used in situations where there is no requirement to retain the original (unreduced) value. Modify the API for bigint_reduce() to reduce the value in place, (removing the separate result buffer), impose a constraint that the modulus and value have the same size, and require the modulus to be passed in writable memory (to allow for scaling in place). This removes the requirement for additional temporary working space. Reverse the order of arguments so that the constant input is first, to match the usage pattern for bigint_add() et al. Signed-off-by: Michael Brown --- src/crypto/bigint.c | 71 ++++++++++++++------------------------- src/include/ipxe/bigint.h | 34 ++++--------------- src/tests/bigint_test.c | 84 ++++++++++++++++++++++------------------------- 3 files changed, 72 insertions(+), 117 deletions(-) diff --git a/src/crypto/bigint.c b/src/crypto/bigint.c index 35701a1d0..4b37c062b 100644 --- a/src/crypto/bigint.c +++ b/src/crypto/bigint.c @@ -139,32 +139,20 @@ void bigint_multiply_raw ( const bigint_element_t *multiplicand0, /** * Reduce big integer * - * @v minuend0 Element 0 of big integer to be reduced - * @v minuend_size Number of elements in minuend * @v modulus0 Element 0 of big integer modulus - * @v modulus_size Number of elements in modulus and result - * @v result0 Element 0 of big integer to hold result - * @v tmp Temporary working space + * @v value0 Element 0 of big integer to be reduced + * @v size Number of elements in modulus and value */ -void bigint_reduce_raw ( const bigint_element_t *minuend0, - unsigned int minuend_size, - const bigint_element_t *modulus0, - unsigned int modulus_size, - bigint_element_t *result0, void *tmp ) { - const bigint_t ( minuend_size ) __attribute__ (( may_alias )) - *minuend = ( ( const void * ) minuend0 ); - const bigint_t ( modulus_size ) __attribute__ (( may_alias )) - *modulus = ( ( const void * ) modulus0 ); - bigint_t ( modulus_size ) __attribute__ (( may_alias )) - *result = ( ( void * ) result0 ); - struct { - bigint_t ( minuend_size ) minuend; - bigint_t ( minuend_size ) modulus; - } *temp = tmp; +void bigint_reduce_raw ( bigint_element_t *modulus0, bigint_element_t *value0, + unsigned int size ) { + bigint_t ( size ) __attribute__ (( may_alias )) + *modulus = ( ( void * ) modulus0 ); + bigint_t ( size ) __attribute__ (( may_alias )) + *value = ( ( void * ) value0 ); const unsigned int width = ( 8 * sizeof ( bigint_element_t ) ); bigint_element_t *element; - unsigned int minuend_max; unsigned int modulus_max; + unsigned int value_max; unsigned int subshift; int offset; int shift; @@ -174,31 +162,23 @@ void bigint_reduce_raw ( const bigint_element_t *minuend0, /* Start profiling */ profile_start ( &bigint_mod_profiler ); - /* Sanity check */ - assert ( minuend_size >= modulus_size ); - assert ( sizeof ( *temp ) == bigint_reduce_tmp_len ( minuend ) ); - - /* Copy minuend and modulus to temporary working space */ - bigint_shrink ( minuend, &temp->minuend ); - bigint_grow ( modulus, &temp->modulus ); - /* Normalise the modulus * * Scale the modulus by shifting left such that both modulus - * "m" and minuend "x" have the same most significant set bit. - * (If this is not possible, then the minuend is already less + * "m" and value "x" have the same most significant set bit. + * (If this is not possible, then the value is already less * than the modulus, and we may therefore skip reduction * completely.) */ - minuend_max = bigint_max_set_bit ( minuend ); + value_max = bigint_max_set_bit ( value ); modulus_max = bigint_max_set_bit ( modulus ); - shift = ( minuend_max - modulus_max ); + shift = ( value_max - modulus_max ); if ( shift < 0 ) goto skip; subshift = ( shift & ( width - 1 ) ); offset = ( shift / width ); - element = temp->modulus.element; - for ( i = ( ( minuend_max - 1 ) / width ) ; ; i-- ) { + element = modulus->element; + for ( i = ( ( value_max - 1 ) / width ) ; ; i-- ) { element[i] = ( element[ i - offset ] << subshift ); if ( i <= offset ) break; @@ -210,14 +190,14 @@ void bigint_reduce_raw ( const bigint_element_t *minuend0, for ( i-- ; i >= 0 ; i-- ) element[i] = 0; - /* Reduce the minuend "x" by iteratively adding or subtracting + /* Reduce the value "x" by iteratively adding or subtracting * the scaled modulus "m". * * On each loop iteration, we maintain the invariant: * * -2m <= x < 2m * - * If x is positive, we obtain the new minuend x' by + * If x is positive, we obtain the new value x' by * subtracting m, otherwise we add m: * * 0 <= x < 2m => x' := x - m => -m <= x' < m @@ -284,21 +264,18 @@ void bigint_reduce_raw ( const bigint_element_t *minuend0, */ for ( msb = 0 ; ( msb || ( shift >= 0 ) ) ; shift-- ) { if ( msb ) { - bigint_add ( &temp->modulus, &temp->minuend ); + bigint_add ( modulus, value ); } else { - bigint_subtract ( &temp->modulus, &temp->minuend ); + bigint_subtract ( modulus, value ); } - msb = bigint_msb_is_set ( &temp->minuend ); + msb = bigint_msb_is_set ( value ); if ( shift > 0 ) - bigint_shr ( &temp->modulus ); + bigint_shr ( modulus ); } skip: /* Sanity check */ - assert ( ! bigint_is_geq ( &temp->minuend, &temp->modulus ) ); - - /* Copy result */ - bigint_shrink ( &temp->minuend, result ); + assert ( ! bigint_is_geq ( value, modulus ) ); /* Stop profiling */ profile_stop ( &bigint_mod_profiler ); @@ -396,7 +373,9 @@ void bigint_mod_multiply_raw ( const bigint_element_t *multiplicand0, bigint_multiply ( multiplicand, multiplier, &temp->result ); /* Reduce result */ - bigint_reduce ( &temp->result, modulus, result, temp ); + bigint_grow ( modulus, &temp->modulus ); + bigint_reduce ( &temp->modulus, &temp->result ); + bigint_shrink ( &temp->result, result ); /* Sanity check */ assert ( ! bigint_is_geq ( result, modulus ) ); diff --git a/src/include/ipxe/bigint.h b/src/include/ipxe/bigint.h index 2a0a200c5..330d7deec 100644 --- a/src/include/ipxe/bigint.h +++ b/src/include/ipxe/bigint.h @@ -232,32 +232,15 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); /** * Reduce big integer * - * @v minuend Big integer to be reduced * @v modulus Big integer modulus - * @v result Big integer to hold result - * @v tmp Temporary working space + * @v value Big integer to be reduced */ -#define bigint_reduce( minuend, modulus, result, tmp ) do { \ - unsigned int minuend_size = bigint_size (minuend); \ - unsigned int modulus_size = bigint_size (modulus); \ - bigint_reduce_raw ( (minuend)->element, minuend_size, \ - (modulus)->element, modulus_size, \ - (result)->element, tmp ); \ +#define bigint_reduce( modulus, value ) do { \ + unsigned int size = bigint_size (modulus); \ + bigint_reduce_raw ( (modulus)->element, \ + (value)->element, size ); \ } while ( 0 ) -/** - * Calculate temporary working space required for reduction - * - * @v minuend Big integer to be reduced - * @ret len Length of temporary working space - */ -#define bigint_reduce_tmp_len( minuend ) ( { \ - unsigned int size = bigint_size (minuend); \ - sizeof ( struct { \ - bigint_t ( size ) temp_minuend; \ - bigint_t ( size ) temp_modulus; \ - } ); } ) - /** * Compute inverse of odd big integer modulo its own size * @@ -422,11 +405,8 @@ void bigint_multiply_raw ( const bigint_element_t *multiplicand0, const bigint_element_t *multiplier0, unsigned int multiplier_size, bigint_element_t *result0 ); -void bigint_reduce_raw ( const bigint_element_t *minuend0, - unsigned int minuend_size, - const bigint_element_t *modulus0, - unsigned int modulus_size, - bigint_element_t *result0, void *tmp ); +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 ); diff --git a/src/tests/bigint_test.c b/src/tests/bigint_test.c index 271d76723..61f78fff9 100644 --- a/src/tests/bigint_test.c +++ b/src/tests/bigint_test.c @@ -185,19 +185,14 @@ void bigint_multiply_sample ( const bigint_element_t *multiplicand0, bigint_multiply ( multiplicand, multiplier, result ); } -void bigint_reduce_sample ( const bigint_element_t *minuend0, - unsigned int minuend_size, - const bigint_element_t *modulus0, - unsigned int modulus_size, - bigint_element_t *result0, void *tmp ) { - const bigint_t ( minuend_size ) __attribute__ (( may_alias )) - *minuend = ( ( const void * ) minuend0 ); - const bigint_t ( modulus_size ) __attribute__ (( may_alias )) - *modulus = ( ( const void * ) modulus0 ); - bigint_t ( modulus_size ) __attribute__ (( may_alias )) - *result = ( ( void * ) result0 ); +void bigint_reduce_sample ( bigint_element_t *modulus0, + bigint_element_t *value0, unsigned int size ) { + bigint_t ( size ) __attribute__ (( may_alias )) + *modulus = ( ( void * ) modulus0 ); + bigint_t ( size ) __attribute__ (( may_alias )) + *value = ( ( void * ) value0 ); - bigint_reduce ( minuend, modulus, result, tmp ); + bigint_reduce ( modulus, value ); } void bigint_mod_invert_sample ( const bigint_element_t *invertend0, @@ -555,43 +550,40 @@ void bigint_mod_exp_sample ( const bigint_element_t *base0, /** * Report result of big integer modular direct reduction test * - * @v minuend Big integer to be reduced * @v modulus Big integer modulus + * @v value Big integer to be reduced * @v expected Big integer expected result */ -#define bigint_reduce_ok( minuend, modulus, expected ) do { \ - static const uint8_t minuend_raw[] = minuend; \ +#define bigint_reduce_ok( modulus, value, expected ) do { \ static const uint8_t modulus_raw[] = modulus; \ + static const uint8_t value_raw[] = value; \ static const uint8_t expected_raw[] = expected; \ uint8_t result_raw[ sizeof ( expected_raw ) ]; \ - unsigned int minuend_size = \ - bigint_required_size ( sizeof ( minuend_raw ) ); \ - unsigned int modulus_size = \ + unsigned int size = \ bigint_required_size ( sizeof ( modulus_raw ) ); \ - bigint_t ( minuend_size ) minuend_temp; \ - bigint_t ( modulus_size ) modulus_temp; \ - bigint_t ( modulus_size ) result_temp; \ - size_t tmp_len = bigint_reduce_tmp_len ( &minuend_temp ); \ - uint8_t tmp[tmp_len]; \ + bigint_t ( size ) modulus_temp; \ + bigint_t ( size ) value_temp; \ {} /* Fix emacs alignment */ \ \ - assert ( bigint_size ( &result_temp ) == \ - bigint_size ( &modulus_temp ) ); \ - bigint_init ( &minuend_temp, minuend_raw, \ - sizeof ( minuend_raw ) ); \ + assert ( bigint_size ( &modulus_temp ) == \ + bigint_size ( &value_temp ) ); \ bigint_init ( &modulus_temp, modulus_raw, \ sizeof ( modulus_raw ) ); \ + bigint_init ( &value_temp, value_raw, sizeof ( value_raw ) ); \ DBG ( "Modular reduce:\n" ); \ - DBG_HDA ( 0, &minuend_temp, sizeof ( minuend_temp ) ); \ DBG_HDA ( 0, &modulus_temp, sizeof ( modulus_temp ) ); \ - bigint_reduce ( &minuend_temp, &modulus_temp, &result_temp, \ - tmp ); \ - DBG_HDA ( 0, &result_temp, sizeof ( result_temp ) ); \ - bigint_done ( &result_temp, result_raw, \ - sizeof ( result_raw ) ); \ + DBG_HDA ( 0, &value_temp, sizeof ( value_temp ) ); \ + bigint_reduce ( &modulus_temp, &value_temp ); \ + DBG_HDA ( 0, &value_temp, sizeof ( value_temp ) ); \ + bigint_done ( &value_temp, result_raw, sizeof ( result_raw ) ); \ \ ok ( memcmp ( result_raw, expected_raw, \ sizeof ( result_raw ) ) == 0 ); \ + \ + bigint_init ( &value_temp, modulus_raw, \ + sizeof ( modulus_raw ) ); \ + ok ( memcmp ( &modulus_temp, &value_temp, \ + sizeof ( modulus_temp ) ) == 0 ); \ } while ( 0 ) /** @@ -1797,16 +1789,16 @@ static void bigint_test_exec ( void ) { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01 ) ); - bigint_reduce_ok ( BIGINT ( 0x00 ), - BIGINT ( 0xaf ), + bigint_reduce_ok ( BIGINT ( 0xaf ), + BIGINT ( 0x00 ), BIGINT ( 0x00 ) ); bigint_reduce_ok ( BIGINT ( 0xab ), BIGINT ( 0xab ), BIGINT ( 0x00 ) ); - bigint_reduce_ok ( BIGINT ( 0x1d, 0x97, 0x63, 0xc9, 0x97, 0xcd, 0x43, - 0xcb, 0x8e, 0x71, 0xac, 0x41, 0xdd ), - BIGINT ( 0xcc, 0x9d, 0xa0, 0x79, 0x96, 0x6a, 0x46, + bigint_reduce_ok ( BIGINT ( 0xcc, 0x9d, 0xa0, 0x79, 0x96, 0x6a, 0x46, 0xd5, 0xb4, 0x30, 0xd2, 0x2b, 0xbf ), + BIGINT ( 0x1d, 0x97, 0x63, 0xc9, 0x97, 0xcd, 0x43, + 0xcb, 0x8e, 0x71, 0xac, 0x41, 0xdd ), BIGINT ( 0x1d, 0x97, 0x63, 0xc9, 0x97, 0xcd, 0x43, 0xcb, 0x8e, 0x71, 0xac, 0x41, 0xdd ) ); bigint_reduce_ok ( BIGINT ( 0x21, 0xfa, 0x4f, 0xce, 0x0f, 0x0f, 0x4d, @@ -1815,15 +1807,19 @@ static void bigint_test_exec ( void ) { 0x43, 0xaa, 0xad, 0x21, 0x30, 0xe5 ), BIGINT ( 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 ) ); - bigint_reduce_ok ( BIGINT ( 0xf9, 0x78, 0x96, 0x39, 0xee, 0x98, 0x42, + bigint_reduce_ok ( BIGINT ( 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0xf3, 0x65, 0x35, 0x41, + 0x66, 0x65 ), + BIGINT ( 0xf9, 0x78, 0x96, 0x39, 0xee, 0x98, 0x42, 0x6a, 0xb8, 0x74, 0x0b, 0xe8, 0x5c, 0x76, 0x34, 0xaf ), - BIGINT ( 0xf3, 0x65, 0x35, 0x41, 0x66, 0x65 ), - BIGINT ( 0xb3, 0x07, 0xe8, 0xb7, 0x01, 0xf6 ) ); - bigint_reduce_ok ( BIGINT ( 0xfe, 0x30, 0xe1, 0xc6, 0x65, 0x97, 0x48, - 0x2e, 0x94, 0xd4 ), - BIGINT ( 0x47, 0xaa, 0x88, 0x00, 0xd0, 0x30, 0x62, + BIGINT ( 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0xb3, 0x07, 0xe8, 0xb7, + 0x01, 0xf6 ) ); + bigint_reduce_ok ( BIGINT ( 0x47, 0xaa, 0x88, 0x00, 0xd0, 0x30, 0x62, 0xfb, 0x5d, 0x55 ), + BIGINT ( 0xfe, 0x30, 0xe1, 0xc6, 0x65, 0x97, 0x48, + 0x2e, 0x94, 0xd4 ), BIGINT ( 0x27, 0x31, 0x49, 0xc3, 0xf5, 0x06, 0x1f, 0x3c, 0x7c, 0xd5 ) ); bigint_mod_invert_ok ( BIGINT ( 0x01 ), BIGINT ( 0x01 ) ); -- cgit