[crypto] Allow multiplicand and multiplier to differ in size

Big integer multiplication is currently used only as part of modular
exponentiation, where both multiplicand and multiplier will be the
same size.

Relax this requirement to allow for the use of big integer
multiplication in other contexts.

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

10 files changed, 103 insertions, 68 deletions

diff --git a/src/arch/arm32/core/arm32_bigint.c b/src/arch/arm32/core/arm32_bigint.c
index 839bead1..29fb40a7 100644
--- a/src/arch/arm32/core/arm32_bigint.c
+++ b/src/arch/arm32/core/arm32_bigint.c
@@ -36,19 +36,23 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
  * Multiply big integers
  *
  * @v multiplicand0	Element 0 of big integer to be multiplied
+ * @v multiplicand_size	Number of elements in multiplicand
  * @v multiplier0	Element 0 of big integer to be multiplied
+ * @v multiplier_size	Number of elements in multiplier
  * @v result0		Element 0 of big integer to hold result
- * @v size		Number of elements
  */
 void bigint_multiply_raw ( const uint32_t *multiplicand0,
+			   unsigned int multiplicand_size,
 			   const uint32_t *multiplier0,
-			   uint32_t *result0, unsigned int size ) {
-	const bigint_t ( size ) __attribute__ (( may_alias )) *multiplicand =
-		( ( const void * ) multiplicand0 );
-	const bigint_t ( size ) __attribute__ (( may_alias )) *multiplier =
-		( ( const void * ) multiplier0 );
-	bigint_t ( size * 2 ) __attribute__ (( may_alias )) *result =
-		( ( void * ) result0 );
+			   unsigned int multiplier_size,
+			   uint32_t *result0 ) {
+	unsigned int result_size = ( multiplicand_size + multiplier_size );
+	const bigint_t ( multiplicand_size ) __attribute__ (( may_alias ))
+		*multiplicand = ( ( const void * ) multiplicand0 );
+	const bigint_t ( multiplier_size ) __attribute__ (( may_alias ))
+		*multiplier = ( ( const void * ) multiplier0 );
+	bigint_t ( result_size ) __attribute__ (( may_alias ))
+		*result = ( ( void * ) result0 );
 	unsigned int i;
 	unsigned int j;
 	uint32_t multiplicand_element;
@@ -62,9 +66,9 @@ void bigint_multiply_raw ( const uint32_t *multiplicand0,
 	memset ( result, 0, sizeof ( *result ) );
 
 	/* Multiply integers one element at a time */
-	for ( i = 0 ; i < size ; i++ ) {
+	for ( i = 0 ; i < multiplicand_size ; i++ ) {
 		multiplicand_element = multiplicand->element[i];
-		for ( j = 0 ; j < size ; j++ ) {
+		for ( j = 0 ; j < multiplier_size ; j++ ) {
 			multiplier_element = multiplier->element[j];
 			result_elements = &result->element[ i + j ];
 			/* Perform a single multiply, and add the
@@ -73,7 +77,7 @@ void bigint_multiply_raw ( const uint32_t *multiplicand0,
 			 * never overflow beyond the end of the
 			 * result, since:
 			 *
-			 *     a < 2^{n}, b < 2^{n} => ab < 2^{2n}
+			 *     a < 2^{n}, b < 2^{m} => ab < 2^{n+m}
 			 */
 			__asm__ __volatile__ ( "umull %1, %2, %5, %6\n\t"
 					       "ldr %3, [%0]\n\t"
diff --git a/src/arch/arm32/include/bits/bigint.h b/src/arch/arm32/include/bits/bigint.h
index 103c6c48..e4b511da 100644
--- a/src/arch/arm32/include/bits/bigint.h
+++ b/src/arch/arm32/include/bits/bigint.h
@@ -310,7 +310,9 @@ bigint_done_raw ( const uint32_t *value0, unsigned int size __unused,
 }
 
 extern void bigint_multiply_raw ( const uint32_t *multiplicand0,
+				  unsigned int multiplicand_size,
 				  const uint32_t *multiplier0,
-				  uint32_t *value0, unsigned int size );
+				  unsigned int multiplier_size,
+				  uint32_t *value0 );
 
 #endif /* _BITS_BIGINT_H */
diff --git a/src/arch/arm64/core/arm64_bigint.c b/src/arch/arm64/core/arm64_bigint.c
index bc4ee9a0..7740f1ae 100644
--- a/src/arch/arm64/core/arm64_bigint.c
+++ b/src/arch/arm64/core/arm64_bigint.c
@@ -36,19 +36,23 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
  * Multiply big integers
  *
  * @v multiplicand0	Element 0 of big integer to be multiplied
+ * @v multiplicand_size	Number of elements in multiplicand
  * @v multiplier0	Element 0 of big integer to be multiplied
+ * @v multiplier_size	Number of elements in multiplier
  * @v result0		Element 0 of big integer to hold result
- * @v size		Number of elements
  */
 void bigint_multiply_raw ( const uint64_t *multiplicand0,
+			   unsigned int multiplicand_size,
 			   const uint64_t *multiplier0,
-			   uint64_t *result0, unsigned int size ) {
-	const bigint_t ( size ) __attribute__ (( may_alias )) *multiplicand =
-		( ( const void * ) multiplicand0 );
-	const bigint_t ( size ) __attribute__ (( may_alias )) *multiplier =
-		( ( const void * ) multiplier0 );
-	bigint_t ( size * 2 ) __attribute__ (( may_alias )) *result =
-		( ( void * ) result0 );
+			   unsigned int multiplier_size,
+			   uint64_t *result0 ) {
+	unsigned int result_size = ( multiplicand_size + multiplier_size );
+	const bigint_t ( multiplicand_size ) __attribute__ (( may_alias ))
+		*multiplicand = ( ( const void * ) multiplicand0 );
+	const bigint_t ( multiplier_size ) __attribute__ (( may_alias ))
+		*multiplier = ( ( const void * ) multiplier0 );
+	bigint_t ( result_size ) __attribute__ (( may_alias ))
+		*result = ( ( void * ) result0 );
 	unsigned int i;
 	unsigned int j;
 	uint64_t multiplicand_element;
@@ -63,9 +67,9 @@ void bigint_multiply_raw ( const uint64_t *multiplicand0,
 	memset ( result, 0, sizeof ( *result ) );
 
 	/* Multiply integers one element at a time */
-	for ( i = 0 ; i < size ; i++ ) {
+	for ( i = 0 ; i < multiplicand_size ; i++ ) {
 		multiplicand_element = multiplicand->element[i];
-		for ( j = 0 ; j < size ; j++ ) {
+		for ( j = 0 ; j < multiplier_size ; j++ ) {
 			multiplier_element = multiplier->element[j];
 			result_elements = &result->element[ i + j ];
 			/* Perform a single multiply, and add the
@@ -74,7 +78,7 @@ void bigint_multiply_raw ( const uint64_t *multiplicand0,
 			 * never overflow beyond the end of the
 			 * result, since:
 			 *
-			 *     a < 2^{n}, b < 2^{n} => ab < 2^{2n}
+			 *     a < 2^{n}, b < 2^{m} => ab < 2^{n+m}
 			 */
 			__asm__ __volatile__ ( "mul %1, %6, %7\n\t"
 					       "umulh %2, %6, %7\n\t"
diff --git a/src/arch/arm64/include/bits/bigint.h b/src/arch/arm64/include/bits/bigint.h
index 79983b41..0d08bbd6 100644
--- a/src/arch/arm64/include/bits/bigint.h
+++ b/src/arch/arm64/include/bits/bigint.h
@@ -311,7 +311,9 @@ bigint_done_raw ( const uint64_t *value0, unsigned int size __unused,
 }
 
 extern void bigint_multiply_raw ( const uint64_t *multiplicand0,
+				  unsigned int multiplicand_size,
 				  const uint64_t *multiplier0,
-				  uint64_t *value0, unsigned int size );
+				  unsigned int multiplier_size,
+				  uint64_t *value0 );
 
 #endif /* _BITS_BIGINT_H */
diff --git a/src/arch/loong64/core/loong64_bigint.c b/src/arch/loong64/core/loong64_bigint.c
index f42b8611..b428e22c 100644
--- a/src/arch/loong64/core/loong64_bigint.c
+++ b/src/arch/loong64/core/loong64_bigint.c
@@ -37,19 +37,23 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
  * Multiply big integers
  *
  * @v multiplicand0	Element 0 of big integer to be multiplied
+ * @v multiplicand_size	Number of elements in multiplicand
  * @v multiplier0	Element 0 of big integer to be multiplied
+ * @v multiplier_size	Number of elements in multiplier
  * @v result0		Element 0 of big integer to hold result
- * @v size		Number of elements
  */
 void bigint_multiply_raw ( const uint64_t *multiplicand0,
+			   unsigned int multiplicand_size,
 			   const uint64_t *multiplier0,
-			   uint64_t *result0, unsigned int size ) {
-	const bigint_t ( size ) __attribute__ (( may_alias )) *multiplicand =
-		( ( const void * ) multiplicand0 );
-	const bigint_t ( size ) __attribute__ (( may_alias )) *multiplier =
-		( ( const void * ) multiplier0 );
-	bigint_t ( size * 2 ) __attribute__ (( may_alias )) *result =
-		( ( void * ) result0 );
+			   unsigned int multiplier_size,
+			   uint64_t *result0 ) {
+	unsigned int result_size = ( multiplicand_size + multiplier_size );
+	const bigint_t ( multiplicand_size ) __attribute__ (( may_alias ))
+		*multiplicand = ( ( const void * ) multiplicand0 );
+	const bigint_t ( multiplier_size ) __attribute__ (( may_alias ))
+		*multiplier = ( ( const void * ) multiplier0 );
+	bigint_t ( result_size ) __attribute__ (( may_alias ))
+		*result = ( ( void * ) result0 );
 	unsigned int i;
 	unsigned int j;
 	uint64_t multiplicand_element;
@@ -64,9 +68,9 @@ void bigint_multiply_raw ( const uint64_t *multiplicand0,
 	memset ( result, 0, sizeof ( *result ) );
 
 	/* Multiply integers one element at a time */
-	for ( i = 0 ; i < size ; i++ ) {
+	for ( i = 0 ; i < multiplicand_size ; i++ ) {
 		multiplicand_element = multiplicand->element[i];
-		for ( j = 0 ; j < size ; j++ ) {
+		for ( j = 0 ; j < multiplier_size ; j++ ) {
 			multiplier_element = multiplier->element[j];
 			result_elements = &result->element[ i + j ];
 			/* Perform a single multiply, and add the
@@ -75,7 +79,7 @@ void bigint_multiply_raw ( const uint64_t *multiplicand0,
 			 * never overflow beyond the end of the
 			 * result, since:
 			 *
-			 *     a < 2^{n}, b < 2^{n} => ab < 2^{2n}
+			 *     a < 2^{n}, b < 2^{m} => ab < 2^{n+m}
 			 */
 			__asm__ __volatile__ ( "mul.d   %1, %6, %7\n\t"
 					       "mulh.du %2, %6, %7\n\t"
diff --git a/src/arch/loong64/include/bits/bigint.h b/src/arch/loong64/include/bits/bigint.h
index 89e0b867..a37ac73c 100644
--- a/src/arch/loong64/include/bits/bigint.h
+++ b/src/arch/loong64/include/bits/bigint.h
@@ -330,7 +330,9 @@ bigint_done_raw ( const uint64_t *value0, unsigned int size __unused,
 }
 
 extern void bigint_multiply_raw ( const uint64_t *multiplicand0,
+				  unsigned int multiplicand_size,
 				  const uint64_t *multiplier0,
-				  uint64_t *value0, unsigned int size );
+				  unsigned int multiplier_size,
+				  uint64_t *value0 );
 
 #endif /* _BITS_BIGINT_H */
diff --git a/src/arch/x86/core/x86_bigint.c b/src/arch/x86/core/x86_bigint.c
index 9a25bdad..74e5da9a 100644
--- a/src/arch/x86/core/x86_bigint.c
+++ b/src/arch/x86/core/x86_bigint.c
@@ -36,19 +36,23 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
  * Multiply big integers
  *
  * @v multiplicand0	Element 0 of big integer to be multiplied
+ * @v multiplicand_size	Number of elements in multiplicand
  * @v multiplier0	Element 0 of big integer to be multiplied
+ * @v multiplier_size	Number of elements in multiplier
  * @v result0		Element 0 of big integer to hold result
- * @v size		Number of elements
  */
 void bigint_multiply_raw ( const uint32_t *multiplicand0,
+			   unsigned int multiplicand_size,
 			   const uint32_t *multiplier0,
-			   uint32_t *result0, unsigned int size ) {
-	const bigint_t ( size ) __attribute__ (( may_alias )) *multiplicand =
-		( ( const void * ) multiplicand0 );
-	const bigint_t ( size ) __attribute__ (( may_alias )) *multiplier =
-		( ( const void * ) multiplier0 );
-	bigint_t ( size * 2 ) __attribute__ (( may_alias )) *result =
-		( ( void * ) result0 );
+			   unsigned int multiplier_size,
+			   uint32_t *result0 ) {
+	unsigned int result_size = ( multiplicand_size + multiplier_size );
+	const bigint_t ( multiplicand_size ) __attribute__ (( may_alias ))
+		*multiplicand = ( ( const void * ) multiplicand0 );
+	const bigint_t ( multiplier_size ) __attribute__ (( may_alias ))
+		*multiplier = ( ( const void * ) multiplier0 );
+	bigint_t ( result_size ) __attribute__ (( may_alias ))
+		*result = ( ( void * ) result0 );
 	unsigned int i;
 	unsigned int j;
 	uint32_t multiplicand_element;
@@ -62,9 +66,9 @@ void bigint_multiply_raw ( const uint32_t *multiplicand0,
 	memset ( result, 0, sizeof ( *result ) );
 
 	/* Multiply integers one element at a time */
-	for ( i = 0 ; i < size ; i++ ) {
+	for ( i = 0 ; i < multiplicand_size ; i++ ) {
 		multiplicand_element = multiplicand->element[i];
-		for ( j = 0 ; j < size ; j++ ) {
+		for ( j = 0 ; j < multiplier_size ; j++ ) {
 			multiplier_element = multiplier->element[j];
 			result_elements = &result->element[ i + j ];
 			/* Perform a single multiply, and add the
@@ -73,7 +77,7 @@ void bigint_multiply_raw ( const uint32_t *multiplicand0,
 			 * never overflow beyond the end of the
 			 * result, since:
 			 *
-			 *     a < 2^{n}, b < 2^{n} => ab < 2^{2n}
+			 *     a < 2^{n}, b < 2^{m} => ab < 2^{n+m}
 			 */
 			__asm__ __volatile__ ( "mull %5\n\t"
 					       "addl %%eax, (%6,%2,4)\n\t"
diff --git a/src/arch/x86/include/bits/bigint.h b/src/arch/x86/include/bits/bigint.h
index 7443d6fd..a6bc2ca1 100644
--- a/src/arch/x86/include/bits/bigint.h
+++ b/src/arch/x86/include/bits/bigint.h
@@ -323,7 +323,9 @@ bigint_done_raw ( const uint32_t *value0, unsigned int size __unused,
 }
 
 extern void bigint_multiply_raw ( const uint32_t *multiplicand0,
+				  unsigned int multiplicand_size,
 				  const uint32_t *multiplier0,
-				  uint32_t *value0, unsigned int size );
+				  unsigned int multiplier_size,
+				  uint32_t *value0 );
 
 #endif /* _BITS_BIGINT_H */
diff --git a/src/include/ipxe/bigint.h b/src/include/ipxe/bigint.h
index 2f99f844..36138dd6 100644
--- a/src/include/ipxe/bigint.h
+++ b/src/include/ipxe/bigint.h
@@ -184,10 +184,11 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
  * @v result		Big integer to hold result
  */
 #define bigint_multiply( multiplicand, multiplier, result ) do {	\
-	unsigned int size = bigint_size (multiplicand);			\
+	unsigned int multiplicand_size = bigint_size (multiplicand);	\
+	unsigned int multiplier_size = bigint_size (multiplier);	\
 	bigint_multiply_raw ( (multiplicand)->element,			\
-			      (multiplier)->element, (result)->element,	\
-			      size );					\
+			      multiplicand_size, (multiplier)->element,	\
+			      multiplier_size, (result)->element );	\
 	} while ( 0 )
 
 /**
@@ -283,9 +284,10 @@ void bigint_shrink_raw ( const bigint_element_t *source0,
 			 unsigned int source_size, bigint_element_t *dest0,
 			 unsigned int dest_size );
 void bigint_multiply_raw ( const bigint_element_t *multiplicand0,
+			   unsigned int multiplicand_size,
 			   const bigint_element_t *multiplier0,
-			   bigint_element_t *result0,
-			   unsigned int size );
+			   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,
diff --git a/src/tests/bigint_test.c b/src/tests/bigint_test.c
index 8d40c318..02568dff 100644
--- a/src/tests/bigint_test.c
+++ b/src/tests/bigint_test.c
@@ -150,15 +150,17 @@ void bigint_shrink_sample ( const bigint_element_t *source0,
 }
 
 void bigint_multiply_sample ( const bigint_element_t *multiplicand0,
+			      unsigned int multiplicand_size,
 			      const bigint_element_t *multiplier0,
-			      bigint_element_t *result0,
-			      unsigned int size ) {
-	const bigint_t ( size ) *multiplicand __attribute__ (( may_alias ))
-		= ( ( const void * ) multiplicand0 );
-	const bigint_t ( size ) *multiplier __attribute__ (( may_alias ))
-		= ( ( const void * ) multiplier0 );
-	bigint_t ( size * 2 ) *result __attribute__ (( may_alias ))
-		= ( ( void * ) result0 );
+			      unsigned int multiplier_size,
+			      bigint_element_t *result0 ) {
+	unsigned int result_size = ( multiplicand_size + multiplier_size );
+	const bigint_t ( multiplicand_size ) __attribute__ (( may_alias ))
+		*multiplicand = ( ( const void * ) multiplicand0 );
+	const bigint_t ( multiplier_size ) __attribute__ (( may_alias ))
+		*multiplier = ( ( const void * ) multiplier0 );
+	bigint_t ( result_size ) __attribute__ (( may_alias ))
+		*result = ( ( void * ) result0 );
 
 	bigint_multiply ( multiplicand, multiplier, result );
 }
@@ -430,17 +432,18 @@ void bigint_mod_exp_sample ( const bigint_element_t *base0,
 	static const uint8_t multiplier_raw[] = multiplier;		\
 	static const uint8_t expected_raw[] = expected;			\
 	uint8_t result_raw[ sizeof ( expected_raw ) ];			\
-	unsigned int size =						\
+	unsigned int multiplicand_size =				\
 		bigint_required_size ( sizeof ( multiplicand_raw ) );	\
-	bigint_t ( size ) multiplicand_temp;				\
-	bigint_t ( size ) multiplier_temp;				\
-	bigint_t ( size * 2 ) result_temp;				\
+	unsigned int multiplier_size =					\
+		bigint_required_size ( sizeof ( multiplier_raw ) );	\
+	bigint_t ( multiplicand_size ) multiplicand_temp;		\
+	bigint_t ( multiplier_size ) multiplier_temp;			\
+	bigint_t ( multiplicand_size + multiplier_size ) result_temp;	\
 	{} /* Fix emacs alignment */					\
 									\
-	assert ( bigint_size ( &multiplier_temp ) ==			\
-		 bigint_size ( &multiplicand_temp ) );			\
 	assert ( bigint_size ( &result_temp ) ==			\
-		 ( 2 * bigint_size ( &multiplicand_temp ) ) );		\
+		 ( bigint_size ( &multiplicand_temp ) +			\
+		   bigint_size ( &multiplier_temp ) ) );		\
 	bigint_init ( &multiplicand_temp, multiplicand_raw,		\
 		      sizeof ( multiplicand_raw ) );			\
 	bigint_init ( &multiplier_temp, multiplier_raw,			\
@@ -1373,6 +1376,12 @@ static void bigint_test_exec ( void ) {
 			     BIGINT ( 0x67, 0x3c, 0x5a, 0x16 ),
 			     BIGINT ( 0x3c, 0xdb, 0x7f, 0xae, 0x12, 0x7e,
 				      0xef, 0x16 ) );
+	bigint_multiply_ok ( BIGINT ( 0x39, 0x1f, 0xc8, 0x6a ),
+			     BIGINT ( 0xba, 0x39, 0x4a, 0xb8, 0xac, 0xb3,
+				      0x4f, 0x64, 0x28, 0x46, 0xa6, 0x99 ),
+			     BIGINT ( 0x29, 0x8d, 0xe0, 0x5d, 0x08, 0xea,
+				      0x0d, 0xc7, 0x82, 0x5d, 0xba, 0x96,
+				      0x1c, 0xef, 0x83, 0x5a ) );
 	bigint_multiply_ok ( BIGINT ( 0xe8, 0x08, 0x0b, 0xe9, 0x29, 0x36,
 				      0xea, 0x51, 0x1d, 0x75, 0x1a, 0xd5,
 				      0xba, 0xc6, 0xa0, 0xf3, 0x48, 0x5c,