Reverse-Engineering NIST ECDSA Curve Seeds: How Claude Solved a 25-Year Cryptographic Mystery
For twenty-five years, a shadow of suspicion hung over the foundations of the modern internet. The elliptic curves standardized by the National Institute of Standards and Technology (NIST)—specifically the P-series (P-192, P-224, P-256, P-384, and P-521)—are the bedrock of the Elliptic Curve Digital Signature Algorithm (ECDSA). They secure everything from TLS handshakes to government communications. Yet, the origin of the “seeds” used to generate these curves remained a total mystery. Unlike “nothing-up-my-sleeve” numbers, such as the digits of pi or e, these seeds appeared to be random strings of hex digits.
The lack of transparency led to decades of cryptanalytic anxiety. In the post-Snowden era, after the revelation of the Dual_EC_DRBG backdoor, many feared that the NSA had carefully selected these seeds to create an algebraic trapdoor—a “backdoor” that would allow them to break ECDSA without anyone noticing. Rumors swirled about the late Jerry Solinas, an NSA mathematician, supposedly using passphrase hashes like “Give Bob and Jerry a raise” to generate the constants.
That cold case was finally closed recently. In an astonishing display of software archaeology and automated reasoning, researchers at Anthropic used Claude to reverse-engineer the seeds in under 30 minutes. By identifying the exact pseudo-random number generator (PRNG) and the specific Unix timestamps used in the late 1990s, the team proved that these curves were not the product of a sophisticated conspiracy, but rather the result of standard C library functions and a very specific moment in time.
Deconstructing the NIST Curve Derivation: Math, Seeds, and SHA-1
To understand the breakthrough, we first have to look at how these curves are defined. NIST curves are defined over prime fields $F_p$ using the short Weierstrass equation:
\[y^2 = x^3 - 3x + b\]In this equation, the coefficient $-3$ is chosen for efficiency reasons, but the parameter $b$ is the variable that defines the curve’s specific properties. To ensure the curve is secure, $b$ must be chosen such that the curve is resistant to known attacks (like the Rho method or MOV attack).
NIST’s process for generating $b$ involved a “seed” value $s$. According to the FIPS 186-2 and ANSI X9.62 standards, the process worked like this:
- Take an arbitrary input seed $s$.
- Hash the seed using SHA-1.
- Use the hash output to derive the curve constant $b$ via a deterministic algorithm.
The problem was that NIST never explained where $s$ came from. In cryptography, we prefer “nothing-up-my-sleeve” numbers. If a developer uses the first 1,000 digits of $\pi$ as a seed, we can be reasonably sure they didn’t brute-force the seed to find a weak curve. But if the seed is bd713447 99d5c7fc dc45b59f d61efc33 73d6627e, as it is for P-256, we have no idea why that specific value was chosen. This lack of verifiable provenance is exactly what fueled the “backdoor” theories for a quarter-century.
Software Archaeology: Unmasking lrand48 and 1990s Unix Timestamps
The breakthrough began when the researchers moved away from the idea of “passphrase hashing” and started looking at the tools available to a developer in 1997. They hypothesized that the seeds weren’t hashes of text, but rather the output of a standard C-library PRNG.
Specifically, they looked at lrand48, a popular Linear Congruential Generator (LCG) found in the POSIX standard. The architecture of lrand48 is defined by the recurrence relation:
Where:
- $a = \text{0x5DEECE66D}$
- $c = \text{0xB}$
When a developer calls srand48(t) to seed the generator with a value $t$ (usually a Unix timestamp), the internal 48-bit state is initialized by setting the high 32 bits to $t$ and the low 16 bits to a fixed constant, 0x330E.
By feeding these parameters into Claude and asking it to look for patterns in the NIST seeds, the AI quickly identified a correlation. The seeds for the prime curves (P-192 through P-521) weren’t random; they were sequential outputs of lrand48.
The researchers discovered that the seeds mapped perfectly to Unix timestamps from the late 90s. For instance:
- P-192: Generated around May 1997.
- P-256: Generated around late 1997/early 1998.
Even more interesting were the binary curves (B-233, B-283, B-409, B-571). These seeds appeared to originate from a single day: April 17, 1998. However, there was a twist—the researchers found that the seeds were generated by taking the Unix timestamp for that day and halving it before passing it to the PRNG. This kind of idiosyncratic “programmer logic” is exactly what makes manual reverse engineering difficult but is often detectable by LLMs trained on vast amounts of legacy code.
| Curve | Seed Origin Type | Estimated Date |
|---|---|---|
| P-192 | lrand48 (Unix Timestamp) |
May 1997 |
| P-256 | lrand48 (Unix Timestamp) |
Late 1997 |
| B-233 | lrand48 (Halved Timestamp) |
April 17, 1998 |
| B-409 | lrand48 (Halved Timestamp) |
April 17, 1998 |
Lattice Cryptanalysis: Reconstructing Truncated LCG State with LLL
Identifying the PRNG was only half the battle. To prove the hypothesis, the researchers had to show they could recover the exact internal state of the generator from the seeds. This is a classic problem in cryptanalysis known as recovering the state of a truncated LCG.
Because the NIST seeds are the result of hashing the PRNG output, and we only see the seeds, we are looking at a “truncated” state. We don’t see the full 48-bit internal state $X_n$; we only see the results derived from it. To solve this, the researchers turned to lattice-based cryptanalysis, specifically the Lenstra–Lenstra–Lovász (LLL) reduction algorithm.
The problem can be formulated as a Closest Vector Problem (CVP). Given a sequence of outputs $y_1, y_2, \dots, y_k$, we want to find an initial state $X_0$ such that the generated sequence matches our observations. We construct a lattice basis matrix $L$ that represents the linear relations of the LCG:
\[L = \begin{pmatrix} 2^{48} & 0 & \dots & 0 \\ a & -1 & \dots & 0 \\ a^2 & 0 & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ a^k & 0 & \dots & -1 \end{pmatrix}\]By applying LLL reduction to this matrix (often using tools like SageMath or the Number Theory Library, NTL), the “shortest” vectors in the lattice reveal the hidden bits of the PRNG state. In the case of the NIST seeds, the LLL algorithm was able to extract the exact 48-bit state in milliseconds. This provided the “smoking gun” proof: the seeds were indeed generated by lrand48 seeded with specific timestamps.
The FreeLIP Artifact: Solving the Base Point Generation Mystery
While the curve parameter $b$ was derived from lrand48, the curves also require a base point $G$ (a generator point). The origin of these points was another point of contention. The research revealed that for P-192 and the ANSI X9.62 example curves, the base points were generated using a different tool: Arjen Lenstra’s FreeLIP library.
FreeLIP was a widely used long-integer package in the 90s. The researchers found that the PRNG within FreeLIP was being initialized with very small, non-random integer counters. For P-192, the counter was 20000.
This discovery highlights a common theme in legacy cryptography: the use of “convenience constants.” Instead of searching for a truly random starting point, the developers likely picked a round number that worked and moved on.
However, the “archaeology” isn’t entirely complete. While the seeds for most P and B curves are solved, the seed for the binary curve B-163 and the base points for the larger P-curves (P-224, P-256, P-384, and P-521) still exhibit unidentified generation sources. They don’t follow the lrand48 or FreeLIP patterns perfectly, suggesting that either a different library was used or the developers changed their methodology mid-project.
Claude as Cryptanalyst: Directing LLMs for Automated Reverse Engineering
What makes this discovery a landmark event isn’t just the cryptographic result, but the method. The Anthropic researchers didn’t manually grind through every possible C library from 1995. Instead, they used Claude as a high-level reasoning engine to guide the search.
The workflow involved several key steps:
- Framing the Search Space: The researchers prompted Claude to hypothesize about the development environment at NIST/NSA in the late 90s. Claude suggested looking at POSIX-compliant C libraries and standard PRNGs like
lrand48. - Iterative Hypothesis Generation: When initial brute-force attempts on passphrases failed, the team used Claude to analyze the mathematical structure of the seeds. Claude helped identify that the seeds looked like outputs of a linear congruential generator rather than high-entropy SHA-1 hashes of long strings.
- Automated Code Synthesis: One of the most powerful aspects of the process was Claude’s ability to write the complex lattice reduction scripts required for the LLL analysis. Claude generated SageMath code that formulated the LCG state recovery as a lattice problem, which the researchers then executed to verify the timestamps.
This represents a significant shift in how we approach software archaeology. As discussed in our guide on Anthropic Claude’s architecture, the model’s ability to maintain a “constitutional” adherence to logical rigor allows it to perform technical tasks that go far beyond simple pattern matching.
By treating the LLM as a collaborator that can synthesize historical context with mathematical expertise, the researchers were able to solve in 30 minutes what the cryptographic community couldn’t solve in 25 years. This has massive implications for auditing legacy systems and identifying vulnerabilities in CI/CD pipelines where legacy code often hides in plain sight.
Security Impact: Dispelling Backdoors and Bridging to Post-Quantum Cryptography
The most immediate impact of this discovery is the definitive dismissal of the “NSA Backdoor” theory for NIST P-256 parameter generation. We now know that the seeds were not chosen because they had special algebraic properties that the NSA could exploit; they were chosen because a computer’s clock happened to be at a certain value on a Tuesday in 1997.
This resolution led to the closure of a community bounty organized by cryptographer Filippo Valsorda. The bounty, totaling $36,864, is being donated to the Internet Security Research Group (ISRG), the non-profit behind Let’s Encrypt.
However, does this mean we can stop worrying about elliptic curve security? Not quite. While the derivation of these curves is now transparent, the curves themselves are still vulnerable to future threats—specifically, Shor’s algorithm running on a sufficiently powerful quantum computer.
The discovery provides operational assurance for legacy FIPS 186-2 deployments, but it doesn’t change the migration trajectory. Organizations must still transition to Post-Quantum Cryptography (PQC) standards like ML-KEM (formerly Kyber) and ML-DSA (formerly Dilithium). The integrity of P-256 is a relief for the present, but it is not a solution for the future.
Furthermore, this case serves as a lesson for future standards. The “nothing-up-my-sleeve” requirement is now non-negotiable. Modern standards, such as those for Ed25519, use deterministic, transparent processes that leave no room for 25-year mysteries. Just as we look at LLM watermarking to ensure the provenance of AI-generated content, we must ensure the provenance of mathematical constants.
Conclusion and Future Outlook: Machine Intelligence in Formal Cryptanalysis
The resolution of the NIST curve seed mystery marks a turning point in the intersection of AI and security. It proves that advanced LLMs like Claude are no longer just “chatbots”—they are becoming sophisticated tools for formal cryptanalysis and historical mathematical forensics.
We are entering an era where AI-driven automated reasoning can audit the “mathematical infrastructure” of our world. Whether it’s finding bugs in legacy COBOL banking systems or verifying the constants in a cryptographic standard, the ability of AI to bridge the gap between human intuition and brute-force computation is transformative.
As we look forward, we can expect:
- Automated Auditing: Standards bodies will use LLMs to “red team” new constants and algorithms before they are published.
- Historical Forensics: More “unexplained” constants in legacy software will be traced back to their origins, cleaning up decades of technical debt and suspicion.
- Zero-Knowledge Standards: Future cryptographic parameters will likely be generated via multi-party computation (MPC) or other verifiable means that provide a mathematical proof of “nothing-up-my-sleeve.”
The 25-year mystery of the NIST seeds didn’t end with a bang or a high-stakes spy reveal. It ended with a 48-bit LCG and a Unix timestamp. In the world of cryptography, that is the best possible ending: the realization that the “ghost in the machine” was just a standard library function all along.