Elliptic-curve cryptography: a finite group you can draw (Miller and Koblitz 1985)

Replace modular exponentiation with repeated addition of curve points. The public key Q=xG is easy to compute; recovering x is the discrete-log problem. Our 19-element example is small enough to solve exhaustively.

Follow repeated addition around a tiny set of points. Exhaustive search recovers the private step count here because this example is deliberately small.

import matplotlib.pyplot as plt

import blockchainkit as bk

curve = bk.crypto.TOY_CURVE
points = [(x, y) for x in range(curve.p) for y in range(curve.p) if curve.contains((x, y))]
assert len(points) + 1 == curve.order  # Include infinity.
assert bk.crypto.multiply(curve.order, curve.generator, curve) is None
public = bk.crypto.public_key(7, curve)
recovered = next(k for k in range(1, curve.order) if bk.crypto.public_key(k, curve) == public)
assert recovered == 7
print("Public key:", public, "; recovered tiny private key:", recovered)

Public key: (0, 6) ; recovered tiny private key: 7

fig, ax = plt.subplots(figsize=(6, 5))
ax.scatter(*zip(*points, strict=True), color="#2563eb", s=55)
for k in (1, 2, 3, 7):
    x, y = bk.crypto.public_key(k, curve)
    ax.annotate(f"{k}G", (x, y), xytext=(6, 6), textcoords="offset points")
ax.set(
    xlabel="x modulo 17",
    ylabel="y modulo 17",
    title="y² = x³ + 2x + 2 over F₁₇",
    xlim=(-1, 17),
    ylim=(-1, 17),
)
ax.set_aspect("equal")
ax.grid(alpha=0.2)
fig.tight_layout()

Larger parameters, same API

large_public = bk.crypto.public_key(7)  # secp256k1 by default.
assert bk.crypto.SECP256K1.contains(large_public)
print("secp256k1 public point:", bk.crypto.encode_point(large_public).hex())

plt.show()

secp256k1 public point: 045cbdf0646e5db4eaa398f365f2ea7a0e3d419b7e0330e39ce92bddedcac4f9bc6aebca40ba255960a3178d6d861a54dba813d0b813fde7b5a5082628087264da

Exercise

Verify G + (-G) = infinity and (a+b)G = aG+bG. Explain why the plot consists of isolated points rather than a smooth curve. Inspect double-and-add and identify where its control flow depends on private scalar bits.

A worked solution is in Exercises: cryptography.