diff options
| -rw-r--r-- | src/crypto/bigint.c | 54 | ||||
| -rw-r--r-- | src/include/ipxe/bigint.h | 28 | ||||
| -rw-r--r-- | src/tests/bigint_test.c | 61 |
3 files changed, 143 insertions, 0 deletions
diff --git a/src/crypto/bigint.c b/src/crypto/bigint.c index a8b99ec3c..3f5db8517 100644 --- a/src/crypto/bigint.c +++ b/src/crypto/bigint.c @@ -306,6 +306,60 @@ void bigint_reduce_raw ( const bigint_element_t *minuend0, } /** + * Compute inverse of odd big integer modulo any power of two + * + * @v invertend0 Element 0 of odd big integer to be inverted + * @v inverse0 Element 0 of big integer to hold result + * @v size Number of elements in invertend and result + * @v tmp Temporary working space + */ +void bigint_mod_invert_raw ( const bigint_element_t *invertend0, + bigint_element_t *inverse0, + unsigned int size, void *tmp ) { + const bigint_t ( size ) __attribute__ (( may_alias )) + *invertend = ( ( const void * ) invertend0 ); + bigint_t ( size ) __attribute__ (( may_alias )) + *inverse = ( ( void * ) inverse0 ); + struct { + bigint_t ( size ) residue; + } *temp = tmp; + const unsigned int width = ( 8 * sizeof ( bigint_element_t ) ); + unsigned int i; + + /* Sanity check */ + assert ( invertend->element[0] & 1 ); + + /* Initialise temporary working space and output value */ + memset ( &temp->residue, 0xff, sizeof ( temp->residue ) ); + memset ( inverse, 0, 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 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). + * + * 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 = 0 ; i < ( 8 * sizeof ( *inverse ) ) ; i++ ) { + if ( temp->residue.element[0] & 1 ) { + inverse->element[ i / width ] |= + ( 1UL << ( i % width ) ); + bigint_add ( invertend, &temp->residue ); + } + bigint_shr ( &temp->residue ); + } +} + +/** * Perform modular multiplication of big integers * * @v multiplicand0 Element 0 of big integer to be multiplied diff --git a/src/include/ipxe/bigint.h b/src/include/ipxe/bigint.h index c56b2155f..f7900e0e6 100644 --- a/src/include/ipxe/bigint.h +++ b/src/include/ipxe/bigint.h @@ -247,6 +247,31 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); } ); } ) /** + * Compute inverse of odd big integer modulo its own size + * + * @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); \ + bigint_mod_invert_raw ( (invertend)->element, \ + (inverse)->element, size, tmp ); \ + } 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 * * @v multiplicand Big integer to be multiplied @@ -373,6 +398,9 @@ void bigint_reduce_raw ( const bigint_element_t *minuend0, const bigint_element_t *modulus0, unsigned int modulus_size, bigint_element_t *result0, void *tmp ); +void bigint_mod_invert_raw ( const bigint_element_t *invertend0, + bigint_element_t *inverse0, + unsigned int size, void *tmp ); void bigint_mod_multiply_raw ( const bigint_element_t *multiplicand0, const bigint_element_t *multiplier0, const bigint_element_t *modulus0, diff --git a/src/tests/bigint_test.c b/src/tests/bigint_test.c index 104e1f362..166c771b9 100644 --- a/src/tests/bigint_test.c +++ b/src/tests/bigint_test.c @@ -200,6 +200,17 @@ void bigint_reduce_sample ( const bigint_element_t *minuend0, bigint_reduce ( minuend, modulus, result, tmp ); } +void bigint_mod_invert_sample ( const bigint_element_t *invertend0, + bigint_element_t *inverse0, + unsigned int size, void *tmp ) { + const bigint_t ( size ) __attribute__ (( may_alias )) + *invertend = ( ( const void * ) invertend0 ); + bigint_t ( size ) __attribute__ (( may_alias )) + *inverse = ( ( void * ) inverse0 ); + + bigint_mod_invert ( invertend, inverse, tmp ); +} + void bigint_mod_multiply_sample ( const bigint_element_t *multiplicand0, const bigint_element_t *multiplier0, const bigint_element_t *modulus0, @@ -574,6 +585,39 @@ void bigint_mod_exp_sample ( const bigint_element_t *base0, } while ( 0 ) /** + * Report result of big integer modular inversion test + * + * @v invertend Big integer to be inverted + * @v expected Big integer expected result + */ +#define bigint_mod_invert_ok( invertend, expected ) do { \ + static const uint8_t invertend_raw[] = invertend; \ + static const uint8_t expected_raw[] = expected; \ + uint8_t inverse_raw[ sizeof ( expected_raw ) ]; \ + unsigned int size = \ + bigint_required_size ( sizeof ( invertend_raw ) ); \ + bigint_t ( size ) invertend_temp; \ + bigint_t ( size ) inverse_temp; \ + size_t tmp_len = bigint_mod_invert_tmp_len ( &invertend_temp ); \ + uint8_t tmp[tmp_len]; \ + {} /* Fix emacs alignment */ \ + \ + assert ( bigint_size ( &invertend_temp ) == \ + bigint_size ( &inverse_temp ) ); \ + bigint_init ( &invertend_temp, invertend_raw, \ + sizeof ( invertend_raw ) ); \ + DBG ( "Modular invert:\n" ); \ + DBG_HDA ( 0, &invertend_temp, sizeof ( invertend_temp ) ); \ + bigint_mod_invert ( &invertend_temp, &inverse_temp, tmp ); \ + DBG_HDA ( 0, &inverse_temp, sizeof ( inverse_temp ) ); \ + bigint_done ( &inverse_temp, inverse_raw, \ + sizeof ( inverse_raw ) ); \ + \ + ok ( memcmp ( inverse_raw, expected_raw, \ + sizeof ( inverse_raw ) ) == 0 ); \ + } while ( 0 ) + +/** * Report result of big integer modular multiplication test * * @v multiplicand Big integer to be multiplied @@ -1760,6 +1804,23 @@ static void bigint_test_exec ( void ) { 0xfb, 0x5d, 0x55 ), BIGINT ( 0x27, 0x31, 0x49, 0xc3, 0xf5, 0x06, 0x1f, 0x3c, 0x7c, 0xd5 ) ); + bigint_mod_invert_ok ( BIGINT ( 0x01 ), BIGINT ( 0x01 ) ); + bigint_mod_invert_ok ( BIGINT ( 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff ), + BIGINT ( 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff ) ); + bigint_mod_invert_ok ( BIGINT ( 0x95, 0x6a, 0xc5, 0xe7, 0x2e, 0x5b, + 0x44, 0xed, 0xbf, 0x7e, 0xfe, 0x8d, + 0xf4, 0x5a, 0x48, 0xc1 ), + BIGINT ( 0xad, 0xb8, 0x3d, 0x85, 0x10, 0xdf, + 0xea, 0x70, 0x71, 0x2c, 0x80, 0xf4, + 0x6e, 0x66, 0x47, 0x41 ) ); + bigint_mod_invert_ok ( BIGINT ( 0x35, 0xe4, 0x80, 0x48, 0xdd, 0xa1, + 0x46, 0xc0, 0x84, 0x63, 0xc1, 0xe4, + 0xf7, 0xbf, 0xb3, 0x05 ), + BIGINT ( 0xf2, 0x9c, 0x63, 0x29, 0xfa, 0xe4, + 0xbf, 0x90, 0xa6, 0x9a, 0xec, 0xcf, + 0x5f, 0xe2, 0x21, 0xcd ) ); bigint_mod_multiply_ok ( BIGINT ( 0x37 ), BIGINT ( 0x67 ), BIGINT ( 0x3f ), |