[crypto] Allow for relaxed Montgomery reduction

Classic Montgomery reduction involves a single conditional subtraction
to ensure that the result is strictly less than the modulus.

When performing chains of Montgomery multiplications (potentially
interspersed with additions and subtractions), it can be useful to
work with values that are stored modulo some small multiple of the
modulus, thereby allowing some reductions to be elided.  Each addition
and subtraction stage will increase this running multiple, and the
following multiplication stages can be used to reduce the running
multiple since the reduction carried out for multiplication products
is generally strong enough to absorb some additional bits in the
inputs.  This approach is already used in the x25519 code, where
multiplication takes two 258-bit inputs and produces a 257-bit output.

Split out the conditional subtraction from bigint_montgomery() and
provide a separate bigint_montgomery_relaxed() for callers who do not
require immediate reduction to within the range of the modulus.

Modular exponentiation could potentially make use of relaxed
Montgomery multiplication, but this would require R>4N, i.e. that the
two most significant bits of the modulus be zero.  For both RSA and
DHE, this would necessitate extending the modulus size by one element,
which would negate any speed increase from omitting the conditional
subtractions.  We therefore retain the use of classic Montgomery
reduction for modular exponentiation, apart from the final conversion
out of Montgomery form.

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

1 files changed, 26 insertions, 10 deletions

diff --git a/src/include/ipxe/bigint.h b/src/include/ipxe/bigint.h
index 90e212b54..db907f1cd 100644
--- a/src/include/ipxe/bigint.h
+++ b/src/include/ipxe/bigint.h
@@ -235,7 +235,7 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
  * @v modulus		Big integer modulus
  * @v value		Big integer to be reduced
  */
-#define bigint_reduce( modulus, value ) do {	\
+#define bigint_reduce( modulus, value ) do {				\
 		unsigned int size = bigint_size (modulus);		\
 		bigint_reduce_raw ( (modulus)->element,			\
 				    (value)->element, size );		\
@@ -254,19 +254,31 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
 	} while ( 0 )
 
 /**
- * Perform Montgomery reduction (REDC) of a big integer product
+ * Perform relaxed Montgomery reduction (REDC) of a big integer
  *
- * @v modulus		Big integer modulus
- * @v mont		Big integer Montgomery product
+ * @v modulus		Big integer odd modulus
+ * @v value		Big integer to be reduced
  * @v result		Big integer to hold result
+ * @ret carry		Carry out
+ */
+#define bigint_montgomery_relaxed( modulus, value, result ) ( {		\
+	unsigned int size = bigint_size (modulus);			\
+	bigint_montgomery_relaxed_raw ( (modulus)->element,		\
+					(value)->element,		\
+					(result)->element, size );	\
+	} )
+
+/**
+ * Perform classic Montgomery reduction (REDC) of a big integer
  *
- * Note that the Montgomery product will be overwritten.
+ * @v modulus		Big integer odd modulus
+ * @v value		Big integer to be reduced
+ * @v result		Big integer to hold result
  */
-#define bigint_montgomery( modulus, mont, result ) do {			\
+#define bigint_montgomery( modulus, value, result ) do {		\
 	unsigned int size = bigint_size (modulus);			\
-	bigint_montgomery_raw ( (modulus)->element, (mont)->element,	\
-				(result)->element,			\
-				size );					\
+	bigint_montgomery_raw ( (modulus)->element, (value)->element,	\
+				(result)->element, size );		\
 	} while ( 0 )
 
 /**
@@ -375,8 +387,12 @@ void bigint_reduce_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,
+				    bigint_element_t *value0,
+				    bigint_element_t *result0,
+				    unsigned int size );
 void bigint_montgomery_raw ( const bigint_element_t *modulus0,
-			     bigint_element_t *mont0,
+			     bigint_element_t *value0,
 			     bigint_element_t *result0, unsigned int size );
 void bigint_mod_exp_raw ( const bigint_element_t *base0,
 			  const bigint_element_t *modulus0,