Side-channel silent modular inverse

Torbjorn Granlund tg at
Fri Dec 27 15:07:17 UTC 2013

nisse at (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.  :-)


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

More information about the gmp-devel mailing list