]> git.ipfire.org Git - thirdparty/ipxe.git/commit
[crypto] Eliminate temporary carry space for big integer multiplication
authorMichael Brown <mcb30@ipxe.org>
Thu, 26 Sep 2024 15:24:57 +0000 (16:24 +0100)
committerMichael Brown <mcb30@ipxe.org>
Fri, 27 Sep 2024 12:51:24 +0000 (13:51 +0100)
commit3f4f843920afdc1d808a8b20354cf3eca481401a
tree278f1835a8dd7b60857f0833bfe4e0702beb1015
parent8844a3d5464c4632a1374cbb9304aeea61d0166f
[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>
src/arch/arm32/include/bits/bigint.h
src/arch/arm64/include/bits/bigint.h
src/arch/loong64/include/bits/bigint.h
src/arch/riscv/include/bits/bigint.h
src/arch/x86/include/bits/bigint.h
src/crypto/bigint.c
src/crypto/x25519.c
src/include/ipxe/bigint.h
src/tests/bigint_test.c