[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, 54 insertions, 0 deletions

diff --git a/src/crypto/bigint.c b/src/crypto/bigint.c
index a8b99ec3c..3f5db8517 100644
--- a/src/crypto/bigint.c
+++ b/src/crypto/bigint.c
@@ -306,6 +306,60 @@ void bigint_reduce_raw ( const bigint_element_t *minuend0,
 }
 
 /**
+ * Compute inverse of odd big integer modulo any power of two
+ *
+ * @v invertend0	Element 0 of odd big integer to be inverted
+ * @v inverse0		Element 0 of big integer to hold result
+ * @v size		Number of elements in invertend and result
+ * @v tmp		Temporary working space
+ */
+void bigint_mod_invert_raw ( const bigint_element_t *invertend0,
+			     bigint_element_t *inverse0,
+			     unsigned int size, void *tmp ) {
+	const bigint_t ( size ) __attribute__ (( may_alias ))
+		*invertend = ( ( const void * ) invertend0 );
+	bigint_t ( size ) __attribute__ (( may_alias ))
+		*inverse = ( ( void * ) inverse0 );
+	struct {
+		bigint_t ( size ) residue;
+	} *temp = tmp;
+	const unsigned int width = ( 8 * sizeof ( bigint_element_t ) );
+	unsigned int i;
+
+	/* Sanity check */
+	assert ( invertend->element[0] & 1 );
+
+	/* Initialise temporary working space and output value */
+	memset ( &temp->residue, 0xff, sizeof ( temp->residue ) );
+	memset ( inverse, 0, sizeof ( *inverse ) );
+
+	/* Compute inverse modulo 2^(width)
+	 *
+	 * This method is a lightly modified version of the pseudocode
+	 * presented in "A New Algorithm for Inversion mod p^k (Koç,
+	 * 2017)".
+	 *
+	 * Each loop iteration calculates one bit of the inverse.  The
+	 * residue value is the two's complement negation of the value
+	 * "b" as used by Koç, to allow for division by two using a
+	 * logical right shift (since we have no arithmetic right
+	 * shift operation for big integers).
+	 *
+	 * Due to the suffix property of inverses mod 2^k, the result
+	 * represents the least significant bits of the inverse modulo
+	 * an arbitrarily large 2^k.
+	 */
+	for ( i = 0 ; i < ( 8 * sizeof ( *inverse ) ) ; i++ ) {
+		if ( temp->residue.element[0] & 1 ) {
+			inverse->element[ i / width ] |=
+				( 1UL << ( i % width ) );
+			bigint_add ( invertend, &temp->residue );
+		}
+		bigint_shr ( &temp->residue );
+	}
+}
+
+/**
  * Perform modular multiplication of big integers
  *
  * @v multiplicand0	Element 0 of big integer to be multiplied