[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>
diff --git a/src/crypto/bigint.c b/src/crypto/bigint.c
index a8b99ec..3f5db85 100644
--- a/src/crypto/bigint.c
+++ b/src/crypto/bigint.c
@@ -306,6 +306,60 @@
}
/**
+ * 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
diff --git a/src/include/ipxe/bigint.h b/src/include/ipxe/bigint.h
index c56b215..f7900e0 100644
--- a/src/include/ipxe/bigint.h
+++ b/src/include/ipxe/bigint.h
@@ -247,6 +247,31 @@
} ); } )
/**
+ * 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 @@
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,
diff --git a/src/tests/bigint_test.c b/src/tests/bigint_test.c
index 104e1f3..166c771 100644
--- a/src/tests/bigint_test.c
+++ b/src/tests/bigint_test.c
@@ -200,6 +200,17 @@
bigint_reduce ( minuend, modulus, result, tmp );
}
+void bigint_mod_invert_sample ( 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 );
+
+ bigint_mod_invert ( invertend, inverse, tmp );
+}
+
void bigint_mod_multiply_sample ( const bigint_element_t *multiplicand0,
const bigint_element_t *multiplier0,
const bigint_element_t *modulus0,
@@ -574,6 +585,39 @@
} while ( 0 )
/**
+ * Report result of big integer modular inversion test
+ *
+ * @v invertend Big integer to be inverted
+ * @v expected Big integer expected result
+ */
+#define bigint_mod_invert_ok( invertend, expected ) do { \
+ static const uint8_t invertend_raw[] = invertend; \
+ static const uint8_t expected_raw[] = expected; \
+ uint8_t inverse_raw[ sizeof ( expected_raw ) ]; \
+ unsigned int size = \
+ bigint_required_size ( sizeof ( invertend_raw ) ); \
+ bigint_t ( size ) invertend_temp; \
+ bigint_t ( size ) inverse_temp; \
+ size_t tmp_len = bigint_mod_invert_tmp_len ( &invertend_temp ); \
+ uint8_t tmp[tmp_len]; \
+ {} /* Fix emacs alignment */ \
+ \
+ assert ( bigint_size ( &invertend_temp ) == \
+ bigint_size ( &inverse_temp ) ); \
+ bigint_init ( &invertend_temp, invertend_raw, \
+ sizeof ( invertend_raw ) ); \
+ DBG ( "Modular invert:\n" ); \
+ DBG_HDA ( 0, &invertend_temp, sizeof ( invertend_temp ) ); \
+ bigint_mod_invert ( &invertend_temp, &inverse_temp, tmp ); \
+ DBG_HDA ( 0, &inverse_temp, sizeof ( inverse_temp ) ); \
+ bigint_done ( &inverse_temp, inverse_raw, \
+ sizeof ( inverse_raw ) ); \
+ \
+ ok ( memcmp ( inverse_raw, expected_raw, \
+ sizeof ( inverse_raw ) ) == 0 ); \
+ } while ( 0 )
+
+/**
* Report result of big integer modular multiplication test
*
* @v multiplicand Big integer to be multiplied
@@ -1760,6 +1804,23 @@
0xfb, 0x5d, 0x55 ),
BIGINT ( 0x27, 0x31, 0x49, 0xc3, 0xf5, 0x06, 0x1f,
0x3c, 0x7c, 0xd5 ) );
+ bigint_mod_invert_ok ( BIGINT ( 0x01 ), BIGINT ( 0x01 ) );
+ bigint_mod_invert_ok ( BIGINT ( 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+ 0xff, 0xff ),
+ BIGINT ( 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+ 0xff, 0xff ) );
+ bigint_mod_invert_ok ( BIGINT ( 0x95, 0x6a, 0xc5, 0xe7, 0x2e, 0x5b,
+ 0x44, 0xed, 0xbf, 0x7e, 0xfe, 0x8d,
+ 0xf4, 0x5a, 0x48, 0xc1 ),
+ BIGINT ( 0xad, 0xb8, 0x3d, 0x85, 0x10, 0xdf,
+ 0xea, 0x70, 0x71, 0x2c, 0x80, 0xf4,
+ 0x6e, 0x66, 0x47, 0x41 ) );
+ bigint_mod_invert_ok ( BIGINT ( 0x35, 0xe4, 0x80, 0x48, 0xdd, 0xa1,
+ 0x46, 0xc0, 0x84, 0x63, 0xc1, 0xe4,
+ 0xf7, 0xbf, 0xb3, 0x05 ),
+ BIGINT ( 0xf2, 0x9c, 0x63, 0x29, 0xfa, 0xe4,
+ 0xbf, 0x90, 0xa6, 0x9a, 0xec, 0xcf,
+ 0x5f, 0xe2, 0x21, 0xcd ) );
bigint_mod_multiply_ok ( BIGINT ( 0x37 ),
BIGINT ( 0x67 ),
BIGINT ( 0x3f ),
