[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 <mcb30@ipxe.org>

1 files changed, 21 insertions, 0 deletions

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
@@ -254,6 +254,23 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
 	} 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
  *
  * @v multiplicand	Big integer to be multiplied
@@ -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,