Extending the mpn interface

[Niels Möller]

I'm currently working on some cryptograpic elliptic curve code, using
gmp for underlying bignum numbers (of moderate size, largest operation
is multiply with 17 limb inputs).

I think I want to keep using mpz_t for user-visible functions, but I'm
leaning towards using the mpn interface internally, for two main
reasons:

* I want to get control over the timing of operations, to avoid timing
  side-channels

* I'd like to write optimized code for computing mod p for certain fixed
  p with nice structure, and those functions have to work on
  mpn-representation.

But I miss some features in the public interface to do this
conveniently; both for mpn <-> mpz interoperation, and there are also
some mpn functions which would be very useful but which are not part of
the public interface.

For the first issue, it would be nice to have

1. A way to extract an mpn number (pointer and length) from an mpz_t,
   for read-only use. I.e., getting the _mp_d and _mp_size.

2. A way to extract an mpn number from an mpz_t, for writing. User has
   to provide maximum size, and then we also need a way to update the
   actual size when done. Basically, this is MPZ_REALLOC/MPZ_NEWALLOC
   and MPN_NORMALIZE.

3. A way to construct an mpz_t from an mpn, for read-only use. A bit
   like MPZ_TMP_INIT, but preferably with a macro expanding to an
   initializer, something like

     #define MPZ_FROM_MPN(p, n) {{ 0, (n), (p) }}
   
     mpz_t x = MPZ_FROM_MPN (xp, xn);

   Then this could be used also for compile-time constant mpz values.

Currently, the only really kosher way to do this is to go via mpz_export
and mpz_import, which isn't particularly convenient, and which also adds
a bit more overhead than I'd like.

What do you think? I think such interfaces can be defined to be safe
across gmp releases. It's ok with function-call overhead for (1) and (2)
and if necessary even for (3), but it would be ideal if they can be
defined without any extra overhead, so that the same interfaces can be
used internally in GMP.

For the second issue, here are some functions which I'm missing in the
public interface:

* mpn_mul_basecase (possibly under some other name, like mpn_mul_small
  or mpn_mul_sec). The most important thing is to have a side-channel
  silent multiply, but it would be nice to also avoid overhead which is
  needed only for largish numbers.

* mpn_addlsh_n, with fallback to mpn_addmul_1, if there's no special
  loop for this. Possibly also for other variants of shift-and-add.

* mpn_addcnd_n and mpn_subcnd_n (BTW, I wonder if the current C
  implementation is faster or slower than calling assembly
  mpn_addmul_1?). Possibly also mpn_addcnd_nc and mpn_subcnd_nc.

* mpn_powm_sec.

* mpn_add_nc, mpn_sub_nc (would it be difficult to ensure these are
  defined on all platforms)?

I think these functions are sufficiently well-understood that we can
design and commit to a public interface.

And a couple of functions I would need are missing:

* mpn_copycnd, like

    void
    mpn_copycnd (int cnd, mp_limb_t *rp, const mp_limb_t *ap, mp_size_t n)
    {
      mp_limb_t mask, keep;
      mp_size_t i;
    
      mask = -(mp_limb_t) (cnd !=0);
      keep = ~mask;
    
      for (i = 0; i < n; i++)
        rp[i] = (rp[i] & keep) + (ap[i] & mask);
    }

  (related to mpn_tabselect).

* mpn_add_1_sec and mpn_sub_1_sec. O(n) operations, always propagating
  carry all the way.

I you think some or all of these extensions of the mpn interface make
sense, I may be able to spend some time on this.

Regards,
/Niels

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