]> git.ipfire.org Git - thirdparty/ipxe.git/commit
[crypto] Use inverse size as effective size for bigint_mod_invert()
authorMichael Brown <mcb30@ipxe.org>
Wed, 27 Nov 2024 12:56:22 +0000 (12:56 +0000)
committerMichael Brown <mcb30@ipxe.org>
Wed, 27 Nov 2024 13:16:05 +0000 (13:16 +0000)
commit96f385d7a48ffe259295991043a86b2cefce1891
treef32876fd70a7e1f5b182cc0dd47b28f9a57cb8c0
parent7c2e68cc87a552c153e13517b0d0d6827f48e95b
[crypto] Use inverse size as effective size for bigint_mod_invert()

Montgomery reduction requires only the least significant element of an
inverse modulo 2^k, which in turn depends upon only the least
significant element of the invertend.

Use the inverse size (rather than the invertend size) as the effective
size for bigint_mod_invert().  This eliminates around 97% of the loop
iterations for a typical 2048-bit RSA modulus.

Signed-off-by: Michael Brown <mcb30@ipxe.org>
src/include/ipxe/bigint.h
src/tests/bigint_test.c