[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>
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 @@
* 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 @@
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 @@
* 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 @@
}
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 @@
* 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 @@
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 @@
* 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 @@
}
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 @@
* 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 @@
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 @@
* 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 @@
}
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 @@
* 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 @@
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 @@
* 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 @@
}
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 @@
* @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 @@
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_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 @@
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 @@
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,
