diff options
| author | Michael Brown <mcb30@ipxe.org> | 2024-09-26 16:24:57 +0100 |
|---|---|---|
| committer | Michael Brown <mcb30@ipxe.org> | 2024-09-27 13:51:24 +0100 |
| commit | 3f4f843920afdc1d808a8b20354cf3eca481401a (patch) | |
| tree | 278f1835a8dd7b60857f0833bfe4e0702beb1015 /src/include/ipxe/bigint.h | |
| parent | 8844a3d5464c4632a1374cbb9304aeea61d0166f (diff) | |
| download | ipxe-3f4f843920afdc1d808a8b20354cf3eca481401a.tar.gz | |
[crypto] Eliminate temporary carry space for big integer multiplication
An n-bit multiplication product may be added to up to two n-bit
integers without exceeding the range of a (2n)-bit integer:
(2^n - 1)*(2^n - 1) + (2^n - 1) + (2^n - 1) = 2^(2n) - 1
Exploit this to perform big integer multiplication in constant time
without requiring the caller to provide temporary carry space.
Signed-off-by: Michael Brown <mcb30@ipxe.org>
Diffstat (limited to 'src/include/ipxe/bigint.h')
| -rw-r--r-- | src/include/ipxe/bigint.h | 14 |
1 files changed, 4 insertions, 10 deletions
diff --git a/src/include/ipxe/bigint.h b/src/include/ipxe/bigint.h index efe156596..bcb7af5ec 100644 --- a/src/include/ipxe/bigint.h +++ b/src/include/ipxe/bigint.h @@ -208,15 +208,13 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); * @v multiplicand Big integer to be multiplied * @v multiplier Big integer to be multiplied * @v result Big integer to hold result - * @v carry Big integer to hold temporary carry space */ -#define bigint_multiply( multiplicand, multiplier, result, carry ) do { \ +#define bigint_multiply( multiplicand, multiplier, result ) do { \ unsigned int multiplicand_size = bigint_size (multiplicand); \ unsigned int multiplier_size = bigint_size (multiplier); \ bigint_multiply_raw ( (multiplicand)->element, \ multiplicand_size, (multiplier)->element, \ - multiplier_size, (result)->element, \ - (carry)->element ); \ + multiplier_size, (result)->element ); \ } while ( 0 ) /** @@ -247,10 +245,7 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); unsigned int size = bigint_size (modulus); \ sizeof ( struct { \ bigint_t ( size * 2 ) temp_result; \ - union { \ - bigint_t ( size * 2 ) temp_modulus; \ - bigint_t ( size * 2 ) temp_carry; \ - }; \ + bigint_t ( size * 2 ) temp_modulus; \ } ); } ) /** @@ -324,8 +319,7 @@ 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, - bigint_element_t *carry0 ); + bigint_element_t *result0 ); void bigint_mod_multiply_raw ( const bigint_element_t *multiplicand0, const bigint_element_t *multiplier0, const bigint_element_t *modulus0, |