mpn_sec_powm

[Niels Möller]

After some discussion with Torbjörn, I intend to change mpn_sec_powm to
take the exponent size argument in bits, rather than limbs (because the
current code may leak high bit of the exponent, which can cause serious
problems for some applications, e.g., dsa signatures). But first, I'd
like to fix a more minor issue.

The window size k should always be smaller than exponent size, k <= eb.
I.e, if you have an exponent of eb bits, the largest window size should
correspond to computing a table of all 2^{eb} powers, and then select
one of them. This works fine, except for corner cases in the tuning of
adding a corresponding assert gives an assertion failure from tuneup.

Say the POWM_SEC_TABLE table (created by tuneup) starts with 1, then the
win_size function uses a table like

  x[] = { 0, 1, 17, ..., ~(mp_bitcnt_t) 0}

The window size k (k >= 1) is chosen so that x[k-1] < eb <= x[k].
So we get

  eb = 1  ==>  k = 1
  eb = 2  ==>  k = 2
  eb = 3  ==>  k = 2

On the other hand, if the tuned table starts with 2, we get

  x[] = { 0, 2, 17, ..., ~(mp_bitcnt_t) 0}

  eb = 1  ==>  k = 1
  eb = 2  ==>  k = 1
  eb = 3  ==>  k = 2

So it differs only for eb = 2: are going to use a window size of either
1 or 2 bits in this case.

But if the tuneup program generates a first entry of 1, or a larger
value, is based on comparison of exponent size of 1 bit with the two
window sizes k == 1 and k == 2. And eb = 1 and k = 2 violates the k <=
eb condition (and any corresponding assert), and generally makes no
sense; it means we compute a table of 4 entries, and then use the
exponent bit to select one of the two first entries.

So there's some kind of off-by-one error here. I think tuning should
start with nbits = 2 (that's tuneup's name for the exponent size, and
the first size where it makes sense to try a window k > 1), and time k =
1 and k = 2. And if k = 2 was faster, output nbits - 1 == 1, not nbits
like the current code.

It might also be interesting to note that there's only a single
gmp-mparam.h file where POWM_SEC_TABLE starts with 1: x86_64/bobcat.
There are a larger number of gmp-mparam.h files where it starts with 2,
which would shrink to 1 if the code is fixed to emit nbits - 1.

All this might not be terribly important, but there is a conditional for
eb < windowsize (before the loop, i.e., for the initial value of eb), not
exercised by the testsuite, but needed because of this tuneup
peculiarity (see
https://gmplib.org/devel/lcov/shell/tmp/lcov/gmp/mpn/sec_powm.c.gcov.html).
And I'd like to eliminate that test.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.