Re: [Cfrg] Constant-time implementations

[Adam Langley <[e-mail]>]

On Tue, Oct 14, 2014 at 6:14 AM, David Jacobson
<[e-mail]> wrote:
> Sometimes data dependent branches cannot be avoided without a serious
> performance penalty.  I'm thinking of modular inversion using the binary
> method. But it that case it is easy to use blinding.
>
> 1/k = b * (1 / (b * k))
>
> where b is a random blinding value.

In practice, field inversion is done using Fermat's little theorem. I
agree that a blinded binary inversion should be faster, but Fermat's
little theorem is simple and safe.

Quoting from the curve25591 paper: "[Inversion] is about 7% of the
Curve25519 computation. An extended-Euclid inversion of z, randomized
to protect against timing attacks, might be faster, but the maximum
potential speedup is very small, while the cost in code complexity is
large."


Cheers

AGL

-- 
Adam Langley [e-mail] https://www.imperialviolet.org