2026-10-21 23:16:51
The NIST elliptic curves have been in the news twice lately. A few days ago Anthropic posted a paper on the NIST curve seeds that I wrote about here. Now the curves are in the news again, this time over broken certificates.
My post a few days ago was about the possibility that the NSA had added a backdoor to the NIST curves. Anthropic researchers showed that this wasn’t the case. The NSA had not been able to defend how the curve seeds were chosen because they forgot, but researchers from Anthropic were able to reverse engineer the source of the seeds.
So apparently the NIST curves do not have a backdoor, but as with all encryption, the Achilles heel is human error. eMudrha was using the NIST curve P-384 with extremely small keys: 4, 56, 115, 155, 156, 230, and 237. To understand why this is a problem, I’ll briefly describe how elliptic curve cryptography works.
P-384 is an elliptic curve designed by NIST, with input from the NSA, for use in cryptography. The curve has on the order of 2384 points [1] because the base field is the integers mod
p = 2384 − 2128 − 296 + 232 − 1,
a 384-bit prime number. Given a basepoint b on the curve and an exponent e, it is practically impossible to recover e from be. That’s the discrete logarithm problem [2], the basis for the security of elliptic curve cryptography. If and when cryptographically relevant quantum computers arrive, the discrete logarithm problem will be solvable and elliptic curve cryptography will be broken.
Until the advent of quantum computing, elliptic curve cryptography is presumably safe, unless someone does something negligent, such as using a tiny value of e like 4.
If e is chosen at random from a group with on the order of 2384 elements, you cannot recover e from be without brute force. But apparently someone said
Let’s see. Is e = 1? Is it 2? Is it 3? Is it 4? Why yes: e = 4.
Ordinarily this would be hopeless. You can’t just try 2384 exponents. But someone thought to test whether the keys were horrifically bad, and they were right.
[1] I don’t know whether the exact number of points on the curve is known. It’s the number of points on an elliptic curve is not simple to calculate, but it is easy to estimate. It’s roughly the size of the base field, which is p.
Update: There are exactly 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643 points on the P384 curve. (NIST SP 800-186, §3.2.1.4)
[2] The exponentiation here is not over the integers, or over the integers mod p. It’s over the group structure of the elliptic curve, and that is what makes it hard to compute the discrete logarithm.
The post Backdoors, Incompetence, and Elliptic Curves first appeared on John D. Cook.2026-10-21 20:04:06
I was watching a video by John Higgins this morning about the poem in Ecclesiastes 3, one of the most famous passages in the Bible.
There is a time for everything,
and a season for every activity under the heavens:a time to be born and a time to die,
a time to plant and a time to uproot,
a time to kill and a time to heal,
a time to tear down and a time to build,
a time to weep and a time to laugh,
a time to mourn and a time to dance,
a time to scatter stones and a time to gather them,
a time to embrace and a time to refrain from embracing,
a time to search and a time to give up,
a time to keep and a time to throw away,
a time to tear and a time to mend,
a time to be silent and a time to speak,
a time to love and a time to hate,
a time for war and a time for peace.
The poem has a great deal of symmetry, from birth and death to war and peace. It has seven couplets, and the number seven in the Bible is symbolic of perfection.
There is a repeated pattern of groups of four words: a time for X, a time for Y. The rhythm reminds me of Beethoven’s fifth symphony, especially the third movement [1].
Higgins points out that there’s something odd in the middle couplet:
a time to scatter stones and a time to gather them,
a time to embrace and a time to refrain from embracing,
It breaks the rhythm, at least in English translation, and presumably in the original language. The poem goes from intransitive adjectival infinitives —to plant, to uproot, etc.—to transitive—to gather stones. Also, the two parts of the couplet do not obviously fit together. There’s a similarity between birth and planting, between killing and tearing down, etc. But what’s the connection between casting stones and embracing?
Higgins explains that this deliberate symmetry breaking fits the theme of the Ecclesiastes as a whole. There is order to the world, and yet we don’t have it all figured out. Even when everything mostly makes sense, there’s something we don’t understand, like the middle couplet.
[1] This has been called the fate motif. There is an apocryphal story that Beethoven described it as such to his secretary and biographer Anton Schindler. Regardless of whether the story is true, the name stuck. Here’s the particular part I had in mind.
2026-10-19 22:55:22
Splitting N! into N factors is trivial. It’s defined as the product of N integers, the integers 1 through N.
Can you still split N! into N factors if you put a minimum size requirement on the factors?
You can’t split 3! into three factors unless one of the factors is 1, but you can split 4! into factors ≥ 2:
4! = 24 = 2 × 2 × 2 × 3
Define t(N) as the largest number such that N! can be expressed as the product of integers greater than or equal to t(N). So based on the discussion above, t(N) ≥ 1 for all N, t(3) = 1 and t(4) = 2. The t(N) are given in OEIS sequence A034258.
Last Thursday an article came out proving an asymptotic estimate for t(N). You can find a preprint on arXiv.
An upper bound on t(N) would be the Nth root of N! because that would correspond to splitting N! into N factors of equal size. But the Nth root of N! will not be an integer for N > 1, so the bound would not be tight.
If we apply Stirling’s approximation for factorial we get
t(N) / N ≤ 1/e + O(log(N) / N).
It was conjectured that for large N
t(N) / N ∼ 1/e − c0 / log(N)
and the new paper proves
t(N) / N ∼ 1/e − c0 / log(N) + O(1 / log1 + c N).
.
The post Refactoring factorials first appeared on John D. Cook.2026-10-19 20:00:43
About 14% of English words can be spelled by stringing together chemical symbols. For example, sarcasm can be written
S Ar Ca Sm
using the symbols for sulfur, argon, calcium, and samarium.
How would you write a program to determine whether a word can be written by stringing together chemical element abbreviations ignoring case? Obviously this isn’t a practical problem, but it illustrates a practical problem.
You could solve the problem with a regular expression:
(h|he|li|be|b|c|n|o|f|ne|na|mg|al|si| … |og)+
This solution could either be very efficient or very inefficient, depending on the inner workings of the software used to match the regular expression.
A DFA (deterministic finite automata) regular expression engine would find a match, or report failure, linear time, i.e. the execution time would be proportional to the length of the string being matched. A NFA (nondeterministic finite automata) engine that uses backtracking could take exponential time.
The root of the problem is the ambiguity in dividing words into single letters or pairs of letters.
Many two-letter chemical symbols are made of letters that are themselves chemical symbols. For example, the symbol for cobalt, Co, consists of the symbols for carbon, C, and oxygen, O. A traditional NFA regular expression engine uses backtracking and could take exponentially long to test whether the word
cococo…j
matches a regular expression for concatenated chemical symbols. If there are n copies of co, the engine would try all 2n possibilities of treating each pair as either co (cobalt) or c o (carbon oxygen).
A DFA regular expression engine always runs in O(n) time, but a (traditional) NFA can take exponential time. So why ever use an NFA engine? Because it can match more advanced patterns such as Perl regular expressions (which are not “regular” expressions in the original meaning of the term). Newer NFA engines have added safeguards to eliminate or at least reduce the chance of running into catastrophic backtracking.
The post A frivolous problem with a deeper lesson first appeared on John D. Cook.2026-10-17 23:39:06
NIST published a set of elliptic curves for cryptography in 2000. The seeds for the curves were supplied by the NSA, and cryptographers suspected the agency may have installed backdoors in the curves. And not without reason: the NSA did insert a backdoor in the Dual_EC_DRBG random number generator.
Two days ago researchers at Anthropic [1] showed that the NIST curves were not seeded with a backdoor. The rest of this post will give the background necessary to appreciate this result.
The security of elliptic curve cryptography depends on the difficult of solving the discrete logarithm problem. In the context of elliptic curve arithmetic, the analog of exponentiation is easy but the analog of taking logarithms is hard.
In general it’s not practical to compute discrete logarithms over large elliptic curves. But it could be easy for someone with inside information to compute discrete logarithms if something about the curve was not “general.”
Specifically, the NIST curves have the form
y² = x³ − 3x + b (mod p)
for various values of p [2], and the suspicion regards the choice of b. For nearly all values of b encryption over the elliptic curve should be secure, as far as we know, but in principle someone could engineer values of b to weaken the encryption.
So where did the b‘s come from? Were they chosen in good faith?
Concern over the choice of seeds, the b‘s, grew following the Snowden revelations. Daniel J. Bernstein emailed Jerry Solinas of the NSA on September 6, 2014 asking where the seeds had come from. Solinas replied in subsequent emails. He said the seeds were generated by hashing the ASCII representation of a humorous English message, but he could no longer remember the exact message or the precise hashing procedure.
On October 5, 2023 Philippo Valsorda announced a bounty for reverse engineering the origin of the NIST elliptic curve seeds. Two days ago researchers from Anthropic claimed the bounty. Valsorda verified the results and awarded the prize. It turns out Solinas found the curve seeds in good faith, but his memory had faded over the years since the curves were published. We now know he used a date, not a phrase, as part of the process of constructing the seeds.
The NIST curves have some nice properties, such as enabling some clever tricks for arithmetic in their base fields. But adoption of the curves has been held back over suspicion regarding their origin. Now the curves have been exhonorated. As Valdorda notes
… this nicely completes the “rehabilitation arc” of NIST elliptic curve cryptography, which I would now personally recommend over Curve25519/Ed25519/X25519. Just in time for them to be retired in favor of post-quantum signatures.
[1] This does not imply that LLMs are necessarily a threat to encryption. The search for the NIST seeds required a lot of brute force. Some cleverness was required in order to come up with possibilities to check by brute force, but even that is sorta brute force at a higher level of abstraction. There has been speculation that labs are looking for weaknesses in cryptographic primitives and protocols, but that’s a different matter than searching for seeds.
[2] The curves P-192, P-224, P-256, P-384, and P-521 are built over the field of integers mod p, where the number of bits in p corresponds to the number in the name. The P-192 curve, for example, has as its base field the integers mod 2192 − 264 − 1, a 192-bit prime.
The post Cloud of suspicion lifted from NIST curves first appeared on John D. Cook.2026-10-16 22:37:07
This post began as a thread on X last night. I’ve edited the thread to turn it into a blog post, making some additions and corrections.
I’m watching 2010: The Year We Make Contact. The movie opens saying the monolith is located at the Lagrange point between Jupiter and Io. I got nerd sniped and wondered where that was.
There are five Lagrange points, but presumably the movie refers to L1 or L2 because these are near Io. Lagrange points L3, L4, and L5 are essentially in the orbit of Io, but 60, 180, and 300 degrees out of phase, all far from Io. (The book says the monolith is at L1.)
Lagrange points L1 and L2 are unstable. Maybe this is a plot hole in the movie, unless there’s an explanation coming.
(In general L1, L2, and L3 are unstable. If the ratio of the masses is large enough, L4 and L5 will be stable. More on that here. The Lagrange points L4 and L5 are indeed stable for the Jupiter-Io system. For the Sun-Earth system L1 is moderately stable over a short time span, but L1 is far less stable for the Jupiter-Io system.)
Here’s a plot of the Lagrange points.
Note that L1 and L2 are very close to Io, about 10,000 km from the moon. The L1 and L2 Lagrange points for the Earth-Sun system are not so close to Earth.
(That’s half true. Yes, Io’s L1 point is closer to it than Earth’s L1 point, in absolute distance. But in relative terms, Io’s L1 point is actually further away. I had been misled by seeing an illustration that exaggerated the distance from Earth to L1.)
