Adding upstream version 0.6.1.upstream/0.6.1upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

18 files changed, 2071 insertions, 0 deletions

diff --git a/pkg/deprecated/deprecated_repo_test.go b/pkg/deprecated/deprecated_repo_test.go
new file mode 100644
index 0000000..e65cb9e
--- /dev/null
+++ b/pkg/deprecated/deprecated_repo_test.go
@@ -0,0 +1,107 @@
+package deprecated
+
+import (
+	"crypto"
+	"crypto/elliptic"
+	"crypto/rand"
+	"crypto/sha256"
+	"encoding/json"
+	"testing"
+
+	"github.com/secure-systems-lab/go-securesystemslib/cjson"
+	repo "github.com/theupdateframework/go-tuf"
+	"github.com/theupdateframework/go-tuf/data"
+	_ "github.com/theupdateframework/go-tuf/pkg/deprecated/set_ecdsa"
+	"github.com/theupdateframework/go-tuf/pkg/keys"
+	. "gopkg.in/check.v1"
+)
+
+func Test(t *testing.T) { TestingT(t) }
+
+type RepoSuite struct{}
+
+var _ = Suite(&RepoSuite{})
+
+func genKey(c *C, r *repo.Repo, role string) []string {
+	keyids, err := r.GenKey(role)
+	c.Assert(err, IsNil)
+	c.Assert(len(keyids) > 0, Equals, true)
+	return keyids
+}
+
+// Deprecated ecdsa key support: Support verification against roots that were
+// signed with hex-encoded ecdsa keys.
+func (rs *RepoSuite) TestDeprecatedHexEncodedKeysSucceed(c *C) {
+	type deprecatedP256Verifier struct {
+		PublicKey data.HexBytes `json:"public"`
+	}
+	files := map[string][]byte{"foo.txt": []byte("foo")}
+	local := repo.MemoryStore(make(map[string]json.RawMessage), files)
+	r, err := repo.NewRepo(local)
+	c.Assert(err, IsNil)
+
+	r.Init(false)
+
+	// Add a root key with hex-encoded ecdsa format - compliant "ecdsa"
+	signer, err := keys.GenerateEcdsaKey()
+	c.Assert(err, IsNil)
+	pub := signer.PublicKey
+	keyValBytes, err := json.Marshal(&deprecatedP256Verifier{PublicKey: elliptic.Marshal(pub.Curve, pub.X, pub.Y)})
+	c.Assert(err, IsNil)
+	publicData := &data.PublicKey{
+		Type:       data.KeyTypeECDSA_SHA2_P256,
+		Scheme:     data.KeySchemeECDSA_SHA2_P256,
+		Algorithms: data.HashAlgorithms,
+		Value:      keyValBytes,
+	}
+	err = r.AddVerificationKey("root", publicData)
+	c.Assert(err, IsNil)
+
+	// Add a root key with hex-encoded ecdsa format - deprecated "ecdsa-sha2-nistp256"
+	signerDeprecated, err := keys.GenerateEcdsaKey()
+	c.Assert(err, IsNil)
+	pubDeprecated := signerDeprecated.PublicKey
+	keyValBytesDeprecated, err := json.Marshal(&deprecatedP256Verifier{PublicKey: elliptic.Marshal(pubDeprecated.Curve, pubDeprecated.X, pubDeprecated.Y)})
+	c.Assert(err, IsNil)
+	publicDataDeprecated := &data.PublicKey{
+		Type:       data.KeyTypeECDSA_SHA2_P256_OLD_FMT,
+		Scheme:     data.KeySchemeECDSA_SHA2_P256,
+		Algorithms: data.HashAlgorithms,
+		Value:      keyValBytesDeprecated,
+	}
+	err = r.AddVerificationKey("root", publicDataDeprecated)
+	c.Assert(err, IsNil)
+
+	// Add other keys as normal
+	genKey(c, r, "targets")
+	genKey(c, r, "snapshot")
+	genKey(c, r, "timestamp")
+	c.Assert(r.AddTarget("foo.txt", nil), IsNil)
+
+	// Sign the root role manually
+	rootMeta, err := r.SignedMeta("root.json")
+	c.Assert(err, IsNil)
+	rootCanonical, err := cjson.EncodeCanonical(rootMeta.Signed)
+	c.Assert(err, IsNil)
+	hash := sha256.Sum256(rootCanonical)
+	rootSig, err := signer.PrivateKey.Sign(rand.Reader, hash[:], crypto.SHA256)
+	c.Assert(err, IsNil)
+	for _, id := range publicData.IDs() {
+		c.Assert(r.AddOrUpdateSignature("root.json", data.Signature{
+			KeyID:     id,
+			Signature: rootSig}), IsNil)
+	}
+
+	rootSigDeprecated, err := signerDeprecated.PrivateKey.Sign(rand.Reader, hash[:], crypto.SHA256)
+	c.Assert(err, IsNil)
+	for _, id := range publicDataDeprecated.IDs() {
+		c.Assert(r.AddOrUpdateSignature("root.json", data.Signature{
+			KeyID:     id,
+			Signature: rootSigDeprecated}), IsNil)
+	}
+
+	// Committing should succeed because the deprecated key pkg is added.
+	c.Assert(r.Snapshot(), IsNil)
+	c.Assert(r.Timestamp(), IsNil)
+	c.Assert(r.Commit(), IsNil)
+}
diff --git a/pkg/deprecated/set_ecdsa/set_ecdsa.go b/pkg/deprecated/set_ecdsa/set_ecdsa.go
new file mode 100644
index 0000000..13967e2
--- /dev/null
+++ b/pkg/deprecated/set_ecdsa/set_ecdsa.go
@@ -0,0 +1,26 @@
+package set_ecdsa
+
+import (
+	"errors"
+
+	"github.com/theupdateframework/go-tuf/data"
+	"github.com/theupdateframework/go-tuf/pkg/keys"
+)
+
+/*
+	Importing this package will allow support for both hex-encoded ECDSA
+	verifiers and PEM-encoded ECDSA verifiers.
+	Note that this package imports "github.com/theupdateframework/go-tuf/pkg/keys"
+	and overrides the ECDSA verifier loaded at init time in that package.
+*/
+
+func init() {
+	_, ok := keys.VerifierMap.Load(data.KeyTypeECDSA_SHA2_P256)
+	if !ok {
+		panic(errors.New("expected to override previously loaded PEM-only ECDSA verifier"))
+	}
+	// store a mapping for both data.KeyTypeECDSA_SHA2_P256_OLD_FMT and data.KeyTypeECDSA_SHA2_P256
+	// in case a client is verifying using both the old non-compliant format and a newly generated root
+	keys.VerifierMap.Store(data.KeyTypeECDSA_SHA2_P256, keys.NewDeprecatedEcdsaVerifier)         // compliant format
+	keys.VerifierMap.Store(data.KeyTypeECDSA_SHA2_P256_OLD_FMT, keys.NewDeprecatedEcdsaVerifier) // deprecated format
+}
diff --git a/pkg/keys/deprecated_ecdsa.go b/pkg/keys/deprecated_ecdsa.go
new file mode 100644
index 0000000..6d48c9d
--- /dev/null
+++ b/pkg/keys/deprecated_ecdsa.go
@@ -0,0 +1,101 @@
+package keys
+
+import (
+	"bytes"
+	"crypto/ecdsa"
+	"crypto/elliptic"
+	"crypto/sha256"
+	"encoding/json"
+	"errors"
+	"fmt"
+	"io"
+
+	"github.com/theupdateframework/go-tuf/data"
+)
+
+func NewDeprecatedEcdsaVerifier() Verifier {
+	return &ecdsaVerifierWithDeprecatedSupport{}
+}
+
+type ecdsaVerifierWithDeprecatedSupport struct {
+	key *data.PublicKey
+	// This will switch based on whether this is a PEM-encoded key
+	// or a deprecated hex-encoded key.
+	Verifier
+}
+
+func (p *ecdsaVerifierWithDeprecatedSupport) UnmarshalPublicKey(key *data.PublicKey) error {
+	p.key = key
+	pemVerifier := &EcdsaVerifier{}
+	if err := pemVerifier.UnmarshalPublicKey(key); err != nil {
+		// Try the deprecated hex-encoded verifier
+		hexVerifier := &deprecatedP256Verifier{}
+		if err := hexVerifier.UnmarshalPublicKey(key); err != nil {
+			return err
+		}
+		p.Verifier = hexVerifier
+		return nil
+	}
+	p.Verifier = pemVerifier
+	return nil
+}
+
+/*
+   Deprecated ecdsaVerifier that used hex-encoded public keys.
+   This MAY be used to verify existing metadata that used this
+   old format. This will be deprecated soon, ensure that repositories
+   are re-signed and clients receieve a fully compliant root.
+*/
+
+type deprecatedP256Verifier struct {
+	PublicKey data.HexBytes `json:"public"`
+	key       *data.PublicKey
+}
+
+func (p *deprecatedP256Verifier) Public() string {
+	return p.PublicKey.String()
+}
+
+func (p *deprecatedP256Verifier) Verify(msg, sigBytes []byte) error {
+	x, y := elliptic.Unmarshal(elliptic.P256(), p.PublicKey)
+	k := &ecdsa.PublicKey{
+		Curve: elliptic.P256(),
+		X:     x,
+		Y:     y,
+	}
+
+	hash := sha256.Sum256(msg)
+
+	if !ecdsa.VerifyASN1(k, hash[:], sigBytes) {
+		return errors.New("tuf: deprecated ecdsa signature verification failed")
+	}
+	return nil
+}
+
+func (p *deprecatedP256Verifier) MarshalPublicKey() *data.PublicKey {
+	return p.key
+}
+
+func (p *deprecatedP256Verifier) UnmarshalPublicKey(key *data.PublicKey) error {
+	// Prepare decoder limited to 512Kb
+	dec := json.NewDecoder(io.LimitReader(bytes.NewReader(key.Value), MaxJSONKeySize))
+
+	// Unmarshal key value
+	if err := dec.Decode(p); err != nil {
+		if errors.Is(err, io.EOF) || errors.Is(err, io.ErrUnexpectedEOF) {
+			return fmt.Errorf("tuf: the public key is truncated or too large: %w", err)
+		}
+		return err
+	}
+
+	curve := elliptic.P256()
+
+	// Parse as uncompressed marshalled point.
+	x, _ := elliptic.Unmarshal(curve, p.PublicKey)
+	if x == nil {
+		return errors.New("tuf: invalid ecdsa public key point")
+	}
+
+	p.key = key
+	return nil
+}
diff --git a/pkg/keys/deprecated_ecdsa_test.go b/pkg/keys/deprecated_ecdsa_test.go
new file mode 100644
index 0000000..ddfaa84
--- /dev/null
+++ b/pkg/keys/deprecated_ecdsa_test.go
@@ -0,0 +1,129 @@
+package keys
+
+import (
+	"crypto"
+	"crypto/ecdsa"
+	"crypto/elliptic"
+	"crypto/rand"
+	"crypto/sha256"
+	"encoding/json"
+	"errors"
+
+	"github.com/theupdateframework/go-tuf/data"
+	. "gopkg.in/check.v1"
+)
+
+type DeprecatedECDSASuite struct{}
+
+var _ = Suite(DeprecatedECDSASuite{})
+
+type deprecatedEcdsaSigner struct {
+	*ecdsa.PrivateKey
+}
+
+type deprecatedEcdsaPublic struct {
+	PublicKey data.HexBytes `json:"public"`
+}
+
+func (s deprecatedEcdsaSigner) PublicData() *data.PublicKey {
+	pub := s.Public().(*ecdsa.PublicKey)
+	keyValBytes, _ := json.Marshal(deprecatedEcdsaPublic{
+		PublicKey: elliptic.Marshal(pub.Curve, pub.X, pub.Y)})
+	return &data.PublicKey{
+		Type:       data.KeyTypeECDSA_SHA2_P256,
+		Scheme:     data.KeySchemeECDSA_SHA2_P256,
+		Algorithms: data.HashAlgorithms,
+		Value:      keyValBytes,
+	}
+}
+
+func (s deprecatedEcdsaSigner) SignMessage(message []byte) ([]byte, error) {
+	hash := sha256.Sum256(message)
+	return s.PrivateKey.Sign(rand.Reader, hash[:], crypto.SHA256)
+}
+
+func (s deprecatedEcdsaSigner) ContainsID(id string) bool {
+	return s.PublicData().ContainsID(id)
+}
+
+func (deprecatedEcdsaSigner) MarshalPrivateKey() (*data.PrivateKey, error) {
+	return nil, errors.New("not implemented for test")
+}
+
+func (deprecatedEcdsaSigner) UnmarshalPrivateKey(key *data.PrivateKey) error {
+	return errors.New("not implemented for test")
+}
+
+func generatedDeprecatedSigner() (*deprecatedEcdsaSigner, error) {
+	privkey, err := ecdsa.GenerateKey(elliptic.P256(), rand.Reader)
+	if err != nil {
+		return nil, err
+	}
+	return &deprecatedEcdsaSigner{privkey}, nil
+}
+
+func (DeprecatedECDSASuite) TestSignVerifyDeprecatedFormat(c *C) {
+	// Create an ecdsa key with a deprecated format.
+	signer, err := generatedDeprecatedSigner()
+	c.Assert(err, IsNil)
+	msg := []byte("foo")
+	sig, err := signer.SignMessage(msg)
+	c.Assert(err, IsNil)
+
+	pub := signer.PublicKey
+
+	keyValBytes, err := json.Marshal(&deprecatedP256Verifier{PublicKey: elliptic.Marshal(pub.Curve, pub.X, pub.Y)})
+	c.Assert(err, IsNil)
+	publicData := &data.PublicKey{
+		Type:       data.KeyTypeECDSA_SHA2_P256,
+		Scheme:     data.KeySchemeECDSA_SHA2_P256,
+		Algorithms: data.HashAlgorithms,
+		Value:      keyValBytes,
+	}
+
+	deprecatedEcdsa := NewDeprecatedEcdsaVerifier()
+	err = deprecatedEcdsa.UnmarshalPublicKey(publicData)
+	c.Assert(err, IsNil)
+	c.Assert(deprecatedEcdsa.Verify(msg, sig), IsNil)
+}
+
+func (DeprecatedECDSASuite) TestECDSAVerifyMismatchMessage(c *C) {
+	signer, err := generatedDeprecatedSigner()
+	c.Assert(err, IsNil)
+	msg := []byte("foo")
+	sig, err := signer.SignMessage(msg)
+	c.Assert(err, IsNil)
+	publicData := signer.PublicData()
+	deprecatedEcdsa := NewDeprecatedEcdsaVerifier()
+	err = deprecatedEcdsa.UnmarshalPublicKey(publicData)
+	c.Assert(err, IsNil)
+	c.Assert(deprecatedEcdsa.Verify([]byte("notfoo"), sig), ErrorMatches, "tuf: deprecated ecdsa signature verification failed")
+}
+
+func (DeprecatedECDSASuite) TestECDSAVerifyMismatchPubKey(c *C) {
+	signer, err := generatedDeprecatedSigner()
+	c.Assert(err, IsNil)
+	msg := []byte("foo")
+	sig, err := signer.SignMessage(msg)
+	c.Assert(err, IsNil)
+
+	signerNew, err := generatedDeprecatedSigner()
+	c.Assert(err, IsNil)
+	deprecatedEcdsa := NewDeprecatedEcdsaVerifier()
+	err = deprecatedEcdsa.UnmarshalPublicKey(signerNew.PublicData())
+	c.Assert(err, IsNil)
+	c.Assert(deprecatedEcdsa.Verify([]byte("notfoo"), sig), ErrorMatches, "tuf: deprecated ecdsa signature verification failed")
+}
+
+func (DeprecatedECDSASuite) TestMarshalUnmarshalPublicKey(c *C) {
+	signer, err := generatedDeprecatedSigner()
+	c.Assert(err, IsNil)
+
+	pub := signer.PublicData()
+
+	deprecatedEcdsa := NewDeprecatedEcdsaVerifier()
+	err = deprecatedEcdsa.UnmarshalPublicKey(pub)
+	c.Assert(err, IsNil)
+
+	c.Assert(deprecatedEcdsa.MarshalPublicKey(), DeepEquals, pub)
+}
diff --git a/pkg/keys/ecdsa.go b/pkg/keys/ecdsa.go
new file mode 100644
index 0000000..9740d1f
--- /dev/null
+++ b/pkg/keys/ecdsa.go
@@ -0,0 +1,173 @@
+package keys
+
+import (
+	"bytes"
+	"crypto/ecdsa"
+	"crypto/elliptic"
+	"crypto/rand"
+	"crypto/sha256"
+	"crypto/x509"
+	"encoding/json"
+	"encoding/pem"
+	"errors"
+	"fmt"
+	"io"
+
+	"github.com/theupdateframework/go-tuf/data"
+)
+
+func init() {
+	// Note: we use LoadOrStore here to prevent accidentally overriding the
+	// an explicit deprecated ECDSA verifier.
+	// TODO: When deprecated ECDSA is removed, this can switch back to Store.
+	VerifierMap.LoadOrStore(data.KeyTypeECDSA_SHA2_P256_OLD_FMT, NewEcdsaVerifier)
+	VerifierMap.LoadOrStore(data.KeyTypeECDSA_SHA2_P256, NewEcdsaVerifier)
+	SignerMap.Store(data.KeyTypeECDSA_SHA2_P256_OLD_FMT, newEcdsaSigner)
+	SignerMap.Store(data.KeyTypeECDSA_SHA2_P256, newEcdsaSigner)
+}
+
+func NewEcdsaVerifier() Verifier {
+	return &EcdsaVerifier{}
+}
+
+func newEcdsaSigner() Signer {
+	return &ecdsaSigner{}
+}
+
+type EcdsaVerifier struct {
+	PublicKey *PKIXPublicKey `json:"public"`
+	ecdsaKey  *ecdsa.PublicKey
+	key       *data.PublicKey
+}
+
+func (p *EcdsaVerifier) Public() string {
+	// This is already verified to succeed when unmarshalling a public key.
+	r, err := x509.MarshalPKIXPublicKey(p.ecdsaKey)
+	if err != nil {
+		// TODO: Gracefully handle these errors.
+		// See https://github.com/theupdateframework/go-tuf/issues/363
+		panic(err)
+	}
+	return string(r)
+}
+
+func (p *EcdsaVerifier) Verify(msg, sigBytes []byte) error {
+	hash := sha256.Sum256(msg)
+
+	if !ecdsa.VerifyASN1(p.ecdsaKey, hash[:], sigBytes) {
+		return errors.New("tuf: ecdsa signature verification failed")
+	}
+	return nil
+}
+
+func (p *EcdsaVerifier) MarshalPublicKey() *data.PublicKey {
+	return p.key
+}
+
+func (p *EcdsaVerifier) UnmarshalPublicKey(key *data.PublicKey) error {
+	// Prepare decoder limited to 512Kb
+	dec := json.NewDecoder(io.LimitReader(bytes.NewReader(key.Value), MaxJSONKeySize))
+
+	// Unmarshal key value
+	if err := dec.Decode(p); err != nil {
+		if errors.Is(err, io.EOF) || errors.Is(err, io.ErrUnexpectedEOF) {
+			return fmt.Errorf("tuf: the public key is truncated or too large: %w", err)
+		}
+		return err
+	}
+
+	ecdsaKey, ok := p.PublicKey.PublicKey.(*ecdsa.PublicKey)
+	if !ok {
+		return fmt.Errorf("invalid public key")
+	}
+
+	if _, err := x509.MarshalPKIXPublicKey(ecdsaKey); err != nil {
+		return fmt.Errorf("marshalling to PKIX key: invalid public key")
+	}
+
+	p.ecdsaKey = ecdsaKey
+	p.key = key
+	return nil
+}
+
+type ecdsaSigner struct {
+	*ecdsa.PrivateKey
+}
+
+type ecdsaPrivateKeyValue struct {
+	Private string         `json:"private"`
+	Public  *PKIXPublicKey `json:"public"`
+}
+
+func (s *ecdsaSigner) PublicData() *data.PublicKey {
+	// This uses a trusted public key JSON format with a trusted Public value.
+	keyValBytes, _ := json.Marshal(EcdsaVerifier{PublicKey: &PKIXPublicKey{PublicKey: s.Public()}})
+	return &data.PublicKey{
+		Type:       data.KeyTypeECDSA_SHA2_P256,
+		Scheme:     data.KeySchemeECDSA_SHA2_P256,
+		Algorithms: data.HashAlgorithms,
+		Value:      keyValBytes,
+	}
+}
+
+func (s *ecdsaSigner) SignMessage(message []byte) ([]byte, error) {
+	hash := sha256.Sum256(message)
+	return ecdsa.SignASN1(rand.Reader, s.PrivateKey, hash[:])
+}
+
+func (s *ecdsaSigner) MarshalPrivateKey() (*data.PrivateKey, error) {
+	priv, err := x509.MarshalECPrivateKey(s.PrivateKey)
+	if err != nil {
+		return nil, err
+	}
+	pemKey := pem.EncodeToMemory(&pem.Block{Type: "EC PRIVATE KEY", Bytes: priv})
+	val, err := json.Marshal(ecdsaPrivateKeyValue{
+		Private: string(pemKey),
+		Public:  &PKIXPublicKey{PublicKey: s.Public()},
+	})
+	if err != nil {
+		return nil, err
+	}
+	return &data.PrivateKey{
+		Type:       data.KeyTypeECDSA_SHA2_P256,
+		Scheme:     data.KeySchemeECDSA_SHA2_P256,
+		Algorithms: data.HashAlgorithms,
+		Value:      val,
+	}, nil
+}
+
+func (s *ecdsaSigner) UnmarshalPrivateKey(key *data.PrivateKey) error {
+	val := ecdsaPrivateKeyValue{}
+	if err := json.Unmarshal(key.Value, &val); err != nil {
+		return err
+	}
+	block, _ := pem.Decode([]byte(val.Private))
+	if block == nil {
+		return errors.New("invalid PEM value")
+	}
+	if block.Type != "EC PRIVATE KEY" {
+		return fmt.Errorf("invalid block type: %s", block.Type)
+	}
+	k, err := x509.ParseECPrivateKey(block.Bytes)
+	if err != nil {
+		return err
+	}
+	if k.Curve != elliptic.P256() {
+		return errors.New("unsupported ecdsa curve")
+	}
+	if _, err := json.Marshal(EcdsaVerifier{
+		PublicKey: &PKIXPublicKey{PublicKey: k.Public()}}); err != nil {
+		return fmt.Errorf("invalid public key: %s", err)
+	}
+
+	s.PrivateKey = k
+	return nil
+}
+
+func GenerateEcdsaKey() (*ecdsaSigner, error) {
+	privkey, err := ecdsa.GenerateKey(elliptic.P256(), rand.Reader)
+	if err != nil {
+		return nil, err
+	}
+	return &ecdsaSigner{privkey}, nil
+}
diff --git a/pkg/keys/ecdsa_test.go b/pkg/keys/ecdsa_test.go
new file mode 100644
index 0000000..2fe6348
--- /dev/null
+++ b/pkg/keys/ecdsa_test.go
@@ -0,0 +1,163 @@
+package keys
+
+import (
+	"crypto/ecdsa"
+	"crypto/elliptic"
+	"crypto/rand"
+	"encoding/hex"
+	"encoding/json"
+	"errors"
+	"io"
+	"strings"
+
+	fuzz "github.com/google/gofuzz"
+	"github.com/theupdateframework/go-tuf/data"
+	. "gopkg.in/check.v1"
+)
+
+type ECDSASuite struct{}
+
+var _ = Suite(ECDSASuite{})
+
+func (ECDSASuite) TestSignVerify(c *C) {
+	signer, err := GenerateEcdsaKey()
+	c.Assert(err, IsNil)
+	msg := []byte("foo")
+	sig, err := signer.SignMessage(msg)
+	c.Assert(err, IsNil)
+	publicData := signer.PublicData()
+	pubKey, err := GetVerifier(publicData)
+	c.Assert(err, IsNil)
+	c.Assert(pubKey.Verify(msg, sig), IsNil)
+}
+
+func (ECDSASuite) TestECDSAVerifyMismatchMessage(c *C) {
+	signer, err := GenerateEcdsaKey()
+	c.Assert(err, IsNil)
+	msg := []byte("foo")
+	sig, err := signer.SignMessage(msg)
+	c.Assert(err, IsNil)
+	publicData := signer.PublicData()
+	pubKey, err := GetVerifier(publicData)
+	c.Assert(err, IsNil)
+	c.Assert(pubKey.Verify([]byte("notfoo"), sig), ErrorMatches, "tuf: ecdsa signature verification failed")
+}
+
+func (ECDSASuite) TestECDSAVerifyMismatchPubKey(c *C) {
+	signer, err := GenerateEcdsaKey()
+	c.Assert(err, IsNil)
+	msg := []byte("foo")
+	sig, err := signer.SignMessage(msg)
+	c.Assert(err, IsNil)
+
+	signerNew, err := GenerateEcdsaKey()
+	c.Assert(err, IsNil)
+	pubKey, err := GetVerifier(signerNew.PublicData())
+	c.Assert(err, IsNil)
+	c.Assert(pubKey.Verify([]byte("notfoo"), sig), ErrorMatches, "tuf: ecdsa signature verification failed")
+}
+
+func (ECDSASuite) TestSignVerifyDeprecatedFails(c *C) {
+	// Create an ecdsa key with a deprecated format.
+	signer, err := GenerateEcdsaKey()
+	c.Assert(err, IsNil)
+
+	type deprecatedP256Verifier struct {
+		PublicKey data.HexBytes `json:"public"`
+	}
+	pub := signer.PublicKey
+	keyValBytes, err := json.Marshal(&deprecatedP256Verifier{PublicKey: elliptic.Marshal(pub.Curve, pub.X, pub.Y)})
+	c.Assert(err, IsNil)
+	publicData := &data.PublicKey{
+		Type:       data.KeyTypeECDSA_SHA2_P256,
+		Scheme:     data.KeySchemeECDSA_SHA2_P256,
+		Algorithms: data.HashAlgorithms,
+		Value:      keyValBytes,
+	}
+
+	_, err = GetVerifier(publicData)
+	c.Assert(err, ErrorMatches, "tuf: error unmarshalling key: invalid PEM value")
+}
+
+func (ECDSASuite) TestMarshalUnmarshalPublicKey(c *C) {
+	signer, err := GenerateEcdsaKey()
+	c.Assert(err, IsNil)
+	publicData := signer.PublicData()
+	pubKey, err := GetVerifier(publicData)
+	c.Assert(err, IsNil)
+	c.Assert(pubKey.MarshalPublicKey(), DeepEquals, publicData)
+}
+
+func (ECDSASuite) TestMarshalUnmarshalPrivateKey(c *C) {
+	signer, err := GenerateEcdsaKey()
+	c.Assert(err, IsNil)
+	privateData, err := signer.MarshalPrivateKey()
+	c.Assert(err, IsNil)
+	c.Assert(privateData.Type, Equals, data.KeyTypeECDSA_SHA2_P256)
+	c.Assert(privateData.Scheme, Equals, data.KeySchemeECDSA_SHA2_P256)
+	c.Assert(privateData.Algorithms, DeepEquals, data.HashAlgorithms)
+	s, err := GetSigner(privateData)
+	c.Assert(err, IsNil)
+	c.Assert(s, DeepEquals, signer)
+}
+
+func (ECDSASuite) TestUnmarshalECDSA(c *C) {
+	priv, err := ecdsa.GenerateKey(elliptic.P256(), strings.NewReader("00001-deterministic-buffer-for-key-generation"))
+	c.Assert(err, IsNil)
+
+	signer := &ecdsaSigner{priv}
+	goodKey := signer.PublicData()
+
+	verifier := NewEcdsaVerifier()
+	c.Assert(verifier.UnmarshalPublicKey(goodKey), IsNil)
+}
+
+func (ECDSASuite) TestUnmarshalECDSA_Invalid(c *C) {
+	badKeyValue, err := json.Marshal(true)
+	c.Assert(err, IsNil)
+
+	badKey := &data.PublicKey{
+		Type:       data.KeyTypeECDSA_SHA2_P256,
+		Scheme:     data.KeySchemeECDSA_SHA2_P256,
+		Algorithms: data.HashAlgorithms,
+		Value:      badKeyValue,
+	}
+	verifier := NewEcdsaVerifier()
+	c.Assert(verifier.UnmarshalPublicKey(badKey), ErrorMatches, "json: cannot unmarshal.*")
+}
+
+func (ECDSASuite) TestUnmarshalECDSA_FastFuzz(c *C) {
+	verifier := NewEcdsaVerifier()
+	for i := 0; i < 50; i++ {
+		// Ensure no basic panic
+
+		f := fuzz.New()
+		var publicData data.PublicKey
+		f.Fuzz(&publicData)
+
+		verifier.UnmarshalPublicKey(&publicData)
+	}
+}
+
+func (ECDSASuite) TestUnmarshalECDSA_TooLongContent(c *C) {
+	randomSeed := make([]byte, MaxJSONKeySize)
+	_, err := io.ReadFull(rand.Reader, randomSeed)
+	c.Assert(err, IsNil)
+
+	tooLongPayload, err := json.Marshal(
+		&ed25519Verifier{
+			PublicKey: data.HexBytes(hex.EncodeToString(randomSeed)),
+		},
+	)
+	c.Assert(err, IsNil)
+
+	badKey := &data.PublicKey{
+		Type:       data.KeyTypeECDSA_SHA2_P256,
+		Scheme:     data.KeySchemeECDSA_SHA2_P256,
+		Algorithms: data.HashAlgorithms,
+		Value:      tooLongPayload,
+	}
+	verifier := NewEcdsaVerifier()
+	err = verifier.UnmarshalPublicKey(badKey)
+	c.Assert(errors.Is(err, io.ErrUnexpectedEOF), Equals, true)
+}
diff --git a/pkg/keys/ed25519.go b/pkg/keys/ed25519.go
new file mode 100644
index 0000000..1e4c66c
--- /dev/null
+++ b/pkg/keys/ed25519.go
@@ -0,0 +1,161 @@
+package keys
+
+import (
+	"bytes"
+	"crypto"
+	"crypto/ed25519"
+	"crypto/rand"
+	"crypto/subtle"
+	"encoding/json"
+	"errors"
+	"fmt"
+	"io"
+
+	"github.com/theupdateframework/go-tuf/data"
+)
+
+func init() {
+	SignerMap.Store(data.KeyTypeEd25519, NewEd25519Signer)
+	VerifierMap.Store(data.KeyTypeEd25519, NewEd25519Verifier)
+}
+
+func NewEd25519Signer() Signer {
+	return &ed25519Signer{}
+}
+
+func NewEd25519Verifier() Verifier {
+	return &ed25519Verifier{}
+}
+
+type ed25519Verifier struct {
+	PublicKey data.HexBytes `json:"public"`
+	key       *data.PublicKey
+}
+
+func (e *ed25519Verifier) Public() string {
+	return string(e.PublicKey)
+}
+
+func (e *ed25519Verifier) Verify(msg, sig []byte) error {
+	if !ed25519.Verify([]byte(e.PublicKey), msg, sig) {
+		return errors.New("tuf: ed25519 signature verification failed")
+	}
+	return nil
+}
+
+func (e *ed25519Verifier) MarshalPublicKey() *data.PublicKey {
+	return e.key
+}
+
+func (e *ed25519Verifier) UnmarshalPublicKey(key *data.PublicKey) error {
+	e.key = key
+
+	// Prepare decoder limited to 512Kb
+	dec := json.NewDecoder(io.LimitReader(bytes.NewReader(key.Value), MaxJSONKeySize))
+
+	// Unmarshal key value
+	if err := dec.Decode(e); err != nil {
+		if errors.Is(err, io.EOF) || errors.Is(err, io.ErrUnexpectedEOF) {
+			return fmt.Errorf("tuf: the public key is truncated or too large: %w", err)
+		}
+		return err
+	}
+	if n := len(e.PublicKey); n != ed25519.PublicKeySize {
+		return fmt.Errorf("tuf: unexpected public key length for ed25519 key, expected %d, got %d", ed25519.PublicKeySize, n)
+	}
+	return nil
+}
+
+type Ed25519PrivateKeyValue struct {
+	Public  data.HexBytes `json:"public"`
+	Private data.HexBytes `json:"private"`
+}
+
+type ed25519Signer struct {
+	ed25519.PrivateKey
+}
+
+func GenerateEd25519Key() (*ed25519Signer, error) {
+	_, private, err := ed25519.GenerateKey(rand.Reader)
+	if err != nil {
+		return nil, err
+	}
+	if err != nil {
+		return nil, err
+	}
+	return &ed25519Signer{
+		PrivateKey: ed25519.PrivateKey(data.HexBytes(private)),
+	}, nil
+}
+
+func NewEd25519SignerFromKey(keyValue Ed25519PrivateKeyValue) *ed25519Signer {
+	return &ed25519Signer{
+		PrivateKey: ed25519.PrivateKey(data.HexBytes(keyValue.Private)),
+	}
+}
+
+func (e *ed25519Signer) SignMessage(message []byte) ([]byte, error) {
+	return e.Sign(rand.Reader, message, crypto.Hash(0))
+}
+
+func (e *ed25519Signer) MarshalPrivateKey() (*data.PrivateKey, error) {
+	valueBytes, err := json.Marshal(Ed25519PrivateKeyValue{
+		Public:  data.HexBytes([]byte(e.PrivateKey.Public().(ed25519.PublicKey))),
+		Private: data.HexBytes(e.PrivateKey),
+	})
+	if err != nil {
+		return nil, err
+	}
+	return &data.PrivateKey{
+		Type:       data.KeyTypeEd25519,
+		Scheme:     data.KeySchemeEd25519,
+		Algorithms: data.HashAlgorithms,
+		Value:      valueBytes,
+	}, nil
+}
+
+func (e *ed25519Signer) UnmarshalPrivateKey(key *data.PrivateKey) error {
+	keyValue := &Ed25519PrivateKeyValue{}
+
+	// Prepare decoder limited to 512Kb
+	dec := json.NewDecoder(io.LimitReader(bytes.NewReader(key.Value), MaxJSONKeySize))
+
+	// Unmarshal key value
+	if err := dec.Decode(keyValue); err != nil {
+		if errors.Is(err, io.EOF) || errors.Is(err, io.ErrUnexpectedEOF) {
+			return fmt.Errorf("tuf: the private key is truncated or too large: %w", err)
+		}
+	}
+
+	// Check private key length
+	if n := len(keyValue.Private); n != ed25519.PrivateKeySize {
+		return fmt.Errorf("tuf: invalid ed25519 private key length, expected %d, got %d", ed25519.PrivateKeySize, n)
+	}
+
+	// Generate public key from private key
+	pub, _, err := ed25519.GenerateKey(bytes.NewReader(keyValue.Private))
+	if err != nil {
+		return fmt.Errorf("tuf: unable to derive public key from private key: %w", err)
+	}
+
+	// Compare keys
+	if subtle.ConstantTimeCompare(keyValue.Public, pub) != 1 {
+		return errors.New("tuf: public and private keys don't match")
+	}
+
+	// Prepare signer
+	*e = ed25519Signer{
+		PrivateKey: ed25519.PrivateKey(data.HexBytes(keyValue.Private)),
+	}
+	return nil
+}
+
+func (e *ed25519Signer) PublicData() *data.PublicKey {
+	keyValBytes, _ := json.Marshal(ed25519Verifier{PublicKey: []byte(e.PrivateKey.Public().(ed25519.PublicKey))})
+	return &data.PublicKey{
+		Type:       data.KeyTypeEd25519,
+		Scheme:     data.KeySchemeEd25519,
+		Algorithms: data.HashAlgorithms,
+		Value:      keyValBytes,
+	}
+}
diff --git a/pkg/keys/ed25519_test.go b/pkg/keys/ed25519_test.go
new file mode 100644
index 0000000..a17cc14
--- /dev/null
+++ b/pkg/keys/ed25519_test.go
@@ -0,0 +1,99 @@
+package keys
+
+import (
+	"crypto/ed25519"
+	"crypto/rand"
+	"encoding/hex"
+	"encoding/json"
+	"errors"
+	"io"
+	"strings"
+
+	fuzz "github.com/google/gofuzz"
+	"github.com/theupdateframework/go-tuf/data"
+	. "gopkg.in/check.v1"
+)
+
+type Ed25519Suite struct{}
+
+var _ = Suite(&Ed25519Suite{})
+
+func (Ed25519Suite) TestUnmarshalEd25519(c *C) {
+	pub, _, err := ed25519.GenerateKey(strings.NewReader("00001-deterministic-buffer-for-key-generation"))
+	c.Assert(err, IsNil)
+
+	publicKey, err := json.Marshal(map[string]string{
+		"public": hex.EncodeToString(pub),
+	})
+	c.Assert(err, IsNil)
+
+	badKey := &data.PublicKey{
+		Type:       data.KeyTypeEd25519,
+		Scheme:     data.KeySchemeEd25519,
+		Algorithms: data.HashAlgorithms,
+		Value:      publicKey,
+	}
+	verifier := NewEd25519Verifier()
+	c.Assert(verifier.UnmarshalPublicKey(badKey), IsNil)
+}
+
+func (Ed25519Suite) TestUnmarshalEd25519_Invalid(c *C) {
+	badKeyValue, err := json.Marshal(true)
+	c.Assert(err, IsNil)
+	badKey := &data.PublicKey{
+		Type:       data.KeyTypeEd25519,
+		Scheme:     data.KeySchemeEd25519,
+		Algorithms: data.HashAlgorithms,
+		Value:      badKeyValue,
+	}
+	verifier := NewEd25519Verifier()
+	c.Assert(verifier.UnmarshalPublicKey(badKey), ErrorMatches, "json: cannot unmarshal.*")
+}
+
+func (Ed25519Suite) TestUnmarshalEd25519_FastFuzz(c *C) {
+	verifier := NewEd25519Verifier()
+	for i := 0; i < 50; i++ {
+		// Ensure no basic panic
+
+		f := fuzz.New()
+		var publicData data.PublicKey
+		f.Fuzz(&publicData)
+
+		verifier.UnmarshalPublicKey(&publicData)
+	}
+}
+
+func (Ed25519Suite) TestUnmarshalEd25519_TooLongContent(c *C) {
+	randomSeed := make([]byte, MaxJSONKeySize)
+	_, err := io.ReadFull(rand.Reader, randomSeed)
+	c.Assert(err, IsNil)
+
+	tooLongPayload, err := json.Marshal(
+		&ed25519Verifier{
+			PublicKey: data.HexBytes(hex.EncodeToString(randomSeed)),
+		},
+	)
+	c.Assert(err, IsNil)
+
+	badKey := &data.PublicKey{
+		Type:       data.KeyTypeEd25519,
+		Scheme:     data.KeySchemeEd25519,
+		Algorithms: data.HashAlgorithms,
+		Value:      tooLongPayload,
+	}
+	verifier := NewEd25519Verifier()
+	err = verifier.UnmarshalPublicKey(badKey)
+	c.Assert(errors.Is(err, io.ErrUnexpectedEOF), Equals, true)
+}
+
+func (Ed25519Suite) TestSignVerify(c *C) {
+	signer, err := GenerateEd25519Key()
+	c.Assert(err, IsNil)
+	msg := []byte("foo")
+	sig, err := signer.SignMessage(msg)
+	c.Assert(err, IsNil)
+	publicData := signer.PublicData()
+	pubKey, err := GetVerifier(publicData)
+	c.Assert(err, IsNil)
+	c.Assert(pubKey.Verify(msg, sig), IsNil)
+}
diff --git a/pkg/keys/keys.go b/pkg/keys/keys.go
new file mode 100644
index 0000000..dc5f3ea
--- /dev/null
+++ b/pkg/keys/keys.go
@@ -0,0 +1,82 @@
+package keys
+
+import (
+	"errors"
+	"fmt"
+	"sync"
+
+	"github.com/theupdateframework/go-tuf/data"
+)
+
+// MaxJSONKeySize defines the maximum length of a JSON payload.
+const MaxJSONKeySize = 512 * 1024 // 512Kb
+
+// SignerMap stores mapping between key type strings and signer constructors.
+var SignerMap sync.Map
+
+// Verifier stores mapping between key type strings and verifier constructors.
+var VerifierMap sync.Map
+
+var (
+	ErrInvalid    = errors.New("tuf: signature verification failed")
+	ErrInvalidKey = errors.New("invalid key")
+)
+
+// A Verifier verifies public key signatures.
+type Verifier interface {
+	// UnmarshalPublicKey takes key data to a working verifier implementation for the key type.
+	// This performs any validation over the data.PublicKey to ensure that the verifier is usable
+	// to verify signatures.
+	UnmarshalPublicKey(key *data.PublicKey) error
+
+	// MarshalPublicKey returns the data.PublicKey object associated with the verifier.
+	MarshalPublicKey() *data.PublicKey
+
+	// This is the public string used as a unique identifier for the verifier instance.
+	Public() string
+
+	// Verify takes a message and signature, all as byte slices,
+	// and determines whether the signature is valid for the given
+	// key and message.
+	Verify(msg, sig []byte) error
+}
+
+type Signer interface {
+	// MarshalPrivateKey returns the private key data.
+	MarshalPrivateKey() (*data.PrivateKey, error)
+
+	// UnmarshalPrivateKey takes private key data to a working Signer implementation for the key type.
+	UnmarshalPrivateKey(key *data.PrivateKey) error
+
+	// Returns the public data.PublicKey from the private key
+	PublicData() *data.PublicKey
+
+	// Sign returns the signature of the message.
+	// The signer is expected to do its own hashing, so the full message will be
+	// provided as the message to Sign with a zero opts.HashFunc().
+	SignMessage(message []byte) ([]byte, error)
+}
+
+func GetVerifier(key *data.PublicKey) (Verifier, error) {
+	st, ok := VerifierMap.Load(key.Type)
+	if !ok {
+		return nil, ErrInvalidKey
+	}
+	s := st.(func() Verifier)()
+	if err := s.UnmarshalPublicKey(key); err != nil {
+		return nil, fmt.Errorf("tuf: error unmarshalling key: %w", err)
+	}
+	return s, nil
+}
+
+func GetSigner(key *data.PrivateKey) (Signer, error) {
+	st, ok := SignerMap.Load(key.Type)
+	if !ok {
+		return nil, ErrInvalidKey
+	}
+	s := st.(func() Signer)()
+	if err := s.UnmarshalPrivateKey(key); err != nil {
+		return nil, fmt.Errorf("tuf: error unmarshalling key: %w", err)
+	}
+	return s, nil
+}
diff --git a/pkg/keys/keys_test.go b/pkg/keys/keys_test.go
new file mode 100644
index 0000000..c1a7d01
--- /dev/null
+++ b/pkg/keys/keys_test.go
@@ -0,0 +1,39 @@
+package keys
+
+import (
+	"testing"
+
+	"github.com/theupdateframework/go-tuf/data"
+	. "gopkg.in/check.v1"
+)
+
+// Hook up gocheck into the "go test" runner.
+func Test(t *testing.T) { TestingT(t) }
+
+type KeysSuite struct{}
+
+var _ = Suite(&KeysSuite{})
+
+func (KeysSuite) TestSignerKeyIDs(c *C) {
+	_, err := GenerateEd25519Key()
+	c.Assert(err, IsNil)
+
+	// If we have a TUF-0.9 key, we won't have a scheme.
+	signer, err := GenerateEd25519Key()
+	c.Assert(err, IsNil)
+	privKey, err := signer.MarshalPrivateKey()
+	c.Assert(err, IsNil)
+	privKey.Scheme = ""
+	err = signer.UnmarshalPrivateKey(privKey)
+	c.Assert(err, IsNil)
+
+	// Make sure we preserve ids if we don't have any
+	// keyid_hash_algorithms.
+	signer, err = GenerateEd25519Key()
+	c.Assert(err, IsNil)
+	privKey, err = signer.MarshalPrivateKey()
+	c.Assert(err, IsNil)
+	privKey.Algorithms = []data.HashAlgorithm{}
+	err = signer.UnmarshalPrivateKey(privKey)
+	c.Assert(err, IsNil)
+}
diff --git a/pkg/keys/pkix.go b/pkg/keys/pkix.go
new file mode 100644
index 0000000..e58d4c9
--- /dev/null
+++ b/pkg/keys/pkix.go
@@ -0,0 +1,56 @@
+package keys
+
+import (
+	"bytes"
+	"crypto"
+	"crypto/x509"
+	"encoding/json"
+	"encoding/pem"
+	"errors"
+	"fmt"
+	"io"
+)
+
+type PKIXPublicKey struct {
+	crypto.PublicKey
+}
+
+func (p *PKIXPublicKey) MarshalJSON() ([]byte, error) {
+	bytes, err := x509.MarshalPKIXPublicKey(p.PublicKey)
+	if err != nil {
+		return nil, err
+	}
+	pemBytes := pem.EncodeToMemory(&pem.Block{
+		Type:  "PUBLIC KEY",
+		Bytes: bytes,
+	})
+	return json.Marshal(string(pemBytes))
+}
+
+func (p *PKIXPublicKey) UnmarshalJSON(b []byte) error {
+	var pemValue string
+	// Prepare decoder limited to 512Kb
+	dec := json.NewDecoder(io.LimitReader(bytes.NewReader(b), MaxJSONKeySize))
+
+	// Unmarshal key value
+	if err := dec.Decode(&pemValue); err != nil {
+		if errors.Is(err, io.EOF) || errors.Is(err, io.ErrUnexpectedEOF) {
+			return fmt.Errorf("tuf: the public key is truncated or too large: %w", err)
+		}
+		return err
+	}
+
+	block, _ := pem.Decode([]byte(pemValue))
+	if block == nil {
+		return errors.New("invalid PEM value")
+	}
+	if block.Type != "PUBLIC KEY" {
+		return fmt.Errorf("invalid block type: %s", block.Type)
+	}
+	pub, err := x509.ParsePKIXPublicKey(block.Bytes)
+	if err != nil {
+		return err
+	}
+	p.PublicKey = pub
+	return nil
+}
diff --git a/pkg/keys/pkix_test.go b/pkg/keys/pkix_test.go
new file mode 100644
index 0000000..4debdde
--- /dev/null
+++ b/pkg/keys/pkix_test.go
@@ -0,0 +1,62 @@
+package keys
+
+import (
+	"crypto/ecdsa"
+	"crypto/rand"
+	"crypto/x509"
+	"encoding/json"
+	"encoding/pem"
+	"errors"
+	"io"
+
+	. "gopkg.in/check.v1"
+)
+
+const ecdsaKey = `-----BEGIN PUBLIC KEY-----
+MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAEftgasQA68yvumeXZmcOTSIHKfbmx
+WT1oYuRF0Un3tKxnzip6xAYwlz0Dt96DUh+0P7BruHH2O6s4MiRR9/TuNw==
+-----END PUBLIC KEY-----
+`
+
+type PKIXSuite struct{}
+
+var _ = Suite(&PKIXSuite{})
+
+func (PKIXSuite) TestMarshalJSON(c *C) {
+	block, _ := pem.Decode([]byte(ecdsaKey))
+	key, err := x509.ParsePKIXPublicKey(block.Bytes)
+	c.Assert(err, IsNil)
+	k := PKIXPublicKey{PublicKey: key}
+	buf, err := json.Marshal(&k)
+	c.Assert(err, IsNil)
+	var val string
+	err = json.Unmarshal(buf, &val)
+	c.Assert(err, IsNil)
+	c.Assert(val, Equals, ecdsaKey)
+}
+
+func (PKIXSuite) TestUnmarshalJSON(c *C) {
+	buf, err := json.Marshal(ecdsaKey)
+	c.Assert(err, IsNil)
+	var k PKIXPublicKey
+	err = json.Unmarshal(buf, &k)
+	c.Assert(err, IsNil)
+	c.Assert(k.PublicKey, FitsTypeOf, (*ecdsa.PublicKey)(nil))
+}
+
+func (PKIXSuite) TestUnmarshalPKIX_TooLongContent(c *C) {
+	randomSeed := make([]byte, MaxJSONKeySize)
+	_, err := io.ReadFull(rand.Reader, randomSeed)
+	c.Assert(err, IsNil)
+
+	pemBytes := pem.EncodeToMemory(&pem.Block{
+		Type:  "PUBLIC KEY",
+		Bytes: randomSeed,
+	})
+	tooLongPayload, err := json.Marshal(string(pemBytes))
+	c.Assert(err, IsNil)
+
+	var k PKIXPublicKey
+	err = json.Unmarshal(tooLongPayload, &k)
+	c.Assert(errors.Is(err, io.ErrUnexpectedEOF), Equals, true)
+}
diff --git a/pkg/keys/rsa.go b/pkg/keys/rsa.go
new file mode 100644
index 0000000..618f104
--- /dev/null
+++ b/pkg/keys/rsa.go
@@ -0,0 +1,162 @@
+package keys
+
+import (
+	"bytes"
+	"crypto"
+	"crypto/rand"
+	"crypto/rsa"
+	"crypto/sha256"
+	"crypto/x509"
+	"encoding/json"
+	"encoding/pem"
+	"errors"
+	"fmt"
+	"io"
+
+	"github.com/theupdateframework/go-tuf/data"
+)
+
+func init() {
+	VerifierMap.Store(data.KeyTypeRSASSA_PSS_SHA256, newRsaVerifier)
+	SignerMap.Store(data.KeyTypeRSASSA_PSS_SHA256, newRsaSigner)
+}
+
+func newRsaVerifier() Verifier {
+	return &rsaVerifier{}
+}
+
+func newRsaSigner() Signer {
+	return &rsaSigner{}
+}
+
+type rsaVerifier struct {
+	PublicKey *PKIXPublicKey `json:"public"`
+	rsaKey    *rsa.PublicKey
+	key       *data.PublicKey
+}
+
+func (p *rsaVerifier) Public() string {
+	// This is already verified to succeed when unmarshalling a public key.
+	r, err := x509.MarshalPKIXPublicKey(p.rsaKey)
+	if err != nil {
+		// TODO: Gracefully handle these errors.
+		// See https://github.com/theupdateframework/go-tuf/issues/363
+		panic(err)
+	}
+	return string(r)
+}
+
+func (p *rsaVerifier) Verify(msg, sigBytes []byte) error {
+	hash := sha256.Sum256(msg)
+
+	return rsa.VerifyPSS(p.rsaKey, crypto.SHA256, hash[:], sigBytes, &rsa.PSSOptions{})
+}
+
+func (p *rsaVerifier) MarshalPublicKey() *data.PublicKey {
+	return p.key
+}
+
+func (p *rsaVerifier) UnmarshalPublicKey(key *data.PublicKey) error {
+	// Prepare decoder limited to 512Kb
+	dec := json.NewDecoder(io.LimitReader(bytes.NewReader(key.Value), MaxJSONKeySize))
+
+	// Unmarshal key value
+	if err := dec.Decode(p); err != nil {
+		if errors.Is(err, io.EOF) || errors.Is(err, io.ErrUnexpectedEOF) {
+			return fmt.Errorf("tuf: the public key is truncated or too large: %w", err)
+		}
+		return err
+	}
+
+	rsaKey, ok := p.PublicKey.PublicKey.(*rsa.PublicKey)
+	if !ok {
+		return fmt.Errorf("invalid public key")
+	}
+
+	if _, err := x509.MarshalPKIXPublicKey(rsaKey); err != nil {
+		return fmt.Errorf("marshalling to PKIX key: invalid public key")
+	}
+
+	p.rsaKey = rsaKey
+	p.key = key
+	return nil
+}
+
+type rsaSigner struct {
+	*rsa.PrivateKey
+}
+
+type rsaPrivateKeyValue struct {
+	Private string         `json:"private"`
+	Public  *PKIXPublicKey `json:"public"`
+}
+
+func (s *rsaSigner) PublicData() *data.PublicKey {
+	keyValBytes, _ := json.Marshal(rsaVerifier{PublicKey: &PKIXPublicKey{PublicKey: s.Public()}})
+	return &data.PublicKey{
+		Type:       data.KeyTypeRSASSA_PSS_SHA256,
+		Scheme:     data.KeySchemeRSASSA_PSS_SHA256,
+		Algorithms: data.HashAlgorithms,
+		Value:      keyValBytes,
+	}
+}
+
+func (s *rsaSigner) SignMessage(message []byte) ([]byte, error) {
+	hash := sha256.Sum256(message)
+	return rsa.SignPSS(rand.Reader, s.PrivateKey, crypto.SHA256, hash[:], &rsa.PSSOptions{})
+}
+
+func (s *rsaSigner) ContainsID(id string) bool {
+	return s.PublicData().ContainsID(id)
+}
+
+func (s *rsaSigner) MarshalPrivateKey() (*data.PrivateKey, error) {
+	priv := x509.MarshalPKCS1PrivateKey(s.PrivateKey)
+	pemKey := pem.EncodeToMemory(&pem.Block{Type: "RSA PRIVATE KEY", Bytes: priv})
+	val, err := json.Marshal(rsaPrivateKeyValue{
+		Private: string(pemKey),
+		Public:  &PKIXPublicKey{PublicKey: s.Public()},
+	})
+	if err != nil {
+		return nil, err
+	}
+	return &data.PrivateKey{
+		Type:       data.KeyTypeRSASSA_PSS_SHA256,
+		Scheme:     data.KeySchemeRSASSA_PSS_SHA256,
+		Algorithms: data.HashAlgorithms,
+		Value:      val,
+	}, nil
+}
+
+func (s *rsaSigner) UnmarshalPrivateKey(key *data.PrivateKey) error {
+	val := rsaPrivateKeyValue{}
+	if err := json.Unmarshal(key.Value, &val); err != nil {
+		return err
+	}
+	block, _ := pem.Decode([]byte(val.Private))
+	if block == nil {
+		return errors.New("invalid PEM value")
+	}
+	if block.Type != "RSA PRIVATE KEY" {
+		return fmt.Errorf("invalid block type: %s", block.Type)
+	}
+	k, err := x509.ParsePKCS1PrivateKey(block.Bytes)
+	if err != nil {
+		return err
+	}
+	if _, err := json.Marshal(rsaVerifier{
+		PublicKey: &PKIXPublicKey{PublicKey: k.Public()}}); err != nil {
+		return fmt.Errorf("invalid public key: %s", err)
+	}
+
+	s.PrivateKey = k
+	return nil
+}
+
+func GenerateRsaKey() (*rsaSigner, error) {
+	privkey, err := rsa.GenerateKey(rand.Reader, 2048)
+	if err != nil {
+		return nil, err
+	}
+	return &rsaSigner{privkey}, nil
+}
diff --git a/pkg/keys/rsa_test.go b/pkg/keys/rsa_test.go
new file mode 100644
index 0000000..7352000
--- /dev/null
+++ b/pkg/keys/rsa_test.go
@@ -0,0 +1,125 @@
+package keys
+
+import (
+	"crypto/rand"
+	"encoding/hex"
+	"encoding/json"
+	"errors"
+	"io"
+
+	"github.com/theupdateframework/go-tuf/data"
+	. "gopkg.in/check.v1"
+)
+
+type RsaSuite struct{}
+
+var _ = Suite(&RsaSuite{})
+
+func (RsaSuite) TestSignVerify(c *C) {
+	signer, err := GenerateRsaKey()
+	c.Assert(err, IsNil)
+	msg := []byte("foo")
+	sig, err := signer.SignMessage(msg)
+	c.Assert(err, IsNil)
+	publicData := signer.PublicData()
+	pubKey, err := GetVerifier(publicData)
+	c.Assert(err, IsNil)
+	c.Assert(pubKey.Verify(msg, sig), IsNil)
+}
+
+func (RsaSuite) TestRSAVerifyMismatchMessage(c *C) {
+	signer, err := GenerateRsaKey()
+	c.Assert(err, IsNil)
+	msg := []byte("foo")
+	sig, err := signer.SignMessage(msg)
+	c.Assert(err, IsNil)
+	publicData := signer.PublicData()
+	pubKey, err := GetVerifier(publicData)
+	c.Assert(err, IsNil)
+	c.Assert(pubKey.Verify([]byte("notfoo"), sig), ErrorMatches, "crypto/rsa: verification error")
+}
+
+func (RsaSuite) TestRSAVerifyMismatchPubKey(c *C) {
+	signer, err := GenerateRsaKey()
+	c.Assert(err, IsNil)
+	msg := []byte("foo")
+	sig, err := signer.SignMessage(msg)
+	c.Assert(err, IsNil)
+
+	signerNew, err := GenerateRsaKey()
+	c.Assert(err, IsNil)
+
+	pubKey, err := GetVerifier(signerNew.PublicData())
+	c.Assert(err, IsNil)
+	c.Assert(pubKey.Verify([]byte("notfoo"), sig), ErrorMatches, "crypto/rsa: verification error")
+}
+
+func (RsaSuite) TestMarshalUnmarshalPublicKey(c *C) {
+	signer, err := GenerateRsaKey()
+	c.Assert(err, IsNil)
+	publicData := signer.PublicData()
+	pubKey, err := GetVerifier(publicData)
+	c.Assert(err, IsNil)
+	c.Assert(pubKey.MarshalPublicKey(), DeepEquals, publicData)
+}
+
+func (RsaSuite) TestMarshalUnmarshalPrivateKey(c *C) {
+	signer, err := GenerateRsaKey()
+	c.Assert(err, IsNil)
+	privateData, err := signer.MarshalPrivateKey()
+	c.Assert(err, IsNil)
+	c.Assert(privateData.Type, Equals, data.KeyTypeRSASSA_PSS_SHA256)
+	c.Assert(privateData.Scheme, Equals, data.KeySchemeRSASSA_PSS_SHA256)
+	c.Assert(privateData.Algorithms, DeepEquals, data.HashAlgorithms)
+	s, err := GetSigner(privateData)
+	c.Assert(err, IsNil)
+	c.Assert(s, DeepEquals, signer)
+}
+
+func (ECDSASuite) TestUnmarshalRSA_Invalid(c *C) {
+	badKeyValue, err := json.Marshal(true)
+	c.Assert(err, IsNil)
+
+	badKey := &data.PublicKey{
+		Type:       data.KeyTypeECDSA_SHA2_P256,
+		Scheme:     data.KeySchemeECDSA_SHA2_P256,
+		Algorithms: data.HashAlgorithms,
+		Value:      badKeyValue,
+	}
+	verifier := NewEcdsaVerifier()
+	c.Assert(verifier.UnmarshalPublicKey(badKey), ErrorMatches, "json: cannot unmarshal.*")
+}
+
+func (ECDSASuite) TestUnmarshalRSAPublicKey(c *C) {
+	priv, err := GenerateRsaKey()
+	c.Assert(err, IsNil)
+
+	signer := &rsaSigner{priv.PrivateKey}
+	goodKey := signer.PublicData()
+
+	verifier := newRsaVerifier()
+	c.Assert(verifier.UnmarshalPublicKey(goodKey), IsNil)
+}
+
+func (ECDSASuite) TestUnmarshalRSA_TooLongContent(c *C) {
+	randomSeed := make([]byte, MaxJSONKeySize)
+	_, err := io.ReadFull(rand.Reader, randomSeed)
+	c.Assert(err, IsNil)
+
+	tooLongPayload, err := json.Marshal(
+		&ed25519Verifier{
+			PublicKey: data.HexBytes(hex.EncodeToString(randomSeed)),
+		},
+	)
+	c.Assert(err, IsNil)
+
+	badKey := &data.PublicKey{
+		Type:       data.KeyTypeECDSA_SHA2_P256,
+		Scheme:     data.KeySchemeECDSA_SHA2_P256,
+		Algorithms: data.HashAlgorithms,
+		Value:      tooLongPayload,
+	}
+	verifier := newRsaVerifier()
+	err = verifier.UnmarshalPublicKey(badKey)
+	c.Assert(errors.Is(err, io.ErrUnexpectedEOF), Equals, true)
+}
diff --git a/pkg/targets/delegation.go b/pkg/targets/delegation.go
new file mode 100644
index 0000000..dce6171
--- /dev/null
+++ b/pkg/targets/delegation.go
@@ -0,0 +1,102 @@
+package targets
+
+import (
+	"errors"
+
+	"github.com/theupdateframework/go-tuf/data"
+	"github.com/theupdateframework/go-tuf/internal/sets"
+	"github.com/theupdateframework/go-tuf/verify"
+)
+
+type Delegation struct {
+	Delegator string
+	Delegatee data.DelegatedRole
+	DB        *verify.DB
+}
+
+type delegationsIterator struct {
+	stack        []Delegation
+	target       string
+	visitedRoles map[string]struct{}
+	parents      map[string]string
+}
+
+var ErrTopLevelTargetsRoleMissing = errors.New("tuf: top level targets role missing from top level keys DB")
+
+// NewDelegationsIterator initialises an iterator with a first step
+// on top level targets.
+func NewDelegationsIterator(target string, topLevelKeysDB *verify.DB) (*delegationsIterator, error) {
+	targetsRole := topLevelKeysDB.GetRole("targets")
+	if targetsRole == nil {
+		return nil, ErrTopLevelTargetsRoleMissing
+	}
+
+	i := &delegationsIterator{
+		target: target,
+		stack: []Delegation{
+			{
+				Delegatee: data.DelegatedRole{
+					Name:      "targets",
+					KeyIDs:    sets.StringSetToSlice(targetsRole.KeyIDs),
+					Threshold: targetsRole.Threshold,
+				},
+				DB: topLevelKeysDB,
+			},
+		},
+		visitedRoles: make(map[string]struct{}),
+		parents:      make(map[string]string),
+	}
+	return i, nil
+}
+
+func (d *delegationsIterator) Next() (value Delegation, ok bool) {
+	if len(d.stack) == 0 {
+		return Delegation{}, false
+	}
+	delegation := d.stack[len(d.stack)-1]
+	d.stack = d.stack[:len(d.stack)-1]
+
+	// 5.6.7.1: If this role has been visited before, then skip this role (so
+	// that cycles in the delegation graph are avoided).
+	roleName := delegation.Delegatee.Name
+	if _, ok := d.visitedRoles[roleName]; ok {
+		return d.Next()
+	}
+	d.visitedRoles[roleName] = struct{}{}
+
+	// 5.6.7.2 trim delegations to visit, only the current role and its delegations
+	// will be considered
+	// https://github.com/theupdateframework/specification/issues/168
+	if delegation.Delegatee.Terminating {
+		// Empty the stack.
+		d.stack = d.stack[0:0]
+	}
+	return delegation, true
+}
+
+func (d *delegationsIterator) Add(roles []data.DelegatedRole, delegator string, db *verify.DB) error {
+	for i := len(roles) - 1; i >= 0; i-- {
+		// Push the roles onto the stack in reverse so we get an preorder traversal
+		// of the delegations graph.
+		r := roles[i]
+		matchesPath, err := r.MatchesPath(d.target)
+		if err != nil {
+			return err
+		}
+		if matchesPath {
+			delegation := Delegation{
+				Delegator: delegator,
+				Delegatee: r,
+				DB:        db,
+			}
+			d.stack = append(d.stack, delegation)
+			d.parents[r.Name] = delegator
+		}
+	}
+
+	return nil
+}
+
+func (d *delegationsIterator) Parent(role string) string {
+	return d.parents[role]
+}
diff --git a/pkg/targets/delegation_test.go b/pkg/targets/delegation_test.go
new file mode 100644
index 0000000..2e0c42b
--- /dev/null
+++ b/pkg/targets/delegation_test.go
@@ -0,0 +1,252 @@
+package targets
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+	"github.com/theupdateframework/go-tuf/data"
+	"github.com/theupdateframework/go-tuf/verify"
+)
+
+var (
+	defaultPathPatterns = []string{"tmp", "*"}
+	noMatchPathPatterns = []string{"vars", "null"}
+)
+
+func TestDelegationsIterator(t *testing.T) {
+	topTargetsPubKey := &data.PublicKey{
+		Type:       data.KeyTypeEd25519,
+		Scheme:     data.KeySchemeEd25519,
+		Algorithms: data.HashAlgorithms,
+		Value:      []byte(`{"public":"aaaaec567e5901ba3976c34f7cd5169704292439bf71e6aa19c64b96706f95ef"}`),
+	}
+	delTargetsPubKey := &data.PublicKey{
+		Type:       data.KeyTypeEd25519,
+		Scheme:     data.KeySchemeEd25519,
+		Algorithms: data.HashAlgorithms,
+		Value:      []byte(`{"public":"bbbbec567e5901ba3976c34f7cd5169704292439bf71e6aa19c64b96706f95ef"}`),
+	}
+
+	defaultKeyIDs := delTargetsPubKey.IDs()
+	var iteratorTests = []struct {
+		testName    string
+		roles       map[string][]data.DelegatedRole
+		file        string
+		resultOrder []string
+		err         error
+	}{
+		{
+			testName: "no delegation",
+			roles: map[string][]data.DelegatedRole{
+				"targets": {},
+			},
+			file:        "test.txt",
+			resultOrder: []string{"targets"},
+		},
+		{
+			testName: "no termination",
+			roles: map[string][]data.DelegatedRole{
+				"targets": {
+					{Name: "b", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+					{Name: "e", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+				"b": {
+					{Name: "c", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+				"c": {
+					{Name: "d", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+				"e": {
+					{Name: "f", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+					{Name: "g", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+				"g": {
+					{Name: "h", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+					{Name: "i", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+					{Name: "j", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+			},
+			file:        "",
+			resultOrder: []string{"targets", "b", "c", "d", "e", "f", "g", "h", "i", "j"},
+		},
+		{
+			testName: "terminated in b",
+			roles: map[string][]data.DelegatedRole{
+				"targets": {
+					{Name: "b", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs, Terminating: true},
+					{Name: "e", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+				"b": {
+					{Name: "c", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+					{Name: "d", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+			},
+			file:        "",
+			resultOrder: []string{"targets", "b", "c", "d"},
+		},
+		{
+			testName: "path does not match b",
+			roles: map[string][]data.DelegatedRole{
+				"targets": {
+					{Name: "b", Paths: noMatchPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+					{Name: "e", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+				"b": {
+					{Name: "c", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+					{Name: "d", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+			},
+			file:        "",
+			resultOrder: []string{"targets", "e"},
+		},
+		{
+			testName: "path does not match b - path prefixes",
+			roles: map[string][]data.DelegatedRole{
+				"targets": {
+					{Name: "b", PathHashPrefixes: []string{"33472a4909"}, Threshold: 1, KeyIDs: defaultKeyIDs},
+					{Name: "c", PathHashPrefixes: []string{"34c85d1ee84f61f10d7dc633"}, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+				"c": {
+
+					{Name: "d", PathHashPrefixes: []string{"8baf"}, Threshold: 1, KeyIDs: defaultKeyIDs},
+					{Name: "e", PathHashPrefixes: []string{"34c85d1ee84f61f10d7dc633472a49096ed87f8f764bd597831eac371f40ac39"}, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+			},
+			file:        "/e/f/g.txt",
+			resultOrder: []string{"targets", "c", "e"},
+		},
+		{
+			testName: "err paths and pathHashPrefixes are set",
+			roles: map[string][]data.DelegatedRole{
+				"targets": {
+					{Name: "b", Paths: defaultPathPatterns, PathHashPrefixes: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+				"b": {},
+			},
+			file:        "",
+			resultOrder: []string{"targets"},
+			err:         data.ErrPathsAndPathHashesSet,
+		},
+		{
+			testName: "cycle avoided 1",
+			roles: map[string][]data.DelegatedRole{
+				"targets": {
+					{Name: "a", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+				"a": {
+					{Name: "b", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+					{Name: "e", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+				"b": {
+					{Name: "a", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+					{Name: "d", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+			},
+			file:        "",
+			resultOrder: []string{"targets", "a", "b", "d", "e"},
+		},
+		{
+			testName: "cycle avoided 2",
+			roles: map[string][]data.DelegatedRole{
+				"targets": {
+					{Name: "a", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+				"a": {
+					{Name: "a", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+					{Name: "b", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+				"b": {
+					{Name: "a", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+					{Name: "b", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+					{Name: "c", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+				"c": {
+					{Name: "c", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+			},
+			file:        "",
+			resultOrder: []string{"targets", "a", "b", "c"},
+		},
+		{
+			testName: "diamond delegation",
+			roles: map[string][]data.DelegatedRole{
+				"targets": {
+					{Name: "b", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+					{Name: "c", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+				"b": {
+					{Name: "d", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+				"c": {
+					{Name: "d", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+			},
+			file:        "",
+			resultOrder: []string{"targets", "b", "d", "c"},
+		},
+		{
+			testName: "simple cycle",
+			roles: map[string][]data.DelegatedRole{
+				"targets": {
+					{Name: "a", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+				"a": {
+					{Name: "a", Paths: defaultPathPatterns, Threshold: 1, KeyIDs: defaultKeyIDs},
+				},
+			},
+			file:        "",
+			resultOrder: []string{"targets", "a"},
+		},
+	}
+
+	for _, tt := range iteratorTests {
+		t.Run(tt.testName, func(t *testing.T) {
+			topLevelDB := verify.NewDB()
+			topLevelDB.AddKey(topTargetsPubKey.IDs()[0], topTargetsPubKey)
+			topLevelDB.AddRole("targets", &data.Role{
+				KeyIDs:    topTargetsPubKey.IDs(),
+				Threshold: 1,
+			})
+
+			d, err := NewDelegationsIterator(tt.file, topLevelDB)
+			assert.NoError(t, err)
+
+			var iterationOrder []string
+			for {
+				r, ok := d.Next()
+				if !ok {
+					break
+				}
+
+				// A delegation should have associated keys. Testing the exact keys
+				// isn't useful in this module since the keys are supplied by the
+				// caller in the arguments to Add().
+				assert.Greater(t, len(r.Delegatee.KeyIDs), 0)
+
+				iterationOrder = append(iterationOrder, r.Delegatee.Name)
+				delegations, ok := tt.roles[r.Delegatee.Name]
+				if !ok {
+					continue
+				}
+
+				db, err := verify.NewDBFromDelegations(&data.Delegations{
+					Roles: delegations,
+				})
+				assert.NoError(t, err)
+
+				err = d.Add(delegations, r.Delegatee.Name, db)
+				assert.Equal(t, tt.err, err)
+			}
+			assert.Equal(t, tt.resultOrder, iterationOrder)
+		})
+	}
+}
+
+func TestNewDelegationsIteratorError(t *testing.T) {
+	// Empty DB. It is supposed to have at least the top-level targets role and
+	// keys.
+	tldb := verify.NewDB()
+
+	_, err := NewDelegationsIterator("targets", tldb)
+	assert.ErrorIs(t, err, ErrTopLevelTargetsRoleMissing)
+}
diff --git a/pkg/targets/hash_bins.go b/pkg/targets/hash_bins.go
new file mode 100644
index 0000000..95f4405
--- /dev/null
+++ b/pkg/targets/hash_bins.go
@@ -0,0 +1,113 @@
+package targets
+
+import (
+	"fmt"
+	"strconv"
+	"strings"
+)
+
+const MinDelegationHashPrefixBitLen = 1
+const MaxDelegationHashPrefixBitLen = 32
+
+// hexEncode formats x as a hex string. The hex string is left padded with
+// zeros to padWidth, if necessary.
+func hexEncode(x uint64, padWidth int) string {
+	// Benchmarked to be more than 10x faster than padding with Sprintf.
+	s := strconv.FormatUint(x, 16)
+	if len(s) >= padWidth {
+		return s
+	}
+	return strings.Repeat("0", padWidth-len(s)) + s
+}
+
+const bitsPerHexDigit = 4
+
+// numHexDigits returns the number of hex digits required to encode the given
+// number of bits.
+func numHexDigits(numBits int) int {
+	// ceil(numBits / bitsPerHexDigit)
+	return ((numBits - 1) / bitsPerHexDigit) + 1
+}
+
+// HashBins represents an ordered list of hash bin target roles, which together
+// partition the space of target path hashes equal-sized buckets based on path
+// has prefix.
+type HashBins struct {
+	rolePrefix  string
+	bitLen      int
+	hexDigitLen int
+
+	numBins           uint64
+	numPrefixesPerBin uint64
+}
+
+// NewHashBins creates a HashBins partitioning with 2^bitLen buckets.
+func NewHashBins(rolePrefix string, bitLen int) (*HashBins, error) {
+	if bitLen < MinDelegationHashPrefixBitLen || bitLen > MaxDelegationHashPrefixBitLen {
+		return nil, fmt.Errorf("bitLen is out of bounds, should be between %v and %v inclusive", MinDelegationHashPrefixBitLen, MaxDelegationHashPrefixBitLen)
+	}
+
+	hexDigitLen := numHexDigits(bitLen)
+	numBins := uint64(1) << bitLen
+
+	numPrefixesTotal := uint64(1) << (bitsPerHexDigit * hexDigitLen)
+	numPrefixesPerBin := numPrefixesTotal / numBins
+
+	return &HashBins{
+		rolePrefix:        rolePrefix,
+		bitLen:            bitLen,
+		hexDigitLen:       hexDigitLen,
+		numBins:           numBins,
+		numPrefixesPerBin: numPrefixesPerBin,
+	}, nil
+}
+
+// NumBins returns the number of hash bin partitions.
+func (hb *HashBins) NumBins() uint64 {
+	return hb.numBins
+}
+
+// GetBin returns the HashBin at index i, or nil if i is out of bounds.
+func (hb *HashBins) GetBin(i uint64) *HashBin {
+	if i >= hb.numBins {
+		return nil
+	}
+
+	return &HashBin{
+		rolePrefix:  hb.rolePrefix,
+		hexDigitLen: hb.hexDigitLen,
+		first:       i * hb.numPrefixesPerBin,
+		last:        ((i + 1) * hb.numPrefixesPerBin) - 1,
+	}
+}
+
+// HashBin represents a hex prefix range. First should be less than Last.
+type HashBin struct {
+	rolePrefix  string
+	hexDigitLen int
+	first       uint64
+	last        uint64
+}
+
+// RoleName returns the name of the role that signs for the HashBin.
+func (b *HashBin) RoleName() string {
+	if b.first == b.last {
+		return b.rolePrefix + hexEncode(b.first, b.hexDigitLen)
+	}
+
+	return b.rolePrefix + hexEncode(b.first, b.hexDigitLen) + "-" + hexEncode(b.last, b.hexDigitLen)
+}
+
+// HashPrefixes returns a slice of all hash prefixes in the bin.
+func (b *HashBin) HashPrefixes() []string {
+	n := int(b.last - b.first + 1)
+	ret := make([]string, int(n))
+
+	x := b.first
+	for i := 0; i < n; i++ {
+		ret[i] = hexEncode(x, b.hexDigitLen)
+		x++
+	}
+
+	return ret
+}
diff --git a/pkg/targets/hash_bins_test.go b/pkg/targets/hash_bins_test.go
new file mode 100644
index 0000000..dce2ab8
--- /dev/null
+++ b/pkg/targets/hash_bins_test.go
@@ -0,0 +1,119 @@
+package targets
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+)
+
+func BenchmarkHexEncode1(b *testing.B) {
+	for n := 0; n <= b.N; n++ {
+		for x := uint64(0); x <= 0xf; x += 1 {
+			hexEncode(x, 1)
+		}
+	}
+}
+
+func BenchmarkHexEncode4(b *testing.B) {
+	for n := 0; n <= b.N; n++ {
+		for x := uint64(0); x <= 0xffff; x += 1 {
+			hexEncode(x, 4)
+		}
+	}
+}
+
+func TestHashBin(t *testing.T) {
+	tcs := []struct {
+		hb           *HashBin
+		roleName     string
+		hashPrefixes []string
+	}{
+		{
+			hb: &HashBin{
+				rolePrefix:  "abc_",
+				hexDigitLen: 1,
+				first:       0x0,
+				last:        0x7,
+			},
+			roleName: "abc_0-7",
+			hashPrefixes: []string{
+				"0", "1", "2", "3", "4", "5", "6", "7",
+			},
+		},
+		{
+			hb: &HashBin{
+				rolePrefix:  "abc_",
+				hexDigitLen: 2,
+				first:       0x0,
+				last:        0xf,
+			},
+			roleName: "abc_00-0f",
+			hashPrefixes: []string{
+				"00", "01", "02", "03", "04", "05", "06", "07",
+				"08", "09", "0a", "0b", "0c", "0d", "0e", "0f",
+			},
+		},
+		{
+			hb: &HashBin{
+				rolePrefix:  "cba_",
+				hexDigitLen: 4,
+				first:       0xcd,
+				last:        0xcf,
+			},
+			roleName:     "cba_00cd-00cf",
+			hashPrefixes: []string{"00cd", "00ce", "00cf"},
+		},
+		{
+			hb: &HashBin{
+				rolePrefix:  "cba_",
+				hexDigitLen: 3,
+				first:       0xc1,
+				last:        0xc1,
+			},
+			roleName:     "cba_0c1",
+			hashPrefixes: []string{"0c1"},
+		},
+	}
+
+	for i, tc := range tcs {
+		assert.Equalf(t, tc.roleName, tc.hb.RoleName(), "test case %v: RoleName()", i)
+		assert.Equalf(t, tc.hashPrefixes, tc.hb.HashPrefixes(), "test case %v: HashPrefixes()", i)
+	}
+}
+
+func TestHashBins(t *testing.T) {
+	tcs := []struct {
+		bitLen    int
+		roleNames []string
+	}{
+		{1, []string{"0-7", "8-f"}},
+		{2, []string{"0-3", "4-7", "8-b", "c-f"}},
+		{3, []string{"0-1", "2-3", "4-5", "6-7", "8-9", "a-b", "c-d", "e-f"}},
+		{4, []string{
+			"0", "1", "2", "3", "4", "5", "6", "7",
+			"8", "9", "a", "b", "c", "d", "e", "f",
+		}},
+		{5, []string{
+			"00-07", "08-0f", "10-17", "18-1f", "20-27", "28-2f", "30-37", "38-3f",
+			"40-47", "48-4f", "50-57", "58-5f", "60-67", "68-6f", "70-77", "78-7f",
+			"80-87", "88-8f", "90-97", "98-9f", "a0-a7", "a8-af", "b0-b7", "b8-bf",
+			"c0-c7", "c8-cf", "d0-d7", "d8-df", "e0-e7", "e8-ef", "f0-f7", "f8-ff",
+		}},
+	}
+	for i, tc := range tcs {
+		got := []string{}
+		hbs, err := NewHashBins("", tc.bitLen)
+		assert.NoError(t, err)
+		n := hbs.NumBins()
+		for i := uint64(0); i < n; i += 1 {
+			hb := hbs.GetBin(i)
+			got = append(got, hb.RoleName())
+		}
+		assert.Equalf(t, tc.roleNames, got, "test case %v", i)
+	}
+
+	_, err := NewHashBins("", 0)
+	assert.Error(t, err)
+	_, err = NewHashBins("", 33)
+	assert.Error(t, err)
+}