May 2017 Archives

Once upon a time, the cool kids used $w$-NAF for their elliptic curve scalar multiplication. Well, the cool kids who were implementing elliptic curve cryptography anyway.

The basic idea is simple enough. You want to multiply some given point $Q$ by a scalar $n$. So you pick a window width $w$, and split $n$ into a sum of signed $w$-bit pieces \[ n = \sum_i n_i 2^i \] with $-2^{w-1} \le n_i < 2^{w-1}$ for each $i$, and with at most one nonzero $n_i$ in any group of $w$. Then you walk through these, in descending order of $i$, multiplying an accumulator by appropriate small multiples of $Q$ plucked from a table and doubling.

Then we found out that actually this was a mostly terrible idea because it broadcasts $n$ through every side-channel available. The new cool idea is to convert $n$ to a signed-digit representation, so \[ n = \sum_i n_i 2^{wi} \] again, with $-2^{w-1} \le n_i < 2^{w-1}$. Now the digits are in predictable places, and all you need to avoid leakage is to do a constant-time table lookup.

This is annoying. And a waste of time and effort. There’s a unique representation of $n$ subject to these constraints. It’s possible to do the signed-digit recoding from right to left in constant time, propagating loans (like borrows in subtraction, but in the other direction) as you go. But you want to do the scalar multiplication from left to right so that you can use your table of small multiples. And, while you can do the signed-digit recoding left-to-right, you might need to look arbitrarily far ahead before you can commit to a digit. (If you see a long sequence of $2^{w-1} - 1$ digits, then you’ll have to inspect the digit after that to tell you whether they all lend one leftwards or not.) I suppose you could do this in constantly quadratic time, but I don’t think anyone would be impressed by that.

But you can have your cake and eat it too, as long as you give up on the unique representation. Relax the condition on $n_i$ to permit $2^{w-1} \le n_i \le 2^{w-1}$ and all is marvellous.

• You can calculate an acceptable recoding in one pass, left to right, with one digit lookahead, and therefore in constant time.

• You can do this in the same pass as the main scalar multiplication, with no additional storage.

• You can work with the same size table of small multiples of $Q$. You already had to cope with the possibility of $n_i = -2^{w-1}$, and dealing with $n_i = \pm 2^{w-1}$ is no harder.

So, suppose you have a current digit $t$, and a lookahead digit $u$. (You start out with $t = 0$ and $u$ is the leftmost digit of $n$ in its standard radix-$2^w$ representation.) If $u \ge 2^{w-1}$, then set $t \gets t + 1$ and $u \gets u - 2^w$ (a loan leftwards); otherwise $u < 2^{2-1}$ and you do nothing. You can now commit to $t$: add $t Q$ to your accumulator or whatever. And finally, move along by setting $t \gets u$ and fetching the next input digit into $u$. At this point, you have $-2^{w-1} \le t < 2^{w-1}$, but you might end up adding one to it when you look at $u$; hence the bound above.

One of the neat things that makes Ed25519 such a fast signature scheme is a clever algorithm for point decompression.

You’re given the point’s $y$-coordinate, and have to calculate $x = \pm\sqrt{(y^2 - 1)/(d y^2 + 1)}$. The naïve approach is to observe that inversion takes a modexp, and square root takes a modexp, so we need two modexps. The Ed25519 authors noticed that you can do both jobs with one modexp. There are two problems which need cleverness: one is how to combine the division and square root calculations; and the other is how to actually calculate a square root in $\mathbb{F}_{2^{255}-19}$ in the first place.

The latter problem is that $p = 2^{255} - 19 \equiv 5 \pmod{8}$, so you can’t calculate square roots directly. Their clever solution, which I can’t improve on, is as follows. Suppose we’re given some $v$, which we know (or are willing to assume) is a square. Therefore, $v$ has order $(p - 1)/2$. The trick is to notice that, if we let $w = v^{(p+3)/8}$, then $w^4 = v^{(p+3)/2} = v^{(p-1)/2} v^2 = v^2$. Therefore $w^2 = \pm v$. Conveniently $-1$ is a square in this field, so we can use $w$ as our square root of $v$ if $w^2 = v$, or pick $i w$ if $w^2 = -v$ (where $i = \sqrt{-1}$).

The paper suggests that, given the problem of calculating a square root of $x/y$, to compute $w = x y^3 (x y^7)^{(p-5)/8}$. This I can make better.

Instead, I suggest calculating $v = x y$, and $w = x v^{3(p-5)/8+1}$. Then $w^4 = x^4 v^{3(p-5)/2+4} = x^4 v^{(3p-7)/2} = x^4 v^{3(p-1)/2-2} = x^4 v^{-2} (v^{(p-1)/2})^3 = x^4/v^2 = x^4/(x^2 y^2) = x^2/y^2$. Phew!

Of course, I didn’t figure it out in that direction. Indeed, I started out with a different problem, in a different field. Specifically, I wanted to decompress a point on the Ed448-Goldilocks curve, over the field $\mathbb{F}_{\phi^2-\phi-1}$, where $\phi = 2^{224}$. Helpfully, $q = \phi^2 - \phi - 1 \equiv 3 \pmod{4}$ because everything about this prime is awesome, so you can compute square roots in $\mathbb{F}_q$ as $\sqrt{v} = w = v^{(q+1)/4}$, since $w^2 = v^{(q+1)/2} = v^{(q-1)/2} v = v$. Which leaves the problem of combining this with division.

I found myself reasoning by analogy with Montgomery’s inversion trick. (If you want to compute both $x^{-1}$ and $y^{-1}$, then let $z = x y$, and compute $x^{-1} = y z^{-1}$ and similarly for $y$.) If I can find a square root $w’$ of $v = 1/x y$, then $w = x w’$ will be a square root of $x/y$. This replaces the problem of division with the problem of inversion. At this point, it’s sort of easy. I’ll go back to the Ed25519 field, and leave the Goldilocks version as an exercise. (Or you can cheat and peek at the Catacomb source code. RFC8032 is no help: it gives an unnecessarily complicated version, similar to the Ed25519 formula above.)

I’ll assume $v$ has order $(p - 1)/2$, so to invert I need to raise to the power $(p - 3)/2$ to find $1/v$. Then I raise to the power $(p + 3)/8$ to find the maybe-square-root of $1/v$ which might be off by a factor of $i$. But if I do these one after the other, then I can just multiply them modulo $(p - 1)/2$. That’s going to be a nuisance because of the divisions. But wait! These are all whole numbers. How do I know this? Because $p \equiv 5 \pmod{8}$. So let’s actually write $p = 8 t + 5$. Then the group of quadratic residues has order $4 t + 2$. To invert, I raise to the power $4 t + 1$; and to find the maybe-square-root, I raise to the power $t + 1$. Altogether, then, I want $m = (4 t + 1) (t + 1) = 4 t^2 + 5 t + 1 = t (4 t + 2) + 3 t + 1 \equiv 3 t + 1 = 3 (p - 5)/8 + 1 \pmod{4 t + 2}$. And I’m done.

[Edited 2017-09-20: Fix a typo in the description of Montgomery’s inversion trick.]