Elliptic curve cryptography works by defining a “point addition” operation on an elliptic curve over a finite field, then adding a public base point G to itself d times to get Q = d·G. The random integer d is the private key, and the point Q is the public key. Computing Q from d is fast, but recovering d from Q is practically impossible, and signature algorithms such as ECDSA are built on that asymmetry. Below, we work through the whole process by hand on a small curve.
What Does an Elliptic Curve Over a Finite Field Look Like?
An elliptic curve in cryptography is usually written as y² = x³ + ax + b, but every operation is taken modulo a large prime p. The curve is no longer a continuous line but a finite set of scattered integer points, and “division” becomes multiplication by a modular inverse. The points appear to be distributed with no pattern at all, which is one reason the reverse calculation is so hard.
The secp256k1 curve used by Bitcoin and Ethereum is y² = x³ + 7, with p slightly smaller than 2²⁵⁶. The standard also fixes a public base point G and its order n (adding G to itself n times returns to the “point at infinity”). Everyone shares these parameters; only the private keys differ.
How Are Points on an Elliptic Curve Added?
Geometrically, draw a line through points P and Q. It meets the curve at a third point, and reflecting that point across the x-axis gives P + Q. To add P to itself, use the tangent line instead, which is called point doubling. If two points are mirror images across the x-axis, their sum is the point at infinity, which plays the role of 0 in ordinary addition.
As formulas: for two different points the slope is λ = (y₂ − y₁) / (x₂ − x₁), and for doubling it is λ = (3x₁² + a) / (2y₁). The result is x₃ = λ² − x₁ − x₂ and y₃ = λ(x₁ − x₃) − y₁, with every step taken modulo p. The sum of any two points stays on the curve, and the operation is associative and commutative, which everything that follows depends on.
How Is a Public Key Computed From a Private Key?
The private key d is a random integer between 1 and n − 1, and the public key is Q = d·G. Since d is close to 2²⁵⁶, you cannot literally add G d times. Instead, the double-and-add algorithm writes d in binary, repeatedly doubles to get G, 2G, 4G, 8G, and so on, then adds the points whose bits are 1. For example, 13 is 1101 in binary, so 13G = 8G + 4G + G. A 256-bit private key needs at most about 256 doublings and 256 additions, which takes milliseconds.
What Does a Worked Example on a Small Curve Look Like?
Take the curve y² = x³ + 2x + 2 with all arithmetic modulo 17, and base point G = (5, 1). Check: 125 + 10 + 2 = 137, which leaves a remainder of 1 when divided by 17, equal to 1². This G has order 19, so private keys can only range from 1 to 18.
First compute 2G: λ = (3 × 25 + 2) / 2 = 77 / 2. Modulo 17, 77 equals 9 and the modular inverse of 2 is 9, so λ = 81, which reduces to 13. Then x₃ = 169 − 10 = 159, which reduces to 6, and y₃ = 13 × (5 − 6) − 1 = −14, which reduces to 3. So 2G = (6, 3).
If the private key is d = 7 (111 in binary), then 7G = 4G + 2G + G. Continuing gives 4G = (3, 1) and 4G + 2G = (16, 13), and adding G yields the public key 7G = (0, 6). It is also on the curve: 36 leaves a remainder of 2 when divided by 17, which equals 0 + 0 + 2.
Going the other way, if you only know the public key (0, 6), you can find d = 7 by computing 1G through 18G one at a time. The only difference between a real curve and this example is the size of the numbers.
Why Is It So Hard to Recover a Private Key From a Public Key?
For secp256k1, n is about 1.16 × 10⁷⁷, so trying every value is clearly out of the question. More importantly, the best known general-purpose algorithms, such as Pollard’s rho, still need roughly √n operations, or about 2¹²⁸ for a 256-bit curve. That is where “128-bit security” comes from. Because the points follow no exploitable pattern, knowing where Q is gives you no help in guessing d, which is why you cannot obtain a private key from a public key.
What Are the Steps of ECDSA Signing and Verification?
Signing: hash the transaction to get an integer z. Pick a random one-time number k, compute R = k·G, and take R’s x-coordinate modulo n as r. Then compute s = k⁻¹ × (z + r × d) modulo n. The pair (r, s) is the signature.
Verification: compute w = s⁻¹, u₁ = z × w, and u₂ = r × w, then compute the point u₁·G + u₂·Q. If the signature is valid, this point is R and its x-coordinate equals r. Only the public key Q is used; the private key d never appears. The signing formula also shows why k must stay secret and never be reused, since otherwise d can be solved for.
Conclusion
In short, on a finite-field curve it is easy to compute a public key from a private key and extremely hard to go the other way. And because a signature is just a set of algebraic operations, secure multi-party computation (MPC) can let several parties jointly produce a standard ECDSA signature from their key shares. Safeheron’s MPC Wallet-as-a-Service provides businesses with MPC key management and a policy engine.
Want your business to stop relying on a single private key for signing? Contact Safeheron’s Sales Team to Book a 1:1 Demo
Looking for a secure way to manage digital assets?
Talk to our experts and find the right solution for your business.
Request a DemoLooking for a secure way to manage digital assets?
Talk to our experts and find the right solution for your business.