Why curves need seeds

In Chapter 2, walking backward on a curve was hopeless. That's true for most curves, but mathematicians have found a few special kinds where it isn't. Three examples, in plain words:

Curves whose point count breaks into small pieces. If the number of points can be split into small factors, the backward walk can be split into small walks, each easy. That's why good curves, like P-256, have a prime number of points.

Curves that can be moved onto a clock. For certain curves, a 1993 technique by Menezes, Okamoto and Vanstone translates the curve problem into the ordinary clock problem from Chapter 1, where better attacks exist.

Curves with exactly p points. Around 1998 and 1999, several researchers showed that on these "anomalous" curves the backward walk becomes fast.

Designers check new curves for all the known weak kinds. The nagging worry is the unknown kinds. What if a designer knew about a weakness nobody else did, and quietly chose a curve that had it? That kind of planted flaw is called a backdoor.

Cryptographers have an old habit for this. When a design needs some random-looking constants, they make them in a way anyone can check, from something boring and obvious. These are called nothing-up-my-sleeve numbers, after the magician's patter.

A famous example is SHA-256, the hash function used by much of the internet today. Its 64 round constants are just the fractional parts of the cube roots of the first 64 prime numbers, written in hex. Check a few yourself:

Nobody could have tuned those numbers to hide something, because anyone can recompute them. Elliptic curves needed the same reassurance, and the ANSI X9.62 standard of the late 1990s offered a recipe for it.

The recipe uses a hash function. Think of it as a blender for data: put in any text or bytes and out comes a fixed-size, scrambled fingerprint. The same input always gives the same output. But change one letter and the output changes completely, and there's no practical way to find an input that blends into an output you picked in advance. The hash used for the NIST curves is called SHA-1, and its fingerprints are 160 bits long.

Here is how the NIST prime curves were made, following X9.62. The clock size p was chosen for speed and a was fixed at −3, also for speed. Only b was left to chance:

Because the blender can't be steered, the designer couldn't have picked b directly. Curves made this way are called verifiably random. Don't take my word for it that NIST followed the recipe. Check:

Every one of the five checks out. The published curves really did come from the published seeds, and changing a single digit of a seed breaks the match completely. The recipe works.

Here's the loophole. The recipe proves the curve came from the seed. It says nothing about where the seed came from. A designer who could pick seeds freely could blend millions of them, privately test each resulting curve for a secret weakness, and publish whichever seed gave the curve they wanted. The output would still look perfectly "verifiably random".

To show how cheap this is, the toy below shops for a seed whose fingerprint starts with a pattern of your choosing. Each extra hex digit you demand makes the search about 16 times longer.

A weak-curve property is like a pattern you're shopping for. If a fraction 1 in 2²⁰ of curves had some secret flaw, a designer would need about a million tries to land one. That's an afternoon's work, even in 1997. Some researchers have made the point vividly by publishing joke curves, produced by this very process, whose numbers spell out words like "BADA55".

So the honest answer to "can we trust these curves?" became: it depends on how much freedom the designer had when choosing the seeds. If the seeds were truly the output of some simple, fixed process, there was no room to shop. If they were picked from an unlimited supply, there was. And for the NIST curves, nobody knew which. That's the mystery.