func ecdsaSign(privKey data.PrivateKey, hashed []byte) ([]byte, error) {
	if _, ok := privKey.(*data.ECDSAPrivateKey); !ok {
		return nil, fmt.Errorf("private key type not supported: %s", privKey.Algorithm())
	}

	// Create an ecdsa.PrivateKey out of the private key bytes
	ecdsaPrivKey, err := x509.ParseECPrivateKey(privKey.Private())
	if err != nil {
		return nil, err
	}

	// Use the ECDSA key to sign the data
	r, s, err := ecdsa.Sign(rand.Reader, ecdsaPrivKey, hashed[:])
	if err != nil {
		return nil, err
	}

	rBytes, sBytes := r.Bytes(), s.Bytes()
	octetLength := (ecdsaPrivKey.Params().BitSize + 7) >> 3

	// MUST include leading zeros in the output
	rBuf := make([]byte, octetLength-len(rBytes), octetLength)
	sBuf := make([]byte, octetLength-len(sBytes), octetLength)

	rBuf = append(rBuf, rBytes...)
	sBuf = append(sBuf, sBytes...)

	return append(rBuf, sBuf...), nil
}

// EncryptPrivateKey returns an encrypted PEM key given a Privatekey
// and a passphrase
func EncryptPrivateKey(key data.PrivateKey, role, passphrase string) ([]byte, error) {
	bt, err := blockType(key)
	if err != nil {
		return nil, err
	}

	password := []byte(passphrase)
	cipherType := x509.PEMCipherAES256

	encryptedPEMBlock, err := x509.EncryptPEMBlock(rand.Reader,
		bt,
		key.Private(),
		password,
		cipherType)
	if err != nil {
		return nil, err
	}

	if encryptedPEMBlock.Headers == nil {
		return nil, fmt.Errorf("unable to encrypt key - invalid PEM file produced")
	}
	encryptedPEMBlock.Headers["role"] = role

	return pem.EncodeToMemory(encryptedPEMBlock), nil
}

// GenRootKey generates a new root key
func (km *KeyStoreManager) GenRootKey(algorithm string) (string, error) {
	var err error
	var privKey data.PrivateKey

	// We don't want external API callers to rely on internal TUF data types, so
	// the API here should continue to receive a string algorithm, and ensure
	// that it is downcased
	switch strings.ToLower(algorithm) {
	case data.RSAKey:
		privKey, err = trustmanager.GenerateRSAKey(rand.Reader, rsaRootKeySize)
	case data.ECDSAKey:
		privKey, err = trustmanager.GenerateECDSAKey(rand.Reader)
	default:
		return "", fmt.Errorf("only RSA or ECDSA keys are currently supported. Found: %s", algorithm)

	}
	if err != nil {
		return "", fmt.Errorf("failed to generate private key: %v", err)
	}

	// Changing the root
	km.KeyStore.AddKey(privKey.ID(), "root", privKey)

	return privKey.ID(), nil
}

// AddGetKeyCryptoServiceInterfaceBehaviorTests tests expected behavior for
// adding keys in a signed.CryptoService and other read operations on the
// crypto service after keys are present
// 1.  Adding a key succeeds
// 2.  Getting the key should return the same key, without error
// 3.  Removing the key succeeds
func AddGetKeyCryptoServiceInterfaceBehaviorTests(t *testing.T, cs signed.CryptoService, algo string) {
	expectedRolesToKeys := make(map[string]string)
	for i := 0; i < 2; i++ {
		var (
			addedPrivKey data.PrivateKey
			err          error
		)
		role := data.BaseRoles[i+1]
		switch algo {
		case data.RSAKey:
			addedPrivKey, err = trustmanager.GenerateRSAKey(rand.Reader, 2048)
		case data.ECDSAKey:
			addedPrivKey, err = trustmanager.GenerateECDSAKey(rand.Reader)
		case data.ED25519Key:
			addedPrivKey, err = trustmanager.GenerateED25519Key(rand.Reader)
		default:
			require.FailNow(t, "invalid algorithm %s", algo)
		}
		require.NoError(t, err)
		require.NotNil(t, addedPrivKey)
		require.NoError(t, cs.AddKey(role, "docker.io/notary", addedPrivKey))
		expectedRolesToKeys[role] = addedPrivKey.ID()
	}

	testGetKey(t, cs, expectedRolesToKeys, algo, true)
}

// GenerateCertificate generates an X509 Certificate from a template, given a GUN
func GenerateCertificate(rootKey data.PrivateKey, gun string) (*x509.Certificate, error) {

	switch rootKey.(type) {
	case *data.RSAPrivateKey, *data.ECDSAPrivateKey:
		// go doesn't fall through
	default:
		return nil, fmt.Errorf("only bare RSA or ECDSA keys (not x509 variants) are currently supported. Found: %s", rootKey.Algorithm())
	}

	template, err := trustmanager.NewCertificate(gun)
	if err != nil {
		return nil, fmt.Errorf("failed to create the certificate template for: %s (%v)", gun, err)
	}

	derBytes, err := x509.CreateCertificate(rand.Reader, template, template, rootKey.CryptoSigner().Public(), rootKey.CryptoSigner())
	if err != nil {
		return nil, fmt.Errorf("failed to create the certificate for: %s (%v)", gun, err)
	}

	// Encode the new certificate into PEM
	cert, err := x509.ParseCertificate(derBytes)
	if err != nil {
		return nil, fmt.Errorf("failed to parse the certificate for key: %s (%v)", gun, err)
	}

	return cert, nil
}

// KeyToPEM returns a PEM encoded key from a Private Key
func KeyToPEM(privKey data.PrivateKey) ([]byte, error) {
	bt, err := blockType(privKey)
	if err != nil {
		return nil, err
	}

	return pem.EncodeToMemory(&pem.Block{Type: bt, Bytes: privKey.Private()}), nil
}

// GenerateCertificate generates an X509 Certificate from a template, given a GUN and validity interval
func GenerateCertificate(rootKey data.PrivateKey, gun string, startTime, endTime time.Time) (*x509.Certificate, error) {
	signer := rootKey.CryptoSigner()
	if signer == nil {
		return nil, fmt.Errorf("key type not supported for Certificate generation: %s\n", rootKey.Algorithm())
	}

	return generateCertificate(signer, gun, startTime, endTime)
}

func blockType(k data.PrivateKey) (string, error) {
	switch k.Algorithm() {
	case data.RSAKey, data.RSAx509Key:
		return "RSA PRIVATE KEY", nil
	case data.ECDSAKey, data.ECDSAx509Key:
		return "EC PRIVATE KEY", nil
	case data.ED25519Key:
		return "ED25519 PRIVATE KEY", nil
	default:
		return "", fmt.Errorf("algorithm %s not supported", k.Algorithm())
	}
}

// AddKey stores the contents of a PEM-encoded private key as a PEM block
func (s *KeyMemoryStore) AddKey(keyInfo KeyInfo, privKey data.PrivateKey) error {
	s.Lock()
	defer s.Unlock()
	if keyInfo.Role == data.CanonicalRootRole || data.IsDelegation(keyInfo.Role) || !data.ValidRole(keyInfo.Role) {
		keyInfo.Gun = ""
	}
	err := addKey(s, s.PassRetriever, s.cachedKeys, filepath.Join(keyInfo.Gun, privKey.ID()), keyInfo.Role, privKey)
	if err != nil {
		return err
	}
	s.keyInfoMap[privKey.ID()] = keyInfo
	return nil
}

// AddKey puts a key inside the Yubikey, as well as writing it to the backup store
func (s *YubiStore) AddKey(keyInfo trustmanager.KeyInfo, privKey data.PrivateKey) error {
	added, err := s.addKey(privKey.ID(), keyInfo.Role, privKey)
	if err != nil {
		return err
	}
	if added && s.backupStore != nil {
		err = s.backupStore.AddKey(keyInfo, privKey)
		if err != nil {
			defer s.RemoveKey(privKey.ID())
			return ErrBackupFailed{err: err.Error()}
		}
	}
	return nil
}

// AddKey puts a key inside the Yubikey, as well as writing it to the backup store
func (s *YubiKeyStore) AddKey(keyID, role string, privKey data.PrivateKey) error {
	added, err := s.addKey(keyID, role, privKey)
	if err != nil {
		return err
	}
	if added {
		err = s.backupStore.AddKey(privKey.ID(), role, privKey)
		if err != nil {
			defer s.RemoveKey(keyID)
			return ErrBackupFailed{err: err.Error()}
		}
	}
	return nil
}

// AddKey stores the contents of a private key. Both role and gun are ignored,
// we always use Key IDs as name, and don't support aliases
func (s *cachedKeyService) AddKey(role, gun string, privKey data.PrivateKey) error {
	if err := s.CryptoService.AddKey(role, gun, privKey); err != nil {
		return err
	}

	// Add the private key to our cache
	s.lock.Lock()
	defer s.lock.Unlock()
	s.cachedKeys[privKey.ID()] = &cachedKey{
		role: role,
		key:  privKey,
	}

	return nil
}

// KeyToPEM returns a PEM encoded key from a Private Key
func KeyToPEM(privKey data.PrivateKey, role string) ([]byte, error) {
	bt, err := blockType(privKey)
	if err != nil {
		return nil, err
	}

	block := &pem.Block{
		Type: bt,
		Headers: map[string]string{
			"role": role,
		},
		Bytes: privKey.Private(),
	}

	return pem.EncodeToMemory(block), nil
}

func rsaPSSSign(privKey data.PrivateKey, hash crypto.Hash, hashed []byte) ([]byte, error) {
	if privKey, ok := privKey.(*data.RSAPrivateKey); !ok {
		return nil, fmt.Errorf("private key type not supported: %s", privKey.Algorithm())
	}

	// Create an rsa.PrivateKey out of the private key bytes
	rsaPrivKey, err := x509.ParsePKCS1PrivateKey(privKey.Private())
	if err != nil {
		return nil, err
	}

	// Use the RSA key to RSASSA-PSS sign the data
	sig, err := rsa.SignPSS(rand.Reader, rsaPrivKey, hash, hashed[:], &rsa.PSSOptions{SaltLength: rsa.PSSSaltLengthEqualsHash})
	if err != nil {
		return nil, err
	}

	return sig, nil
}

// Only add if we haven't seen the key already.  Return whether the key was
// added.
func (s *YubiKeyStore) addKey(keyID, role string, privKey data.PrivateKey) (
	bool, error) {

	// We only allow adding root keys for now
	if role != data.CanonicalRootRole {
		return false, fmt.Errorf(
			"yubikey only supports storing root keys, got %s for key: %s", role, keyID)
	}

	ctx, session, err := SetupHSMEnv(pkcs11Lib, s.libLoader)
	if err != nil {
		logrus.Debugf("Failed to initialize PKCS11 environment: %s", err.Error())
		return false, err
	}
	defer cleanup(ctx, session)

	if k, ok := s.keys[keyID]; ok {
		if k.role == role {
			// already have the key and it's associated with the correct role
			return false, nil
		}
	}

	slot, err := getNextEmptySlot(ctx, session)
	if err != nil {
		logrus.Debugf("Failed to get an empty yubikey slot: %s", err.Error())
		return false, err
	}
	logrus.Debugf("Attempting to store key using yubikey slot %v", slot)

	err = addECDSAKey(
		ctx, session, privKey, slot, s.passRetriever, role)
	if err == nil {
		s.keys[privKey.ID()] = yubiSlot{
			role:   role,
			slotID: slot,
		}
		return true, nil
	}
	logrus.Debugf("Failed to add key to yubikey: %v", err)

	return false, err
}

func rsaPKCS1v15Sign(privKey data.PrivateKey, hash crypto.Hash, hashed []byte) ([]byte, error) {
	if privKey, ok := privKey.(*data.RSAPrivateKey); !ok {
		return nil, fmt.Errorf("private key type not supported: %s", privKey.Algorithm())
	}

	// Create an rsa.PrivateKey out of the private key bytes
	rsaPrivKey, err := x509.ParsePKCS1PrivateKey(privKey.Private())
	if err != nil {
		return nil, err
	}

	// Use the RSA key to RSAPKCS1v15 sign the data
	sig, err := rsa.SignPKCS1v15(rand.Reader, rsaPrivKey, hash, hashed[:])
	if err != nil {
		return nil, err
	}

	return sig, nil
}

// EncryptPrivateKey returns an encrypted PEM key given a Privatekey
// and a passphrase
func EncryptPrivateKey(key data.PrivateKey, passphrase string) ([]byte, error) {
	bt, err := blockType(key)
	if err != nil {
		return nil, err
	}

	password := []byte(passphrase)
	cipherType := x509.PEMCipherAES256

	encryptedPEMBlock, err := x509.EncryptPEMBlock(rand.Reader,
		bt,
		key.Private(),
		password,
		cipherType)
	if err != nil {
		return nil, err
	}

	return pem.EncodeToMemory(encryptedPEMBlock), nil
}

// AddKey adds a private key to a specified role.
// The GUN is inferred from the cryptoservice itself for non-root roles
func (cs *CryptoService) AddKey(role, gun string, key data.PrivateKey) (err error) {
	// First check if this key already exists in any of our keystores
	for _, ks := range cs.keyStores {
		if keyInfo, err := ks.GetKeyInfo(key.ID()); err == nil {
			if keyInfo.Role != role {
				return fmt.Errorf("key with same ID already exists for role: %s", keyInfo.Role)
			}
			logrus.Debugf("key with same ID %s and role %s already exists", key.ID(), keyInfo.Role)
			return nil
		}
	}
	// If the key didn't exist in any of our keystores, add and return on the first successful keystore
	for _, ks := range cs.keyStores {
		// Try to add to this keystore, return if successful
		if err = ks.AddKey(trustmanager.KeyInfo{Role: role, Gun: gun}, key); err == nil {
			return nil
		}
	}
	return // returns whatever the final values were
}

// AddKey stores the contents of a PEM-encoded private key as a PEM block
func (s *GenericKeyStore) AddKey(keyInfo KeyInfo, privKey data.PrivateKey) error {
	var (
		chosenPassphrase string
		giveup           bool
		err              error
		pemPrivKey       []byte
	)
	s.Lock()
	defer s.Unlock()
	if keyInfo.Role == data.CanonicalRootRole || data.IsDelegation(keyInfo.Role) || !data.ValidRole(keyInfo.Role) {
		keyInfo.Gun = ""
	}
	keyID := privKey.ID()
	for attempts := 0; ; attempts++ {
		chosenPassphrase, giveup, err = s.PassRetriever(keyID, keyInfo.Role, true, attempts)
		if err == nil {
			break
		}
		if giveup || attempts > 10 {
			return ErrAttemptsExceeded{}
		}
	}

	if chosenPassphrase != "" {
		pemPrivKey, err = utils.EncryptPrivateKey(privKey, keyInfo.Role, keyInfo.Gun, chosenPassphrase)
	} else {
		pemPrivKey, err = utils.KeyToPEM(privKey, keyInfo.Role, keyInfo.Gun)
	}

	if err != nil {
		return err
	}

	s.cachedKeys[keyID] = &cachedKey{alias: keyInfo.Role, key: privKey}
	err = s.store.Set(keyID, pemPrivKey)
	if err != nil {
		return err
	}
	s.keyInfoMap[privKey.ID()] = keyInfo
	return nil
}

// KeyToPEM returns a PEM encoded key from a Private Key
func KeyToPEM(privKey data.PrivateKey, role, gun string) ([]byte, error) {
	bt, err := blockType(privKey)
	if err != nil {
		return nil, err
	}

	headers := map[string]string{}
	if role != "" {
		headers["role"] = role
	}
	if gun != "" {
		headers["gun"] = gun
	}

	block := &pem.Block{
		Type:    bt,
		Headers: headers,
		Bytes:   privKey.Private(),
	}

	return pem.EncodeToMemory(block), nil
}