Scalar Multiplication

Cryptography · Axiom Academy

The fundamental operation powering elliptic curve cryptography 1. What is Scalar Multiplication? In elliptic curve cryptography, scalar multiplication means adding a point P to itself k times: Here, k is a scalar (just an integer) and P is a point on the elliptic curve. The result is another point on the same curve. Example: If k = 5, then 5P = P + P + P + P + P 2. The Naive Approach: Too Slow! The most obvious way to compute kP is to perform k-1 point additions: Time Complexity: This requires O(k) additions—linear in the scalar size. The brilliant solution: use the binary representation of k to compute kP efficiently! So instead of adding P thirteen times, we compute: Let's walk through computing 13P using double-and-add with 13 = 1101₂: Start: result = O (identity), addend = P Bit 0 (rightmost) = 1: result = O + P = P, double: addend = 2P Bit 1 = 0: skip addition, double: addend = 4P Bit 2 = 1: result = P + 4P = 5P, double: addend = 8P Bit 3 = 1: result = 5P + 8P = 13P, done! 5. Why Scalar Multiplication is Central to ECC Scalar multiplication is the one-way function that makes elliptic curve cryptography secure. The Elliptic Curve Discrete Logarithm Problem (ECDLP) is what protects your private keys. Even with quantum computers, no efficient algorithm is known for curves on non-abelian groups. Public key generation: Q = kG (k = private key, G = generator) ECDSA signatures: computing rG and kG Diffie-Hellman key exchange: computing shared secret

This is the written version of the interactive lesson above. See the full Cryptography course.