Napkin Cryptography

I was a cryptography researcher in a past life. Occasionally I experience echoes from my previous incarnation: a paper review here, a technical question there, so I still feel somewhat connected.

A couple of weeks ago I bumped into Daniel J. Bernstein and Tanja Lange, whom I had last seen in 2003 at a conference in Chicago. [Thanks to Dan for inviting me, and also for taking everyone out to the downtown bars and restaurants. I had a blast!] Only then did I realize how far I had fallen from the light. In a hurried notes-on-a-napkin conversation I tried to catch up on what was once my field:

2048 is the new 1024

Firstly, I was mildly surprised when I learned governments and standards bodies are actually heeding warnings that 1024-bit RSA keys are crackable by large corporations and botnets, thus now mandate 2048-bit keys.

Ah, the memories. Just how vulnerable are 1024-bit keys? Back in the ivory tower, this was the subject of an intense high-profile debate, with Bernstein on one side, and Lenstra, Shamir, Tomlinson and Tromer on the other. The heated arguments seemed to get personal at times, providing excellent fodder for gossip amongst us grad students.

I have no idea if the parties ever reconciled, nor if the fireworks have even subsided, but I’m relieved that everybody agrees 1024 bits is insufficient nowadays.

Fast ECC

More interesting to me are the new breed of elliptic curve cryptography (ECC) implementations. Dan instructed me to "forget everything you know about elliptic curves" before launching into the world’s fastest course on the world’s fastest algorithms for elliptic curves.

Consider a unit circle, x² + y² = 1. We can define a group operation on the points of the unit circle via angle addition. It’s easiest to describe with polar coordinates I suppose: cis(α) composed with cis(β) gives cis(α+β). Except for some reason we want (0,1) to be the identity so make that cis(α+β-π).

In Cartesian coordinates, if the two input points are (x₁, y₁) and (x₂, y₂) then we get (x₁ y₂ + x₂ y₁, y₁ y₂ - x₁ x₂). Let us denote this point by (a, b).

An Edwards curve is a deformed circle that is equivalent to an elliptic curve in some sense. There is some deal about requiring a point of order 4, which is probably related to the quadrilateral symmetry of the Edwards curve. It is parameterized by d which I’m guessing is akin to the j-invariant, and has the equation x² + y² = 1 + d x² y².

Using the above notation, group addition produces the point (a / (1 + D), b / (1 - D)) where D = d x₁ x₂ y₁ y₂. Unlike elliptic curves, the same formula applies for identical inputs, and the also for the identity element: in paricular, there is no special formula for point doubling. From this equation one can write code to multiply points at breakneck speed.

Montgomery curves are given by B y² = x³ + A x² + x, and possess fast point addition with one big string attached: you can only add P and Q if you know P - Q; this point forms the base of an addition "ladder". This is fine for exponentiations and hence ECDSA, but may be unsuitable for other cryptosystems.

The details, and more, can be found at the Explicit-Formulas Database. Also, see this highly optimized implementation of the curve 25519.

DNSCurve

To Dan, speedy ECC is merely a means to an end: a brilliant and diabolical scheme to usurp DNSSEC with DNSCurve. If DNSSEC does indeed have the drawbacks he described, then I wish him well. Kill it before it spreads! The Denial-of-Service attack amplification issue is enough to justify revoking its netizenship.

Pairings

For the PBC library, the good news is that Weierstrass curves are still the best known way to get at pairings (because of the order 4 point brouhaha), though research on alternate curves for pairing computation continues at a furious pace.

The bad news is that the sample pairing parameters I’ve been distributing are mostly too weak. Additionally, Barreto-Naehrig curves, the least-optimized case in the library, are arguably now the most important pairing type.

By the way, our discussion literally involved scribbling on a serviette:

Alas, I am not a coauthor of this paper: the handwriting belongs exclusively to Bernstein and Lange.