1
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ For $\mathbb{Z}_p^*$ and $g=2$, computing the result for the first $\lfloor\log_2 \log_2 p\rfloor - 1$ bits of $k$ is a single bit, a slight additional optimization. $\endgroup$ – Myria Jul 8 at 22:32
  • $\begingroup$ @Myria: for standard DSA (FIPS 186), g can't be 2; more exactly g must have order q which is 160, 224 or 256 bits depending on the security parameter, and the chance of g=2 doing so is negligible. A mathematically equivalent scheme could allow (or even require) g=2. For DH X9.42 and RFC2631 also specify q and g this way, but in practice many DH implementations allow and often default to g=2 (and usually p=2q+1). $\endgroup$ – dave_thompson_085 Aug 3 at 9:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.