Re: [Cfrg] 40 bit loop and DragonFly

[David Jacobson <[e-mail]>]

On 1/6/14 8:46 AM, Igoe, Kevin M. wrote:
> [snip]
> 4) That just leaves multiplying sqrt((r**2)*f ) = r*sqrt(f)
> by (1/r) => need to calculate 1/r, which can be done either
> by an exponentiation or by the extended Euclidean algorithm.
> Since the extended Euclidean algorithm is variable time, it
> might leak information about r, so exponentiating by p-2 is
> the safer alternative.  Fortunately, this only has to be done
> once, not "40" times.
>
>

Isn't this easy?  Choose a random non-zero b from the same field as r.  
Compute b*(r*sqrt(f)) and b*r.  Compute 1/(b*r).  Since all values of b 
are equally likely and the attacker does not know b, any leakage from 
the inverse that makes some values of b*r more likely gives no 
information at all about r.  Now compute (b*(r*sqrt(f)) * (1/(b*r))  = 
sqrt(f).

      --David