// parseECDSA parses an ECDSA key according to RFC 5656, section 3.1.
func parseECDSA(in []byte) (out PublicKey, rest []byte, err error) {
	var identifier []byte
	var ok bool
	if identifier, in, ok = parseString(in); !ok {
		return nil, nil, errShortRead
	}

	key := new(ecdsa.PublicKey)

	switch string(identifier) {
	case "nistp256":
		key.Curve = elliptic.P256()
	case "nistp384":
		key.Curve = elliptic.P384()
	case "nistp521":
		key.Curve = elliptic.P521()
	default:
		return nil, nil, errors.New("ssh: unsupported curve")
	}

	var keyBytes []byte
	if keyBytes, in, ok = parseString(in); !ok {
		return nil, nil, errShortRead
	}

	key.X, key.Y = elliptic.Unmarshal(key.Curve, keyBytes)
	if key.X == nil || key.Y == nil {
		return nil, nil, errors.New("ssh: invalid curve point")
	}
	return (*ecdsaPublicKey)(key), in, nil
}

// parseECDSA parses an ECDSA key according to RFC 5656, section 3.1.
func parseECDSA(in []byte) (out *ecdsa.PublicKey, rest []byte, ok bool) {
	var identifier []byte
	if identifier, in, ok = parseString(in); !ok {
		return
	}

	key := new(ecdsa.PublicKey)

	switch string(identifier) {
	case "nistp256":
		key.Curve = elliptic.P256()
	case "nistp384":
		key.Curve = elliptic.P384()
	case "nistp521":
		key.Curve = elliptic.P521()
	default:
		ok = false
		return
	}

	var keyBytes []byte
	if keyBytes, in, ok = parseString(in); !ok {
		return
	}

	key.X, key.Y = elliptic.Unmarshal(key.Curve, keyBytes)
	if key.X == nil || key.Y == nil {
		ok = false
		return
	}
	return key, in, ok
}

// publicKeyCurve returns the Curve public key from the DNSKEY record.
func (k *RR_DNSKEY) publicKeyCurve() *ecdsa.PublicKey {
	keybuf, err := packBase64([]byte(k.PublicKey))
	if err != nil {
		return nil
	}
	pubkey := new(ecdsa.PublicKey)
	switch k.Algorithm {
	case ECDSAP256SHA256:
		pubkey.Curve = elliptic.P256()
		if len(keybuf) != 64 {
			// wrongly encoded key
			return nil
		}
	case ECDSAP384SHA384:
		pubkey.Curve = elliptic.P384()
		if len(keybuf) != 96 {
			// Wrongly encoded key
			return nil
		}
	}
	pubkey.X = big.NewInt(0)
	pubkey.X.SetBytes(keybuf[:len(keybuf)/2])
	pubkey.Y = big.NewInt(0)
	pubkey.Y.SetBytes(keybuf[len(keybuf)/2:])
	return pubkey
}

// parseECDSA parses an ECDSA key according to RFC 5656, section 3.1.
func parseECDSA(in []byte) (out PublicKey, rest []byte, err error) {
	var w struct {
		Curve    string
		KeyBytes []byte
		Rest     []byte `ssh:"rest"`
	}

	if err := Unmarshal(in, &w); err != nil {
		return nil, nil, err
	}

	key := new(ecdsa.PublicKey)

	switch w.Curve {
	case "nistp256":
		key.Curve = elliptic.P256()
	case "nistp384":
		key.Curve = elliptic.P384()
	case "nistp521":
		key.Curve = elliptic.P521()
	default:
		return nil, nil, errors.New("ssh: unsupported curve")
	}

	key.X, key.Y = elliptic.Unmarshal(key.Curve, w.KeyBytes)
	if key.X == nil || key.Y == nil {
		return nil, nil, errors.New("ssh: invalid curve point")
	}
	return (*ecdsaPublicKey)(key), w.Rest, nil
}

// toECDSA takes the internal ECPublicKey and returns an equivalent
// an ecdsa.PublicKey
func (pk *ECPublicKey) toECDSA() *ecdsa.PublicKey {
	ecdsaPub := new(ecdsa.PublicKey)
	ecdsaPub.Curve = pk.Curve
	ecdsaPub.X = pk.X
	ecdsaPub.Y = pk.Y

	return ecdsaPub
}

func NewEcdsaPublicKey(pk *ecdsa.PublicKey) *EcdsaPublicKey {
	pubkey := &EcdsaPublicKey{
		Curve: jwa.EllipticCurveAlgorithm(pk.Params().Name),
	}
	pubkey.X.SetBytes(pk.X.Bytes())
	pubkey.Y.SetBytes(pk.Y.Bytes())
	return pubkey
}

// NewEcdsaPublicKey creates a new JWK from a EC-DSA public key
func NewEcdsaPublicKey(pk *ecdsa.PublicKey) *EcdsaPublicKey {
	pubkey := &EcdsaPublicKey{
		EssentialHeader: &EssentialHeader{KeyType: jwa.EC},
		Curve:           jwa.EllipticCurveAlgorithm(pk.Params().Name),
	}
	n := pk.Params().BitSize / 8
	pubkey.X.SetBytes(i2osp(pk.X, n))
	pubkey.Y.SetBytes(i2osp(pk.Y, n))
	return pubkey
}

func UnmarshalPublicCertificate(data []byte) PublicCertificate {
	x, y := elliptic.Unmarshal(curve, data)

	cert := new(ecdsa.PublicKey)

	cert.Curve = curve
	cert.X = x
	cert.Y = y

	return cert
}

func (sv *x509ECDSASignatureVerifierImpl) verifyImpl(vk *ecdsa.PublicKey, signature, message []byte) (bool, error) {
	ecdsaSignature := new(ECDSASignature)
	_, err := asn1.Unmarshal(signature, ecdsaSignature)
	if err != nil {
		return false, err
	}

	h, err := computeHash(message, vk.Params().BitSize)
	if err != nil {
		return false, err
	}

	return ecdsa.Verify(vk, h, ecdsaSignature.R, ecdsaSignature.S), nil
}

// Extract the Curve public key from the Key record
func (k *RR_DNSKEY) pubKeyCurve() *ecdsa.PublicKey {
	keybuf, err := packBase64([]byte(k.PublicKey))
	if err != nil {
		return nil
	}
	var c *elliptic.Curve
	switch k.Algorithm {
	case ECDSAP256SHA256:
		c = elliptic.P256()
	case ECDSAP384SHA384:
		c = elliptic.P384()
	}
	x, y := c.Unmarshal(keybuf)
	pubkey := new(ecdsa.PublicKey)
	pubkey.X = x
	pubkey.Y = y
	pubkey.Curve = c
	return pubkey
}

func verify(signerKeyFile, userKeyFile, sigFile string) bool {
	rawSigner, err := ioutil.ReadFile(signerKeyFile)
	if err != nil {
		fmt.Printf("Failed to read signature key: %v\n", err)
		return false
	}
	var signer ecdsa.PublicKey
	signer.X, signer.Y = elliptic.Unmarshal(elliptic.P521(), rawSigner)
	if signer.X == nil {
		fmt.Println("Invalid signature key.")
		return false
	}
	signer.Curve = elliptic.P521()

	rawUser, err := ioutil.ReadFile(userKeyFile)
	if err != nil {
		fmt.Printf("Failed to read user key: %v\n", err)
		return false
	}

	x, _ := elliptic.Unmarshal(elliptic.P521(), rawUser)
	if x == nil {
		fmt.Println("Invalid user key.")
		return false
	}

	rawSig, err := ioutil.ReadFile(sigFile)
	if err != nil {
		fmt.Printf("Failed to load signature: %v\n", err)
		return false
	}

	var sig ECDSASignature
	_, err = asn1.Unmarshal(rawSig, &sig)
	if err != nil {
		fmt.Printf("Failed to parse signature: %v\n", err)
		return false
	}

	h := sha512.Sum384(rawUser)
	return ecdsa.Verify(&signer, h[:], sig.R, sig.S)
}

// marshalPubECDSA serializes an ECDSA public key according to RFC 5656, section 3.1.
func marshalPubECDSA(key *ecdsa.PublicKey) []byte {
	var identifier []byte
	switch key.Params().BitSize {
	case 256:
		identifier = []byte("nistp256")
	case 384:
		identifier = []byte("nistp384")
	case 521:
		identifier = []byte("nistp521")
	default:
		panic("ssh: unsupported ecdsa key size")
	}
	keyBytes := elliptic.Marshal(key.Curve, key.X, key.Y)

	length := stringLength(len(identifier))
	length += stringLength(len(keyBytes))

	ret := make([]byte, length)
	r := marshalString(ret, identifier)
	r = marshalString(r, keyBytes)
	return ret
}

// Multiply a large integer and a point.  The resulting point
// is represented as an ECDSA public key.
func ScalarMult(k *big.Int, B *ecdsa.PublicKey) *ecdsa.PublicKey {
	key := new(ecdsa.PublicKey)
	key.Curve = Secp256k1()
	key.X, key.Y = Secp256k1().ScalarMult(B.X, B.Y, k.Bytes())
	return key
}

// GoodKeyECDSA determines if an ECDSA pubkey meets our requirements
func (policy *KeyPolicy) goodKeyECDSA(key ecdsa.PublicKey) (err error) {
	// Check the curve.
	//
	// The validity of the curve is an assumption for all following tests.
	err = policy.goodCurve(key.Curve)
	if err != nil {
		return err
	}

	// Key validation routine adapted from NIST SP800-56A § 5.6.2.3.2.
	// <http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar2.pdf>
	//
	// Assuming a prime field since a) we are only allowing such curves and b)
	// crypto/elliptic only supports prime curves. Where this assumption
	// simplifies the code below, it is explicitly stated and explained. If ever
	// adapting this code to support non-prime curves, refer to NIST SP800-56A §
	// 5.6.2.3.2 and adapt this code appropriately.
	params := key.Params()

	// SP800-56A § 5.6.2.3.2 Step 1.
	// Partial check of the public key for an invalid range in the EC group:
	// Verify that key is not the point at infinity O.
	// This code assumes that the point at infinity is (0,0), which is the
	// case for all supported curves.
	if isPointAtInfinityNISTP(key.X, key.Y) {
		return core.MalformedRequestError("Key x, y must not be the point at infinity")
	}

	// SP800-56A § 5.6.2.3.2 Step 2.
	//   "Verify that x_Q and y_Q are integers in the interval [0,p-1] in the
	//    case that q is an odd prime p, or that x_Q and y_Q are bit strings
	//    of length m bits in the case that q = 2**m."
	//
	// Prove prime field: ASSUMED.
	// Prove q != 2: ASSUMED. (Curve parameter. No supported curve has q == 2.)
	// Prime field && q != 2  => q is an odd prime p
	// Therefore "verify that x, y are in [0, p-1]" satisfies step 2.
	//
	// Therefore verify that both x and y of the public key point have the unique
	// correct representation of an element in the underlying field by verifying
	// that x and y are integers in [0, p-1].
	if key.X.Sign() < 0 || key.Y.Sign() < 0 {
		return core.MalformedRequestError("Key x, y must not be negative")
	}

	if key.X.Cmp(params.P) >= 0 || key.Y.Cmp(params.P) >= 0 {
		return core.MalformedRequestError("Key x, y must not exceed P-1")
	}

	// SP800-56A § 5.6.2.3.2 Step 3.
	//   "If q is an odd prime p, verify that (y_Q)**2 === (x_Q)***3 + a*x_Q + b (mod p).
	//    If q = 2**m, verify that (y_Q)**2 + (x_Q)*(y_Q) == (x_Q)**3 + a*(x_Q)*2 + b in
	//    the finite field of size 2**m.
	//    (Ensures that the public key is on the correct elliptic curve.)"
	//
	// q is an odd prime p: proven/assumed above.
	// a = -3 for all supported curves.
	//
	// Therefore step 3 is satisfied simply by showing that
	//   y**2 === x**3 - 3*x + B (mod P).
	//
	// This proves that the public key is on the correct elliptic curve.
	// But in practice, this test is provided by crypto/elliptic, so use that.
	if !key.Curve.IsOnCurve(key.X, key.Y) {
		return core.MalformedRequestError("Key point is not on the curve")
	}

	// SP800-56A § 5.6.2.3.2 Step 4.
	//   "Verify that n*Q == O.
	//    (Ensures that the public key has the correct order. Along with check 1,
	//     ensures that the public key is in the correct range in the correct EC
	//     subgroup, that is, it is in the correct EC subgroup and is not the
	//     identity element.)"
	//
	// Ensure that public key has the correct order:
	// verify that n*Q = O.
	//
	// n*Q = O iff n*Q is the point at infinity (see step 1).
	ox, oy := key.Curve.ScalarMult(key.X, key.Y, params.N.Bytes())
	if !isPointAtInfinityNISTP(ox, oy) {
		return core.MalformedRequestError("Public key does not have correct order")
	}

	// End of SP800-56A § 5.6.2.3.2 Public Key Validation Routine.
	// Key is valid.
	return nil
}

// Adds two points to create a third.  Points are represented as
// ECDSA public keys.
func Add(a, b *ecdsa.PublicKey) *ecdsa.PublicKey {
	key := new(ecdsa.PublicKey)
	key.Curve = Secp256k1()
	key.X, key.Y = Secp256k1().Add(a.X, a.Y, b.X, b.Y)
	return key
}

// ParsePubKey parses a public key for a koblitz curve from a bytestring into a
// ecdsa.Publickey, verifying that it is valid. It supports compressed,
// uncompressed and hybrid signature formats.
func ParsePubKey(pubKeyStr []byte, curve *KoblitzCurve) (key *ecdsa.PublicKey, err error) {
	pubkey := ecdsa.PublicKey{}
	pubkey.Curve = curve

	format := pubKeyStr[0]
	ybit := (format & 0x1) == 0x1
	format &= ^byte(0x1)

	switch len(pubKeyStr) {
	case 65: // normal public key
		if format != pubkeyUncompressed && format != pubkeyHybrid {
			return nil, fmt.Errorf("invalid magic in pubkey str: "+
				"%d", pubKeyStr[0])
		}

		pubkey.X = new(big.Int).SetBytes(pubKeyStr[1:33])
		pubkey.Y = new(big.Int).SetBytes(pubKeyStr[33:])
		// hybrid keys have extra information, make use of it.
		if format == pubkeyHybrid && ybit != isOdd(pubkey.Y) {
			return nil, fmt.Errorf("ybit doesn't match oddness")
		}
	case 33: // compressed public key
		// format is 0x2 | solution, <X coordinate>
		// solution determines which solution of the curve we use.
		/// y^2 = x^3 + Curve.B
		if format != pubkeyCompressed {
			return nil, fmt.Errorf("invalid magic in compressed "+
				"pubkey string: %d", pubKeyStr[0])
		}
		pubkey.X = new(big.Int).SetBytes(pubKeyStr[1:33])
		// Y = +-sqrt(x^3 + B)
		x3 := new(big.Int).Mul(pubkey.X, pubkey.X)
		x3.Mul(x3, pubkey.X)
		x3.Add(x3, pubkey.Curve.Params().B)

		// now calculate sqrt mod p of x2 + B
		// This code used to do a full sqrt based on tonelli/shanks,
		// but this was replaced by the algorithms referenced in
		// https://bitcointalk.org/index.php?topic=162805.msg1712294#msg1712294
		y := new(big.Int).Exp(x3, curve.QPlus1Div4(), pubkey.Curve.Params().P)

		if ybit != isOdd(y) {
			y.Sub(pubkey.Curve.Params().P, y)
		}
		if ybit != isOdd(y) {
			return nil, fmt.Errorf("ybit doesn't match oddness")
		}

		pubkey.Y = y
	default: // wrong!
		return nil, fmt.Errorf("invalid pub key length %d",
			len(pubKeyStr))
	}

	if pubkey.X.Cmp(pubkey.Curve.Params().P) >= 0 {
		return nil, fmt.Errorf("pubkey X parameter is >= to P")
	}
	if pubkey.Y.Cmp(pubkey.Curve.Params().P) >= 0 {
		return nil, fmt.Errorf("pubkey Y parameter is >= to P")
	}
	if !pubkey.Curve.IsOnCurve(pubkey.X, pubkey.Y) {
		return nil, fmt.Errorf("pubkey isn't on secp265k1 curve")
	}
	return &pubkey, nil
}

// Multiplies the base G by a large integer.  The resulting
// point is represented as an ECDSA public key since that's
// typically how they're used.
func ScalarBaseMult(k *big.Int) *ecdsa.PublicKey {
	key := new(ecdsa.PublicKey)
	key.Curve = Secp256k1()
	key.X, key.Y = Secp256k1().ScalarBaseMult(k.Bytes())
	return key
}