Uncategorized

Where else to find me

This blog is the main place I write, but I also use other platforms, either to write new content or to announce blog posts.

X (née Twitter)

I have a several X accounts, one personal account (@JohnDCook) and several specialized accounts (@CompSciFact, @AlgebraFact, @DataSciFact, etc.). I announce new blog posts on the most relevant account.

RSS

You can subscribe to the blog via RSS and find out about each post as it’s published.

RSS was very popular before Google killed its RSS reader, but it still works just fine. I use RSS to subscribe to the blogs I read.

The hard part of using RSS is finding a reader you like. I use Inoreader. I’m sure an LLM could help you find an RSS reader for your preferences and help you get started using it.

Mathstodon & Bluesky

I announce my math-related posts on Mathstodon at mathstodon.xyz/@johndcook. I also use a service that repeats my Mathstodon posts to Bluesky at johndcook.mathstodon.xyz.ap.brid.gy.

I don’t know why, but more people have started following me on Mathstodon over the last couple weeks.

Substack

Some people like to get email notifications of posts. I used two or three services that sent out such emails and they all stopped working. I tried out Substack and it has worked smoothly ever since.

My Substack newsletter has evolved into a bit more than just blog post announcements. I give a little intro to each post and some additional info such as how a sequence of posts are related or ideas that occurred to me after writing the post.

LinkedIn

Once in a while I post something to LinkedIn. If you’d like to know more about my background, you can see my profile there.

Backdoors, Incompetence, and Elliptic Curves

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 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 [1], 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] 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.

Deliberate imperfection

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.

Sheet music for Beethoven: Symphony No. 5, Op. 67. Third Movement Horn Theme

Refactoring factorials

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).

.

Cloud of suspicion lifted from NIST curves

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.

Related posts

[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.

Privacy policies and modal logic

If you’ve followed this blog for a while, you may know that I do a lot of work with data privacy and that I have an interest in modal logic. Recently these two worlds collided: I became aware of work that uses modal logic to reason about data privacy.

The story begins with Helen Nissenbaum’s paper Privacy as Contextual Integrity [1]. Rather than simply classifying data as public or private, Nissenbaum looks at norms around the context in which data exists and moves.

… the benchmark of privacy is contextual integrity; that in any given situation, a complaint that privacy has been violated is sound in the event that one or the other types of the informational norms has been transgressed.

A couple years later Nissenbaum coauthored a paper [2] with three Stanford computer scientists using modal logic, specifically linear temporal logic (LTL), to reason about contextual integrity. The paper uses four modal operators: the usual box and diamond, plus past tense versions with a minus sign across the middle.

box, diamond, box minus, diamond minus

These four operators can be read as “henceforth”, “eventually”, “historically”, and “once.”

Henceforth means something will always be true into the future; historically means something was always true in the past.

Eventually means something will happen at some time in the future; once means something occurred at some time in the past.

You could imagine using these operators to formalize statements such as data sharing in some context is permissible (henceforth) if the data subject has (once) signed a consent form.

Understanding simple stand-alone policies does not require the machinery of formal logic, but analyzing large collections of interacting policies may. It may be, for example, that a collection of policies cannot all be satisfied, though this is not obvious from looking at the individual policies. Formalizing policies in the language modal logic makes their analysis amenable to well established algorithms.

Related posts

[1] H. Nissenbaum. Privacy as contextual integrity. Washington Law Review, 79(1):119–158, 2004.

[2] A. Barth, A. Datta, J. C. Mitchell, and H. Nissenbaum, “Privacy and contextual integrity: Framework and applications,” in Proc. 2006 IEEE Symp. Security and Privacy (S&P’06), Berkeley/Oakland, CA, USA, 2006, pp. 184–198, doi: 10.1109/SP.2006.32.

Topological models of modal logic

The previous post discussed a superficial connection between modal logic and topology, that both use the terms regular and normal to indicate added sets of axioms. McKinsey and Tarski developed a deeper connection between modal logic and topology that we’ll discuss here.

Starting with a topological space X and a proposition p, define [[p]] as the set of points in X at which p is true. Define □p to be true at points in the interior of [[p]] and define ◇p to be true on the closure of [[p]].

You could think of □p as the points where p is robustly true. Not only is p true at x, there’s some wiggle room around x, i.e. an open set, in which p remains true.

You could think of ◇p as the points where we cannot rule out the possibility of p being true using open sets. If ◇p includes x, any open set containing x also contains part of ◇p, though it may also contain points outside of ◇p.

Regularity

For any topology on X, the logic constructed above is normal. The axiom

\Diamond p \Leftrightarrow \lnot (\Box \lnot p)

holds because the closure of a set is the complement of the interior of its complement [1].

Note that this is a regularity result for the modal logic, not the topology. The topology could be arbitrary, and not necessarily regular or normal in the topological sense.

S4

The logic constructed above also satisfies a couple more axioms. We have

\Box p \to p

because the interior of a set is a subset of the set, and

\Box p \to \Box\Box p

because the interior of the interior of a set is simply the interior. This means the modal logic corresponding to a topology satisfies the S4 axioms. You could say S4 is the logic that corresponds to the McKinsey and Tarski logic of all topological spaces.

More logics and more topologies

So S4 is the logic that corresponds to all topologies. We could look at more restricted topologies and ask what are their corresponding logics. Or we could start with a modal logic and ask whether there’s a topology that models that logic.

Interesting logics correspond to badly behaved topological spaces. Familiar topological spaces like the real line correspond to S4.

Trivial modal logic

The discrete topology corresponds to the trivial modal logic. All sets are open, and closed, so any set is the same as its interior and its closure. So □p and ◇p reduce to just p.

S5

For the indiscrete topology, □p corresponds to a proposition holding everywhere and ◇p corresponds to it holding somewhere. If the topological space has infinitely many points, the corresponding modal logic is S5. [2]

Between S4 and S5

The cofinite topology on an infinite set X defines a set U to be open if the complement of U is finite. The McKinsey-Tarski logic of the cofinite topology is somewhere between S4 and S5. You can show that the formula

p \land \Diamond\Box p \to \Box p

holds, which doesn’t hold in S4, and the formula

\Diamond p \to \Box\Diamond p

does not hold, though it must hold in S5.

Related posts

[1] We should also verify that if A ∩ B ⊂ C, then Interior(A) ∩ Interior(B) ⊂ Interior(C).

[2] Propositions can only have a finite number of terms. Having infinite points in the topological space prevents the corresponding logic from proving theorems that don’t necessarily hold in S5.

Servers in dawn-dusk orbit

Despite the predictions that no one would ever put build data centers in space, Google is starting on Thursday. Google’s prototype satellite will be one of 130 payloads on SpaceX’s Transporter 18 mission on October 1.

The server will follow a dawn-dusk orbit, a special case of a sun-synchronous orbit (SSO), following the terminator line between daylight on dark on the earth below. A dawn-dusk orbit allows the satellite’s solar panels to stay in nearly continuous daylight, while also being in a relatively inexpensive low earth orbit (LEO). Geostationary orbit (GEO) would allow solar panels to always receive sunlight, but launching a satellite into GEO requires more fuel and so is more expensive.

Another advantage of LEO is that radiation levels are a couple orders of magnitude less than at GEO. Lower radiation means electronics do not need to be as hardened against radiation.

A dawn-dusk orbit would not be possible if the earth were perfectly spherical. The earth’s equatorial bulge makes it possible to design an orbit that precesses once per year. David Hammen explains this in an answer to a question on the Space Exploration Stack Exchange site.

If the Earth had a spherically distributed gravitational field, a satellite’s right ascension of ascending node would be constant. … Fortunately, the Earth’s gravitational field is not spherical. The Earth’s rotation results in an equatorial bulge. This equatorial bulge causes RAAN to precess (or recess). …

Sun synchronous orbits are chosen so that RAAN precesses by 360 degrees per year, or a bit less than one degree per day. …

A dawn-dusk satellite is a special case of a sun synchronous orbit. … A dawn-dusk orbit typically does not quite follow the terminator. Following the terminator would require a rather high orbit.

Related posts

Nathaniel Bowditch

A couple days ago a friend told me about the book Carry On, Mr. Bowditch, a fictional account of the life of Nathaniel Bowditch (1773–1838). I’ve been listening to the book on Audible, and apparently it’s only lightly fictionalized.

Bowditch was a self-educated mathematician and astronomer, best known for his book The American Practical Navigator, first published in 1801. The book has been continually revised over the last two centuries and is still in print, available for download from the National Geospatial-Intelligence Agency. The latest edition begins with a brief account of Bowditch’s life, confirming the essential details of the fictional biography.

Two things stand out about Bowditch: his attention to detail and his desire to make ideas accessible. He taught himself Latin in order to read Newton’s Principia and followed the text so closely that he found a number of errors.

Bowditch’s navigation book grew out of the numerous corrections he made to error he found in John Hamilton Moore’s The Practical Navigator, the leading navigation text of the time.

At the beginning of the 19th century it was theoretically possible to determine time, and hence longitude, from lunar observation. However, the method required ideal observation conditions and laborious calculation. Bowditch developed a way to make the necessary measurements under more general conditions, and simplified the necessary calculations. According to the biographical preface mentioned above,

Bowditch vowed while writing this edition [of his navigation text] to “put down in the book nothing I can’t teach the crew,” and it is said that every member of his crew including the cook could take a lunar observation and plot the ship’s position.

After completing The American Practical Navigator, Bowditch began an English translation of Pierre Laplace’s encyclopedic Mecanique Celeste, filling in details to make the work accessible to a wider audience. He was able to translate four out of the five volumes by the end of his life.

Related posts

Phone words

I recently bought a copy of Los Alamos Rolodex, a book displaying business cards from Los Alamos Nation Labs from 1967 to 1978. You can find some examples of the cards here.

One of the cards in the book is for Eugene Frank, President of B & F Instruments. His card lists his phone number as

(215) MErcury 9-7100

At first glance I thought the “E” in “MErcury” had been accidentally capitalized. Then I realized the intention was that someone would dial ME (i.e. 63) and ignore “rcury”. So the phone number would be (215) 639-7100.

This card was from 1968, the height of the space race. Maybe the card was alluding to the Project Mercury or the planet Mercury, or both. [1]

The telephone keypad mapping (ITU E.161 standard) is a poor attempt at making phone numbers more memorable. For starters, there’s no way to encode 0 or 1 [2]. It’s unlikely a phone number will correspond to anything memorable unless you come up with the word first and then try to obtain the phone number, such as 800 FLOWERS.

Inserting extra letters, as Mr. Frank did, greatly increases the chances of encoding a phone number as a word. But then you need to denote which letters count and which ones are filler, so there’s not much advantage. Still, I wanted to play around with it for fun. I found 109 words [3] containing the letters from a telephone encoding of 4228646. (I’m using the file /usr/share/dict/words on my laptop as my list of words.)

Here are some of the more interesting hits.

  • semicatholicism
  • heartburning
  • gladiatorism
  • diabetogenic
  • galactogenetic
  • xanthocreatinine

There are over 30,000 words containing an encoding of the area code 832. One of these is traditional, and so I could write my phone number as

TraDitionAl semICAThOlIcisM.

Another choice for 832 is intercosmic, so

inTErCosmic GAlaCTOGeNetic

is another possibility.

Galactogentic can refer to the production of milk by the mammary glands or to the formation of galaxies (e.g. the Milky Way). Here intercosmic fits with the later sense.

I got greedy and tried to find a word containing the full phone number, 8324228646, but didn’t find anything.

Here’s my business card in the style of the Los Alamos Rolodex cards, created by Grok, using (832) GlAdiATOrIsM as the phone number.

Now suppose you remembered “gladiatorism” but not which letters were capitalized. Then you’d have to try up to 792, i.e. 12 choose 7, possible numbers, so this really isn’t a practical mnemonic. If you remembered “traditional semicatholicism” without capitalization it would be worse, with over a million possibilities (11 choose 3 times 15 choose 7). Some possibilities are counted twice, since different ways of selecting letters can lead to the same phone number, but still there are too many possibilities to try.

Related posts

[1] Thanks to Andrew for pointing out in his comment that it was common at one time to encode the first two numbers of the exchange (the second triplet of numbers in a phone number) as letters, and assign a word to those letters. Sometimes this was standardized, such as Pennsylvania 6 for 736, an example made famous by Glenn Miller. But from what I can tell, not all exchanges had standard names, and proposed standards weren’t always adopted in practice.

In the example above, I don’t know whether it was common to encode 639 as Mercury 9, or even ME 9, or whether Mr. Frank chose this. It was common chose some encoding for the first two numbers of the exchange, though that practice was going away by 1968. Perhaps Mr. Frank was an older man who retained a habit he acquired when it was more common. None of the other cards in the book spelled out the exchange.

Update: Thanks to Chuck for pointing out this list of recommended words for exchanges. Note that there are multiple suggestions for most exchanges, including six for 63X.

[2] Not only are there no letters for 0 and 1, the letters O and I represent digits. At one point in time the first digit of an exchange (the middle three digits) could not be a 0 or 1, but these digits could appear anywhere else.

[3] I initially found a list of 185 words, but some of these were duplicates: a word can represent a phone number in more than one way.