Side-channel silent modular inverse

[Torbjorn Granlund]

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

  As you can see, it depends on a couple of other functions,
  mpn_sec_add_1, mpn_cnd_neg, mpn_cnd_swap, mpn_sec_eq_ui, which would
  probably have to be written in assembly to ensure that they avoid
  operations with branches or data-dependent timing.
  
* mpn_sec_add_1

I'd say use the obvious algorithm: Create vector of n-1 zeros and then
the input limb arg at index 0, invoke mpn_add_n.

Dedicated asm would require a lot of work, since mpn_add_n exists to
an awful lot of optimised variants.  We would need to (almost)
duplicate these implementations' code replacing one load with a
zeroing op.  MPN_ZERO is fast.
(This requires a scratch parameter.)

* mpn_cnd_neg

Create zero vector, invoke mpn_sub_n.
(This too requires a scratch parameter.)

  And its some 10 times slower than mpn_gcdext, using Lehmer's algorithm.
  
Typo overflow.  :-)


Torbjörn

"To accept selfishness as an all-purpose excuse for mistreating others
is to reject the whole idea of right and wrong" - Richard Stallman