mirror of
https://github.com/ipxe/ipxe.git
synced 2025-01-06 14:03:09 -06:00
iPXE network bootloader
83ba34076a
Classic Montgomery reduction involves a single conditional subtraction to ensure that the result is strictly less than the modulus. When performing chains of Montgomery multiplications (potentially interspersed with additions and subtractions), it can be useful to work with values that are stored modulo some small multiple of the modulus, thereby allowing some reductions to be elided. Each addition and subtraction stage will increase this running multiple, and the following multiplication stages can be used to reduce the running multiple since the reduction carried out for multiplication products is generally strong enough to absorb some additional bits in the inputs. This approach is already used in the x25519 code, where multiplication takes two 258-bit inputs and produces a 257-bit output. Split out the conditional subtraction from bigint_montgomery() and provide a separate bigint_montgomery_relaxed() for callers who do not require immediate reduction to within the range of the modulus. Modular exponentiation could potentially make use of relaxed Montgomery multiplication, but this would require R>4N, i.e. that the two most significant bits of the modulus be zero. For both RSA and DHE, this would necessitate extending the modulus size by one element, which would negate any speed increase from omitting the conditional subtractions. We therefore retain the use of classic Montgomery reduction for modular exponentiation, apart from the final conversion out of Montgomery form. Signed-off-by: Michael Brown <mcb30@ipxe.org> |
||
|---|---|---|
| .github/workflows | ||
| contrib | ||
| src | ||
| COPYING | ||
| COPYING.GPLv2 | ||
| COPYING.UBDL | ||
| README | ||
iPXE README File Quick start guide: cd src make For any more detailed instructions, see http://ipxe.org