[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>

1 files changed, 26 insertions, 4 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) */