libgo: update to go1.15rc1

Reviewed-on: https://go-review.googlesource.com/c/gofrontend/+/245157

2 files changed, 186 insertions, 44 deletions

diff --git a/libgo/go/crypto/elliptic/elliptic.go b/libgo/go/crypto/elliptic/elliptic.go
index e2f71cd..f93dc16 100644
--- a/libgo/go/crypto/elliptic/elliptic.go
+++ b/libgo/go/crypto/elliptic/elliptic.go
@@ -20,7 +20,10 @@ import (
 )
 
 // A Curve represents a short-form Weierstrass curve with a=-3.
-// See https://www.hyperelliptic.org/EFD/g1p/auto-shortw.html
+//
+// Note that the point at infinity (0, 0) is not considered on the curve, and
+// although it can be returned by Add, Double, ScalarMult, or ScalarBaseMult, it
+// can't be marshaled or unmarshaled, and IsOnCurve will return false for it.
 type Curve interface {
 	// Params returns the parameters for the curve.
 	Params() *CurveParams
@@ -52,11 +55,8 @@ func (curve *CurveParams) Params() *CurveParams {
 	return curve
 }
 
-func (curve *CurveParams) IsOnCurve(x, y *big.Int) bool {
-	// y² = x³ - 3x + b
-	y2 := new(big.Int).Mul(y, y)
-	y2.Mod(y2, curve.P)
-
+// polynomial returns x³ - 3x + b.
+func (curve *CurveParams) polynomial(x *big.Int) *big.Int {
 	x3 := new(big.Int).Mul(x, x)
 	x3.Mul(x3, x)
 
@@ -67,7 +67,15 @@ func (curve *CurveParams) IsOnCurve(x, y *big.Int) bool {
 	x3.Add(x3, curve.B)
 	x3.Mod(x3, curve.P)
 
-	return x3.Cmp(y2) == 0
+	return x3
+}
+
+func (curve *CurveParams) IsOnCurve(x, y *big.Int) bool {
+	// y² = x³ - 3x + b
+	y2 := new(big.Int).Mul(y, y)
+	y2.Mod(y2, curve.P)
+
+	return curve.polynomial(x).Cmp(y2) == 0
 }
 
 // zForAffine returns a Jacobian Z value for the affine point (x, y). If x and
@@ -277,7 +285,7 @@ var mask = []byte{0xff, 0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f}
 func GenerateKey(curve Curve, rand io.Reader) (priv []byte, x, y *big.Int, err error) {
 	N := curve.Params().N
 	bitSize := N.BitLen()
-	byteLen := (bitSize + 7) >> 3
+	byteLen := (bitSize + 7) / 8
 	priv = make([]byte, byteLen)
 
 	for x == nil {
@@ -302,30 +310,40 @@ func GenerateKey(curve Curve, rand io.Reader) (priv []byte, x, y *big.Int, err e
 	return
 }
 
-// Marshal converts a point into the uncompressed form specified in section 4.3.6 of ANSI X9.62.
+// Marshal converts a point on the curve into the uncompressed form specified in
+// section 4.3.6 of ANSI X9.62.
 func Marshal(curve Curve, x, y *big.Int) []byte {
-	byteLen := (curve.Params().BitSize + 7) >> 3
+	byteLen := (curve.Params().BitSize + 7) / 8
 
 	ret := make([]byte, 1+2*byteLen)
 	ret[0] = 4 // uncompressed point
 
-	xBytes := x.Bytes()
-	copy(ret[1+byteLen-len(xBytes):], xBytes)
-	yBytes := y.Bytes()
-	copy(ret[1+2*byteLen-len(yBytes):], yBytes)
+	x.FillBytes(ret[1 : 1+byteLen])
+	y.FillBytes(ret[1+byteLen : 1+2*byteLen])
+
 	return ret
 }
 
+// MarshalCompressed converts a point on the curve into the compressed form
+// specified in section 4.3.6 of ANSI X9.62.
+func MarshalCompressed(curve Curve, x, y *big.Int) []byte {
+	byteLen := (curve.Params().BitSize + 7) / 8
+	compressed := make([]byte, 1+byteLen)
+	compressed[0] = byte(y.Bit(0)) | 2
+	x.FillBytes(compressed[1:])
+	return compressed
+}
+
 // Unmarshal converts a point, serialized by Marshal, into an x, y pair.
 // It is an error if the point is not in uncompressed form or is not on the curve.
 // On error, x = nil.
 func Unmarshal(curve Curve, data []byte) (x, y *big.Int) {
-	byteLen := (curve.Params().BitSize + 7) >> 3
+	byteLen := (curve.Params().BitSize + 7) / 8
 	if len(data) != 1+2*byteLen {
-		return
+		return nil, nil
 	}
 	if data[0] != 4 { // uncompressed form
-		return
+		return nil, nil
 	}
 	p := curve.Params().P
 	x = new(big.Int).SetBytes(data[1 : 1+byteLen])
@@ -339,6 +357,37 @@ func Unmarshal(curve Curve, data []byte) (x, y *big.Int) {
 	return
 }
 
+// UnmarshalCompressed converts a point, serialized by MarshalCompressed, into an x, y pair.
+// It is an error if the point is not in compressed form or is not on the curve.
+// On error, x = nil.
+func UnmarshalCompressed(curve Curve, data []byte) (x, y *big.Int) {
+	byteLen := (curve.Params().BitSize + 7) / 8
+	if len(data) != 1+byteLen {
+		return nil, nil
+	}
+	if data[0] != 2 && data[0] != 3 { // compressed form
+		return nil, nil
+	}
+	p := curve.Params().P
+	x = new(big.Int).SetBytes(data[1:])
+	if x.Cmp(p) >= 0 {
+		return nil, nil
+	}
+	// y² = x³ - 3x + b
+	y = curve.Params().polynomial(x)
+	y = y.ModSqrt(y, p)
+	if y == nil {
+		return nil, nil
+	}
+	if byte(y.Bit(0)) != data[0]&1 {
+		y.Neg(y).Mod(y, p)
+	}
+	if !curve.IsOnCurve(x, y) {
+		return nil, nil
+	}
+	return
+}
+
 var initonce sync.Once
 var p384 *CurveParams
 var p521 *CurveParams
diff --git a/libgo/go/crypto/elliptic/elliptic_test.go b/libgo/go/crypto/elliptic/elliptic_test.go
index 09c5483..e80e773 100644
--- a/libgo/go/crypto/elliptic/elliptic_test.go
+++ b/libgo/go/crypto/elliptic/elliptic_test.go
@@ -5,6 +5,7 @@
 package elliptic
 
 import (
+	"bytes"
 	"crypto/rand"
 	"encoding/hex"
 	"fmt"
@@ -417,41 +418,62 @@ func TestP256Mult(t *testing.T) {
 	}
 }
 
-func TestInfinity(t *testing.T) {
-	tests := []struct {
-		name  string
-		curve Curve
-	}{
-		{"p224", P224()},
-		{"p256", P256()},
+func testInfinity(t *testing.T, curve Curve) {
+	_, x, y, _ := GenerateKey(curve, rand.Reader)
+	x, y = curve.ScalarMult(x, y, curve.Params().N.Bytes())
+	if x.Sign() != 0 || y.Sign() != 0 {
+		t.Errorf("x^q != ∞")
 	}
 
-	for _, test := range tests {
-		curve := test.curve
-		x, y := curve.ScalarBaseMult(nil)
-		if x.Sign() != 0 || y.Sign() != 0 {
-			t.Errorf("%s: x^0 != ∞", test.name)
-		}
+	x, y = curve.ScalarBaseMult([]byte{0})
+	if x.Sign() != 0 || y.Sign() != 0 {
+		t.Errorf("b^0 != ∞")
 		x.SetInt64(0)
 		y.SetInt64(0)
+	}
 
-		x2, y2 := curve.Double(x, y)
-		if x2.Sign() != 0 || y2.Sign() != 0 {
-			t.Errorf("%s: 2∞ != ∞", test.name)
-		}
+	x2, y2 := curve.Double(x, y)
+	if x2.Sign() != 0 || y2.Sign() != 0 {
+		t.Errorf("2∞ != ∞")
+	}
 
-		baseX := curve.Params().Gx
-		baseY := curve.Params().Gy
+	baseX := curve.Params().Gx
+	baseY := curve.Params().Gy
 
-		x3, y3 := curve.Add(baseX, baseY, x, y)
-		if x3.Cmp(baseX) != 0 || y3.Cmp(baseY) != 0 {
-			t.Errorf("%s: x+∞ != x", test.name)
-		}
+	x3, y3 := curve.Add(baseX, baseY, x, y)
+	if x3.Cmp(baseX) != 0 || y3.Cmp(baseY) != 0 {
+		t.Errorf("x+∞ != x")
+	}
 
-		x4, y4 := curve.Add(x, y, baseX, baseY)
-		if x4.Cmp(baseX) != 0 || y4.Cmp(baseY) != 0 {
-			t.Errorf("%s: ∞+x != x", test.name)
-		}
+	x4, y4 := curve.Add(x, y, baseX, baseY)
+	if x4.Cmp(baseX) != 0 || y4.Cmp(baseY) != 0 {
+		t.Errorf("∞+x != x")
+	}
+
+	if curve.IsOnCurve(x, y) {
+		t.Errorf("IsOnCurve(∞) == true")
+	}
+}
+
+func TestInfinity(t *testing.T) {
+	tests := []struct {
+		name  string
+		curve Curve
+	}{
+		{"P-224", P224()},
+		{"P-256", P256()},
+		{"P-256/Generic", P256().Params()},
+		{"P-384", P384()},
+		{"P-521", P521()},
+	}
+	if testing.Short() {
+		tests = tests[:1]
+	}
+	for _, test := range tests {
+		curve := test.curve
+		t.Run(test.name, func(t *testing.T) {
+			testInfinity(t, curve)
+		})
 	}
 }
 
@@ -628,3 +650,74 @@ func TestUnmarshalToLargeCoordinates(t *testing.T) {
 		t.Errorf("Unmarshal accepts invalid Y coordinate")
 	}
 }
+
+func TestMarshalCompressed(t *testing.T) {
+	t.Run("P-256/03", func(t *testing.T) {
+		data, _ := hex.DecodeString("031e3987d9f9ea9d7dd7155a56a86b2009e1e0ab332f962d10d8beb6406ab1ad79")
+		x, _ := new(big.Int).SetString("13671033352574878777044637384712060483119675368076128232297328793087057702265", 10)
+		y, _ := new(big.Int).SetString("66200849279091436748794323380043701364391950689352563629885086590854940586447", 10)
+		testMarshalCompressed(t, P256(), x, y, data)
+	})
+	t.Run("P-256/02", func(t *testing.T) {
+		data, _ := hex.DecodeString("021e3987d9f9ea9d7dd7155a56a86b2009e1e0ab332f962d10d8beb6406ab1ad79")
+		x, _ := new(big.Int).SetString("13671033352574878777044637384712060483119675368076128232297328793087057702265", 10)
+		y, _ := new(big.Int).SetString("49591239931264812013903123569363872165694192725937750565648544718012157267504", 10)
+		testMarshalCompressed(t, P256(), x, y, data)
+	})
+
+	t.Run("Invalid", func(t *testing.T) {
+		data, _ := hex.DecodeString("02fd4bf61763b46581fd9174d623516cf3c81edd40e29ffa2777fb6cb0ae3ce535")
+		X, Y := UnmarshalCompressed(P256(), data)
+		if X != nil || Y != nil {
+			t.Error("expected an error for invalid encoding")
+		}
+	})
+
+	if testing.Short() {
+		t.Skip("skipping other curves on short test")
+	}
+
+	t.Run("P-224", func(t *testing.T) {
+		_, x, y, err := GenerateKey(P224(), rand.Reader)
+		if err != nil {
+			t.Fatal(err)
+		}
+		testMarshalCompressed(t, P224(), x, y, nil)
+	})
+	t.Run("P-384", func(t *testing.T) {
+		_, x, y, err := GenerateKey(P384(), rand.Reader)
+		if err != nil {
+			t.Fatal(err)
+		}
+		testMarshalCompressed(t, P384(), x, y, nil)
+	})
+	t.Run("P-521", func(t *testing.T) {
+		_, x, y, err := GenerateKey(P521(), rand.Reader)
+		if err != nil {
+			t.Fatal(err)
+		}
+		testMarshalCompressed(t, P521(), x, y, nil)
+	})
+}
+
+func testMarshalCompressed(t *testing.T, curve Curve, x, y *big.Int, want []byte) {
+	if !curve.IsOnCurve(x, y) {
+		t.Fatal("invalid test point")
+	}
+	got := MarshalCompressed(curve, x, y)
+	if want != nil && !bytes.Equal(got, want) {
+		t.Errorf("got unexpected MarshalCompressed result: got %x, want %x", got, want)
+	}
+
+	X, Y := UnmarshalCompressed(curve, got)
+	if X == nil || Y == nil {
+		t.Fatalf("UnmarshalCompressed failed unexpectedly")
+	}
+
+	if !curve.IsOnCurve(X, Y) {
+		t.Error("UnmarshalCompressed returned a point not on the curve")
+	}
+	if X.Cmp(x) != 0 || Y.Cmp(y) != 0 {
+		t.Errorf("point did not round-trip correctly: got (%v, %v), want (%v, %v)", X, Y, x, y)
+	}
+}