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

diff --git a/src/tests/bigint_test.c b/src/tests/bigint_test.c
index 07ba13bb4..fce5f5ca3 100644
--- a/src/tests/bigint_test.c
+++ b/src/tests/bigint_test.c
@@ -207,17 +207,17 @@ void bigint_mod_invert_sample ( const bigint_element_t *invertend0,
 }
 
 void bigint_montgomery_sample ( const bigint_element_t *modulus0,
-				bigint_element_t *mont0,
+				bigint_element_t *value0,
 				bigint_element_t *result0,
 				unsigned int size ) {
 	const bigint_t ( size ) __attribute__ (( may_alias ))
 		*modulus = ( ( const void * ) modulus0 );
 	bigint_t ( 2 * size ) __attribute__ (( may_alias ))
-		*mont = ( ( void * ) mont0 );
+		*value = ( ( void * ) value0 );
 	bigint_t ( size ) __attribute__ (( may_alias ))
 		*result = ( ( void * ) result0 );
 
-	bigint_montgomery ( modulus, mont, result );
+	bigint_montgomery ( modulus, value, result );
 }
 
 void bigint_mod_exp_sample ( const bigint_element_t *base0,