crypto/ecdsa: use bigmod and nistec instead of math/big and crypto/elliptic

Ignoring custom curves, this makes the whole package constant-time.
There is a slight loss in performance for P-384 and P-521 because bigmod
is slower than math/big (but P-256 has an assembly scalar field
inversion, so doesn't use bigmod for anything big).

name                old time/op    new time/op    delta
Sign/P256-8           19.2µs ± 2%    19.1µs ± 2%     ~     (p=0.268 n=9+10)
Sign/P384-8            166µs ± 3%     188µs ± 2%  +13.52%  (p=0.000 n=10+10)
Sign/P521-8            337µs ± 2%     359µs ± 2%   +6.46%  (p=0.000 n=10+10)
Verify/P256-8         58.1µs ± 2%    58.1µs ± 2%     ~     (p=0.971 n=10+10)
Verify/P384-8          484µs ± 2%     569µs ±12%  +17.65%  (p=0.000 n=10+10)
Verify/P521-8         1.03ms ± 4%    1.14ms ± 2%  +11.02%  (p=0.000 n=10+10)
GenerateKey/P256-8    12.4µs ±12%    12.0µs ± 2%     ~     (p=0.063 n=10+10)
GenerateKey/P384-8     129µs ±18%     119µs ± 2%     ~     (p=0.190 n=10+10)
GenerateKey/P521-8     241µs ± 2%     240µs ± 2%     ~     (p=0.436 n=10+10)

name                old alloc/op   new alloc/op   delta
Sign/P256-8           3.08kB ± 0%    2.47kB ± 0%  -19.77%  (p=0.000 n=10+10)
Sign/P384-8           6.16kB ± 0%    2.64kB ± 0%  -57.16%  (p=0.000 n=10+10)
Sign/P521-8           7.87kB ± 0%    3.01kB ± 0%  -61.80%  (p=0.000 n=10+10)
Verify/P256-8         1.29kB ± 1%    0.48kB ± 0%  -62.69%  (p=0.000 n=10+10)
Verify/P384-8         2.49kB ± 1%    0.64kB ± 0%  -74.25%  (p=0.000 n=10+10)
Verify/P521-8         3.31kB ± 0%    0.96kB ± 0%  -71.02%  (p=0.000 n=7+10)
GenerateKey/P256-8      720B ± 0%      920B ± 0%  +27.78%  (p=0.000 n=10+10)
GenerateKey/P384-8      921B ± 0%     1120B ± 0%  +21.61%  (p=0.000 n=9+10)
GenerateKey/P521-8    1.30kB ± 0%    1.44kB ± 0%  +10.45%  (p=0.000 n=10+10)

name                old allocs/op  new allocs/op  delta
Sign/P256-8             45.0 ± 0%      33.0 ± 0%  -26.67%  (p=0.000 n=10+10)
Sign/P384-8             69.0 ± 0%      34.0 ± 0%  -50.72%  (p=0.000 n=10+10)
Sign/P521-8             71.0 ± 0%      35.0 ± 0%  -50.70%  (p=0.000 n=10+10)
Verify/P256-8           23.0 ± 0%      10.0 ± 0%  -56.52%  (p=0.000 n=10+10)
Verify/P384-8           43.0 ± 0%      14.0 ± 0%  -67.44%  (p=0.000 n=10+10)
Verify/P521-8           45.0 ± 0%      14.0 ± 0%  -68.89%  (p=0.000 n=7+10)
GenerateKey/P256-8      13.0 ± 0%      14.0 ± 0%   +7.69%  (p=0.000 n=10+10)
GenerateKey/P384-8      16.0 ± 0%      17.0 ± 0%   +6.25%  (p=0.000 n=10+10)
GenerateKey/P521-8      16.5 ± 3%      17.0 ± 0%   +3.03%  (p=0.033 n=10+10)

Change-Id: I4e074ef039b0f7ffbc436a4cdbe4ef90c647018d
Reviewed-on: https://go-review.googlesource.com/c/go/+/353849
Auto-Submit: Filippo Valsorda <filippo@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Than McIntosh <thanm@google.com>
Reviewed-by: David Chase <drchase@google.com>
Run-TryBot: Filippo Valsorda <filippo@golang.org>
Reviewed-by: Roland Shoemaker <roland@golang.org>

4 files changed, 63 insertions, 9 deletions

diff --git a/src/crypto/internal/bigmod/nat.go b/src/crypto/internal/bigmod/nat.go
index 679eb34b1f..b9d09751cd 100644
--- a/src/crypto/internal/bigmod/nat.go
+++ b/src/crypto/internal/bigmod/nat.go
@@ -74,7 +74,7 @@ type Nat struct {
 // common and most performant RSA key size. It's also enough to cover some of
 // the operations of key sizes up to 4096.
 const preallocTarget = 2048
-const preallocLimbs = (preallocTarget + _W) / _W
+const preallocLimbs = (preallocTarget + _W - 1) / _W
 
 // NewNat returns a new nat with a size of zero, just like new(Nat), but with
 // the preallocated capacity to hold a number of up to preallocTarget bits.
@@ -179,10 +179,37 @@ func (x *Nat) Bytes(m *Modulus) []byte {
 }
 
 // SetBytes assigns x = b, where b is a slice of big-endian bytes.
-// SetBytes returns an error if b > m.
+// SetBytes returns an error if b >= m.
 //
 // The output will be resized to the size of m and overwritten.
 func (x *Nat) SetBytes(b []byte, m *Modulus) (*Nat, error) {
+	if err := x.setBytes(b, m); err != nil {
+		return nil, err
+	}
+	if x.cmpGeq(m.nat) == yes {
+		return nil, errors.New("input overflows the modulus")
+	}
+	return x, nil
+}
+
+// SetOverflowingBytes assigns x = b, where b is a slice of big-endian bytes. SetOverflowingBytes
+// returns an error if b has a longer bit length than m, but reduces overflowing
+// values up to 2^⌈log2(m)⌉ - 1.
+//
+// The output will be resized to the size of m and overwritten.
+func (x *Nat) SetOverflowingBytes(b []byte, m *Modulus) (*Nat, error) {
+	if err := x.setBytes(b, m); err != nil {
+		return nil, err
+	}
+	leading := _W - bitLen(x.limbs[len(x.limbs)-1])
+	if leading < m.leading {
+		return nil, errors.New("input overflows the modulus")
+	}
+	x.sub(x.cmpGeq(m.nat), m.nat)
+	return x, nil
+}
+
+func (x *Nat) setBytes(b []byte, m *Modulus) error {
 	outI := 0
 	shift := 0
 	x.resetFor(m)
@@ -197,17 +224,14 @@ func (x *Nat) SetBytes(b []byte, m *Modulus) (*Nat, error) {
 			outI++
 			if outI >= len(x.limbs) {
 				if overflow > 0 || i > 0 {
-					return nil, errors.New("input overflows the modulus")
+					return errors.New("input overflows the modulus")
 				}
 				break
 			}
 			x.limbs[outI] = uint(overflow)
 		}
 	}
-	if x.cmpGeq(m.nat) == yes {
-		return nil, errors.New("input overflows the modulus")
-	}
-	return x, nil
+	return nil
 }
 
 // Equal returns 1 if x == y, and 0 otherwise.
@@ -226,6 +250,19 @@ func (x *Nat) Equal(y *Nat) choice {
 	return equal
 }
 
+// IsZero returns 1 if x == 0, and 0 otherwise.
+func (x *Nat) IsZero() choice {
+	// Eliminate bounds checks in the loop.
+	size := len(x.limbs)
+	xLimbs := x.limbs[:size]
+
+	zero := yes
+	for i := 0; i < size; i++ {
+		zero &= ctEq(xLimbs[i], 0)
+	}
+	return zero
+}
+
 // cmpGeq returns 1 if x >= y, and 0 otherwise.
 //
 // Both operands must have the same announced length.
@@ -372,8 +409,12 @@ func bitLen(n uint) int {
 
 // Size returns the size of m in bytes.
 func (m *Modulus) Size() int {
-	bits := len(m.nat.limbs)*_W - int(m.leading)
-	return (bits + 7) / 8
+	return (m.BitLen() + 7) / 8
+}
+
+// BitLen returns the size of m in bits.
+func (m *Modulus) BitLen() int {
+	return len(m.nat.limbs)*_W - int(m.leading)
 }
 
 // Nat returns m as a Nat. The return value must not be written to.
diff --git a/src/crypto/internal/nistec/p256_asm_ordinv.go b/src/crypto/internal/nistec/p256_ordinv.go
index 86a7a230bd..86a7a230bd 100644
--- a/src/crypto/internal/nistec/p256_asm_ordinv.go
+++ b/src/crypto/internal/nistec/p256_ordinv.go
diff --git a/src/crypto/internal/nistec/p256_ordinv_noasm.go b/src/crypto/internal/nistec/p256_ordinv_noasm.go
new file mode 100644
index 0000000000..213875ce76
--- /dev/null
+++ b/src/crypto/internal/nistec/p256_ordinv_noasm.go
@@ -0,0 +1,13 @@
+// Copyright 2022 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+//go:build !amd64 && !arm64
+
+package nistec
+
+import "errors"
+
+func P256OrdInverse(k []byte) ([]byte, error) {
+	return nil, errors.New("unimplemented")
+}
diff --git a/src/crypto/internal/nistec/p256_asm_ordinv_test.go b/src/crypto/internal/nistec/p256_ordinv_test.go
index 72de6bd487..72de6bd487 100644
--- a/src/crypto/internal/nistec/p256_asm_ordinv_test.go
+++ b/src/crypto/internal/nistec/p256_ordinv_test.go