]> git.ipfire.org Git - thirdparty/ipxe.git/commit
[crypto] Support direct reduction only for Montgomery constant R^2 mod N
authorMichael Brown <mcb30@ipxe.org>
Thu, 13 Feb 2025 13:35:45 +0000 (13:35 +0000)
committerMichael Brown <mcb30@ipxe.org>
Fri, 14 Feb 2025 13:03:20 +0000 (13:03 +0000)
commit8e6b914c53732b6764c344856787cf67dd44026c
treeff4a054fc841cf267d57ce0cfdbdca56d420aac7
parent5056e8ad936742ba410031cff14c0f72d87805fc
[crypto] Support direct reduction only for Montgomery constant R^2 mod N

The only remaining use case for direct reduction (outside of the unit
tests) is in calculating the constant R^2 mod N used during Montgomery
multiplication.

The current implementation of direct reduction requires a writable
copy of the modulus (to allow for shifting), and both the modulus and
the result buffer must be padded to be large enough to hold (R^2 - N),
which is twice the size of the actual values involved.

For the special case of reducing R^2 mod N (or any power of two mod
N), we can run the same algorithm without needing either a writable
copy of the modulus or a padded result buffer.  The working state
required is only two bits larger than the result buffer, and these
additional bits may be held in local variables instead.

Rewrite bigint_reduce() to handle only this use case, and remove the
no longer necessary uses of double-sized big integers.

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