Side-channel silent modular inverse

[Torbjorn Granlund]

nisse at lysator.liu.se (Niels Möller) writes:

  Should work (except if T is computed mod B^n, one doesn't get the
  correct carry out, but that isn't needed here). But it's a bit awkward,

I realise one needs some (straightforward) handling of carry out.

  and this is a performacne critical function; some 30% of the time to
  create a side-channel silent ecdsa signature is spent doing the modular
  inversion.
  
I had neglected the significance of modular inversion for elliptic curve
arithmetic.

We need reasonable fall-back routines for the needed primitives.  We can
also implement some in assembly, but as always in the GMP setting that
is optional.  My suggestion was just for a reasonably efficient
fall-back.

Torbjörn
Please encrypt, key id 0xC8601622