RustCrypto: w-NAF scalar multiplication
w-NAF (w-ary non-adjacent form) variable-time scalar multiplication implemented generically over elliptic curve groups, including multiscalar multiplication using Straus's interleaved window method.
About
w-NAF is a signed-digit representation of a scalar with a minimal number of non-zero digits, reducing the number of costly group additions required during the double-and-add loop.
The core idea is to represent a scalar k as a sequence of digits in:
{-(2^(w-1)-1), ..., -1, 0, 1, ..., 2^(w-1)-1}
such that no two consecutive digits are non-zero.
A configurable window size trades memory for speed: a larger window precomputes more multiples
of the base point (a table of 2^(w-2) entries) but requires fewer group additions per-bit of
the scalar.
⚠️ Security Warning
w-NAF scalar multiplications should NOT be used with secret scalar values (i.e. elliptic curve private keys) because they are variable-time and can leak the secret value.
Minimum Supported Rust Version (MSRV) Policy
MSRV increases are not considered breaking changes and can happen in patch releases.
The crate MSRV accounts for all supported targets and crate feature combinations, excluding explicitly unstable features.
License
Licensed under either of:
at your option.
Contribution
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.