AI Solves 25-Year NSA Cryptography Mystery

An advanced research model from Anthropic, named Claude, has successfully traced the origins of five crucial NSA-supplied elliptic curve seeds, a puzzle that had remained unsolved for approximately 25 years. The AI achieved this feat in under 30 minutes, providing historical clarity on how these important public security parameters were generated. This breakthrough does not represent a cryptographic break or expose any new vulnerabilities, but rather demystifies the selection process for widely used cryptographic standards.

The seeds in question are integral to NIST's widely adopted elliptic curve cryptography standards, specifically NIST curves P-192, P-224, P-256, P-384, and P-521. These curves are foundational for the Elliptic Curve Digital Signature Algorithm (ECDSA), a standard for digital signatures used to verify data integrity and authenticity. While NIST adopted ECDSA in its FIPS 186-2 standard in 2000, the origin of the seeds used in the SHA-1-based process to derive curve parameters was never explicitly documented by the NSA, leading to speculation and theories.

For years, cryptographers and researchers debated the source of these seeds. A prominent theory, recalled by former NSA mathematician Jerry Solinas, suggested the values might have been derived from hashes of humorous phrases, such as “Give Bob and Jerry a raise.” This theory, while intriguing, lacked concrete evidence and left a lingering question mark over the security parameters. The lack of a clear explanation fueled concerns, albeit unsubstantiated by any demonstrated attack, that the NSA might have intentionally embedded hidden weaknesses into these curves.

Claude's approach differed significantly from the phrase-hashing theory. Instead, the AI focused on identifying common random-number generators used in software during the 1990s. It employed a scanner to analyze 34 combinations of generators and output slices, searching for discernible patterns within the published seeds. The AI observed that some binary-curve seeds consistently had a zero in the highest bit of their 32-bit words, a characteristic matching the output of lrand48, an older C library random-number generator known to produce 31 bits of randomness from a 48-bit internal state.

By testing potential hidden bits within the generator's state and verifying subsequent outputs, Claude successfully recovered candidate states. For the prime-curve seeds, which retained only eight bits from each generator output, Claude utilized the Lenstra–Lenstra–Lovász (LLL) lattice reduction algorithm to reconstruct the internal states from these partial values. This meticulous process led to matches with the same construction for five NIST seeds and five ANSI X9.62 example seeds.

Further analysis by Claude revealed that the initialization values for these generators corresponded to Unix timestamps between May 1997 and April 1998. For instance, the published seed for P-256 was identified as the 1,842nd candidate generated from a run initialized on August 16, 1997, at 01:52:34 UTC. The AI also found that four binary-curve seeds appeared to be derived from a clock value divided by two, though this interpretation is noted as a possibility rather than a confirmed fact.

Anthropic has emphasized that this discovery is not a cryptographic break, nor does it reveal any new attacks or weaknesses in ECDSA. The identified seeds are public curve-generation parameters, not private signing keys, and their reconstruction does not enable attackers to forge signatures. The researchers suggest that the simple and repeatable generation process makes deliberate manipulation less plausible. While the findings strengthen confidence in the selection of these curves, the report acknowledges that not all aspects are fully explained, such as the unexplained seed for B-163 and certain base points. Anthropic has released reproduction code to allow for independent verification of their findings.