Lookup table for DSA/ECDSA/Schnorr multiplication

Question

Something in common to [EC]DSA and related signature schemes like Schnorr is that the most expensive part of signing is calculating $r = g^k$ in the group for some per-signature $k$ of length $b$ bits. But this is always taking the same generator to a power.

Because it's always the same base, we could precompute $\{g^1, g^2, g^4, ... g^{2^{b-1}}\}$ into a table. Then calculating $g^k$ is multiplying by the entries in the table corresponding to the $1$ bits of $k$. (Always do the multiply, but discard the result, for $0$ bits to stop timing and power attacks.)

This seems like it would save time, because instead of doing $b$ squares and $b$ multiplies, you'd only do $b$ multiplies.

This is most useful for signing. For verifying, you'd need a second precomputed table for the squares of the public key $y$. This could be stored as part of the public key, though, if the key length isn't a problem.

Existing implementations don't seem to do this optimization. Why not? (Or maybe I'm wrong and they do...?)

Answer 1

Actually, doing $k-1$ multiplications isn't all that much less than what can be achieved using a more sophisticated power algorithm (say, base $2^w$, for an appropriately chosen $w$) - and these algorithms don't need a precomputed table.

On the other hand, there are more sophisticated precomputational algorithms out there, which drastically reduce the number of multiplications (and sometimes also shrink the size of the table as well).

Now, I haven't seen this sort of optimization when dealing with finite field groups ($\mathbb{Z}_p^*$); in my experience, general power routines (or possibly optimizing for the case of $g=2$) appears to be the norm.

However, it is quite common when dealing with Elliptic Curve groups.

As for my speculations for why this is:

• The $\mathbb{Z}_p^*$ routines tend to be older; perhaps no one considered it worth the bother to updating them to use precomputed tables.

• The tables for $\mathbb{Z}_p^*$ would be larger (because each precomputed element would be larger).

• With ECC, you can efficiently compute inverses - we can take advantage of this to improve our precomputation algorithms somewhat, making the precomputational advantage somewhat larger.