code review 82740043: crypto/(ec)dsa: use Fermat's inversion.

crypto/(ec)dsa: use Fermat's inversion.

Now that we have a constant-time P-256 implementation, it's worth
paying more attention elsewhere.

The inversion of k in (EC)DSA was using Euclid's algorithm which isn't
constant-time. This change switches to Fermat's algorithm, which is
much better. However, it's important to note that math/big itself isn't
constant time and is using a 4-bit window for exponentiation with
variable memory access patterns.

(Since math/big depends quite deeply on its values being in minimal (as
opposed to fixed-length) represetation, perhaps crypto/elliptic should
grow a constant-time implementation of exponentiation in the scalar
field.)

R=bradfitz
Fixes issue 7652.

[agl1, 2014-03-31 17:34:29]

Hello golang-codereviews@googlegroups.com,

I'd like you to review this change to
https://code.google.com/p/go/

[agl1, 2014-04-03 15:31:22]

ping.

[bradfitz, 2014-04-03 15:33:34]

Nowadays you should either mail it to somebody (R=) or cc one or more
likely reviewers.
 On Apr 3, 2014 8:31 AM, <agl@golang.org> wrote:

> ping.
>
> https://codereview.appspot.com/82740043/
>
> --
> You received this message because you are subscribed to the Google Groups
> "golang-codereviews" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-codereviews+unsubscribe@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>

[rsc, 2014-04-03 19:30:48]

LGTM

[agl1, 2014-04-08 23:33:21]

*** Submitted as https://code.google.com/p/go/source/detail?r=8b76bd413bcb ***

crypto/(ec)dsa: use Fermat's inversion.

Now that we have a constant-time P-256 implementation, it's worth
paying more attention elsewhere.

The inversion of k in (EC)DSA was using Euclid's algorithm which isn't
constant-time. This change switches to Fermat's algorithm, which is
much better. However, it's important to note that math/big itself isn't
constant time and is using a 4-bit window for exponentiation with
variable memory access patterns.

(Since math/big depends quite deeply on its values being in minimal (as
opposed to fixed-length) represetation, perhaps crypto/elliptic should
grow a constant-time implementation of exponentiation in the scalar
field.)

R=bradfitz
Fixes issue 7652.

LGTM=rsc
R=golang-codereviews, bradfitz, rsc
CC=golang-codereviews
https://codereview.appspot.com/82740043