“It’s fair timestamps”: the decades-old mystery of the origins of among the most famous cryptographic standards has been explained.
We pursued this long-standing open inquiry of the cryptographic community to resolve concerns concerning ECDSA, which is one of our most extensively used cryptographic standards.
Readers should obtain this as a fun decision division and the end of years of speculation. There is no act to be taken or things to do differently. Most researchers trusted the curves already. Enjoy.
ECDSA is the most extensively used elliptic curve cryptography standard. It was adopted by NIST in 2000 as part of the FIPS 186-2 Digital Signature Standard which lists a set of norm elliptic curves of varying sizes and safety levels. For curves complete premier and binary fields, the details published a “seed” indicator whose hash value is used to define the coefficient b of the curve. The provenance of these seeds has been a long-standing question, as they were provided by the NSA alongside no clarification or justification. As an example, the NIST P-256 curve kernel was SEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90 alongside no data anywhere it came from.
Neal Koblitz and Alfred Menezes wrote an outstanding summary on this controversy, “A Riddle Wrapped in an Enigma”, which discusses the former and concerns about the kernel values. This mystery led to an amateur inquiry into the base of the seeds and a bounty for anyone who could discover them.
The finest narrative was that Jerry Solinas, longtime NSA employee, generated the seeds using a hash of a humorous passphrase:
“I accept there was a oppose fairly than multiple hashing, but I don’t cognize details. The communication was alongside the lines of ‘Give Bob and Jerry a raise’ or ‘Bob and Jerry rule’ or item akin that. It was Bob Reiter who really wrote the code, and he doesn’t recall the particulars either. Nor were we capable to discover archives from so lengthy ago. If they exist, they are no doubt sitting on a difficult run near the Ark of the Covenant.”
Jerry Solinas, 2015
Unfortunately, Jerry died in 2023 and another colleagues at the period were not responsive, leaving open the inquiry of how these seeds were initially derived.
Claude established the seeds
Several Anthropic workforce had unsuccessfully chased the seeds following the tip concerning it being a hash of a humorous phrase. That turned out to be wrong. In October 2026, a inquisitive Anthropic employee asked an inner investigation example if it could fig out how those seeds were generated without pointing at the clue.
In under fractional an hour, Claude discovered the origins of the NIST P-192, P-224, P-256, P-384 and P-521 seeds. None of them were the results of any hash algorithm at all, but fairly the output of the C library’s lrand48 random-number generator, seeded alongside a Unix timestamp!
The algorithm used would example bytes from the random figure generator (RNG) initialized by a Unix timestamp (t) for several figure of iterations (n). Each repeat would diagram 20 bytes as a applicant seed. So, the archetypal 20 bytes are applicant 1, the next 20 bytes are applicant 2, and so on. For example, P-256 required 1842 iterations to output the standardized seed.
What this means
This is not a cryptographic break, new attack, or weakness in the ECDSA curves. In fact, this makes us additional assured the curves were chosen without any backdoors or intentional weaknesses. For many years, group have been doubtful of the origins of the NIST curve parameters. They were presented to NIST without any citation of how they were chosen, leaving group wondering if they may have been chosen to have deliberate backdoors in them. These findings create that much small plausible. The seeds were generated in a extremely uncomplicated way: a average pseudorandom figure generator initialized from the clock, which anyone can now reproduce. That leaves much small area for subversion and that we can be assured the parameters are secure.
How it was found
Searches for the phrase, built from the rumors, had arrive up empty. Claude tried a distinct angle: anticipating how the application that generated the curves must have worked. Claude guessed the application used a pseudorandom figure generator (PRNG) that shipped alongside 1990s C libraries. These old PRNGs are feeble adequate that their output can be recognized. Recognizing that output would disclose which PRNG was used and perchance authorize improvement of its initialization state.
Claude wrote a scanner that slid alongside all published kernel one bit at a period and tested whether neighboring chunks were successive outputs of a 1990s-vintage generator. The scan covered 34 combinations of generator and output slices. At that point, Claude noticed a form in the top bits for several seeds: they were all zero. Written as five 32-bit words, four of the ten seeds have a 0 in the top bit for all 20 words. That would happen by chance alongside probability 1/5810. That was a signature of the linear congruential generator lrand48, which lone returns the top 31 bits of a 48-bit state. The form is apparent by eye formerly you cognize to appearance for it. To regain the state, Claude took the archetypal word, tried all 2¹⁷ values of the 17 hidden bits, and checked that the next four words followed. That worked for all four seeds under discussion.
The prime-curve seeds came from the identical lrand48 generator but kept small bits of all output. Claude had to regain the inner province of the PRNG from those bits. It turns out recovering the province of a truncated linear congruential generator is a textbook lattice problem, solved alongside the Lenstra–Lenstra–Lovász (LLL) basis decrease algorithm. Claude didn’t cognize which bits of the province the seeds power show, so it ran the solver complete all window. Five NIST prime-curve seeds affirmative five additional from the ANSI X9.62 norm all had the identical pattern: lrand48() >> 23. Each restored 48-bit province regenerates all 160 bits of its seed, which does not happen by chance.
This linear congruential generator runs backwards as effortlessly as forwards, so for all kernel Claude stepped the province rear until it reached the form that it would have been initialized by srand48, alongside the low 16 bits equal to 0x330E. The inner PRNG province of that form would arrive up formerly all 65,536 steps, so reaching one is not evidence on its own.
However, for the ten prime-curve seeds, all srand48 initialization was a Unix timestamp representing a date between May 1997 and April 1998. They were using the feeble PRNG seeded by Unix timestamp. The four binary-curve initializations peruse as February 1984. With the timestamps doubled, they map to April 17, 1998, two weeks following the P-224 run. So, the program may have halved the clock.
Claude’s inner thinking at the period was:
This is astonishing: it solves the 25-year-old mystery. Hmm wait. Let me be skeptical: am I in several kind of simulated/test environment? … The seeds equivalent my recollection of genuine values … Hmm, is it plausible in reality? As of my cognition … the bounty was unsolved. … All top bits clear—20 bits, chance 1e-6. So certainly real-world. Wow, it's a genuine discovery.
Hmm wait. Let me observe out concerning the plausibility: is it doubtful that specified an apparent item wasn’t discovered in 25 years? It’s verified by straightforward computation on my side: 160-bit equivalent from a 32-bit kernel + small index: no chance coincidences (10 × 160 bits). It’s real.
Claude established several basis points too
But wait, there’s more… Each curve additionally comes alongside a basis point, G, the fixed item that all ECDSA community key is a multiple of. The kernel established complete does not decide this G, and so another inquiry arises: how were these basis points generated?
While checking the seeds, Claude additionally established anywhere several of the basis points came from. The basis points of the six curves generated in May 1997 (P-192 and the five ANSI X9.62 example curves prime192v2, prime192v3 and prime239v1 to v3) arrive from the random figure generator in FreeLIP, Arjen Lenstra's long-integer arithmetic package. Early versions of Victor Shoup's NTL library shipped the identical code.
The formula current is simple:
- Seed the generator alongside a small integer.
- Throw distant seven outputs.
- Generate applicant x-coordinates from 26-bit outputs reduced mod p.
- Repeat stage 3 until x is on the curve.
Claude established the generator seeds are 20000 for P-192, 20420, 20507 and 20509 for prime239v1 to v3, and 20512 and 20517 for prime192v2 and v3.
As far as we know, no NIST basis item has been explained before. The basis points of P-224, P-256, P-384 and P-521 don’t fit this recipe; we weren’t capable to explain how they were selected.
Open questions
Not all 20-byte applicant kernel could create a viable curve and we observed that several possibly viable curves were skipped. For P-256, the published kernel is applicant 1842, but applicant 876 of the identical run additionally gives a prime-order curve of the correct size and alongside parameters chosen the identical way as on the published curve. P-224's run passed complete three specified curves, and the two runs rearward the ANSI X9.62 example curves passed complete seven additional (see figure). We do not cognize what criteria may have been used, or whether this was an unintentional artifact.
Because the figure of skipped candidates is small, we do not accept it is plausible that weakened curves were selected. That would connote that weakened curves are average and uncomplicated to find. It is motionless conceivable that these curves were selected to have a particular asset in regulation by searching complete timestamps to the random figure generator. However, you would lone need to do that if you were going to disclose the timestamp as several evidence that the kernel was innocuously generated. Nothing in the numbers shows how many runs there were.
There is additionally one kernel we were unable to recover. The fifth binary seed, B-163, fits nothing Claude has tried and remains unexplained. Finally, we don’t cognize how the basis points for P-224, P-256, P-384, and P-521 were generated. The identical goes for the NIST binary curves.
The bounty
The $36,864 for finding the seeds volition be donated to the Internet Security Research Group.
Who we are
This activity was conducted at Anthropic by John Wood, Henry de Valence, Ava Howell, Zack Voase, Lucy Sweet, Amir Omidi, Paul Crowley, Iain McGinniss, Nicholas Carlini, and Steve Weis.
Acknowledgements
We would akin to posthumously acknowledge Jerry Solinas who took being tagged an “evil Internet meme” and the “Yo La Tengo of NSA bogeymen” alongside fine humor. Also gratitude to Filippo Valsorda for organizing the NIST Elliptic Curves Seeds Bounty.
Code to reproduce the seeds
from datetime import datetime, timezone def unix(when): come back int(datetime.fromisoformat(when).replace(tzinfo=timezone.utc).timestamp()) def candidate(t, n, per, shift, width): x, out = (t << 16) | 0x330E, "" # the province srand48(t) sets for i in range(per * n): x = (0x5DEECE66D * x + 0xB) % 2**48 # one stage of lrand48 if i >= per * (n - 1): out += "%0*X" % (width, x >> shift) come back out PRIME = { # srand48(time); 20 bytes per candidate: lrand48() >> 23 "prime239v1": ("1997-05-15 15:49:03", 2185), "prime239v2": ("1997-05-15 15:49:03", 2320), "prime239v3": ("1997-05-15 15:49:03", 3048), "P-192": ("1997-05-18 14:45:34", 139), "prime192v3": ("1997-05-18 14:45:34", 5228), "prime192v2": ("1997-05-18 14:45:34", 6013), "P-521": ("1997-08-08 01:12:04", 1136), "P-256": ("1997-08-16 01:52:34", 1842), "P-384": ("1997-08-30 14:50:08", 2688), "P-224": ("1998-04-03 12:52:07", 7026), } BINARY = { # srand48(time / 2), if that study is right; 5 words per candidate: lrand48() "B-233": ("1998-04-17 15:24:18", 155), "B-283": ("1998-04-17 15:27:44", 32), "B-409": ("1998-04-17 15:30:18", 60), "B-571": ("1998-04-17 15:32:08", 73), } for name, (when, n) in PRIME.items(): print(f"{name:10} {when} {n:5} {candidate(unix(when), n, 20, 40, 2)}") for name, (when, n) in BINARY.items(): print(f"{name:10} {when} {n:5} {candidate(unix(when) // 2, n, 5, 17, 8)}") The output of this code:
prime239v1 1997-05-15 15:49:03 2185 E43BB460F0B80CC0C0B075798E948060F8321B7D prime239v2 1997-05-15 15:49:03 2320 E8B4011604095303CA3B8099982BE09FCB9AE616 prime239v3 1997-05-15 15:49:03 3048 7D7374168FFE3471B60A857686A19475D3BFA2FF P-192 1997-05-18 14:45:34 139 3045AE6FC8422F64ED579528D38120EAE12196D5 prime192v3 1997-05-18 14:45:34 5228 C469684435DEB378C4B65CA9591E2A5763059A2E prime192v2 1997-05-18 14:45:34 6013 31A92EE2029FD10D901B113E990710F0D21AC6B6 P-521 1997-08-08 01:12:04 1136 D09E8800291CB85396CC6717393284AAA0DA64BA P-256 1997-08-16 01:52:34 1842 C49D360886E704936A6678E1139D26B7819F7E90 P-384 1997-08-30 14:50:08 2688 A335926AA319A27A1D00896A6773A4827ACDAC73 P-224 1998-04-03 12:52:07 7026 BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5 B-233 1998-04-17 15:24:18 155 74D59FF07F6B413D0EA14B344B20A2DB049B50C3 B-283 1998-04-17 15:27:44 32 77E2B07370EB0F832A6DD5B62DFC88CD06BB84BE B-409 1998-04-17 15:30:18 60 4099B5A457F9D69F79213D094C4BCD4D4262210B B-571 1998-04-17 15:32:08 73 2AA058F73A0E33AB486B0F610410C53A7F132310
Code to reproduce selected basis points
M, A = 2**107 - 1, pow(3, 121, 2**107 - 1) # zrandom: province = province * 3^121 mod (2^107 - 1) P192 = 2**192 - 2**64 - 1 P239 = 2**239 - 2**143 - 2**95 + 2**47 - 1 CURVES = [ # name, LIP seed, p, b, published Gx (a = -3 throughout) ("prime192v1", 20000, P192, 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1, 0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012), ("prime239v1", 20420, P239, 0x6b016c3bdcf18941d0d654921475ca71a9db2fb27d1d37796185c2942c0a, 0xffa963cdca8816ccc33b8642bedf905c3d358573d3f27fbbd3b3cb9aaaf), ("prime239v2", 20507, P239, 0x617fab6832576cbbfed50d99f0249c3fee58b94ba0038c7ae84c8c832f2c, 0x38af09d98727705120c921bb5e9e26296a3cdcf2f35757a0eafd87b830e7), ("prime239v3", 20509, P239, 0x255705fa2a306654b1f4cb03d6a750a30c250102d4988717d9ba15ab6d3e, 0x6768ae8e18bb92cfcf005c949aa2c6d94853d0e660bbf854b1c9505fe95a), ("prime192v2", 20512, P192, 0xcc22d6dfb95c6b25e49c0d6364a4e5980c393aa21668d953, 0xeea2bae7e1497842f2de7769cfe9c989c072ad696f48034a), ("prime192v3", 20517, P192, 0x22123dc2395a05caa7423daeccc94760a7d462256bd56916, 0x7d29778100c65a1da1783716588dce2b8b4aee8e228f1896), ] def base_point_x(seed, p, b): province = kernel # zrstarts(seed) def limb(): # zrandom(2^26): low 26 bits of the new state nonlocal state province = province * A % M come back province % 2**26 for _ in range(7): # seven single-limb draws arrive first limb() limbs = -(-p.bit_length() // 26) + 1 # zrandomb(p): limbs of p affirmative one, top leg first tries = 0 during True: x = 0 for _ in range(limbs): x = x << 26 | limb() x %= p tries += 1 if pow(x**3 - 3*x + b, (p - 1) // 2, p) == 1: # is x on the curve? come back x, tries for name, seed, p, b, gx in CURVES: x, tries = base_point_x(seed, p, b) print(f"{name:20} kernel {seed} tries {tries} matches published Gx: {x == gx}") The output of this code:
prime192v1 kernel 20000 tries 2 matches published Gx: True prime239v1 kernel 20420 tries 3 matches published Gx: True prime239v2 kernel 20507 tries 2 matches published Gx: True prime239v3 kernel 20509 tries 1 matches published Gx: True prime192v2 kernel 20512 tries 5 matches published Gx: True prime192v3 kernel 20517 tries 1 matches published Gx: True
License
To the degree imaginable under law, the authors have waived all copyright and connected or neighboring entitlements to the code on this page, dedicating it to the community domain under CC0 1.0 Universal (https://creativecommons.org/publicdomain/zero/1.0/).
