func benchDouble(curve elliptic.Curve, n int) {
	x := curve.Params().Gx
	y := curve.Params().Gy
	for i := 0; i < n; i++ {
		curve.Double(x, y)
	}
}

func benchScalarMult(curve elliptic.Curve, k []byte, n int) {
	x := curve.Params().Gx
	y := curve.Params().Gy
	for i := 0; i < n; i++ {
		curve.ScalarMult(x, y, k)
	}
}

func benchAdd(curve elliptic.Curve, n int) {
	x := curve.Params().Gx
	y := curve.Params().Gy
	for i := 0; i < n; i++ {
		curve.Add(x, y, x, y)
	}
}

// parseECPrivateKey parses an ASN.1 Elliptic Curve Private Key Structure.
// The OID for the named curve may be provided from another source (such as
// the PKCS8 container) - if it is provided then use this instead of the OID
// that may exist in the EC private key structure.
func parseECPrivateKey(namedCurveOID *asn1.ObjectIdentifier, der []byte) (key *ecdsa.PrivateKey, err error) {
	var privKey ecPrivateKey
	if _, err := asn1.Unmarshal(der, &privKey); err != nil {
		return nil, errors.New("x509: failed to parse EC private key: " + err.Error())
	}
	if privKey.Version != ecPrivKeyVersion {
		return nil, fmt.Errorf("x509: unknown EC private key version %d", privKey.Version)
	}

	var curve elliptic.Curve
	if namedCurveOID != nil {
		curve = namedCurveFromOID(*namedCurveOID)
	} else {
		curve = namedCurveFromOID(privKey.NamedCurveOID)
	}
	if curve == nil {
		return nil, errors.New("x509: unknown elliptic curve")
	}

	k := new(big.Int).SetBytes(privKey.PrivateKey)
	if k.Cmp(curve.Params().N) >= 0 {
		return nil, errors.New("x509: invalid elliptic curve private key value")
	}
	priv := new(ecdsa.PrivateKey)
	priv.Curve = curve
	priv.D = k
	priv.X, priv.Y = curve.ScalarBaseMult(privKey.PrivateKey)

	return priv, nil
}

// getSuitableAlgFromCurve inspects the key length in curve, and determines the
// corresponding jwt.Algorithm.
func getSuitableAlgFromCurve(curve elliptic.Curve) (jwt.Algorithm, error) {
	curveBitSize := curve.Params().BitSize

	// compute curve key len
	keyLen := curveBitSize / 8
	if curveBitSize%8 > 0 {
		keyLen++
	}

	// determine alg
	var alg jwt.Algorithm
	switch 2 * keyLen {
	case 64:
		alg = jwt.ES256
	case 96:
		alg = jwt.ES384
	case 132:
		alg = jwt.ES512

	default:
		return jwt.NONE, fmt.Errorf("invalid key length %d", keyLen)
	}

	return alg, nil
}

func UnmarshalBallot(c elliptic.Curve, bytes []byte) (*Ballot, error) {
	if len(bytes) < 4 {
		return nil, errors.New("Not long enough!")
	}
	numballots := int(bytes[0])<<24 + int(bytes[1])<<16 +
		int(bytes[2])<<8 + int(bytes[3])
	ret := new(Ballot)
	ret.boxes = make([]*Checkbox, numballots, numballots)
	bytesize := (c.Params().BitSize + 7) >> 3
	ballotlen := 2 + 8*bytesize
	if len(bytes) != 4+numballots*ballotlen+2*bytesize {
		return nil, errors.New("Wrong length!")
	}
	for i := 0; i < numballots; i++ {
		ret.boxes[i] = UnmarshalCheckbox(c, bytes[i*ballotlen+4:(i+1)*ballotlen+4])
		if ret.boxes[i] == nil {
			return nil, errors.New("Incorrect serialization")
		}
	}
	ret.c = new(big.Int)
	ret.c.SetBytes(bytes[numballots*ballotlen+4 : numballots*ballotlen+
		4+bytesize])
	ret.r = new(big.Int)
	ret.r.SetBytes(bytes[numballots*ballotlen+4+bytesize : numballots*ballotlen+4+2*bytesize])
	return ret, nil
}

func (key rawJSONWebKey) ecPrivateKey() (*ecdsa.PrivateKey, error) {
	var curve elliptic.Curve
	switch key.Crv {
	case "P-256":
		curve = elliptic.P256()
	case "P-384":
		curve = elliptic.P384()
	case "P-521":
		curve = elliptic.P521()
	default:
		return nil, fmt.Errorf("square/go-jose: unsupported elliptic curve '%s'", key.Crv)
	}

	if key.X == nil || key.Y == nil || key.D == nil {
		return nil, fmt.Errorf("square/go-jose: invalid EC private key, missing x/y/d values")
	}

	x := key.X.bigInt()
	y := key.Y.bigInt()

	if !curve.IsOnCurve(x, y) {
		return nil, errors.New("square/go-jose: invalid EC key, X/Y are not on declared curve")
	}

	return &ecdsa.PrivateKey{
		PublicKey: ecdsa.PublicKey{
			Curve: curve,
			X:     x,
			Y:     y,
		},
		D: key.D.bigInt(),
	}, nil
}

func hashG(c elliptic.Curve, m []byte) (hx, hy *big.Int) {
	h := sha256.New()
	h.Write(m)
	d := h.Sum(nil)
	hx, hy = c.ScalarBaseMult(d) // g^H'()
	return
}

// https://tools.ietf.org/html/rfc6979#section-2.3.4
func bits2octets(in []byte, curve elliptic.Curve, rolen int) []byte {
	z1 := hashToInt(in, curve)
	z2 := new(big.Int).Sub(z1, curve.Params().N)
	if z2.Sign() < 0 {
		return int2octets(z1, rolen)
	}
	return int2octets(z2, rolen)
}

// kexECDH performs Elliptic Curve Diffie-Hellman key exchange as
// described in RFC 5656, section 4.
func (c *ClientConn) kexECDH(curve elliptic.Curve, magics *handshakeMagics, hostKeyAlgo string) (*kexResult, error) {
	ephKey, err := ecdsa.GenerateKey(curve, c.config.rand())
	if err != nil {
		return nil, err
	}

	kexInit := kexECDHInitMsg{
		ClientPubKey: elliptic.Marshal(curve, ephKey.PublicKey.X, ephKey.PublicKey.Y),
	}

	serialized := marshal(msgKexECDHInit, kexInit)
	if err := c.writePacket(serialized); err != nil {
		return nil, err
	}

	packet, err := c.readPacket()
	if err != nil {
		return nil, err
	}

	var reply kexECDHReplyMsg
	if err = unmarshal(&reply, packet, msgKexECDHReply); err != nil {
		return nil, err
	}

	x, y := elliptic.Unmarshal(curve, reply.EphemeralPubKey)
	if x == nil {
		return nil, errors.New("ssh: elliptic.Unmarshal failure")
	}
	if !validateECPublicKey(curve, x, y) {
		return nil, errors.New("ssh: ephemeral server key not on curve")
	}

	// generate shared secret
	secret, _ := curve.ScalarMult(x, y, ephKey.D.Bytes())

	hashFunc := ecHash(curve)
	h := hashFunc.New()
	writeString(h, magics.clientVersion)
	writeString(h, magics.serverVersion)
	writeString(h, magics.clientKexInit)
	writeString(h, magics.serverKexInit)
	writeString(h, reply.HostKey)
	writeString(h, kexInit.ClientPubKey)
	writeString(h, reply.EphemeralPubKey)
	K := make([]byte, intLength(secret))
	marshalInt(K, secret)
	h.Write(K)

	return &kexResult{
		H:         h.Sum(nil),
		K:         K,
		HostKey:   reply.HostKey,
		Signature: reply.Signature,
		Hash:      hashFunc,
	}, nil
}

func testKeyGeneration(t *testing.T, c elliptic.Curve, tag string) {
	priv, err := GenerateKey(c, rand.Reader)
	if err != nil {
		t.Errorf("%s: error: %s", tag, err)
		return
	}
	if !c.IsOnCurve(priv.PublicKey.X, priv.PublicKey.Y) {
		t.Errorf("%s: public key invalid: %s", tag, err)
	}
}

// ecHash returns the hash to match the given elliptic curve, see RFC
// 5656, section 6.2.1
func ecHash(curve elliptic.Curve) crypto.Hash {
	bitSize := curve.Params().BitSize
	switch {
	case bitSize <= 256:
		return crypto.SHA256
	case bitSize <= 384:
		return crypto.SHA384
	}
	return crypto.SHA512
}

func MarshalMark(c elliptic.Curve, m *Mark) []byte {
	bytelen := (c.Params().BitSize + 7) >> 3
	pointlen := 1 + 2*bytelen
	outlen := 2 * pointlen
	ret := make([]byte, outlen, outlen)
	abytes := elliptic.Marshal(c, m.ax, m.ay)
	copy(ret, abytes)
	bbytes := elliptic.Marshal(c, m.bx, m.by)
	copy(ret[pointlen:], bbytes)
	return ret
}

func UnmarshalMark(c elliptic.Curve, bytes []byte) *Mark {
	bytelen := (c.Params().BitSize + 7) >> 3
	pointlen := 1 + 2*bytelen
	if len(bytes) != 2*pointlen {
		return nil
	}
	ret := new(Mark)
	ret.ax, ret.ay = elliptic.Unmarshal(c, bytes[:pointlen])
	ret.bx, ret.by = elliptic.Unmarshal(c, bytes[pointlen:2*pointlen])
	return ret
}

// Marshal encodes a ECC Point into it's compressed representation
func Marshal(curve elliptic.Curve, x, y *big.Int) []byte {
	byteLen := (curve.Params().BitSize + 7) >> 3

	ret := make([]byte, 1+byteLen)
	ret[0] = 2 + byte(y.Bit(0))

	xBytes := x.Bytes()
	copy(ret[1+byteLen-len(xBytes):], xBytes)

	return ret
}

// GoodCurve determines if an elliptic curve meets our requirements.
func (policy *KeyPolicy) goodCurve(c elliptic.Curve) (err error) {
	// Simply use a whitelist for now.
	params := c.Params()
	switch {
	case policy.AllowECDSANISTP256 && params == elliptic.P256().Params():
		return nil
	case policy.AllowECDSANISTP384 && params == elliptic.P384().Params():
		return nil
	default:
		return core.MalformedRequestError(fmt.Sprintf("ECDSA curve %v not allowed", params.Name))
	}
}

// Unmarshal converts a point, serialized by Marshal, into an x, y pair.
// It is an error if the point is not on the curve. On error, x = nil.
func Unmarshal(curve elliptic.Curve, data []byte) (x, y *big.Int) {
	byteLen := (curve.Params().BitSize + 7) >> 3
	if len(data) != 1+2*byteLen {
		return
	}
	if data[0] != 4 { // uncompressed form
		return
	}
	x = new(big.Int).SetBytes(data[1 : 1+byteLen])
	y = new(big.Int).SetBytes(data[1+byteLen:])
	return
}

// GenerateKey generates a public and private key pair.
func GenerateKey(c elliptic.Curve, rand io.Reader) (priv *PrivateKey, err error) {
	k, err := randFieldElement(c, rand)
	if err != nil {
		return
	}

	priv = new(PrivateKey)
	priv.PublicKey.Curve = c
	priv.D = k
	priv.PublicKey.X, priv.PublicKey.Y = c.ScalarBaseMult(k.Bytes())
	return
}

// Get size of curve in bytes
func curveSize(crv elliptic.Curve) int {
	bits := crv.Params().BitSize

	div := bits / 8
	mod := bits % 8

	if mod == 0 {
		return div
	}

	return div + 1
}

func parseECCoordinate(cB64Url string, curve elliptic.Curve) (*big.Int, error) {
	curveByteLen := (curve.Params().BitSize + 7) >> 3

	cBytes, err := joseBase64UrlDecode(cB64Url)
	if err != nil {
		return nil, fmt.Errorf("invalid base64 URL encoding: %s", err)
	}
	cByteLength := len(cBytes)
	if cByteLength != curveByteLen {
		return nil, fmt.Errorf("invalid number of octets: got %d, should be %d", cByteLength, curveByteLen)
	}
	return new(big.Int).SetBytes(cBytes), nil
}