commit 83ac98ce22b5b735cba4d1a21db8cc8e8648dfa4
author Michael Brown <mcb30@ipxe.org> Mon Nov 25 15:59:22 2024 +0000
committer Michael Brown <mcb30@ipxe.org> Thu Nov 28 15:06:01 2024 +0000
tree e226bd3863e9b0a1d666a7f5656431f6b069b881
parent 4f7dd7fbba205d413cf9b989f7cdc928fa02caf2

[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>