Lesson 4 of 7 · about 8 minutes

Keys

A private key is a number. A public key is that number times the generator. Everything else in ECDSA is bookkeeping around those two facts.

Everything needed for a key pair is now on the table. A private key is a randomly chosen integer d between 1 and n − 1, where n is the number of points on the curve. A public key is the point Q = dG, where G is a generator that everyone using that curve shares and that is published in the standard.

That is the whole of key generation. One random number and one ladder. There is no key “format” involved at this stage, no prime search of the kind RSA needs, and no structure to get wrong: any integer in range is a valid private key, which is why elliptic-curve key generation is thousands of times faster than its RSA equivalent.

Why publishing Q is safe

Q is dG, and recovering d from it is the discrete logarithm from the previous lesson. On this toy curve that recovery takes eighteen additions, so nothing here is secret in any real sense — that is the point of using a curve small enough to inspect. On P-256 the same recovery is a 2¹²⁸-step search, and 2¹²⁸ steps is not a difficult problem, it is an impossible one. So Q goes into certificates, into JWKS documents, into SSH authorized_keys lines and into passkey registrations, and it can be shouted from a rooftop without consequence.

how a P-256 public key actually travels

uncompressed   04 || x || y            65 bytes
compressed     02 or 03 || x          33 bytes   (the byte says which
                                                  of the two mirrored
                                                  y values to use)
JWK            {"kty":"EC","crv":"P-256","x":"...","y":"..."}  base64url
SPKI/PEM       -----BEGIN PUBLIC KEY----- ...   DER-wrapped, with an OID
                                                naming the curve

Those are four spellings of the same pair of coordinates, and a surprising share of real-world “invalid key” errors are nothing more than one program handing another the wrong spelling. The Certificate Decoder and DER ⇄ Raw Converter exist mostly to settle those arguments.

Your turn

Turn a private key into a public key

Your private key is the scalar d = 7. The public key is the point Q = dG, with G = (5, 1) as before. Seven is 111 in binary, so the ladder is: start at G, double, add G, double, add G.

Q = 7G =

Which numbers am I allowed to use as a private key?

Any integer from 1 to n − 1, where n = 19 is the number of points. Zero is excluded because 0·G is the point at infinity, which is nobody's public key. On P-256 the same rule gives you a range of about 2²⁵⁶ values, and “pick a private key” means “draw one uniformly at random from that range” — nothing more elaborate than that, and nothing less careful, because the randomness is the whole secret.

Your turn

Now size up a real key space

On this curve there are 18 possible private keys, so an attacker tries all of them over breakfast. A P-256 private key is drawn from a range of about 2²⁵⁶ values. Suppose a machine could test a trillion candidate keys every second — one for every second in thirty thousand years, every second. How long would the search take?

A few seconds — modern hardware is fast.A few thousand years — expensive, but eventually done.Vastly longer than the age of the universe, by more than fifty orders of magnitude.It depends on the curve; P-256 keys can be searched in weeks.

The numbers, if you want to run it yourself

2^256                = 115792089237316195423570985008687907853
                       269984665640564039457584007913129639936
                     ~ 1.16 * 10^77
trillion per second  = 10^12 / s
seconds needed       ~ 1.16 * 10^65
age of the universe  ~ 4.4  * 10^17 seconds

What you now know

Private key d is a scalar in 1 … n−1; public key Q is the point dG.
Publishing Q leaks nothing usable about d, because inverting scalar multiplication is the discrete-log problem.
Real curves run identical formulas on 256-bit integers — about 10⁷⁷ possible keys.