Merge branch 'master' into openslxopenslx

1 files changed, 239 insertions, 52 deletions

diff --git a/src/include/ipxe/bigint.h b/src/include/ipxe/bigint.h
index 3dc344dff..9c31f4540 100644
--- a/src/include/ipxe/bigint.h
+++ b/src/include/ipxe/bigint.h
@@ -7,6 +7,7 @@
  */
 
 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
+FILE_SECBOOT ( PERMITTED );
 
 #include <assert.h>
 
@@ -28,8 +29,8 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
  * @ret size		Number of elements
  */
 #define bigint_required_size( len )					\
-	( ( (len) + sizeof ( bigint_element_t ) - 1 ) /			\
-	  sizeof ( bigint_element_t ) )
+	( (len) ? ( ( (len) + sizeof ( bigint_element_t ) - 1 ) /	\
+		    sizeof ( bigint_element_t ) ) : 1 )
 
 /**
  * Determine number of elements in big-integer type
@@ -41,6 +42,17 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
 	( sizeof ( *(bigint) ) / sizeof ( (bigint)->element[0] ) )
 
 /**
+ * Transcribe big integer (for debugging)
+ *
+ * @v value		Big integer to be transcribed
+ * @ret string		Big integer in string form (may be abbreviated)
+ */
+#define bigint_ntoa( value ) ( {					\
+	unsigned int size = bigint_size (value);			\
+	bigint_ntoa_raw ( (value)->element, size );			\
+	} )
+
+/**
  * Initialise big integer
  *
  * @v value		Big integer to initialise
@@ -70,43 +82,47 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
  *
  * @v addend		Big integer to add
  * @v value		Big integer to be added to
+ * @ret carry		Carry out
  */
-#define bigint_add( addend, value ) do {				\
+#define bigint_add( addend, value ) ( {					\
 	unsigned int size = bigint_size (addend);			\
 	bigint_add_raw ( (addend)->element, (value)->element, size );	\
-	} while ( 0 )
+	} )
 
 /**
  * Subtract big integers
  *
  * @v subtrahend	Big integer to subtract
  * @v value		Big integer to be subtracted from
+ * @ret borrow		Borrow out
  */
-#define bigint_subtract( subtrahend, value ) do {			\
+#define bigint_subtract( subtrahend, value ) ( {			\
 	unsigned int size = bigint_size (subtrahend);			\
 	bigint_subtract_raw ( (subtrahend)->element, (value)->element,	\
 			      size );					\
-	} while ( 0 )
+	} )
 
 /**
- * Rotate big integer left
+ * Shift big integer left
  *
  * @v value		Big integer
+ * @ret out		Bit shifted out
  */
-#define bigint_rol( value ) do {					\
+#define bigint_shl( value ) ( {						\
 	unsigned int size = bigint_size (value);			\
-	bigint_rol_raw ( (value)->element, size );			\
-	} while ( 0 )
+	bigint_shl_raw ( (value)->element, size );			\
+	} )
 
 /**
- * Rotate big integer right
+ * Shift big integer right
  *
  * @v value		Big integer
+ * @ret out		Bit shifted out
  */
-#define bigint_ror( value ) do {					\
+#define bigint_shr( value ) ( {						\
 	unsigned int size = bigint_size (value);			\
-	bigint_ror_raw ( (value)->element, size );			\
-	} while ( 0 )
+	bigint_shr_raw ( (value)->element, size );			\
+	} )
 
 /**
  * Test if big integer is equal to zero
@@ -132,6 +148,28 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
 			    size ); } )
 
 /**
+ * Set bit in big integer
+ *
+ * @v value		Big integer
+ * @v bit		Bit to set
+ */
+#define bigint_set_bit( value, bit ) do {				\
+	unsigned int size = bigint_size (value);			\
+	bigint_set_bit_raw ( (value)->element, size, bit );		\
+	} while ( 0 )
+
+/**
+ * Clear bit in big integer
+ *
+ * @v value		Big integer
+ * @v bit		Bit to set
+ */
+#define bigint_clear_bit( value, bit ) do {				\
+	unsigned int size = bigint_size (value);			\
+	bigint_clear_bit_raw ( (value)->element, size, bit );		\
+	} while ( 0 )
+
+/**
  * Test if bit is set in big integer
  *
  * @v value		Big integer
@@ -143,6 +181,16 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
 	bigint_bit_is_set_raw ( (value)->element, size, bit ); } )
 
 /**
+ * Test if most significant bit is set in big integer
+ *
+ * @v value		Big integer
+ * @ret is_set		Most significant bit is set
+ */
+#define bigint_msb_is_set( value ) ( {					\
+	unsigned int size = bigint_size (value);			\
+	bigint_msb_is_set_raw ( (value)->element, size ); } )
+
+/**
  * Find highest bit set in big integer
  *
  * @v value		Big integer
@@ -218,35 +266,74 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
 	} while ( 0 )
 
 /**
- * Perform modular multiplication of big integers
+ * Reduce big integer R^2 modulo N
  *
- * @v multiplicand	Big integer to be multiplied
- * @v multiplier	Big integer to be multiplied
  * @v modulus		Big integer modulus
  * @v result		Big integer to hold result
- * @v tmp		Temporary working space
  */
-#define bigint_mod_multiply( multiplicand, multiplier, modulus,		\
-			     result, tmp ) do {				\
-	unsigned int size = bigint_size (multiplicand);			\
-	bigint_mod_multiply_raw ( (multiplicand)->element,		\
-				  (multiplier)->element,		\
-				  (modulus)->element,			\
-				  (result)->element, size, tmp );	\
+#define bigint_reduce( modulus, result ) do {				\
+	unsigned int size = bigint_size (modulus);			\
+	bigint_reduce_raw ( (modulus)->element, (result)->element,	\
+			    size );					\
 	} while ( 0 )
 
 /**
- * Calculate temporary working space required for moduluar multiplication
+ * Compute inverse of odd big integer modulo any power of two
  *
- * @v modulus		Big integer modulus
- * @ret len		Length of temporary working space
+ * @v invertend		Odd big integer to be inverted
+ * @v inverse		Big integer to hold result
  */
-#define bigint_mod_multiply_tmp_len( modulus ) ( {			\
+#define bigint_mod_invert( invertend, inverse ) do {			\
+	unsigned int size = bigint_size ( inverse );			\
+	bigint_mod_invert_raw ( (invertend)->element,			\
+				(inverse)->element, size );		\
+	} while ( 0 )
+
+/**
+ * Perform relaxed Montgomery reduction (REDC) of a big integer
+ *
+ * @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);			\
-	sizeof ( struct {						\
-		bigint_t ( size * 2 ) temp_result;			\
-		bigint_t ( size * 2 ) temp_modulus;			\
-	} ); } )
+	bigint_montgomery_relaxed_raw ( (modulus)->element,		\
+					(value)->element,		\
+					(result)->element, size );	\
+	} )
+
+/**
+ * Perform classic Montgomery reduction (REDC) of a big integer
+ *
+ * @v modulus		Big integer odd modulus
+ * @v value		Big integer to be reduced
+ * @v result		Big integer to hold result
+ */
+#define bigint_montgomery( modulus, value, result ) do {		\
+	unsigned int size = bigint_size (modulus);			\
+	bigint_montgomery_raw ( (modulus)->element, (value)->element,	\
+				(result)->element, size );		\
+	} while ( 0 )
+
+/**
+ * Perform generalised exponentiation via a Montgomery ladder
+ *
+ * @v result		Big integer result (initialised to identity element)
+ * @v multiple		Big integer multiple (initialised to generator)
+ * @v exponent		Big integer exponent
+ * @v op		Montgomery ladder commutative operation
+ * @v ctx		Operation context (if needed)
+ * @v tmp		Temporary working space (if needed)
+ */
+#define bigint_ladder( result, multiple, exponent, op, ctx, tmp ) do {	\
+	unsigned int size = bigint_size (result);			\
+	unsigned int exponent_size = bigint_size (exponent);		\
+	bigint_ladder_raw ( (result)->element, (multiple)->element,	\
+			    size, (exponent)->element, exponent_size,	\
+			    (op), (ctx), (tmp) );			\
+	} while ( 0 )
 
 /**
  * Perform modular exponentiation of big integers
@@ -269,32 +356,114 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
  * Calculate temporary working space required for moduluar exponentiation
  *
  * @v modulus		Big integer modulus
- * @v exponent		Big integer exponent
  * @ret len		Length of temporary working space
  */
-#define bigint_mod_exp_tmp_len( modulus, exponent ) ( {			\
+#define bigint_mod_exp_tmp_len( modulus ) ( {				\
 	unsigned int size = bigint_size (modulus);			\
-	unsigned int exponent_size = bigint_size (exponent);		\
-	size_t mod_multiply_len =					\
-		bigint_mod_multiply_tmp_len (modulus);			\
 	sizeof ( struct {						\
-		bigint_t ( size ) temp_base;				\
-		bigint_t ( exponent_size ) temp_exponent;		\
-		uint8_t mod_multiply[mod_multiply_len];			\
+		bigint_t ( size ) temp[4];				\
 	} ); } )
 
 #include <bits/bigint.h>
 
+/**
+ * A big integer Montgomery ladder commutative operation
+ *
+ * @v operand		Element 0 of first input operand (may overlap result)
+ * @v result		Element 0 of second input operand and result
+ * @v size		Number of elements in operands and result
+ * @v ctx		Operation context (if needed)
+ * @v tmp		Temporary working space (if needed)
+ */
+typedef void ( bigint_ladder_op_t ) ( const bigint_element_t *operand0,
+				      bigint_element_t *result0,
+				      unsigned int size, const void *ctx,
+				      void *tmp );
+
+/**
+ * Set bit in big integer
+ *
+ * @v value0		Element 0 of big integer
+ * @v size		Number of elements
+ * @v bit		Bit to set
+ */
+static inline __attribute__ (( always_inline )) void
+bigint_set_bit_raw ( bigint_element_t *value0, unsigned int size,
+		     unsigned int bit ) {
+	bigint_t ( size ) __attribute__ (( may_alias )) *value =
+		( ( void * ) value0 );
+	unsigned int index = ( bit / ( 8 * sizeof ( value->element[0] ) ) );
+	unsigned int subindex = ( bit % ( 8 * sizeof ( value->element[0] ) ) );
+
+	value->element[index] |= ( 1UL << subindex );
+}
+
+/**
+ * Clear bit in big integer
+ *
+ * @v value0		Element 0 of big integer
+ * @v size		Number of elements
+ * @v bit		Bit to clear
+ */
+static inline __attribute__ (( always_inline )) void
+bigint_clear_bit_raw ( bigint_element_t *value0, unsigned int size,
+		       unsigned int bit ) {
+	bigint_t ( size ) __attribute__ (( may_alias )) *value =
+		( ( void * ) value0 );
+	unsigned int index = ( bit / ( 8 * sizeof ( value->element[0] ) ) );
+	unsigned int subindex = ( bit % ( 8 * sizeof ( value->element[0] ) ) );
+
+	value->element[index] &= ~( 1UL << subindex );
+}
+
+/**
+ * Test if bit is set in big integer
+ *
+ * @v value0		Element 0 of big integer
+ * @v size		Number of elements
+ * @v bit		Bit to test
+ * @ret is_set		Bit is set
+ */
+static inline __attribute__ (( always_inline )) int
+bigint_bit_is_set_raw ( const bigint_element_t *value0, unsigned int size,
+			unsigned int bit ) {
+	const bigint_t ( size ) __attribute__ (( may_alias )) *value =
+		( ( const void * ) value0 );
+	unsigned int index = ( bit / ( 8 * sizeof ( value->element[0] ) ) );
+	unsigned int subindex = ( bit % ( 8 * sizeof ( value->element[0] ) ) );
+
+	return ( !! ( value->element[index] & ( 1UL << subindex ) ) );
+}
+
+/**
+ * Test if most significant bit is set in big integer
+ *
+ * @v value0		Element 0 of big integer
+ * @v size		Number of elements
+ * @ret is_set		Most significant bit is set
+ */
+static inline __attribute__ (( always_inline )) int
+bigint_msb_is_set_raw ( const bigint_element_t *value0, unsigned int size ) {
+	const bigint_t ( size ) __attribute__ (( may_alias )) *value =
+		( ( const void * ) value0 );
+	unsigned int index = ( size - 1 );
+	unsigned int subindex = ( ( 8 * sizeof ( value->element[0] ) ) - 1 );
+
+	return ( !! ( value->element[index] & ( 1UL << subindex ) ) );
+}
+
+const char * bigint_ntoa_raw ( const bigint_element_t *value0,
+			       unsigned int size );
 void bigint_init_raw ( bigint_element_t *value0, unsigned int size,
 		       const void *data, size_t len );
 void bigint_done_raw ( const bigint_element_t *value0, unsigned int size,
 		       void *out, size_t len );
-void bigint_add_raw ( const bigint_element_t *addend0,
-		      bigint_element_t *value0, unsigned int size );
-void bigint_subtract_raw ( const bigint_element_t *subtrahend0,
-			   bigint_element_t *value0, unsigned int size );
-void bigint_rol_raw ( bigint_element_t *value0, unsigned int size );
-void bigint_ror_raw ( bigint_element_t *value0, unsigned int size );
+int bigint_add_raw ( const bigint_element_t *addend0,
+		     bigint_element_t *value0, unsigned int size );
+int bigint_subtract_raw ( const bigint_element_t *subtrahend0,
+			  bigint_element_t *value0, unsigned int size );
+int bigint_shl_raw ( bigint_element_t *value0, unsigned int size );
+int bigint_shr_raw ( bigint_element_t *value0, unsigned int size );
 int bigint_is_zero_raw ( const bigint_element_t *value0, unsigned int size );
 int bigint_is_geq_raw ( const bigint_element_t *value0,
 			const bigint_element_t *reference0,
@@ -311,16 +480,34 @@ void bigint_shrink_raw ( const bigint_element_t *source0,
 			 unsigned int dest_size );
 void bigint_swap_raw ( bigint_element_t *first0, bigint_element_t *second0,
 		       unsigned int size, int swap );
+void bigint_multiply_one ( const bigint_element_t multiplicand,
+			   const bigint_element_t multiplier,
+			   bigint_element_t *result,
+			   bigint_element_t *carry );
 void bigint_multiply_raw ( const bigint_element_t *multiplicand0,
 			   unsigned int multiplicand_size,
 			   const bigint_element_t *multiplier0,
 			   unsigned int multiplier_size,
 			   bigint_element_t *result0 );
-void bigint_mod_multiply_raw ( const bigint_element_t *multiplicand0,
-			       const bigint_element_t *multiplier0,
-			       const bigint_element_t *modulus0,
-			       bigint_element_t *result0,
-			       unsigned int size, void *tmp );
+void bigint_reduce_raw ( const bigint_element_t *modulus0,
+			 bigint_element_t *result0, 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 *value0,
+			     bigint_element_t *result0, unsigned int size );
+void bigint_ladder_raw ( bigint_element_t *result0,
+			 bigint_element_t *multiple0, unsigned int size,
+			 const bigint_element_t *exponent0,
+			 unsigned int exponent_size, bigint_ladder_op_t *op,
+			 const void *ctx, void *tmp );
+void bigint_mod_exp_ladder ( const bigint_element_t *multiplier0,
+			     bigint_element_t *result0, unsigned int size,
+			     const void *ctx, void *tmp );
 void bigint_mod_exp_raw ( const bigint_element_t *base0,
 			  const bigint_element_t *modulus0,
 			  const bigint_element_t *exponent0,