The geometry of elliptic curves

Scalar multiplication and the discrete logarithm problem

Point addition alone does not make a cryptography. What makes it useful is repeating it — and observing that it creates a one-way function, easy to compute but nearly impossible to invert.

Multiplying a point by an integer

Adding a point P to itself several times defines scalar multiplication. For an integer k:

k·P = P + P + P + ... + P     (k times)

So 2·P = P + P, 3·P = P + P + P, and so on. The result k·P is still a point on the curve. The integer k is a scalar; it does not live on the curve, it is a plain number.

The computation is efficient

At first glance, computing k·P seems to require k additions — catastrophic if k has 77 digits. But you proceed by successive doublings, exactly like fast exponentiation.

To compute 2·P, 4·P, 8·P, ..., you simply double at each step. You then combine these powers of 2 according to the binary representation of k. Example for k = 13 = 8 + 4 + 1:

Doubling:    P → 2P → 4P → 8P        (3 doublings)
Adding:      13·P = 8·P + 4·P + P    (2 additions)

Instead of 12 additions, you make 5. For a k of 256 bits, you go from 2^256 operations (impossible) to about 380 (instantaneous). The direction k → k·P is therefore perfectly practical.

The reverse direction is infeasible

Here is the crucial point. An attacker knows the starting point P (public) and the endpoint Q = k·P (public). Can they recover the scalar k? This is the elliptic curve discrete logarithm problem (ECDLP, Elliptic Curve Discrete Logarithm Problem). And no one knows how to solve it efficiently.

There is no geometric « division » that would give k directly. The best known attacks must search through the space of possibilities: for a good 256-bit curve, on the order of 2^128 operations — beyond the reach of any machine.

   EASY (a fraction of a millisecond)
   k, P  ───────────────────────────►  Q = k·P

   INFEASIBLE (billions of billions of years)
   P, Q  ─────────────────X◄───────────  k = ?
              ECDLP: no fast algorithm known

A familiar asymmetry

We find exactly the logic of RSA: a one-way function, easy in one direction, locked in the other. RSA relies on the difficulty of factoring; elliptic curves rely on that of the ECDLP.

The big difference is efficiency: no known attack on the ECDLP is as « fast » as the modern factoring algorithms used against RSA. That is why an elliptic key can be much shorter for equal security — the subject of the next chapter.

As with RSA, this difficulty is not proven: we only observe that no one succeeds on well-chosen curves. The security is computational, not absolute. The choice of parameters is therefore never left to chance, it is set by proven standards.

In summary