Scalar Multiplication

Given a point P and integer k, scalar multiplication kP = P + P + ... + P (k times).

This is the elliptic-curve analog of g^k mod p in DH. It's the heavy lifting in ECDSA — every signature is "the public key times some scalar".

Naive: O(k) point additions. For 256-bit k, infeasible.

Double-and-add: O(log k) operations.

For 256-bit k: ~256 doublings + ~128 additions = ~384 point operations.

Side-channel issue: branch on k's bits → timing attack reveals k.

Constant-time alternatives:

• Montgomery ladder: always do double + add, just choose which result to keep.
• Window methods (wNAF): precompute a few multiples, scan k in chunks.

Always two operations per bit; bit value picks which result to advance.

Real implementations use projective/Jacobian coordinates to avoid the modular inverse per addition — only one inverse at the end.