Scalar & Attack

Scalar Multiplication

Scalar multiplication is repeated point addition. The toy rows make the first multiples visible.

highlighted = computed this step

Why scalar multiplication is repeated addition

Elliptic-curve scalar multiplication walks through repeated additions of G. The table lists the early multiples until Q appears.

kGkG
Scalar multiples of GScalar rows are recomputed until Q appears.Scalar multiples of G - recovered=3quantityvaluek=1(5,1)k=2(6,3)k=3 recovered(10,6)

Read the first multiples

The first multiples are G=(5,1), two G=(6,3), and three G=(10,6).

3G=(10,6)3G=(10,6)
Scalar multiples of GScalar rows are recomputed until Q appears.Scalar multiples of G - recovered=3quantityvaluek=1(5,1)k=2(6,3)k=3 recovered(10,6)

The cycle length

The base point has order 19, so that many additions returns to infinity.

order(G)=19\text{order}(G)=19
Scalar multiples of GScalar rows are recomputed until Q appears.Scalar multiples of G - recovered=3quantityvaluek=1(5,1)k=2(6,3)k=3 recovered(10,6)

Summary

Scalar multiplication is repeated point addition over the exact finite field. NOTE: toy-modulus; no-side-channel; no-production; never-roll-your-own. Exact point arithmetic over a deliberately tiny prime field; real ECC uses about 256-bit curves such as Curve25519 in reviewed protocols.

scalar rows recomputed\text{scalar rows recomputed}
Scalar multiples of GScalar rows are recomputed until Q appears.Scalar multiples of G - recovered=3quantityvaluek=1(5,1)k=2(6,3)k=3 recovered(10,6)