diff --git a/ssh/certs.go b/ssh/certs.go
index 916c840..6605bf6 100644
--- a/ssh/certs.go
+++ b/ssh/certs.go
@@ -14,7 +14,7 @@
 	"time"
 )
 
-// These constants from [PROTOCOL.certkeys] represent the algorithm names
+// These constants from [PROTOCOL.certkeys] represent the key algorithm names
 // for certificate types supported by this package.
 const (
 	CertAlgoRSAv01        = "ssh-rsa-cert-v01@openssh.com"
@@ -27,6 +27,14 @@
 	CertAlgoSKED25519v01  = "sk-ssh-ed25519-cert-v01@openssh.com"
 )
 
+// These constants from [PROTOCOL.certkeys] represent additional signature
+// algorithm names for certificate types supported by this package.
+const (
+	CertSigAlgoRSAv01        = "ssh-rsa-cert-v01@openssh.com"
+	CertSigAlgoRSASHA2256v01 = "rsa-sha2-256-cert-v01@openssh.com"
+	CertSigAlgoRSASHA2512v01 = "rsa-sha2-512-cert-v01@openssh.com"
+)
+
 // Certificate types distinguish between host and user
 // certificates. The values can be set in the CertType field of
 // Certificate.
@@ -423,6 +431,12 @@
 	}
 	c.SignatureKey = authority.PublicKey()
 
+	if v, ok := authority.(AlgorithmSigner); ok {
+		if v.PublicKey().Type() == KeyAlgoRSA {
+			authority = &rsaSigner{v, SigAlgoRSASHA2512}
+		}
+	}
+
 	sig, err := authority.Sign(rand, c.bytesForSigning())
 	if err != nil {
 		return err
@@ -431,8 +445,14 @@
 	return nil
 }
 
+// certAlgoNames includes a mapping from signature algorithms to the
+// corresponding certificate signature algorithm. When a key type (such
+// as ED25516) is associated with only one algorithm, the KeyAlgo
+// constant is used instead of the SigAlgo.
 var certAlgoNames = map[string]string{
-	KeyAlgoRSA:        CertAlgoRSAv01,
+	SigAlgoRSA:        CertSigAlgoRSAv01,
+	SigAlgoRSASHA2256: CertSigAlgoRSASHA2256v01,
+	SigAlgoRSASHA2512: CertSigAlgoRSASHA2512v01,
 	KeyAlgoDSA:        CertAlgoDSAv01,
 	KeyAlgoECDSA256:   CertAlgoECDSA256v01,
 	KeyAlgoECDSA384:   CertAlgoECDSA384v01,
diff --git a/ssh/certs_test.go b/ssh/certs_test.go
index c8e7cf5..bae7f7e 100644
--- a/ssh/certs_test.go
+++ b/ssh/certs_test.go
@@ -9,12 +9,12 @@
 	"crypto/ecdsa"
 	"crypto/elliptic"
 	"crypto/rand"
+	"fmt"
+	"io"
 	"net"
 	"reflect"
 	"testing"
 	"time"
-
-	"golang.org/x/crypto/ssh/testdata"
 )
 
 // Cert generated by ssh-keygen 6.0p1 Debian-4.
@@ -226,53 +226,33 @@
 	}
 }
 
+type legacyRSASigner struct {
+	Signer
+}
+
+func (s *legacyRSASigner) Sign(rand io.Reader, data []byte) (*Signature, error) {
+	v, ok := s.Signer.(AlgorithmSigner)
+	if !ok {
+		return nil, fmt.Errorf("invalid signer")
+	}
+	return v.SignWithAlgorithm(rand, data, SigAlgoRSA)
+}
+
 func TestCertTypes(t *testing.T) {
 	var testVars = []struct {
-		name string
-		keys func() Signer
+		name   string
+		signer Signer
+		algo   string
 	}{
-		{
-			name: CertAlgoECDSA256v01,
-			keys: func() Signer {
-				s, _ := ParsePrivateKey(testdata.PEMBytes["ecdsap256"])
-				return s
-			},
-		},
-		{
-			name: CertAlgoECDSA384v01,
-			keys: func() Signer {
-				s, _ := ParsePrivateKey(testdata.PEMBytes["ecdsap384"])
-				return s
-			},
-		},
-		{
-			name: CertAlgoECDSA521v01,
-			keys: func() Signer {
-				s, _ := ParsePrivateKey(testdata.PEMBytes["ecdsap521"])
-				return s
-			},
-		},
-		{
-			name: CertAlgoED25519v01,
-			keys: func() Signer {
-				s, _ := ParsePrivateKey(testdata.PEMBytes["ed25519"])
-				return s
-			},
-		},
-		{
-			name: CertAlgoRSAv01,
-			keys: func() Signer {
-				s, _ := ParsePrivateKey(testdata.PEMBytes["rsa"])
-				return s
-			},
-		},
-		{
-			name: CertAlgoDSAv01,
-			keys: func() Signer {
-				s, _ := ParsePrivateKey(testdata.PEMBytes["dsa"])
-				return s
-			},
-		},
+		{CertAlgoECDSA256v01, testSigners["ecdsap256"], ""},
+		{CertAlgoECDSA384v01, testSigners["ecdsap384"], ""},
+		{CertAlgoECDSA521v01, testSigners["ecdsap521"], ""},
+		{CertAlgoED25519v01, testSigners["ed25519"], ""},
+		{CertAlgoRSAv01, testSigners["rsa"], SigAlgoRSASHA2512},
+		{CertAlgoRSAv01, &legacyRSASigner{testSigners["rsa"]}, SigAlgoRSA},
+		{CertAlgoRSAv01, testSigners["rsa-sha2-256"], SigAlgoRSASHA2512},
+		{CertAlgoRSAv01, testSigners["rsa-sha2-512"], SigAlgoRSASHA2512},
+		{CertAlgoDSAv01, testSigners["dsa"], ""},
 	}
 
 	k, err := ecdsa.GenerateKey(elliptic.P256(), rand.Reader)
@@ -304,7 +284,7 @@
 
 			go NewServerConn(c1, conf)
 
-			priv := m.keys()
+			priv := m.signer
 			if err != nil {
 				t.Fatalf("error generating ssh pubkey: %v", err)
 			}
@@ -320,6 +300,10 @@
 				t.Fatalf("error generating cert signer: %v", err)
 			}
 
+			if m.algo != "" && cert.Signature.Format != m.algo {
+				t.Errorf("expected %q signature format, got %q", m.algo, cert.Signature.Format)
+			}
+
 			config := &ClientConfig{
 				User:            "user",
 				HostKeyCallback: func(h string, r net.Addr, k PublicKey) error { return nil },
diff --git a/ssh/client.go b/ssh/client.go
index 99f68bd..ba8621a 100644
--- a/ssh/client.go
+++ b/ssh/client.go
@@ -115,12 +115,25 @@
 
 // verifyHostKeySignature verifies the host key obtained in the key
 // exchange.
-func verifyHostKeySignature(hostKey PublicKey, result *kexResult) error {
+func verifyHostKeySignature(hostKey PublicKey, algo string, result *kexResult) error {
 	sig, rest, ok := parseSignatureBody(result.Signature)
 	if len(rest) > 0 || !ok {
 		return errors.New("ssh: signature parse error")
 	}
 
+	// For keys, underlyingAlgo is exactly algo. For certificates,
+	// we have to look up the underlying key algorithm that SSH
+	// uses to evaluate signatures.
+	underlyingAlgo := algo
+	for sigAlgo, certAlgo := range certAlgoNames {
+		if certAlgo == algo {
+			underlyingAlgo = sigAlgo
+		}
+	}
+	if sig.Format != underlyingAlgo {
+		return fmt.Errorf("ssh: invalid signature algorithm %q, expected %q", sig.Format, underlyingAlgo)
+	}
+
 	return hostKey.Verify(result.H, sig)
 }
 
diff --git a/ssh/client_test.go b/ssh/client_test.go
index 6aaa003..3063433 100644
--- a/ssh/client_test.go
+++ b/ssh/client_test.go
@@ -5,6 +5,8 @@
 package ssh
 
 import (
+	"bytes"
+	"crypto/rand"
 	"strings"
 	"testing"
 )
@@ -116,6 +118,45 @@
 	}
 }
 
+func TestVerifyHostKeySignature(t *testing.T) {
+	for _, tt := range []struct {
+		key        string
+		signAlgo   string
+		verifyAlgo string
+		wantError  string
+	}{
+		{"rsa", SigAlgoRSA, SigAlgoRSA, ""},
+		{"rsa", SigAlgoRSASHA2256, SigAlgoRSASHA2256, ""},
+		{"rsa", SigAlgoRSA, SigAlgoRSASHA2512, `ssh: invalid signature algorithm "ssh-rsa", expected "rsa-sha2-512"`},
+		{"ed25519", KeyAlgoED25519, KeyAlgoED25519, ""},
+	} {
+		key := testSigners[tt.key].PublicKey()
+		s, ok := testSigners[tt.key].(AlgorithmSigner)
+		if !ok {
+			t.Fatalf("needed an AlgorithmSigner")
+		}
+		sig, err := s.SignWithAlgorithm(rand.Reader, []byte("test"), tt.signAlgo)
+		if err != nil {
+			t.Fatalf("couldn't sign: %q", err)
+		}
+
+		b := bytes.Buffer{}
+		writeString(&b, []byte(sig.Format))
+		writeString(&b, sig.Blob)
+
+		result := kexResult{Signature: b.Bytes(), H: []byte("test")}
+
+		err = verifyHostKeySignature(key, tt.verifyAlgo, &result)
+		if err != nil {
+			if tt.wantError == "" || !strings.Contains(err.Error(), tt.wantError) {
+				t.Errorf("got error %q, expecting %q", err.Error(), tt.wantError)
+			}
+		} else if tt.wantError != "" {
+			t.Errorf("succeeded, but want error string %q", tt.wantError)
+		}
+	}
+}
+
 func TestBannerCallback(t *testing.T) {
 	c1, c2, err := netPipe()
 	if err != nil {
diff --git a/ssh/common.go b/ssh/common.go
index 290382d..5ae2275 100644
--- a/ssh/common.go
+++ b/ssh/common.go
@@ -69,11 +69,13 @@
 // supportedHostKeyAlgos specifies the supported host-key algorithms (i.e. methods
 // of authenticating servers) in preference order.
 var supportedHostKeyAlgos = []string{
-	CertAlgoRSAv01, CertAlgoDSAv01, CertAlgoECDSA256v01,
+	CertSigAlgoRSASHA2512v01, CertSigAlgoRSASHA2256v01,
+	CertSigAlgoRSAv01, CertAlgoDSAv01, CertAlgoECDSA256v01,
 	CertAlgoECDSA384v01, CertAlgoECDSA521v01, CertAlgoED25519v01,
 
 	KeyAlgoECDSA256, KeyAlgoECDSA384, KeyAlgoECDSA521,
-	KeyAlgoRSA, KeyAlgoDSA,
+	SigAlgoRSASHA2512, SigAlgoRSASHA2256,
+	SigAlgoRSA, KeyAlgoDSA,
 
 	KeyAlgoED25519,
 }
@@ -90,16 +92,20 @@
 // hashFuncs keeps the mapping of supported algorithms to their respective
 // hashes needed for signature verification.
 var hashFuncs = map[string]crypto.Hash{
-	KeyAlgoRSA:          crypto.SHA1,
-	KeyAlgoDSA:          crypto.SHA1,
-	KeyAlgoECDSA256:     crypto.SHA256,
-	KeyAlgoECDSA384:     crypto.SHA384,
-	KeyAlgoECDSA521:     crypto.SHA512,
-	CertAlgoRSAv01:      crypto.SHA1,
-	CertAlgoDSAv01:      crypto.SHA1,
-	CertAlgoECDSA256v01: crypto.SHA256,
-	CertAlgoECDSA384v01: crypto.SHA384,
-	CertAlgoECDSA521v01: crypto.SHA512,
+	SigAlgoRSA:               crypto.SHA1,
+	SigAlgoRSASHA2256:        crypto.SHA256,
+	SigAlgoRSASHA2512:        crypto.SHA512,
+	KeyAlgoDSA:               crypto.SHA1,
+	KeyAlgoECDSA256:          crypto.SHA256,
+	KeyAlgoECDSA384:          crypto.SHA384,
+	KeyAlgoECDSA521:          crypto.SHA512,
+	CertSigAlgoRSAv01:        crypto.SHA1,
+	CertSigAlgoRSASHA2256v01: crypto.SHA256,
+	CertSigAlgoRSASHA2512v01: crypto.SHA512,
+	CertAlgoDSAv01:           crypto.SHA1,
+	CertAlgoECDSA256v01:      crypto.SHA256,
+	CertAlgoECDSA384v01:      crypto.SHA384,
+	CertAlgoECDSA521v01:      crypto.SHA512,
 }
 
 // unexpectedMessageError results when the SSH message that we received didn't
diff --git a/ssh/handshake.go b/ssh/handshake.go
index 2b10b05..05ad49c 100644
--- a/ssh/handshake.go
+++ b/ssh/handshake.go
@@ -457,8 +457,15 @@
 
 	if len(t.hostKeys) > 0 {
 		for _, k := range t.hostKeys {
-			msg.ServerHostKeyAlgos = append(
-				msg.ServerHostKeyAlgos, k.PublicKey().Type())
+			algo := k.PublicKey().Type()
+			switch algo {
+			case KeyAlgoRSA:
+				msg.ServerHostKeyAlgos = append(msg.ServerHostKeyAlgos, []string{SigAlgoRSASHA2512, SigAlgoRSASHA2256, SigAlgoRSA}...)
+			case CertAlgoRSAv01:
+				msg.ServerHostKeyAlgos = append(msg.ServerHostKeyAlgos, []string{CertSigAlgoRSASHA2512v01, CertSigAlgoRSASHA2256v01, CertSigAlgoRSAv01}...)
+			default:
+				msg.ServerHostKeyAlgos = append(msg.ServerHostKeyAlgos, algo)
+			}
 		}
 	} else {
 		msg.ServerHostKeyAlgos = t.hostKeyAlgorithms
@@ -614,8 +621,22 @@
 func (t *handshakeTransport) server(kex kexAlgorithm, algs *algorithms, magics *handshakeMagics) (*kexResult, error) {
 	var hostKey Signer
 	for _, k := range t.hostKeys {
-		if algs.hostKey == k.PublicKey().Type() {
+		kt := k.PublicKey().Type()
+		if kt == algs.hostKey {
 			hostKey = k
+		} else if signer, ok := k.(AlgorithmSigner); ok {
+			// Some signature algorithms don't show up as key types
+			// so we have to manually check for a compatible host key.
+			switch kt {
+			case KeyAlgoRSA:
+				if algs.hostKey == SigAlgoRSASHA2256 || algs.hostKey == SigAlgoRSASHA2512 {
+					hostKey = &rsaSigner{signer, algs.hostKey}
+				}
+			case CertAlgoRSAv01:
+				if algs.hostKey == CertSigAlgoRSASHA2256v01 || algs.hostKey == CertSigAlgoRSASHA2512v01 {
+					hostKey = &rsaSigner{signer, certToPrivAlgo(algs.hostKey)}
+				}
+			}
 		}
 	}
 
@@ -634,7 +655,7 @@
 		return nil, err
 	}
 
-	if err := verifyHostKeySignature(hostKey, result); err != nil {
+	if err := verifyHostKeySignature(hostKey, algs.hostKey, result); err != nil {
 		return nil, err
 	}
 
diff --git a/ssh/keys.go b/ssh/keys.go
index 31f2634..c67d3a3 100644
--- a/ssh/keys.go
+++ b/ssh/keys.go
@@ -939,6 +939,15 @@
 	return &dsaPrivateKey{key}, nil
 }
 
+type rsaSigner struct {
+	AlgorithmSigner
+	defaultAlgorithm string
+}
+
+func (s *rsaSigner) Sign(rand io.Reader, data []byte) (*Signature, error) {
+	return s.AlgorithmSigner.SignWithAlgorithm(rand, data, s.defaultAlgorithm)
+}
+
 type wrappedSigner struct {
 	signer crypto.Signer
 	pubKey PublicKey
diff --git a/ssh/server.go b/ssh/server.go
index b6911e8..6a58e12 100644
--- a/ssh/server.go
+++ b/ssh/server.go
@@ -284,7 +284,7 @@
 
 func isAcceptableAlgo(algo string) bool {
 	switch algo {
-	case KeyAlgoRSA, KeyAlgoDSA, KeyAlgoECDSA256, KeyAlgoECDSA384, KeyAlgoECDSA521, KeyAlgoSKECDSA256, KeyAlgoED25519, KeyAlgoSKED25519,
+	case SigAlgoRSA, SigAlgoRSASHA2256, SigAlgoRSASHA2512, KeyAlgoDSA, KeyAlgoECDSA256, KeyAlgoECDSA384, KeyAlgoECDSA521, KeyAlgoSKECDSA256, KeyAlgoED25519, KeyAlgoSKED25519,
 		CertAlgoRSAv01, CertAlgoDSAv01, CertAlgoECDSA256v01, CertAlgoECDSA384v01, CertAlgoECDSA521v01, CertAlgoSKECDSA256v01, CertAlgoED25519v01, CertAlgoSKED25519v01:
 		return true
 	}
diff --git a/ssh/session_test.go b/ssh/session_test.go
index 39853bf..fbec952 100644
--- a/ssh/session_test.go
+++ b/ssh/session_test.go
@@ -757,7 +757,13 @@
 	connect(clientConf, KeyAlgoECDSA256)
 
 	// Client asks for RSA explicitly.
-	clientConf.HostKeyAlgorithms = []string{KeyAlgoRSA}
+	clientConf.HostKeyAlgorithms = []string{SigAlgoRSA}
+	connect(clientConf, KeyAlgoRSA)
+
+	// Client asks for RSA-SHA2-512 explicitly.
+	clientConf.HostKeyAlgorithms = []string{SigAlgoRSASHA2512}
+	// We get back an "ssh-rsa" key but the verification happened
+	// with an RSA-SHA2-512 signature.
 	connect(clientConf, KeyAlgoRSA)
 
 	c1, c2, err := netPipe()
diff --git a/ssh/test/test_unix_test.go b/ssh/test/test_unix_test.go
index dbd02c7..804163c 100644
--- a/ssh/test/test_unix_test.go
+++ b/ssh/test/test_unix_test.go
@@ -35,7 +35,7 @@
 HostKey {{.Dir}}/id_rsa
 HostKey {{.Dir}}/id_dsa
 HostKey {{.Dir}}/id_ecdsa
-HostCertificate {{.Dir}}/id_rsa-cert.pub
+HostCertificate {{.Dir}}/id_rsa-sha2-512-cert.pub
 Pidfile {{.Dir}}/sshd.pid
 #UsePrivilegeSeparation no
 KeyRegenerationInterval 3600
diff --git a/ssh/testdata/keys.go b/ssh/testdata/keys.go
index f1e2fc5..4f2f3a4 100644
--- a/ssh/testdata/keys.go
+++ b/ssh/testdata/keys.go
@@ -61,6 +61,38 @@
 KCXFGd+SQ5GdUcEMe9isUH6DYj/6/yCDoFrXXmpQb+M=
 -----END RSA PRIVATE KEY-----
 `),
+	"rsa-sha2-256": []byte(`-----BEGIN RSA PRIVATE KEY-----
+MIICXAIBAAKBgQC8A6FGHDiWCSREAXCq6yBfNVr0xCVG2CzvktFNRpue+RXrGs/2
+a6ySEJQb3IYquw7HlJgu6fg3WIWhOmHCjfpG0PrL4CRwbqQ2LaPPXhJErWYejcD8
+Di00cF3677+G10KMZk9RXbmHtuBFZT98wxg8j+ZsBMqGM1+7yrWUvynswQIDAQAB
+AoGAJMCk5vqfSRzyXOTXLGIYCuR4Kj6pdsbNSeuuRGfYBeR1F2c/XdFAg7D/8s5R
+38p/Ih52/Ty5S8BfJtwtvgVY9ecf/JlU/rl/QzhG8/8KC0NG7KsyXklbQ7gJT8UT
+Ojmw5QpMk+rKv17ipDVkQQmPaj+gJXYNAHqImke5mm/K/h0CQQDciPmviQ+DOhOq
+2ZBqUfH8oXHgFmp7/6pXw80DpMIxgV3CwkxxIVx6a8lVH9bT/AFySJ6vXq4zTuV9
+6QmZcZzDAkEA2j/UXJPIs1fQ8z/6sONOkU/BjtoePFIWJlRxdN35cZjXnBraX5UR
+fFHkePv4YwqmXNqrBOvSu+w2WdSDci+IKwJAcsPRc/jWmsrJW1q3Ha0hSf/WG/Bu
+X7MPuXaKpP/DkzGoUmb8ks7yqj6XWnYkPNLjCc8izU5vRwIiyWBRf4mxMwJBAILa
+NDvRS0rjwt6lJGv7zPZoqDc65VfrK2aNyHx2PgFyzwrEOtuF57bu7pnvEIxpLTeM
+z26i6XVMeYXAWZMTloMCQBbpGgEERQpeUknLBqUHhg/wXF6+lFA+vEGnkY+Dwab2
+KCXFGd+SQ5GdUcEMe9isUH6DYj/6/yCDoFrXXmpQb+M=
+-----END RSA PRIVATE KEY-----
+`),
+	"rsa-sha2-512": []byte(`-----BEGIN RSA PRIVATE KEY-----
+MIICXAIBAAKBgQC8A6FGHDiWCSREAXCq6yBfNVr0xCVG2CzvktFNRpue+RXrGs/2
+a6ySEJQb3IYquw7HlJgu6fg3WIWhOmHCjfpG0PrL4CRwbqQ2LaPPXhJErWYejcD8
+Di00cF3677+G10KMZk9RXbmHtuBFZT98wxg8j+ZsBMqGM1+7yrWUvynswQIDAQAB
+AoGAJMCk5vqfSRzyXOTXLGIYCuR4Kj6pdsbNSeuuRGfYBeR1F2c/XdFAg7D/8s5R
+38p/Ih52/Ty5S8BfJtwtvgVY9ecf/JlU/rl/QzhG8/8KC0NG7KsyXklbQ7gJT8UT
+Ojmw5QpMk+rKv17ipDVkQQmPaj+gJXYNAHqImke5mm/K/h0CQQDciPmviQ+DOhOq
+2ZBqUfH8oXHgFmp7/6pXw80DpMIxgV3CwkxxIVx6a8lVH9bT/AFySJ6vXq4zTuV9
+6QmZcZzDAkEA2j/UXJPIs1fQ8z/6sONOkU/BjtoePFIWJlRxdN35cZjXnBraX5UR
+fFHkePv4YwqmXNqrBOvSu+w2WdSDci+IKwJAcsPRc/jWmsrJW1q3Ha0hSf/WG/Bu
+X7MPuXaKpP/DkzGoUmb8ks7yqj6XWnYkPNLjCc8izU5vRwIiyWBRf4mxMwJBAILa
+NDvRS0rjwt6lJGv7zPZoqDc65VfrK2aNyHx2PgFyzwrEOtuF57bu7pnvEIxpLTeM
+z26i6XVMeYXAWZMTloMCQBbpGgEERQpeUknLBqUHhg/wXF6+lFA+vEGnkY+Dwab2
+KCXFGd+SQ5GdUcEMe9isUH6DYj/6/yCDoFrXXmpQb+M=
+-----END RSA PRIVATE KEY-----
+`),
 	"pkcs8": []byte(`-----BEGIN PRIVATE KEY-----
 MIIEvgIBADANBgkqhkiG9w0BAQEFAASCBKgwggSkAgEAAoIBAQCitzS2KiRQTccf
 VApb0mbPpo1lt29JjeLBYAehXHWfQ+w8sXpd8e04n/020spx1R94yg+v0NjXyh2R
@@ -192,6 +224,10 @@
 	//    ssh-keygen -s ca -h -n host.example.com -V +500w -I host.example.com-key rsa.pub
 	"rsa": []byte(`ssh-rsa-cert-v01@openssh.com AAAAHHNzaC1yc2EtY2VydC12MDFAb3BlbnNzaC5jb20AAAAgLjYqmmuTSEmjVhSfLQphBSTJMLwIZhRgmpn8FHKLiEIAAAADAQABAAAAgQC8A6FGHDiWCSREAXCq6yBfNVr0xCVG2CzvktFNRpue+RXrGs/2a6ySEJQb3IYquw7HlJgu6fg3WIWhOmHCjfpG0PrL4CRwbqQ2LaPPXhJErWYejcD8Di00cF3677+G10KMZk9RXbmHtuBFZT98wxg8j+ZsBMqGM1+7yrWUvynswQAAAAAAAAAAAAAAAgAAABRob3N0LmV4YW1wbGUuY29tLWtleQAAABQAAAAQaG9zdC5leGFtcGxlLmNvbQAAAABZHN8UAAAAAGsjIYUAAAAAAAAAAAAAAAAAAAEXAAAAB3NzaC1yc2EAAAADAQABAAABAQC+D11D0hEbn2Vglv4YRJ8pZNyHjIGmvth3DWOQrq++2vH2MujmGQDxfr4SVE9GpMBlKU3lwGbpgIBxAg6yZcNSfo6PWVU9ACg6NMFO+yMzc2MaG+/naQdNjSewywF5j2rkNO2XOaViRVSrZroe2B/aY2LTV0jDl8nu5NOjwRs1/s7SLe5z1rw/X0dpmXk0qJY3gQhmR8HZZ1dhEkJUGwaBCPd0T8asSYf1Ag2rUD4aQ28r3q69mbwfWOOa6rMemVZruUV5dzHwVNVNtVv+ImtnYtz8m8g+K0plaGptHn3KsaOnASkh3tujhaE7kvc4HR9Igli9+76jhZie3h/dTN5zAAABDwAAAAdzc2gtcnNhAAABALeDea+60H6xJGhktAyosHaSY7AYzLocaqd8hJQjEIDifBwzoTlnBmcK9CxGhKuaoJFThdCLdaevCeOSuquh8HTkf+2ebZZc/G5T+2thPvPqmcuEcmMosWo+SIjYhbP3S6KD49aLC1X0kz8IBQeauFvURhkZ5ZjhA1L4aQYt9NjL73nqOl8PplRui+Ov5w8b4ldul4zOvYAFrzfcP6wnnXk3c1Zzwwf5wynD5jakO8GpYKBuhM7Z4crzkKSQjU3hla7xqgfomC5Gz4XbR2TNjcQiRrJQ0UlKtX3X3ObRCEhuvG0Kzjklhv+Ddw6txrhKjMjiSi/Yyius/AE8TmC1p4U= host.example.com
 `),
+	"rsa-sha2-256": []byte(`ssh-rsa-cert-v01@openssh.com AAAAHHNzaC1yc2EtY2VydC12MDFAb3BlbnNzaC5jb20AAAAgOyK28gunJkM60qp4EbsYAjgbUsyjS8u742OLjipIgc0AAAADAQABAAAAgQC8A6FGHDiWCSREAXCq6yBfNVr0xCVG2CzvktFNRpue+RXrGs/2a6ySEJQb3IYquw7HlJgu6fg3WIWhOmHCjfpG0PrL4CRwbqQ2LaPPXhJErWYejcD8Di00cF3677+G10KMZk9RXbmHtuBFZT98wxg8j+ZsBMqGM1+7yrWUvynswQAAAAAAAAAAAAAAAgAAABRob3N0LmV4YW1wbGUuY29tLWtleQAAABQAAAAQaG9zdC5leGFtcGxlLmNvbQAAAABeSMJ4AAAAAHBPBLwAAAAAAAAAAAAAAAAAAAEXAAAAB3NzaC1yc2EAAAADAQABAAABAQC+D11D0hEbn2Vglv4YRJ8pZNyHjIGmvth3DWOQrq++2vH2MujmGQDxfr4SVE9GpMBlKU3lwGbpgIBxAg6yZcNSfo6PWVU9ACg6NMFO+yMzc2MaG+/naQdNjSewywF5j2rkNO2XOaViRVSrZroe2B/aY2LTV0jDl8nu5NOjwRs1/s7SLe5z1rw/X0dpmXk0qJY3gQhmR8HZZ1dhEkJUGwaBCPd0T8asSYf1Ag2rUD4aQ28r3q69mbwfWOOa6rMemVZruUV5dzHwVNVNtVv+ImtnYtz8m8g+K0plaGptHn3KsaOnASkh3tujhaE7kvc4HR9Igli9+76jhZie3h/dTN5zAAABFAAAAAxyc2Etc2hhMi0yNTYAAAEAbG4De/+QiqopPS3O1H7ySeEUCY56qmdgr02sFErnihdXPDaWXUXxacvJHaEtLrSTSaPL/3v3iKvjLWDOHaQ5c+cN9J7Tqzso7RQCXZD2nK9bwCUyBoiDyBCRe8w4DQEtfL5okpVzQsSAiojQ8hBohMOpy3gFfXrdm4PVC1ZKqlZh4fAc7ajieRq/Tpq2xOLdHwxkcgPNR83WVHva6K9/xjev/5n227/gkHo0qbGs8YYDOFXIEhENi+B23IzxdNVieWdyQpYpe0C2i95Jhyo0wJmaFY2ArruTS+D1jGQQpMPvAQRy26/A5hI83GLhpwyhrN/M8wCxzAhyPL6Ieuh5tQ== host.example.com
+`),
+       "rsa-sha2-512": []byte(`ssh-rsa-cert-v01@openssh.com AAAAHHNzaC1yc2EtY2VydC12MDFAb3BlbnNzaC5jb20AAAAgFGv4IpXfs4L/Y0b3rmUdPFhWoUrVnXuPxXr6aHGs7wgAAAADAQABAAAAgQC8A6FGHDiWCSREAXCq6yBfNVr0xCVG2CzvktFNRpue+RXrGs/2a6ySEJQb3IYquw7HlJgu6fg3WIWhOmHCjfpG0PrL4CRwbqQ2LaPPXhJErWYejcD8Di00cF3677+G10KMZk9RXbmHtuBFZT98wxg8j+ZsBMqGM1+7yrWUvynswQAAAAAAAAAAAAAAAgAAABRob3N0LmV4YW1wbGUuY29tLWtleQAAABQAAAAQaG9zdC5leGFtcGxlLmNvbQAAAABeSMRYAAAAAHBPBp4AAAAAAAAAAAAAAAAAAAEXAAAAB3NzaC1yc2EAAAADAQABAAABAQC+D11D0hEbn2Vglv4YRJ8pZNyHjIGmvth3DWOQrq++2vH2MujmGQDxfr4SVE9GpMBlKU3lwGbpgIBxAg6yZcNSfo6PWVU9ACg6NMFO+yMzc2MaG+/naQdNjSewywF5j2rkNO2XOaViRVSrZroe2B/aY2LTV0jDl8nu5NOjwRs1/s7SLe5z1rw/X0dpmXk0qJY3gQhmR8HZZ1dhEkJUGwaBCPd0T8asSYf1Ag2rUD4aQ28r3q69mbwfWOOa6rMemVZruUV5dzHwVNVNtVv+ImtnYtz8m8g+K0plaGptHn3KsaOnASkh3tujhaE7kvc4HR9Igli9+76jhZie3h/dTN5zAAABFAAAAAxyc2Etc2hhMi01MTIAAAEAnF4fVj6mm+UFeNCIf9AKJCv9WzymjjPvzzmaMWWkPWqoV0P0m5SiYfvbY9SbA73Blpv8SOr0DmpublF183kodREia4KyVuC8hLhSCV2Y16hy9MBegOZMepn80w+apj7Rn9QCz5OfEakDdztp6OWTBtqxnZFcTQ4XrgFkNWeWRElGdEvAVNn2WHwHi4EIdz0mdv48Imv5SPlOuW862ZdFG4Do1dUfDIiGsBofLlgcyIYlf+eNHul6sBeUkuwFxisMpI5DQzNp8PX1g/QJA2wzwT674PTqDXNttKjyh50Fdr4sXxm9Gz1+jVLoESvFNa55ERdSyAqNu4wTy11MZsWwSA== host.example.com
+`),
 }
 
 var PEMEncryptedKeys = []struct {
diff --git a/ssh/testdata_test.go b/ssh/testdata_test.go
index 2da8c79..83aa51b 100644
--- a/ssh/testdata_test.go
+++ b/ssh/testdata_test.go
@@ -34,6 +34,14 @@
 			panic(fmt.Sprintf("Unable to parse test key %s: %v", t, err))
 		}
 		testSigners[t], err = NewSignerFromKey(testPrivateKeys[t])
+		if v, ok := testSigners[t].(*rsaSigner); ok {
+			switch t {
+			case "rsa-sha2-256":
+				testSigners[t] = &rsaSigner{v, SigAlgoRSASHA2256}
+			case "rsa-sha2-512":
+				testSigners[t] = &rsaSigner{v, SigAlgoRSASHA2512}
+			}
+		}
 		if err != nil {
 			panic(fmt.Sprintf("Unable to create signer for test key %s: %v", t, err))
 		}