[crypto] Allow multiplicand and multiplier to differ in sizemult

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 839bead..29fb40a 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 103c6c4..e4b511d 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 bc4ee9a..7740f1a 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 79983b4..0d08bbd 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 f42b861..b428e22 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 89e0b86..a37ac73 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 9a25bda..74e5da9 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 7443d6f..a6bc2ca 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 2f99f84..36138dd 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 8d40c31..02568df 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,