diff options
author | Vlad Krasnov <vlad@cloudflare.com> | 2015-04-17 06:10:35 -0700 |
---|---|---|
committer | Adam Langley <agl@golang.org> | 2015-11-10 22:16:56 +0000 |
commit | 7bacfc640fba4fb2e50bbcc16a4c15fe4bf5b870 (patch) | |
tree | 697564cd702bcc37c694e8f36b6247baa7ac9d0f /src/crypto/ecdsa/ecdsa.go | |
parent | 50fa64677611313bdd343c1dab85bf0c297d21a4 (diff) | |
download | go-7bacfc640fba4fb2e50bbcc16a4c15fe4bf5b870.tar.gz go-7bacfc640fba4fb2e50bbcc16a4c15fe4bf5b870.zip |
crypto/elliptic,crypto/ecdsa: P256 amd64 assembly
This is based on the implementation used in OpenSSL, from a
submission by Shay Gueron and myself. Besides using assembly,
this implementation employs several optimizations described in:
S.Gueron and V.Krasnov, "Fast prime field elliptic-curve
cryptography with 256-bit primes"
In addition a new and improved modular inverse modulo N is
implemented here.
The performance measured on a Haswell based Macbook Pro shows 21X
speedup for the sign and 9X for the verify operations.
The operation BaseMult is 30X faster (and the Diffie-Hellman/ECDSA
key generation that use it are sped up as well).
The adaptation to Go with the help of Filippo Valsorda
Updated the submission for faster verify/ecdh, fixed some asm syntax
and API problems and added benchmarks.
Change-Id: I86a33636747d5c92f15e0c8344caa2e7e07e0028
Reviewed-on: https://go-review.googlesource.com/8968
Run-TryBot: Adam Langley <agl@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Adam Langley <agl@golang.org>
Diffstat (limited to 'src/crypto/ecdsa/ecdsa.go')
-rw-r--r-- | src/crypto/ecdsa/ecdsa.go | 39 |
1 files changed, 34 insertions, 5 deletions
diff --git a/src/crypto/ecdsa/ecdsa.go b/src/crypto/ecdsa/ecdsa.go index 8d66477fd1..0731f2b670 100644 --- a/src/crypto/ecdsa/ecdsa.go +++ b/src/crypto/ecdsa/ecdsa.go @@ -27,6 +27,17 @@ import ( "math/big" ) +// A invertible implements fast inverse mod Curve.Params().N +type invertible interface { + // Inverse returns the inverse of k in GF(P) + Inverse(k *big.Int) *big.Int +} + +// combinedMult implements fast multiplication S1*g + S2*p (g - generator, p - arbitrary point) +type combinedMult interface { + CombinedMult(bigX, bigY *big.Int, baseScalar, scalar []byte) (x, y *big.Int) +} + const ( aesIV = "IV for ECDSA CTR" ) @@ -179,7 +190,12 @@ func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err err return } - kInv = fermatInverse(k, N) + if in, ok := priv.Curve.(invertible); ok { + kInv = in.Inverse(k) + } else { + kInv = fermatInverse(k, N) + } + r, _ = priv.Curve.ScalarBaseMult(k.Bytes()) r.Mod(r, N) if r.Sign() != 0 { @@ -214,16 +230,29 @@ func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool { return false } e := hashToInt(hash, c) - w := new(big.Int).ModInverse(s, N) + + var w *big.Int + if in, ok := c.(invertible); ok { + w = in.Inverse(s) + } else { + w = new(big.Int).ModInverse(s, N) + } u1 := e.Mul(e, w) u1.Mod(u1, N) u2 := w.Mul(r, w) u2.Mod(u2, N) - x1, y1 := c.ScalarBaseMult(u1.Bytes()) - x2, y2 := c.ScalarMult(pub.X, pub.Y, u2.Bytes()) - x, y := c.Add(x1, y1, x2, y2) + // Check if implements S1*g + S2*p + var x, y *big.Int + if opt, ok := c.(combinedMult); ok { + x, y = opt.CombinedMult(pub.X, pub.Y, u1.Bytes(), u2.Bytes()) + } else { + x1, y1 := c.ScalarBaseMult(u1.Bytes()) + x2, y2 := c.ScalarMult(pub.X, pub.Y, u2.Bytes()) + x, y = c.Add(x1, y1, x2, y2) + } + if x.Sign() == 0 && y.Sign() == 0 { return false } |