diff options
| author | Michael Brown <mcb30@ipxe.org> | 2024-11-25 15:59:22 +0000 |
|---|---|---|
| committer | Michael Brown <mcb30@ipxe.org> | 2024-11-28 15:06:01 +0000 |
| commit | 83ac98ce22b5b735cba4d1a21db8cc8e8648dfa4 (patch) | |
| tree | e226bd3863e9b0a1d666a7f5656431f6b069b881 /src/include/ipxe | |
| parent | 4f7dd7fbba205d413cf9b989f7cdc928fa02caf2 (diff) | |
| download | ipxe-83ac98ce22b5b735cba4d1a21db8cc8e8648dfa4.tar.gz | |
[crypto] Use Montgomery reduction for modular exponentiation
Speed up modular exponentiation by using Montgomery reduction rather
than direct modular reduction.
Montgomery reduction in base 2^n requires the modulus to be coprime to
2^n, which would limit us to requiring that the modulus is an odd
number. Extend the implementation to include support for
exponentiation with even moduli via Garner's algorithm as described in
"Montgomery reduction with even modulus" (Koç, 1994).
Since almost all use cases for modular exponentation require a large
prime (and hence odd) modulus, the support for even moduli could
potentially be removed in future.
Signed-off-by: Michael Brown <mcb30@ipxe.org>
Diffstat (limited to 'src/include/ipxe')
| -rw-r--r-- | src/include/ipxe/bigint.h | 10 |
1 files changed, 2 insertions, 8 deletions
diff --git a/src/include/ipxe/bigint.h b/src/include/ipxe/bigint.h index 6c9730252..3ca871962 100644 --- a/src/include/ipxe/bigint.h +++ b/src/include/ipxe/bigint.h @@ -322,18 +322,12 @@ 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> |