Fast constant-time gcd computation and modular inversion

[Niels Möller]

Torbjörn Granlund <tg at gmplib.org> writes:

> That count is a proven "upper bound" of the numbver of iterations.  Does
> the paper discuss how tight it is, i.e., is it close to a "lower bound"
> of the required number of iterations.

As an upper bound, I think it's rather tight at least for smallish
sizes, since proof includes an exhastive search up to some small limit
on bit size, and the results from that guide the approach for the
general proof. (It's rather complex, I don't get all the details).

Much more unclear to me how close it might be to the typical or average
number of iterations needed.

> Comparing to the existing side-channel-silent inversion code would 
> impress more, I think.

That would be a very relevant benchmark, yes. Omitted in this version
just because interface is a bit different from what's used in the prototype.

> What percentage of Ec scalar mul is used for the final inversion?  Not
> much, I suppose. 

After a quick look at my benchmark numbers, if one compares the time for 

A. inversion modulo the field prime, and

B. scalar multiplication using the fixed generator point, and with
   output in projective or jacobian coordinates (i.e., inverse free),

then ratio A/B is in the range 10% (smaller curves) to 16% for ed448.

> Does Nettle use exponentiation there today, or
> mpn_sec_invert?

Currently uses exponentiation for the field inverse, and nettle's
version of sec_invert for inverses mod the group order, as needed by
ecdsa. Except for the somewhat obscure gost curves (Russian standards),
where sec_invert is used for all inverses, and A/B for gost-gc512a is
almost 30%.

Regards,
/Niels

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