[crypto] Add bigint_mod_invert() to calculate inverse modulo a power of two

Montgomery multiplication requires calculating the inverse of the
modulus modulo a larger power of two.

Add bigint_mod_invert() to calculate the inverse of any (odd) big
integer modulo an arbitrary power of two, using a lightly modified
version of the algorithm presented in "A New Algorithm for Inversion
mod p^k (Koç, 2017)".

The power of two is taken to be 2^k, where k is the number of bits
available in the big integer representation of the invertend.  The
inverse modulo any smaller power of two may be obtained simply by
masking off the relevant bits in the inverse.

Signed-off-by: Michael Brown <mcb30@ipxe.org>

1 files changed, 28 insertions, 0 deletions

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,