crypto/rsa,crypto/ecdsa,crypto/ed25519: implement PublicKey.Equal

This makes all modern public keys in the standard library implement a
common interface (below) that can be used by applications for better
type safety and allows for checking that public (and private keys via
Public()) are equivalent.

interface {
    Equal(crypto.PublicKey) bool
}

Equality for ECDSA keys is complicated, we take a strict interpretation
that works for all secure applications (the ones not using the
unfortunate non-constant time CurveParams implementation) and fails
closed otherwise.

Tests in separate files to make them x_tests and avoid an import loop
with crypto/x509.

Re-landing of CL 223754. Dropped the test that was assuming named curves
are not implemented by CurveParams, because it's not true for all
curves, and anyway is not a property we need to test. There is still a
test to check that different curves make keys not Equal.

Fixes #21704
Fixes #38035

Reviewed-on: https://go-review.googlesource.com/c/go/+/223754
Reviewed-by: Katie Hockman <katie@golang.org>
Change-Id: I736759b145bfb4f7f8eecd78c324315d5a05385c
Reviewed-on: https://go-review.googlesource.com/c/go/+/225460
Run-TryBot: Filippo Valsorda <filippo@golang.org>
Run-TryBot: Bryan C. Mills <bcmills@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
diff --git a/src/crypto/ecdsa/ecdsa.go b/src/crypto/ecdsa/ecdsa.go
index 744182a..189399d 100644
--- a/src/crypto/ecdsa/ecdsa.go
+++ b/src/crypto/ecdsa/ecdsa.go
@@ -62,6 +62,24 @@
 	X, Y *big.Int
 }
 
+// Equal reports whether pub and x have the same value.
+//
+// Two keys are only considered to have the same value if they have the same Curve value.
+// Note that for example elliptic.P256() and elliptic.P256().Params() are different
+// values, as the latter is a generic not constant time implementation.
+func (pub *PublicKey) Equal(x crypto.PublicKey) bool {
+	xx, ok := x.(*PublicKey)
+	if !ok {
+		return false
+	}
+	return pub.X.Cmp(xx.X) == 0 && pub.Y.Cmp(xx.Y) == 0 &&
+		// Standard library Curve implementations are singletons, so this check
+		// will work for those. Other Curves might be equivalent even if not
+		// singletons, but there is no definitive way to check for that, and
+		// better to err on the side of safety.
+		pub.Curve == xx.Curve
+}
+
 // PrivateKey represents an ECDSA private key.
 type PrivateKey struct {
 	PublicKey
diff --git a/src/crypto/ecdsa/equal_test.go b/src/crypto/ecdsa/equal_test.go
new file mode 100644
index 0000000..9b507dd
--- /dev/null
+++ b/src/crypto/ecdsa/equal_test.go
@@ -0,0 +1,66 @@
+// Copyright 2020 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.
+
+package ecdsa_test
+
+import (
+	"crypto"
+	"crypto/ecdsa"
+	"crypto/elliptic"
+	"crypto/rand"
+	"crypto/x509"
+	"testing"
+)
+
+func testEqual(t *testing.T, c elliptic.Curve) {
+	private, _ := ecdsa.GenerateKey(c, rand.Reader)
+	public := &private.PublicKey
+
+	if !public.Equal(public) {
+		t.Errorf("public key is not equal to itself: %v", public)
+	}
+	if !public.Equal(crypto.Signer(private).Public().(*ecdsa.PublicKey)) {
+		t.Errorf("private.Public() is not Equal to public: %q", public)
+	}
+
+	enc, err := x509.MarshalPKIXPublicKey(public)
+	if err != nil {
+		t.Fatal(err)
+	}
+	decoded, err := x509.ParsePKIXPublicKey(enc)
+	if err != nil {
+		t.Fatal(err)
+	}
+	if !public.Equal(decoded) {
+		t.Errorf("public key is not equal to itself after decoding: %v", public)
+	}
+
+	other, _ := ecdsa.GenerateKey(c, rand.Reader)
+	if public.Equal(other) {
+		t.Errorf("different public keys are Equal")
+	}
+
+	// Ensure that keys with the same coordinates but on different curves
+	// aren't considered Equal.
+	differentCurve := &ecdsa.PublicKey{}
+	*differentCurve = *public // make a copy of the public key
+	if differentCurve.Curve == elliptic.P256() {
+		differentCurve.Curve = elliptic.P224()
+	} else {
+		differentCurve.Curve = elliptic.P256()
+	}
+	if public.Equal(differentCurve) {
+		t.Errorf("public keys with different curves are Equal")
+	}
+}
+
+func TestEqual(t *testing.T) {
+	t.Run("P224", func(t *testing.T) { testEqual(t, elliptic.P224()) })
+	if testing.Short() {
+		return
+	}
+	t.Run("P256", func(t *testing.T) { testEqual(t, elliptic.P256()) })
+	t.Run("P384", func(t *testing.T) { testEqual(t, elliptic.P384()) })
+	t.Run("P521", func(t *testing.T) { testEqual(t, elliptic.P521()) })
+}
diff --git a/src/crypto/ed25519/ed25519.go b/src/crypto/ed25519/ed25519.go
index dcb4f95..b4f6956 100644
--- a/src/crypto/ed25519/ed25519.go
+++ b/src/crypto/ed25519/ed25519.go
@@ -40,6 +40,15 @@
 // PublicKey is the type of Ed25519 public keys.
 type PublicKey []byte
 
+// Equal reports whether pub and x have the same value.
+func (pub PublicKey) Equal(x crypto.PublicKey) bool {
+	xx, ok := x.(PublicKey)
+	if !ok {
+		return false
+	}
+	return bytes.Equal(pub, xx)
+}
+
 // PrivateKey is the type of Ed25519 private keys. It implements crypto.Signer.
 type PrivateKey []byte
 
diff --git a/src/crypto/ed25519/ed25519_test.go b/src/crypto/ed25519/ed25519_test.go
index cacd281..98e22a7 100644
--- a/src/crypto/ed25519/ed25519_test.go
+++ b/src/crypto/ed25519/ed25519_test.go
@@ -88,6 +88,22 @@
 	}
 }
 
+func TestEqual(t *testing.T) {
+	public, private, _ := GenerateKey(rand.Reader)
+
+	if !public.Equal(public) {
+		t.Errorf("public key is not equal to itself: %q", public)
+	}
+	if !public.Equal(crypto.Signer(private).Public().(PublicKey)) {
+		t.Errorf("private.Public() is not Equal to public: %q", public)
+	}
+
+	other, _, _ := GenerateKey(rand.Reader)
+	if public.Equal(other) {
+		t.Errorf("different public keys are Equal")
+	}
+}
+
 func TestGolden(t *testing.T) {
 	// sign.input.gz is a selection of test cases from
 	// https://ed25519.cr.yp.to/python/sign.input
diff --git a/src/crypto/rsa/equal_test.go b/src/crypto/rsa/equal_test.go
new file mode 100644
index 0000000..b00d0ea
--- /dev/null
+++ b/src/crypto/rsa/equal_test.go
@@ -0,0 +1,42 @@
+// Copyright 2020 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.
+
+package rsa_test
+
+import (
+	"crypto"
+	"crypto/rand"
+	"crypto/rsa"
+	"crypto/x509"
+	"testing"
+)
+
+func TestEqual(t *testing.T) {
+	private, _ := rsa.GenerateKey(rand.Reader, 512)
+	public := &private.PublicKey
+
+	if !public.Equal(public) {
+		t.Errorf("public key is not equal to itself: %v", public)
+	}
+	if !public.Equal(crypto.Signer(private).Public().(*rsa.PublicKey)) {
+		t.Errorf("private.Public() is not Equal to public: %q", public)
+	}
+
+	enc, err := x509.MarshalPKIXPublicKey(public)
+	if err != nil {
+		t.Fatal(err)
+	}
+	decoded, err := x509.ParsePKIXPublicKey(enc)
+	if err != nil {
+		t.Fatal(err)
+	}
+	if !public.Equal(decoded) {
+		t.Errorf("public key is not equal to itself after decoding: %v", public)
+	}
+
+	other, _ := rsa.GenerateKey(rand.Reader, 512)
+	if public.Equal(other) {
+		t.Errorf("different public keys are Equal")
+	}
+}
diff --git a/src/crypto/rsa/rsa.go b/src/crypto/rsa/rsa.go
index d058949..5a429906 100644
--- a/src/crypto/rsa/rsa.go
+++ b/src/crypto/rsa/rsa.go
@@ -50,6 +50,15 @@
 	return (pub.N.BitLen() + 7) / 8
 }
 
+// Equal reports whether pub and x have the same value.
+func (pub *PublicKey) Equal(x crypto.PublicKey) bool {
+	xx, ok := x.(*PublicKey)
+	if !ok {
+		return false
+	}
+	return pub.N.Cmp(xx.N) == 0 && pub.E == xx.E
+}
+
 // OAEPOptions is an interface for passing options to OAEP decryption using the
 // crypto.Decrypter interface.
 type OAEPOptions struct {