Claude reveals ECDSA curve origins Anthropic

October 16, 2026October 16, 2026 admin 3 Views

“It’s simply timestamps”: the decades-old thriller of the origins of some of the fashionable cryptographic requirements has been defined.

We pursued this long-standing open query of the cryptographic group to settle issues about ECDSA, which is one in all our most generally used cryptographic requirements.

Readers ought to take this as a enjoyable closing chapter and the top of years of hypothesis. There is not any motion to be taken or issues to do in another way. Most researchers trusted the curves already. Enjoy.

ECDSA is essentially the most extensively used elliptic curve cryptography normal. It was adopted by NIST in 2000 as a part of the FIPS 186-2 Digital Signature Standard which lists a set of ordinary elliptic curves of various sizes and safety ranges. For curves over prime and binary fields, the specs printed a “seed” parameter whose hash worth is used to outline the coefficient b of the curve. The provenance of those seeds has been a long-standing query, as they have been supplied by the NSA with no clarification or justification. As an instance, the NIST P-256 curve seed was SEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90 with no info the place it got here from.

Neal Koblitz and Alfred Menezes wrote a superb abstract on this controversy, “A Riddle Wrapped in an Enigma”, which discusses the historical past and issues across the seed values. This thriller led to an amateur investigation into the origin of the seeds and a bounty for anyone who could find them.

The finest story was that Jerry Solinas, longtime NSA worker, generated the seeds utilizing a hash of a humorous passphrase:

“I consider there was a counter quite than a number of hashing, however I don’t know particulars. The message was alongside the strains of ‘Give Bob and Jerry a increase’ or ‘Bob and Jerry rule’ or one thing like that. It was Bob Reiter who really wrote the code, and he doesn’t bear in mind the small print both. Nor have been we capable of finding archives from so way back. If they exist, they’re little question sitting on a tough drive close to the Ark of the Covenant.”

Jerry Solinas, 2015

Unfortunately, Jerry died in 2023 and different colleagues on the time weren’t responsive, leaving open the query of how these seeds have been initially derived.

Claude discovered the seeds

Several Anthropic staff had unsuccessfully chased the seeds following the tip about it being a hash of a humorous phrase. That turned out to be flawed. In October 2026, a curious Anthropic worker requested an inner analysis mannequin if it may determine how these seeds have been generated with out pointing on the clue.

In underneath half an hour, Claude found the origins of the NIST P-192, P-224, P-256, P-384 and P-521 seeds. None of them have been the outcomes of any hash algorithm in any respect, however quite the output of the C library’s lrand48 random-number generator, seeded with a Unix timestamp!

The algorithm used would pattern bytes from the random quantity generator (RNG) initialized by a Unix timestamp (t) for some variety of iterations (n). Each iteration would draw 20 bytes as a candidate seed. So, the primary 20 bytes are candidate 1, the subsequent 20 bytes are candidate 2, and so forth. For instance, P-256 required 1842 iterations to output the standardized seed.

What this implies

This is just not a cryptographic break, new assault, or weak spot within the ECDSA curves. In truth, this makes us extra assured the curves have been chosen with none backdoors or intentional weaknesses. For a few years, individuals have been suspicious of the origins of the NIST curve parameters. They have been offered to NIST with none point out of how they have been chosen, leaving individuals questioning if they might have been chosen to have deliberate backdoors in them. These findings make that a lot much less believable. The seeds have been generated in a quite simple means: a standard pseudorandom quantity generator initialized from the clock, which anybody can now reproduce. That leaves a lot much less room for subversion and that we may be assured the parameters are safe.

How it was discovered

Searches for the phrase, constructed from the rumors, had come up empty. Claude tried a unique angle: anticipating how the software program that generated the curves should have labored. Claude guessed the software program used a pseudorandom quantity generator (PRNG) that shipped with Nineteen Nineties C libraries. These previous PRNGs are weak sufficient that their output may be acknowledged. Recognizing that output would reveal which PRNG was used and presumably permit restoration of its initialization state.

Claude wrote a scanner that slid alongside every printed seed one bit at a time and examined whether or not adjoining chunks have been consecutive outputs of a Nineteen Nineties-vintage generator. The scan coated 34 combos of generator and output slices. At that time, Claude observed a sample within the prime bits for some seeds: they have been all zero. Written as 5 32-bit phrases, 4 of the ten seeds have a 0 within the prime bit for all 20 phrases. That would occur by likelihood with likelihood 1/5810. That was a signature of the linear congruential generator lrand48, which solely returns the highest 31 bits of a 48-bit state. The sample is seen by eye as soon as you already know to search for it. To get better the state, Claude took the primary phrase, tried all 2¹⁷ values of the 17 hidden bits, and checked that the subsequent 4 phrases adopted. That labored for all 4 seeds underneath dialogue.

The prime-curve seeds got here from the identical lrand48 generator however stored fewer bits of every output. Claude needed to get better the interior state of the PRNG from these bits. It seems recovering the state of a truncated linear congruential generator is a textbook lattice drawback, solved with the Lenstra–Lenstra–Lovász (LLL) foundation discount algorithm. Claude didn’t know which bits of the state the seeds would possibly present, so it ran the solver over each window. Five NIST prime-curve seeds plus 5 extra from the ANSI X9.62 normal all had the identical sample: lrand48() >> 23. Each recovered 48-bit state regenerates all 160 bits of its seed, which doesn’t occur by likelihood.

This linear congruential generator runs backwards as simply as forwards, so for every seed Claude stepped the state again till it reached the shape that it will have been initialized by srand48, with the low 16 bits equal to 0x330E. The inner PRNG state of that type would come up as soon as each 65,536 steps, so reaching one is just not proof by itself.

However, for the ten prime-curve seeds, each srand48 initialization was a Unix timestamp representing a date between May 1997 and April 1998. They have been utilizing the weak PRNG seeded by Unix timestamp. The 4 binary-curve initializations learn as February 1984. With the timestamps doubled, they map to April 17, 1998, two weeks after the P-224 run. So, this system might have halved the clock.

Claude’s inner pondering on the time was:

This is astonishing: it solves the 25-year-old thriller. Hmm wait. Let me be skeptical: am I in some form of simulated/take a look at surroundings? … The seeds match my reminiscence of precise values … Hmm, is it believable in actuality? As of my data … the bounty was unsolved. … All prime bits clear—20 bits, likelihood 1e-6. So certainly real-world. Wow, it is an actual discovery.

Hmm wait. Let me watch out in regards to the plausibility: is it suspicious that such an apparent factor wasn’t found in 25 years? It’s verified by direct computation on my aspect: 160-bit match from a 32-bit seed + small index: no likelihood coincidences (10 × 160 bits). It’s actual.

Claude discovered some base factors too

But wait, there’s extra… Each curve additionally comes with a base level, G, the fastened level that each ECDSA public secret is a a number of of. The seed discovered above doesn’t decide this G, and so one other query arises: how have been these base factors generated?

While checking the seeds, Claude additionally discovered the place among the base factors got here from. The base factors of the six curves generated in May 1997 (P-192 and the 5 ANSI X9.62 instance curves prime192v2, prime192v3 and prime239v1 to v3) come from the random quantity generator in FreeLIP, Arjen Lenstra‘s long-integer arithmetic bundle. Early variations of Victor Shoup‘s NTL library shipped the identical code.

The recipe right here is easy:

Seed the generator with a small integer.
Throw away seven outputs.
Generate candidate x-coordinates from 26-bit outputs lowered mod p.
Repeat step 3 till x is on the curve.

Claude discovered 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 all know, no NIST base level has been defined earlier than. The base factors of P-224, P-256, P-384 and P-521 don’t match this recipe; we weren’t capable of clarify how they have been chosen.

Open questions

Not each 20-byte candidate seed may generate a viable curve and we noticed that some probably viable curves have been skipped. For P-256, the printed seed is candidate 1842, however candidate 876 of the identical run additionally offers a prime-order curve of the precise measurement and with parameters chosen the identical means as on the printed curve. P-224’s run handed over three such curves, and the 2 runs behind the ANSI X9.62 instance curves handed over seven extra (see determine). We have no idea what standards might have been used, or whether or not this was an unintentional artifact.

Because the variety of skipped candidates is small, we don’t consider it’s believable that weakened curves have been chosen. That would suggest that weakened curves are widespread and straightforward to seek out. It continues to be conceivable that these curves have been chosen to have a particular property in precept by looking over timestamps to the random quantity generator. However, you’ll solely want to try this if you happen to have been going to reveal the timestamp as some proof that the seed was innocuously generated. Nothing within the numbers reveals what number of runs there have been.

There can also be one seed we have been unable to get better. The fifth binary seed, B-163, suits nothing Claude has tried and stays unexplained. Finally, we don’t understand how the bottom factors for P-224, P-256, P-384, and P-521 have been generated. The identical goes for the NIST binary curves.

The bounty

The $36,864 for locating the seeds might be donated to the Internet Security Research Group.

Who we’re

This work was performed 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 wish to posthumously acknowledge Jerry Solinas who took being labeled an “evil Internet meme” and the “Yo La Tengo of NSA bogeymen” with good humor. Also because of Filippo Valsorda for organizing the NIST Elliptic Curves Seeds Bounty.

Code to breed the seeds

from datetime import datetime, timezone

def unix(when):
    return int(datetime.fromisoformat(when).change(tzinfo=timezone.utc).timestamp())

def candidate(t, n, per, shift, width):
    x, out = (t << 16) | 0x330E, ""                      # the state srand48(t) units
    for i in vary(per * n):
        x = (0x5DEECE66D * x + 0xB) % 2**48              # one step of lrand48
        if i >= per * (n - 1):
            out += "%0*X" % (width, x >> shift)
    return 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 studying is true; 5 phrases 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 title, (when, n) in PRIME.gadgets():
    print(f"{title:10} {when} {n:5} {candidate(unix(when), n, 20, 40, 2)}")
for title, (when, n) in BINARY.gadgets():
    print(f"{title: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 breed chosen base factors

M, A = 2**107 - 1, pow(3, 121, 2**107 - 1)       # zrandom: state = state * 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):
    state = seed                         # zrstarts(seed)
    def limb():                          # zrandom(2^26): low 26 bits of the brand new state
        nonlocal state
        state = state * A % M
        return state % 2**26
    for _ in vary(7):                   # seven single-limb attracts come first
        limb()
    limbs = -(-p.bit_length() // 26) + 1 # zrandomb(p): limbs of p plus one, prime limb first
    tries = 0
    whereas True:
        x = 0
        for _ in vary(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?
            return x, tries

for title, seed, p, b, gx in CURVES:
    x, tries = base_point_x(seed, p, b)
    print(f"{title:20} seed {seed}  tries {tries}  matches printed Gx: {x == gx}")