[crypto] Extract bigint_reduce_supremum() from bigint_mod_exp()

Calculating the Montgomery constant (R^2 mod N) is done in our
implementation by zeroing the double-width representation of N,
subtracting N once to give (R^2 - N) in order to obtain a positive
value, then reducing this value modulo N.

Extract this logic from bigint_mod_exp() to a separate function
bigint_reduce_supremum(), to allow for reuse by other code.

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

2 files changed, 44 insertions, 7 deletions

diff --git a/src/crypto/bigint.c b/src/crypto/bigint.c
index 92747982e..e5e6e2f12 100644
--- a/src/crypto/bigint.c
+++ b/src/crypto/bigint.c
@@ -278,6 +278,30 @@ void bigint_reduce_raw ( bigint_element_t *modulus0, bigint_element_t *value0,
 }
 
 /**
+ * Reduce supremum of big integer representation
+ *
+ * @v modulus0		Element 0 of big integer modulus
+ * @v result0		Element 0 of big integer to hold result
+ * @v size		Number of elements in modulus and value
+ *
+ * Reduce the value 2^k (where k is the bit width of the big integer
+ * representation) modulo the specified modulus.
+ */
+void bigint_reduce_supremum_raw ( bigint_element_t *modulus0,
+				  bigint_element_t *result0,
+				  unsigned int size ) {
+	bigint_t ( size ) __attribute__ (( may_alias ))
+		*modulus = ( ( void * ) modulus0 );
+	bigint_t ( size ) __attribute__ (( may_alias ))
+		*result = ( ( void * ) result0 );
+
+	/* Calculate (2^k) mod N via direct reduction of (2^k - N) mod N */
+	memset ( result, 0, sizeof ( *result ) );
+	bigint_subtract ( modulus, result );
+	bigint_reduce ( modulus, result );
+}
+
+/**
  * Compute inverse of odd big integer modulo any power of two
  *
  * @v invertend0	Element 0 of odd big integer to be inverted
@@ -629,10 +653,8 @@ void bigint_mod_exp_raw ( const bigint_element_t *base0,
 	if ( ! submask )
 		submask = ~submask;
 
-	/* Calculate (R^2 mod N) via direct reduction of (R^2 - N) */
-	memset ( &temp->product.full, 0, sizeof ( temp->product.full ) );
-	bigint_subtract ( &temp->padded_modulus, &temp->product.full );
-	bigint_reduce ( &temp->padded_modulus, &temp->product.full );
+	/* Calculate (R^2 mod N) */
+	bigint_reduce_supremum ( &temp->padded_modulus, &temp->product.full );
 	bigint_copy ( &temp->product.low, &temp->stash );
 
 	/* Initialise result = Montgomery(1, R^2 mod N) */
diff --git a/src/include/ipxe/bigint.h b/src/include/ipxe/bigint.h
index db907f1cd..2dd99380d 100644
--- a/src/include/ipxe/bigint.h
+++ b/src/include/ipxe/bigint.h
@@ -236,9 +236,21 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
  * @v value		Big integer to be reduced
  */
 #define bigint_reduce( modulus, value ) do {				\
-		unsigned int size = bigint_size (modulus);		\
-		bigint_reduce_raw ( (modulus)->element,			\
-				    (value)->element, size );		\
+	unsigned int size = bigint_size (modulus);			\
+	bigint_reduce_raw ( (modulus)->element, (value)->element,	\
+			    size );					\
+	} while ( 0 )
+
+/**
+ * Reduce supremum of big integer representation
+ *
+ * @v modulus0		Big integer modulus
+ * @v result0		Big integer to hold result
+ */
+#define bigint_reduce_supremum( modulus, result ) do {			\
+	unsigned int size = bigint_size (modulus);			\
+	bigint_reduce_supremum_raw ( (modulus)->element,		\
+				     (result)->element, size );		\
 	} while ( 0 )
 
 /**
@@ -385,6 +397,9 @@ void bigint_multiply_raw ( const bigint_element_t *multiplicand0,
 			   bigint_element_t *result0 );
 void bigint_reduce_raw ( bigint_element_t *modulus0, bigint_element_t *value0,
 			 unsigned int size );
+void bigint_reduce_supremum_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 );
 int bigint_montgomery_relaxed_raw ( const bigint_element_t *modulus0,