Fast constant-time gcd computation and modular inversion

[Niels Möller]

Albin Ahlbäck <albin.ahlback at gmail.com> writes:

> Have you looked at https://eprint.iacr.org/2020/972.pdf, where the
> author seems to suggests an even faster algorithm? Or at least it was
> faster under heavy optimization under the assumption of what inputs
> the algorithm recieved.

No, I wasn't ware of that. I've now had a quick look (algorithm 2, page
6, seems to be the main part).

It's pretty close to standard extended binary, and like gmp's
mpn_sec_invert, a single innerloop iteration is one conditional
subtraction of the smaller number from the larger and right shift of a
single bit.

The trick (which is new to me) is to reduce k-1 bits by taking the least
significant k-1 bits *and* most significant approx k+1 bits of both
numbers, and then the innerloop operates only on these smaller nubmers,
ignoring the middle bits. The iteration steps are collected into a
transformation matrix.

And then have an outerloop applying that transformation matrix to the
complete numbers and the cofactors.

I haven't read the correctness argument, but there seems to be some
subtle issues: At line 3,

  n = max(len(a), len(b), 2k)

makes n data dependant, which in turn makes side-channel silent
extraction of top bits, floor (a / 2^{n-k-1}) a bit tricky, since the
way these bits straddles a boundaries becomes data dependent.

And the need for the conditional negations (lines 18 -- 21) seems
related to rounding errors from ignored middle bits.

Regards,
/Niels

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.