Math

How the eMudrha certificate debacle might have happened

Posted on by John

You may have seen references to a password being the number 4. There are countless allusions to this online, but they don’t give the context.

As I mentioned in an earlier post, eMudrha was using the numbers 4, 56, 115, 155, 156, 230, and 237 as secret keys. I haven’t seen details of how this happened, but in this post I’ll give a plausible account of how it might have happened, what someone could have done to produce those results. I’m not trying to do forensic analysis on this specific incident, just exploring what someone might do.

eMudrha was using the NIST elliptic curve P-384, and a secret key should be a random number chosen between 1 and 2384. That upper bound isn’t exactly correct, but it’s close. See this post if you want to know the exact number.

Someone might have chosen numbers up to 384 rather than 2384 out of ignorance. Or they might done so by a typo. Maybe they generated a random value that might have been larger than 2384 and then intended to reduce the number mod 2384, but instead of typing 

% 2**384

they typed 

% 384

It seems more likely, however, that somehow someone took one byte of a random value because all the keys are less than 28 = 256.

The probability of choosing seven numbers from 1 to 384 and all being less than or equal to 237 is around 0.034. But the same probability for numbers chosen between 1 and 256 is about 0.60.

The number of points on an elliptic curve

Posted on by John

An elliptic curve E over a finite field F consists of the set of points (x, y) satisfying the equation

y² = x³ + ax + b

with x and y in F. Typically in cryptography the field F is the integers mod p where p is a very large prime number.

The number of points on E is roughly the number of elements in F. So for a curve over the integers mod p, the curve has roughly p points.

The next section will give an intuitive argument for why the number of points on E should be roughly the number of elements in F. Then the next section will give a rigorous bound. Then after that we’ll work through an example.

Hand-wavy estimate

For a prime p, half the non-zero integers mod p have a square root and half do not. The ones that do have a square root have two square roots. For example, look at the integers mod 7. The numbers 1, 2, and 4 have square roots but the numbers 3, 5, and 6 do not. Here’s a little bit of Python to verify this.

>>> [x**2 % 7 for x in range(1,7)]
[1, 4, 2, 2, 4, 1]

Now if we wanted to count the number of solutions to

y² = x (mod p)

we’d find it equals p. That’s because (0, 0) is a point on the curve, and for (p − 1)/2 values of x there are two values of y, and for the remaining values of x there are no values of y.

To put it another way, if we pick a value of x at random, it will have two square roots or no square roots with roughly equal probability.

Now suppose we pick an x at random and compute x³ + ax + b. We might guess that this process scatters x values in an unbiased way, being no more likely to produce a square than a non-square. Our guess turns out to be approximately correct, though there may be a small bias in favor of squares or non-squares.

Precise bound

Hasse’s theorem gives a precise bound on the number of points on an elliptic curve E. It says

#E = p + 1 − t

where

|t| ≤ 2√p.

So if p is on the order of 2n, the number of points on E is also on the order of 2n because √p is far smaller than p. That’s all you need to know at a high level. The rest of this post will look at a particular example in full detail.

Detailed example

The NIST curve P-384 has been in the news lately. For this curve, the based field is integers modulo a 384-bit prime p and so the number of points on the curve is also 384-bit number. Specifically

p = 2384 − 2128 − 296 + 232 − 1,

and so we know a priori that the number of points on the curve equals 2384 plus or minus a factor less than 2193.

The number of points on the elliptic curve P-384 is known to be

 n = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643

See NIST SP 800-186, §3.2.1.4⁠.

We can calculate t at a Python REPL.

>>> n = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643
>>>  p = 2**384 - 2**128 - 2**96 + 2**32 - 1
>>> t = p + 1 - n
>>> t
1388124618062372383606759648309780106643088307173319169677

The fact that t is positive means the number of points n on our curve is slightly less than p. Here “slightly” is relative. The value of p − n is a huge number, but it’s small relative to p.

We can verify that |t| is less than our a priori bound of 2√p.

>>> from math import sqrt
>>> t/(2*sqrt(p))
0.11057050503394951

So the actual value of t is about nine times smaller than its bound.

LaTeX package for Pascal-like triangles

Posted on by John

When I wrote about the harmonic triangle yesterday, I displayed the triangle left-aligned using fixed-width text because that was easier than producing the format you usually see for Pascal’s triangle and related triangles.

    1
    1/2  1/2
    1/3  1/6   1/3
    1/4  1/12  1/12  1/4
    1/5  1/20  1/30  1/20  1/5
    …

I asked Claude to write a LaTeX package to make it easier to create Pascal-like triangles and it did a great job, including handy features I didn’t think to ask for. You can download it here: numtriangle.sty.

I used this package to create the more attractive display below.

Here’s the LaTeX code that produced the image above.

\documentclass[border=4pt]{standalone}
\usepackage{numtriangle}
\NewTriangle{\Leibniz}{start=1, edges=1/\n, rule=\L - \P, fractions,
  format=\displaystyle, xsep=2.8em, ysep=2.8em}
\begin{document}
\Leibniz[rows=5]
\end{document}

I then compiled the code to an SVG file with the following.

pdflatex leibniz.pdf
pdftocairo -svg leibniz.pdf leibniz.svg

Bell’s triangle is not defined in a way that the LaTeX package supports, but I can produce the triangle by listing the content. I made the triangle left-aligned rather than centered just to show that this can be done.

The LaTeX code was the following:

\ListTriangle[shape=left]{
    1; 1, 2; 2, 3, 5; 5, 7, 10, 15; 15, 20, 27, 37, 52}

Here’s a particularly photogenic image, Pascal’s triangle with odd numbers highlighted, showing the Sierpiński triangle pattern.

The code to produce the image:

\PascalTriangle[rows=16, mod=2, xsep=1.9em, ysep=1.3em,
  cell style={font=\tiny, minimum size=1.2em},
  highlight style={fill=orange!40}]

A generalization of the Pythagorean theorem

Posted on by John

G. D. Chakerian [1] discovered the following generalization of the Pythagorean theorem.

Take any triangle and attach squares to each side. From each triangle vertex, extend a line perpendicular to the opposite side and extend the line through the square, as shown in the figure below. Then the areas of the rectangles with the same labels are equal.

It’s not clear at first why this is a generalization of the Pythagorean theorem, but if we make our triangle closer to a right triangle it’s easier to see the connection.

As the angle at B becomes closer to a right angle, the area of the orange triangles labeled II goes to zero. In the limit we’re left a theorem saying that the areas of the blue and green squares add up to the area of the square attached to the hypotenuse.

Update: Kirill Osenkov made an interactive version of the figure above here.

The paper [1] caught my eye because it gives a connection between a geometry problem and a circuit problem, much like this post. However, I find the theorem itself more interesting than the connection to circuits.

The first diagram is my reproduction of the first figure from the paper, with color added. I then moved the vertex A to make the connection to the Pythagorean theorem easier to see.

Related posts

[1] G. D. Chakerian and M. S. Klamkin. A Generalization of the Pythagorean Theorem Seen as a Problem of Equivalent Resistances. Mathematics Magazine, Vol. 59, No. 3 (Jun., 1986), pp. 149–153.

The first line of the paper is “The following result (observed several years ago by the first author) may be viewed as a generalization of the Pythagorean Theorem.” The paper also gives two other sources of the theorem. Presumably Chakerian independently discovered a theorem that was already known.

Poe, Bessel, and Drones

Posted on by John

What’s a connection between Edgar Allan Poe and Friedrich Wilhelm Bessel?

Poe’s story The Pit and the Pendulum describes a pendulum with a semicircular blade being lowered on a cable. This is an interesting variation on the usual harmonic oscillator because the length L of the pendulum is not constant but rather an increasing function of time L(t).

Using the small angle approximation sin(θ) ≈ θ, the equation of motion is

L θ″ + L′ θ′ + g θ = 0.

If we assume the length is increasing at a constant rate, then with a change of variables described in [1], this differential equation becomes Bessel’s equation and its solutions are Bessel functions.

The authors of [1] state that their primary interest is whether a pendulum can have the motion that Poe describes. But as they indicate in their opening sentence,

The study of the motion of a steadily descending pendulum has practical applications (e.g., to the oscillations of a load being lowered by a crane).

A more recent application would be describing the motion of a package being delivered by a Zipline drone.

Related posts

[1] Robert L. Borrelli, Courtney S. Coleman, and Dana D. Hobson. Poe’s Pendulum. Mathematics Magazine, Vol. 58, No. 2 (Mar., 1985), pp. 78–83

Harmonic triangle

Posted on by John

Pascal’s triangle is the most famous triangular arrangement of numbers. I’ve written about other numerical triangles, such as Bell’s triangle and the trinomial triangle. There’s another well-known triangle that somehow I never heard of until recently: the harmonic triangle, first explored by Leibniz around 1700.

To create the harmonic triangle, start with the harmonic series

1, 1/2, 1/3, 1/4, 1/5, …

This is the first column of the triangle. Next take the differences of the terms:

(1 − 1/2), (1/2 − 1/3), (1/3 − 1/4), … = 1/2, 1/6, 1/12, …

This, shifted down one space, is the second column of the triangle. Taking differences again gives the third column, and so forth. Column c of the triangle consists of the cth differences of the harmonic series.

    1
    1/2  1/2
    1/3  1/6   1/3
    1/4  1/12  1/12  1/4
    1/5  1/20  1/30  1/20  1/5
    …

Each entry is the difference of the entries to its west and northwest. If we let L(r, c) be the element in the rth row and cth column, then

L(r,c) = L(r-1, c-1) - L(r, c - 1)

Every numerator is 1, though it’s not immediately obvious why this should be the case. And every number is a value of the beta function, the function that gives the normalizing constant for the beta distribution [1].

L(r,c) = \frac{1}{r\binom{r-1}{c-1}} = \beta(c, r-c+1)

Related posts

[1] Ayoub B. Ayoub. The Harmonic Triangle and the Beta Function. Mathematics Magazine, Vol. 60, No. 4 (Oct., 1987), pp. 223-225

Categorical models of logics

Posted on by John

A few days ago I wrote about topological models of modal logic. If you find general topology more familiar than modal logic, this correspondence could be helpful. If you think the motivation for general topology is evident but the motivation for modal logic is suspect, the correspondence between the two fields might relieve some of your suspicion of the latter.

Topological models, however, are quite limited. You can’t model provability logic, for example, by the usual approach to constructing topological models, though there is an alternative construction.

Categorical models are less limited. You can model a wide variety of logics using categories via the Curry-Howard-Lambek correspondence. This may be cold comfort if you find category theory and logic equally mysterious. Even so, there’s something intriguing about a correspondence between two things you find mysterious.

Categorical semantics is deep and broad, but I’ll keep this post brief. The correspondence between logic [1] and categories [2] is summarized in the table below.

\begin{tabular}{ll} \hline \textbf{Logic} & \textbf{Category theory} \\ \hline Proposition / formula & Object \\ Proof of \(A\) from \(\Gamma\) & Morphism \(\Gamma\to A\) \\ Truth \(\top\) & Terminal object \(1\) \\ Falsehood \(\bot\) & Initial object \(0\) \\ Conjunction \(A\land B\) & Product \(A\times B\) \\ Disjunction \(A\lor B\) & Coproduct \(A+B\) \\ Implication \(A\to B\) & Exponential \(B^A\) \\ Negation \(\neg A\) & Exponential \(0^A\) \\ \hline \end{tabular}

It’s interesting how model logic fits into this picture. Axiom K, required by normal modal logics, says

\Box(A\to B)\;\longrightarrow\;(\Box A\to\Box B)

In categorial semantics, this says the box operator □ is a functor, mapping objects representing propositions to objects representing propositions, and mapping morphisms representing proofs to mapping morphisms representing proofs.

Related posts

[1] More precisely, intuitionistic propositional calculus.

[2] More precisely, bicartesian closed categories.

Consequences of progress toward the Riemann Hypothesis

Posted on by John

The Riemann Hypothesis (RH) is the conjecture that all the zeros of the Riemann zeta function ζ(s) in the critical strip, i.e. the region of the complex plane with real part between 0 and 1, have real part equal to ½.

The Quasi Riemann Hypothesis (QRH) says that there exists a constant θ < 1 such that no zeros of ζ(s) have real part greater than θ. OpenAI has published a paper claiming QRH with θ = 7/8.

The RH is so important to number theory that even partial results can have big consequences. This post will focus on one consequence: the error term in the Prime Number Theorem.

The Prime Number Theorem says that π(x), the number of primes less than x, is asymptotically equal to Li(x). We’d like to know more specifically at what rate π(x) approaches Li(x).

The best known result before the QRH announcement was

\pi(x) = \operatorname{Li}(x) + {\cal O} \left(x \exp\!\left(-c\,\frac{(\log x)^{3/5}}{(\log\log x)^{1/5}}\right)\right)

If the QRH holds for some θ, such as OpenAI’s assertion that θ = 7/8,

\pi(x) = \operatorname{Li}(x) + {\cal O} \left(x^\theta\,\log x\right).
If RH holds, θ = ½.

Incidentally, you may have seen the Prime Number Theorem stated with x/log(x) rather than Li(x). These two functions are asymptotically equal, so they give the same theorem, if you’re not interested in quantifying the rate of convergence. The function Li(x) gives better error bounds.

Faster Fourier Transform

Posted on by John

The Fast Fourier Transform (FFT) algorithm can compute the discrete Fourier transform of a sequence of length n in time

O(n log n).

OpenAI recently posted a paper saying there is an algorithm that could compute the discrete Fourier transform in

O(n (log n)1 − ε)

time for ε = 10−13.

This result is amazing. It seemed that O(n log n) was as good as you could do, which it provably is for sorting algorithms.

The result is also of absolutely no practical value, for now. But since the theorem shows that our assumptions were wrong, however slightly, about what is possible, maybe we’re in for further surprises. Maybe the ε crack will grow. It wouldn’t be the first time.

Related posts

Irrationality exponent of π

Posted on by John

For a real number x, the irrationality index μ(x) is a way of measuring how well x can be approximated by rational numbers. If x is rational, μ(x) = 1. If x is irrational, μ(x) ≥ 2.

OpenAI recently published a proof that μ(π) = 2. Almost all real numbers have irrationality exponent 2, so the new result says π is typical in this regard. There are numbers proven to have irrationality index greater than 2 (more on that below), but π isn’t one of them.

The irrationality exponent μ(x) is defined as the supremum of the set of values ν such that

0 < \left| x - \frac{p}{q} \right| < \frac{1}{q^\nu}

for infinitely many coprime integers p and q with q > 0.

This means that the approximation error for approximating π with a rational number p/q is typically on the order of 1/q², just like most irrational numbers.

There are numbers with higher irrationality exponents. For example, Cahen’s constant C has irrationality exponent 3. This means C is an irrational number that has infinitely many rational approximations p/q with error less than 1/q³.