• Adam Langley's avatar
    crypto/(ec)dsa: use Fermat's inversion. · f23d3ea8
    Adam Langley authored
    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 #7652.
    
    LGTM=rsc
    R=golang-codereviews, bradfitz, rsc
    CC=golang-codereviews
    https://golang.org/cl/82740043
    f23d3ea8
ecdsa.go 4.11 KB