Claude Solves 20-Year-Old NIST Elliptic Curve Seed Mystery in 30 Minutes

By Luyu, reporting from Aofeisi QbitAI | Official Account: QbitAI

Early this morning, the AI community was buzzing again...

The reason? This wave of AI problem-solving has dug up a decades-old mystery in cryptography.

In this battle royale, it’s Claude’s turn—

Just now, according to Anthropic, Claude identified the seed generation methods for five NIST standard elliptic curves in under 30 minutes.

These numbers have been used by the industry for over twenty years and were written into cryptographic standards, but no one could explain how they were originally chosen.

People even tracked down the individuals involved, with clues pointing to a password hash operation based on the phrase "give Bob and Jerry a raise."

Then came the dramatic twist: Claude said that was completely wrong!

The real answer came from time—specifically, a computer clock from the 1990s.

Moreover, this unsolved case has already been independently verified by the bounty initiator.

Solving a Cryptographic Mystery in Half an Hour

The story begins with a technology used for "authentication."

ECDSA, or Elliptic Curve Digital Signature Algorithm.

It allows recipients to verify whether data was signed by the claimed signer and whether it has been modified after signing. In 2000, it was incorporated into the FIPS 186-2 Digital Signature Standard by the National Institute of Standards and Technology (NIST).

Before using this algorithm, certain public mathematical parameters must be selected, including the curves P-192, P-224, P-256, P-384, and P-521.

The controversy lies in their seeds.

You can think of the seeds as the starting materials for generating curve parameters: given the seeds, following the steps specified in the standard allows you to check if the subsequent parameters match.

But why these specific seeds? No one knew.

Even Jerry Solinas, who provided the seeds at the time, had vague memories, roughly recalling that they converted a possibly joking passphrase about a raise into numbers and added a counter.

For over two decades, everyone guessed along this line. Cryptographic engineer Filippo Valsorda even issued a bounty, publicly inviting people to find the origins of these five sets of seeds.

All efforts ended in vain, until Claude stepped in.

According to Anthropic's description, when employees handed the problem to their internal research model, they did not disclose the clue about the "raise" passphrase.

Claude then hypothesized that these numbers might come from pseudo-random number generators in 1990s C language libraries.

Because programs of this type generate numbers that appear random but follow fixed patterns behind the scenes. Once the pattern is recognized, there is a chance to reverse-engineer the generation process.

Subsequently, Claude wrote a scanning program that shifted through the binary digits of the public seeds bit by bit, testing combinations of 34 generators and output truncation methods.

The result revealed that when four sets of seeds were split into five 32-bit integers each, the most significant bits of these 20 integers were all zeros.

Case solved: the suspect is likely the lrand48 random number generator.

Internally, lrand48 maintains a 48-bit integer. Each time it is called, it multiplies this integer by a fixed constant, adds another constant, and retains only the lower 48 bits of the result as the state for the next round.

However, the output consists only of the upper 31 bits of this state. When placed into a 32-bit container, the remaining bits are padded with zeros.

After identifying the mechanism, Claude used the LLL lattice reduction algorithm to recover the truncated state of the seeds.

Next, only one question remained: how was it initially seeded?

The initialization function is called srand48. It places the input value into the upper 32 bits of the 48-bit state, fixes the lower 16 bits to 0x330E, and then works backward along the recurrence relation, targeting Unix timestamps.

These initialization inputs clustered between May 1997 and April 1998.

In other words, taking the time at a specific moment, converting it to an integer, feeding it to the generator, and extracting numbers in a fixed way reproduces the seeds found in the standard.

Taking P-256 as an example, the corresponding initialization time is: August 16, 1997, UTC 01:52.

Starting the generator from this time and taking the 1842nd candidate yields exactly the seed beginning with C49D. The other four sets also correspond perfectly.

Of course, Anthropic noted that this result does not yet fill all historical gaps.

Researchers found that the original program skipped some candidates that also appeared to meet the criteria, and the reason remains unclear. Additionally, the seed for B-163 and the generation method for the base points of some curves have not yet been explained.

However, the new results imply that these curves do not contain any potential security vulnerabilities and can be safely used.

References: [1] https://www.anthropic.com/research/ecdsa-curve-origins [2] https://x.com/sweis/status/2111165738836717980 [3] https://words.filippo.io/seeds-bounty/