Side-channel silent modular inverse
tg at gmplib.org
Fri Dec 27 15:07:17 UTC 2013
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.
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.)
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