From 4f7dd7fbba205d413cf9b989f7cdc928fa02caf2 Mon Sep 17 00:00:00 2001 From: Michael Brown Date: Wed, 27 Nov 2024 13:25:18 +0000 Subject: [crypto] Add bigint_montgomery() to perform Montgomery reduction Montgomery reduction is substantially faster than direct reduction, and is better suited for modular exponentiation operations. Add bigint_montgomery() to perform the Montgomery reduction operation (often referred to as "REDC"), along with some test vectors. Signed-off-by: Michael Brown --- src/include/ipxe/bigint.h | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) (limited to 'src/include/ipxe') diff --git a/src/include/ipxe/bigint.h b/src/include/ipxe/bigint.h index 14f3c5f28..6c9730252 100644 --- a/src/include/ipxe/bigint.h +++ b/src/include/ipxe/bigint.h @@ -253,6 +253,23 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); (inverse)->element, size ); \ } while ( 0 ) +/** + * Perform Montgomery reduction (REDC) of a big integer product + * + * @v modulus Big integer modulus + * @v modinv Big integer inverse of the modulus modulo 2^k + * @v mont Big integer Montgomery product + * @v result Big integer to hold result + * + * Note that the Montgomery product will be overwritten. + */ +#define bigint_montgomery( modulus, modinv, mont, result ) do { \ + unsigned int size = bigint_size (modulus); \ + bigint_montgomery_raw ( (modulus)->element, (modinv)->element, \ + (mont)->element, (result)->element, \ + size ); \ + } while ( 0 ) + /** * Perform modular multiplication of big integers * @@ -396,6 +413,10 @@ 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 bigint_montgomery_raw ( const bigint_element_t *modulus0, + const bigint_element_t *modinv0, + bigint_element_t *mont0, + bigint_element_t *result0, 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