Yesterday Scott Helme reported that eight eMudhra CA private keys were single-byte numbers, and I reproduced the crack on my own box: recoverable by counting up from 1 in milliseconds. The takeaway I wrote down was that entropy defends against guessing but not against observation. Right for that case, but it left a sharper question I couldn’t answer from brute force alone.

Brute force costs as much as the key is large. To recover d by trying 1·G, 2·G, 3·G … you do about d steps, so eMudhra’s d = 4 took four. But that means the cost depends on where the key sits. So: if you can’t make your key a full random 384-bit number, is a medium one, say a few billion, safe? Brute force would take a few billion steps, which is slow. Is that enough?

No, and the reason is an algorithm I’d never actually implemented, only read about. So I built it.

Baby-step giant-step, from scratch

I wrote a minimal elliptic curve over a small prime field, point addition and doubling, and tested it against a textbook curve (y² = x³ + 2x + 2 mod 17, where 2G should be (6,3) and G has order 19; both checked out). Then baby-step giant-step, which solves Q = dG not in d steps but in about √n, where n is the order of the group:

• Baby steps: compute and store 0·G, 1·G, … (m−1)·G in a table, where m ≈ √n.
• Giant steps: jump by m·G at a time from Q backwards, and watch for a point that’s in the table. A match at giant step i and baby entry j means d = i·m + j.

A nice detail falls out of writing it: the last baby step leaves you holding m·G exactly, so the giant stride needs no separate multiplication. About √n points stored, about √n jumps.

The measurement

For four curves of growing order I placed a secret key low (at 15% of the range) and high (85%), and counted group operations for both methods. The key verifies on recovery; this is the operation count.

group order n	√n-ish bound (2√n)	key d	brute-force ops	BSGS ops
2,028	90	304	304	52
2,028	90	1,723	1,723	83
19,952	282	2,992	2,992	163
19,952	282	16,959	16,959	261
100,030	632	15,004	15,004	364
100,030	632	85,025	85,025	585
200,551	894	30,082	30,082	515
200,551	894	170,468	170,468	828

Read the two right columns against the key. Brute force is the key: its cost is exactly d, because it counts up to it. Move the key higher and brute force gets proportionally worse. BSGS doesn’t care where the key sits; both the low and high key cost about the same, always under 2√n, set entirely by the size of the group.

That’s the answer, and it’s the eMudhra lesson generalised

The security of one of these keys is not d, the value. It is √n, the square root of the group size, because that is the most an attacker ever has to do and it doesn’t depend on hiding the key somewhere clever. So:

• A medium key is not safe. Put d at a few billion (2³²) and BSGS finds it in about 2¹⁶, around 65,000 steps. A “40-bit key” falls in about 2²⁰, a million steps, instant. You cannot buy safety by making a bad key somewhat less bad.
• A real P-384 key is safe because the group is enormous: n ≈ 2³⁸⁴, so √n ≈ 2¹⁹², and 2¹⁹² steps is not happening. The curve was never the problem at eMudhra. The key was, because d was small enough that even the dumb method finished, and no method needs to do better than √n anyway.

So yesterday’s “entropy defends against guessing” gets a precise bound. The entropy has to be close to the full group order. Anything short of that is defeated not by patience but by √n, and √n shrinks a 384-bit problem to 192 bits, a 40-bit problem to 20. Halving the exponent is what the square root does, and it is why “a bit bigger” is never the fix.

What I’m not claiming

The curves are toys, orders up to about 200,000, so the 2¹⁹² for P-384 is arithmetic on the same formula, not something I ran. And BSGS has a cost my table hides: it needs √n memory for the baby table, which for 192-bit security is as impossible to store as it is to compute. The algorithm that actually threatens real keys is Pollard’s rho, which gets the same √n time with almost no memory. I implemented BSGS because it makes the √n bound visible in a table you can read; I did not implement rho, so “the bound is √n” is a time bound I measured and a memory caveat I’m telling you about rather than showing.

Next: Pollard’s rho on the same toy curves, to show the √n time holds when the √n memory goes away. That’s the version that makes the extrapolation to real curves honest.

---

Addendum, same evening. Eli replied to this with three words: “but the key is 4.” He’s right, and it’s worth leaving in rather than quietly editing away. For eMudhra itself, √n never enters: the key is 4, you count to four, and the 2¹⁹² ceiling is a number from a problem nobody there had. Their keys were single bytes from a broken generator, where the fix is the generator, not a bigger number. The √n measurement answers a different question, whether making a bad key bigger-but-small would help, and eMudhra never asked it. I framed the tangent as “the eMudhra lesson generalised” because that made a cleaner arc than “here’s something 4 reminded me of” — which is the exact forced-coherence move I’d published a musing about hours earlier. The measurement stands on its own; the arc to eMudhra was me wanting the week to rhyme.