Re: [Cfrg] square roots

[Ilari Liusvaara <[e-mail]>]

On Thu, Jun 04, 2015 at 09:14:53AM -0700, David Jacobson wrote:
> On 6/4/15 6:27 AM, Rene Struik wrote:
> >Hi Ilari:
> >
> >Just curious about your side channel remarks: could you give an example
> >where side channel resistance of sqrt{x} is required? Wouldn't this
> >computation only arise if one were to uncompress points, or can you give
> >another example?
> >
>
> If the field modulus p is congruent to 3 mod 4, one of the square roots of x
> can be computed by x^((p+1)/4) mod p, and the inverse can computed with
> x^(p-2) mod p.  Since the exponent is known, one does not need to worry
> about leaking bits of the exponent.  Underneath that, it is just multiplies
> and adds, and of those leak were are had anyway.

I was talking about l, not p (even ECDH needs constant-time 1/x mod p,
and sqrt(x) mod p pretty much only pops up in point decompression, which
is verification side).


Sqrt(x) mod l: l can be 1 mod 8, even for p 3 mod 4 (e.g. Curve41417).
Fortunately, no signature primitive seems to use sqrt(x) mod l for anything.

1/x mod l: x^(l-2) mod l does work, but is pretty slow (there are more multiples
and each multiply is slower than with 1/x mod p). ECDSA does have this when
signing (it inverts secret k), easily creating side channels when unsafe methods
(e.g. EGCD) are used.



-Ilari