diff --git a/ssh/certs.go b/ssh/certs.go
index 17d4f6e..c7a4dd0 100644
--- a/ssh/certs.go
+++ b/ssh/certs.go
@@ -440,10 +440,14 @@
 	}
 	c.SignatureKey = authority.PublicKey()
 
-	if v, ok := authority.(AlgorithmSigner); ok {
-		if v.PublicKey().Type() == KeyAlgoRSA {
-			authority = &rsaSigner{v, KeyAlgoRSASHA512}
+	// Default to KeyAlgoRSASHA512 for ssh-rsa signers.
+	if v, ok := authority.(AlgorithmSigner); ok && v.PublicKey().Type() == KeyAlgoRSA {
+		sig, err := v.SignWithAlgorithm(rand, c.bytesForSigning(), KeyAlgoRSASHA512)
+		if err != nil {
+			return err
 		}
+		c.Signature = sig
+		return nil
 	}
 
 	sig, err := authority.Sign(rand, c.bytesForSigning())
@@ -454,30 +458,29 @@
 	return nil
 }
 
-// certAlgoNames includes a mapping from signature algorithms to the
-// corresponding certificate signature algorithm.
-var certAlgoNames = map[string]string{
-	KeyAlgoRSA:        CertAlgoRSAv01,
-	KeyAlgoRSASHA256:  CertAlgoRSASHA256v01,
-	KeyAlgoRSASHA512:  CertAlgoRSASHA512v01,
-	KeyAlgoDSA:        CertAlgoDSAv01,
-	KeyAlgoECDSA256:   CertAlgoECDSA256v01,
-	KeyAlgoECDSA384:   CertAlgoECDSA384v01,
-	KeyAlgoECDSA521:   CertAlgoECDSA521v01,
-	KeyAlgoSKECDSA256: CertAlgoSKECDSA256v01,
-	KeyAlgoED25519:    CertAlgoED25519v01,
-	KeyAlgoSKED25519:  CertAlgoSKED25519v01,
+// certKeyAlgoNames is a mapping from known certificate algorithm names to the
+// corresponding public key signature algorithm.
+var certKeyAlgoNames = map[string]string{
+	CertAlgoRSAv01:        KeyAlgoRSA,
+	CertAlgoRSASHA256v01:  KeyAlgoRSASHA256,
+	CertAlgoRSASHA512v01:  KeyAlgoRSASHA512,
+	CertAlgoDSAv01:        KeyAlgoDSA,
+	CertAlgoECDSA256v01:   KeyAlgoECDSA256,
+	CertAlgoECDSA384v01:   KeyAlgoECDSA384,
+	CertAlgoECDSA521v01:   KeyAlgoECDSA521,
+	CertAlgoSKECDSA256v01: KeyAlgoSKECDSA256,
+	CertAlgoED25519v01:    KeyAlgoED25519,
+	CertAlgoSKED25519v01:  KeyAlgoSKED25519,
 }
 
-// certToPrivAlgo returns the underlying algorithm for a certificate algorithm.
-// Panics if a non-certificate algorithm is passed.
-func certToPrivAlgo(algo string) string {
-	for privAlgo, pubAlgo := range certAlgoNames {
-		if pubAlgo == algo {
-			return privAlgo
-		}
+// underlyingAlgo returns the signature algorithm associated with algo (which is
+// an advertised or negotiated public key or host key algorithm). These are
+// usually the same, except for certificate algorithms.
+func underlyingAlgo(algo string) string {
+	if a, ok := certKeyAlgoNames[algo]; ok {
+		return a
 	}
-	panic("unknown cert algorithm")
+	return algo
 }
 
 func (cert *Certificate) bytesForSigning() []byte {
@@ -523,11 +526,13 @@
 
 // Type returns the certificate algorithm name. It is part of the PublicKey interface.
 func (c *Certificate) Type() string {
-	algo, ok := certAlgoNames[c.Key.Type()]
-	if !ok {
-		panic("unknown cert key type " + c.Key.Type())
+	keyType := c.Key.Type()
+	for certName, keyName := range certKeyAlgoNames {
+		if keyName == keyType {
+			return certName
+		}
 	}
-	return algo
+	panic("unknown certificate type for key type " + keyType)
 }
 
 // Verify verifies a signature against the certificate's public
diff --git a/ssh/certs_test.go b/ssh/certs_test.go
index 12c1afd..ba6dbca 100644
--- a/ssh/certs_test.go
+++ b/ssh/certs_test.go
@@ -216,12 +216,12 @@
 		_, _, _, err = NewClientConn(c2, test.addr, config)
 
 		if (err == nil) != test.succeed {
-			t.Fatalf("NewClientConn(%q): %v", test.addr, err)
+			t.Errorf("NewClientConn(%q): %v", test.addr, err)
 		}
 
 		err = <-errc
 		if (err == nil) != test.succeed {
-			t.Fatalf("NewServerConn(%q): %v", test.addr, err)
+			t.Errorf("NewServerConn(%q): %v", test.addr, err)
 		}
 	}
 }
@@ -249,9 +249,7 @@
 		{CertAlgoECDSA521v01, testSigners["ecdsap521"], ""},
 		{CertAlgoED25519v01, testSigners["ed25519"], ""},
 		{CertAlgoRSAv01, testSigners["rsa"], KeyAlgoRSASHA512},
-		{CertAlgoRSAv01, &legacyRSASigner{testSigners["rsa"]}, KeyAlgoRSA},
-		{CertAlgoRSAv01, testSigners["rsa-sha2-256"], KeyAlgoRSASHA512},
-		{CertAlgoRSAv01, testSigners["rsa-sha2-512"], KeyAlgoRSASHA512},
+		{"legacyRSASigner", &legacyRSASigner{testSigners["rsa"]}, KeyAlgoRSA},
 		{CertAlgoDSAv01, testSigners["dsa"], ""},
 	}
 
diff --git a/ssh/client.go b/ssh/client.go
index 43fbe25..bdc356c 100644
--- a/ssh/client.go
+++ b/ssh/client.go
@@ -113,25 +113,16 @@
 	return c.clientAuthenticate(config)
 }
 
-// verifyHostKeySignature verifies the host key obtained in the key
-// exchange.
+// verifyHostKeySignature verifies the host key obtained in the key exchange.
+// algo is the negotiated algorithm, and may be a certificate type.
 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)
+	if a := underlyingAlgo(algo); sig.Format != a {
+		return fmt.Errorf("ssh: invalid signature algorithm %q, expected %q", sig.Format, a)
 	}
 
 	return hostKey.Verify(result.H, sig)
diff --git a/ssh/common.go b/ssh/common.go
index 768641f..d6d9bf9 100644
--- a/ssh/common.go
+++ b/ssh/common.go
@@ -89,23 +89,33 @@
 
 var supportedCompressions = []string{compressionNone}
 
-// hashFuncs keeps the mapping of supported algorithms to their respective
-// hashes needed for signature verification.
+// hashFuncs keeps the mapping of supported signature algorithms to their
+// respective hashes needed for signing and verification.
 var hashFuncs = map[string]crypto.Hash{
-	KeyAlgoRSA:           crypto.SHA1,
-	KeyAlgoRSASHA256:     crypto.SHA256,
-	KeyAlgoRSASHA512:     crypto.SHA512,
-	KeyAlgoDSA:           crypto.SHA1,
-	KeyAlgoECDSA256:      crypto.SHA256,
-	KeyAlgoECDSA384:      crypto.SHA384,
-	KeyAlgoECDSA521:      crypto.SHA512,
-	CertAlgoRSAv01:       crypto.SHA1,
-	CertAlgoRSASHA256v01: crypto.SHA256,
-	CertAlgoRSASHA512v01: crypto.SHA512,
-	CertAlgoDSAv01:       crypto.SHA1,
-	CertAlgoECDSA256v01:  crypto.SHA256,
-	CertAlgoECDSA384v01:  crypto.SHA384,
-	CertAlgoECDSA521v01:  crypto.SHA512,
+	KeyAlgoRSA:       crypto.SHA1,
+	KeyAlgoRSASHA256: crypto.SHA256,
+	KeyAlgoRSASHA512: crypto.SHA512,
+	KeyAlgoDSA:       crypto.SHA1,
+	KeyAlgoECDSA256:  crypto.SHA256,
+	KeyAlgoECDSA384:  crypto.SHA384,
+	KeyAlgoECDSA521:  crypto.SHA512,
+	// KeyAlgoED25519 doesn't pre-hash.
+	KeyAlgoSKECDSA256: crypto.SHA256,
+	KeyAlgoSKED25519:  crypto.SHA256,
+}
+
+// algorithmsForKeyFormat returns the supported signature algorithms for a given
+// public key format (PublicKey.Type), in order of preference. See RFC 8332,
+// Section 2. See also the note in sendKexInit on backwards compatibility.
+func algorithmsForKeyFormat(keyFormat string) []string {
+	switch keyFormat {
+	case KeyAlgoRSA:
+		return []string{KeyAlgoRSASHA256, KeyAlgoRSASHA512, KeyAlgoRSA}
+	case CertAlgoRSAv01:
+		return []string{CertAlgoRSASHA256v01, CertAlgoRSASHA512v01, CertAlgoRSAv01}
+	default:
+		return []string{keyFormat}
+	}
 }
 
 // unexpectedMessageError results when the SSH message that we received didn't
diff --git a/ssh/handshake.go b/ssh/handshake.go
index 5eeddb3..4bceb33 100644
--- a/ssh/handshake.go
+++ b/ssh/handshake.go
@@ -455,21 +455,29 @@
 	}
 	io.ReadFull(rand.Reader, msg.Cookie[:])
 
-	if len(t.hostKeys) > 0 {
+	isServer := len(t.hostKeys) > 0
+	if isServer {
 		for _, k := range t.hostKeys {
-			algo := k.PublicKey().Type()
-			switch algo {
-			case KeyAlgoRSA:
-				msg.ServerHostKeyAlgos = append(msg.ServerHostKeyAlgos, []string{KeyAlgoRSASHA512, KeyAlgoRSASHA256, KeyAlgoRSA}...)
-			case CertAlgoRSAv01:
-				msg.ServerHostKeyAlgos = append(msg.ServerHostKeyAlgos, []string{CertAlgoRSASHA512v01, CertAlgoRSASHA256v01, CertAlgoRSAv01}...)
-			default:
-				msg.ServerHostKeyAlgos = append(msg.ServerHostKeyAlgos, algo)
+			// If k is an AlgorithmSigner, presume it supports all signature algorithms
+			// associated with the key format. (Ideally AlgorithmSigner would have a
+			// method to advertise supported algorithms, but it doesn't. This means that
+			// adding support for a new algorithm is a breaking change, as we will
+			// immediately negotiate it even if existing implementations don't support
+			// it. If that ever happens, we'll have to figure something out.)
+			// If k is not an AlgorithmSigner, we can only assume it only supports the
+			// algorithms that matches the key format. (This means that Sign can't pick
+			// a different default.)
+			keyFormat := k.PublicKey().Type()
+			if _, ok := k.(AlgorithmSigner); ok {
+				msg.ServerHostKeyAlgos = append(msg.ServerHostKeyAlgos, algorithmsForKeyFormat(keyFormat)...)
+			} else {
+				msg.ServerHostKeyAlgos = append(msg.ServerHostKeyAlgos, keyFormat)
 			}
 		}
 	} else {
 		msg.ServerHostKeyAlgos = t.hostKeyAlgorithms
 	}
+
 	packet := Marshal(msg)
 
 	// writePacket destroys the contents, so save a copy.
@@ -589,9 +597,9 @@
 
 	var result *kexResult
 	if len(t.hostKeys) > 0 {
-		result, err = t.server(kex, t.algorithms, &magics)
+		result, err = t.server(kex, &magics)
 	} else {
-		result, err = t.client(kex, t.algorithms, &magics)
+		result, err = t.client(kex, &magics)
 	}
 
 	if err != nil {
@@ -618,33 +626,52 @@
 	return nil
 }
 
-func (t *handshakeTransport) server(kex kexAlgorithm, algs *algorithms, magics *handshakeMagics) (*kexResult, error) {
-	var hostKey Signer
-	for _, k := range t.hostKeys {
-		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 == KeyAlgoRSASHA256 || algs.hostKey == KeyAlgoRSASHA512 {
-					hostKey = &rsaSigner{signer, algs.hostKey}
-				}
-			case CertAlgoRSAv01:
-				if algs.hostKey == CertAlgoRSASHA256v01 || algs.hostKey == CertAlgoRSASHA512v01 {
-					hostKey = &rsaSigner{signer, certToPrivAlgo(algs.hostKey)}
-				}
+// algorithmSignerWrapper is an AlgorithmSigner that only supports the default
+// key format algorithm.
+//
+// This is technically a violation of the AlgorithmSigner interface, but it
+// should be unreachable given where we use this. Anyway, at least it returns an
+// error instead of panicing or producing an incorrect signature.
+type algorithmSignerWrapper struct {
+	Signer
+}
+
+func (a algorithmSignerWrapper) SignWithAlgorithm(rand io.Reader, data []byte, algorithm string) (*Signature, error) {
+	if algorithm != underlyingAlgo(a.PublicKey().Type()) {
+		return nil, errors.New("ssh: internal error: algorithmSignerWrapper invoked with non-default algorithm")
+	}
+	return a.Sign(rand, data)
+}
+
+func pickHostKey(hostKeys []Signer, algo string) AlgorithmSigner {
+	for _, k := range hostKeys {
+		if algo == k.PublicKey().Type() {
+			return algorithmSignerWrapper{k}
+		}
+		k, ok := k.(AlgorithmSigner)
+		if !ok {
+			continue
+		}
+		for _, a := range algorithmsForKeyFormat(k.PublicKey().Type()) {
+			if algo == a {
+				return k
 			}
 		}
 	}
+	return nil
+}
 
-	r, err := kex.Server(t.conn, t.config.Rand, magics, hostKey)
+func (t *handshakeTransport) server(kex kexAlgorithm, magics *handshakeMagics) (*kexResult, error) {
+	hostKey := pickHostKey(t.hostKeys, t.algorithms.hostKey)
+	if hostKey == nil {
+		return nil, errors.New("ssh: internal error: negotiated unsupported signature type")
+	}
+
+	r, err := kex.Server(t.conn, t.config.Rand, magics, hostKey, t.algorithms.hostKey)
 	return r, err
 }
 
-func (t *handshakeTransport) client(kex kexAlgorithm, algs *algorithms, magics *handshakeMagics) (*kexResult, error) {
+func (t *handshakeTransport) client(kex kexAlgorithm, magics *handshakeMagics) (*kexResult, error) {
 	result, err := kex.Client(t.conn, t.config.Rand, magics)
 	if err != nil {
 		return nil, err
@@ -655,7 +682,7 @@
 		return nil, err
 	}
 
-	if err := verifyHostKeySignature(hostKey, algs.hostKey, result); err != nil {
+	if err := verifyHostKeySignature(hostKey, t.algorithms.hostKey, result); err != nil {
 		return nil, err
 	}
 
diff --git a/ssh/handshake_test.go b/ssh/handshake_test.go
index 46bfd6d..b05aab3 100644
--- a/ssh/handshake_test.go
+++ b/ssh/handshake_test.go
@@ -583,3 +583,38 @@
 		<-checker.called
 	}
 }
+
+// TestNoSHA2Support tests a host key Signer that is not an AlgorithmSigner and
+// therefore can't do SHA-2 signatures. Ensures the server does not advertise
+// support for them in this case.
+func TestNoSHA2Support(t *testing.T) {
+	c1, c2, err := netPipe()
+	if err != nil {
+		t.Fatalf("netPipe: %v", err)
+	}
+	defer c1.Close()
+	defer c2.Close()
+
+	serverConf := &ServerConfig{
+		PasswordCallback: func(conn ConnMetadata, password []byte) (*Permissions, error) {
+			return &Permissions{}, nil
+		},
+	}
+	serverConf.AddHostKey(&legacyRSASigner{testSigners["rsa"]})
+	go func() {
+		_, _, _, err := NewServerConn(c1, serverConf)
+		if err != nil {
+			t.Error(err)
+		}
+	}()
+
+	clientConf := &ClientConfig{
+		User:            "test",
+		Auth:            []AuthMethod{Password("testpw")},
+		HostKeyCallback: FixedHostKey(testSigners["rsa"].PublicKey()),
+	}
+
+	if _, _, _, err := NewClientConn(c2, "", clientConf); err != nil {
+		t.Fatal(err)
+	}
+}
diff --git a/ssh/kex.go b/ssh/kex.go
index 94287e4..927a90c 100644
--- a/ssh/kex.go
+++ b/ssh/kex.go
@@ -77,8 +77,9 @@
 // kexAlgorithm abstracts different key exchange algorithms.
 type kexAlgorithm interface {
 	// Server runs server-side key agreement, signing the result
-	// with a hostkey.
-	Server(p packetConn, rand io.Reader, magics *handshakeMagics, s Signer) (*kexResult, error)
+	// with a hostkey. algo is the negotiated algorithm, and may
+	// be a certificate type.
+	Server(p packetConn, rand io.Reader, magics *handshakeMagics, s AlgorithmSigner, algo string) (*kexResult, error)
 
 	// Client runs the client-side key agreement. Caller is
 	// responsible for verifying the host key signature.
@@ -151,7 +152,7 @@
 	}, nil
 }
 
-func (group *dhGroup) Server(c packetConn, randSource io.Reader, magics *handshakeMagics, priv Signer) (result *kexResult, err error) {
+func (group *dhGroup) Server(c packetConn, randSource io.Reader, magics *handshakeMagics, priv AlgorithmSigner, algo string) (result *kexResult, err error) {
 	packet, err := c.readPacket()
 	if err != nil {
 		return
@@ -193,7 +194,7 @@
 
 	// H is already a hash, but the hostkey signing will apply its
 	// own key-specific hash algorithm.
-	sig, err := signAndMarshal(priv, randSource, H)
+	sig, err := signAndMarshal(priv, randSource, H, algo)
 	if err != nil {
 		return nil, err
 	}
@@ -314,7 +315,7 @@
 	return true
 }
 
-func (kex *ecdh) Server(c packetConn, rand io.Reader, magics *handshakeMagics, priv Signer) (result *kexResult, err error) {
+func (kex *ecdh) Server(c packetConn, rand io.Reader, magics *handshakeMagics, priv AlgorithmSigner, algo string) (result *kexResult, err error) {
 	packet, err := c.readPacket()
 	if err != nil {
 		return nil, err
@@ -359,7 +360,7 @@
 
 	// H is already a hash, but the hostkey signing will apply its
 	// own key-specific hash algorithm.
-	sig, err := signAndMarshal(priv, rand, H)
+	sig, err := signAndMarshal(priv, rand, H, algo)
 	if err != nil {
 		return nil, err
 	}
@@ -384,6 +385,19 @@
 	}, nil
 }
 
+// ecHash returns the hash to match the given elliptic curve, see RFC
+// 5656, section 6.2.1
+func ecHash(curve elliptic.Curve) crypto.Hash {
+	bitSize := curve.Params().BitSize
+	switch {
+	case bitSize <= 256:
+		return crypto.SHA256
+	case bitSize <= 384:
+		return crypto.SHA384
+	}
+	return crypto.SHA512
+}
+
 var kexAlgoMap = map[string]kexAlgorithm{}
 
 func init() {
@@ -496,7 +510,7 @@
 	}, nil
 }
 
-func (kex *curve25519sha256) Server(c packetConn, rand io.Reader, magics *handshakeMagics, priv Signer) (result *kexResult, err error) {
+func (kex *curve25519sha256) Server(c packetConn, rand io.Reader, magics *handshakeMagics, priv AlgorithmSigner, algo string) (result *kexResult, err error) {
 	packet, err := c.readPacket()
 	if err != nil {
 		return
@@ -537,7 +551,7 @@
 
 	H := h.Sum(nil)
 
-	sig, err := signAndMarshal(priv, rand, H)
+	sig, err := signAndMarshal(priv, rand, H, algo)
 	if err != nil {
 		return nil, err
 	}
@@ -666,7 +680,7 @@
 // Server half implementation of the Diffie Hellman Key Exchange with SHA1 and SHA256.
 //
 // This is a minimal implementation to satisfy the automated tests.
-func (gex dhGEXSHA) Server(c packetConn, randSource io.Reader, magics *handshakeMagics, priv Signer) (result *kexResult, err error) {
+func (gex dhGEXSHA) Server(c packetConn, randSource io.Reader, magics *handshakeMagics, priv AlgorithmSigner, algo string) (result *kexResult, err error) {
 	// Receive GexRequest
 	packet, err := c.readPacket()
 	if err != nil {
@@ -736,7 +750,7 @@
 
 	// H is already a hash, but the hostkey signing will apply its
 	// own key-specific hash algorithm.
-	sig, err := signAndMarshal(priv, randSource, H)
+	sig, err := signAndMarshal(priv, randSource, H, algo)
 	if err != nil {
 		return nil, err
 	}
diff --git a/ssh/kex_test.go b/ssh/kex_test.go
index 1416b17..327013b 100644
--- a/ssh/kex_test.go
+++ b/ssh/kex_test.go
@@ -41,7 +41,7 @@
 						c <- kexResultErr{r, e}
 					}()
 					go func() {
-						r, e := kex.Server(b, rand.Reader, &magics, testSigners["ecdsa"])
+						r, e := kex.Server(b, rand.Reader, &magics, testSigners["ecdsa"].(AlgorithmSigner), testSigners["ecdsa"].PublicKey().Type())
 						b.Close()
 						s <- kexResultErr{r, e}
 					}()
diff --git a/ssh/keys.go b/ssh/keys.go
index 17b46a4..1c7de1a 100644
--- a/ssh/keys.go
+++ b/ssh/keys.go
@@ -76,7 +76,7 @@
 	case KeyAlgoSKED25519:
 		return parseSKEd25519(in)
 	case CertAlgoRSAv01, CertAlgoDSAv01, CertAlgoECDSA256v01, CertAlgoECDSA384v01, CertAlgoECDSA521v01, CertAlgoSKECDSA256v01, CertAlgoED25519v01, CertAlgoSKED25519v01:
-		cert, err := parseCert(in, certToPrivAlgo(algo))
+		cert, err := parseCert(in, certKeyAlgoNames[algo])
 		if err != nil {
 			return nil, nil, err
 		}
@@ -295,18 +295,21 @@
 	return b.Bytes()
 }
 
-// PublicKey is an abstraction of different types of public keys.
+// PublicKey represents a public key using an unspecified algorithm.
+//
+// Some PublicKeys provided by this package also implement CryptoPublicKey.
 type PublicKey interface {
-	// Type returns the key's type, e.g. "ssh-rsa".
+	// Type returns the key format name, e.g. "ssh-rsa".
 	Type() string
 
-	// Marshal returns the serialized key data in SSH wire format,
-	// with the name prefix. To unmarshal the returned data, use
-	// the ParsePublicKey function.
+	// Marshal returns the serialized key data in SSH wire format, with the name
+	// prefix. To unmarshal the returned data, use the ParsePublicKey function.
 	Marshal() []byte
 
-	// Verify that sig is a signature on the given data using this
-	// key. This function will hash the data appropriately first.
+	// Verify that sig is a signature on the given data using this key. This
+	// method will hash the data appropriately first. sig.Format is allowed to
+	// be any signature algorithm compatible with the key type, the caller
+	// should check if it has more stringent requirements.
 	Verify(data []byte, sig *Signature) error
 }
 
@@ -317,23 +320,32 @@
 }
 
 // A Signer can create signatures that verify against a public key.
+//
+// Some Signers provided by this package also implement AlgorithmSigner.
 type Signer interface {
-	// PublicKey returns an associated PublicKey instance.
+	// PublicKey returns the associated PublicKey.
 	PublicKey() PublicKey
 
-	// Sign returns raw signature for the given data. This method
-	// will apply the hash specified for the keytype to the data.
+	// Sign returns a signature for the given data. This method will hash the
+	// data appropriately first. The signature algorithm is expected to match
+	// the key format returned by the PublicKey.Type method (and not to be any
+	// alternative algorithm supported by the key format).
 	Sign(rand io.Reader, data []byte) (*Signature, error)
 }
 
-// A AlgorithmSigner is a Signer that also supports specifying a specific
-// algorithm to use for signing.
+// An AlgorithmSigner is a Signer that also supports specifying an algorithm to
+// use for signing.
+//
+// An AlgorithmSigner can't advertise the algorithms it supports, so it should
+// be prepared to be invoked with every algorithm supported by the public key
+// format.
 type AlgorithmSigner interface {
 	Signer
 
 	// SignWithAlgorithm is like Signer.Sign, but allows specifying a desired
 	// signing algorithm. Callers may pass an empty string for the algorithm in
-	// which case the AlgorithmSigner will use a default algorithm.
+	// which case the AlgorithmSigner will use a default algorithm. This default
+	// doesn't currently control any behavior in this package.
 	SignWithAlgorithm(rand io.Reader, data []byte, algorithm string) (*Signature, error)
 }
 
@@ -385,17 +397,11 @@
 }
 
 func (r *rsaPublicKey) Verify(data []byte, sig *Signature) error {
-	var hash crypto.Hash
-	switch sig.Format {
-	case KeyAlgoRSA:
-		hash = crypto.SHA1
-	case KeyAlgoRSASHA256:
-		hash = crypto.SHA256
-	case KeyAlgoRSASHA512:
-		hash = crypto.SHA512
-	default:
+	supportedAlgos := algorithmsForKeyFormat(r.Type())
+	if !contains(supportedAlgos, sig.Format) {
 		return fmt.Errorf("ssh: signature type %s for key type %s", sig.Format, r.Type())
 	}
+	hash := hashFuncs[sig.Format]
 	h := hash.New()
 	h.Write(data)
 	digest := h.Sum(nil)
@@ -470,7 +476,7 @@
 	if sig.Format != k.Type() {
 		return fmt.Errorf("ssh: signature type %s for key type %s", sig.Format, k.Type())
 	}
-	h := crypto.SHA1.New()
+	h := hashFuncs[sig.Format].New()
 	h.Write(data)
 	digest := h.Sum(nil)
 
@@ -503,7 +509,7 @@
 }
 
 func (k *dsaPrivateKey) Sign(rand io.Reader, data []byte) (*Signature, error) {
-	return k.SignWithAlgorithm(rand, data, "")
+	return k.SignWithAlgorithm(rand, data, k.PublicKey().Type())
 }
 
 func (k *dsaPrivateKey) SignWithAlgorithm(rand io.Reader, data []byte, algorithm string) (*Signature, error) {
@@ -511,7 +517,7 @@
 		return nil, fmt.Errorf("ssh: unsupported signature algorithm %s", algorithm)
 	}
 
-	h := crypto.SHA1.New()
+	h := hashFuncs[k.PublicKey().Type()].New()
 	h.Write(data)
 	digest := h.Sum(nil)
 	r, s, err := dsa.Sign(rand, k.PrivateKey, digest)
@@ -607,19 +613,6 @@
 	return curve == elliptic.P256() || curve == elliptic.P384() || curve == elliptic.P521()
 }
 
-// ecHash returns the hash to match the given elliptic curve, see RFC
-// 5656, section 6.2.1
-func ecHash(curve elliptic.Curve) crypto.Hash {
-	bitSize := curve.Params().BitSize
-	switch {
-	case bitSize <= 256:
-		return crypto.SHA256
-	case bitSize <= 384:
-		return crypto.SHA384
-	}
-	return crypto.SHA512
-}
-
 // parseECDSA parses an ECDSA key according to RFC 5656, section 3.1.
 func parseECDSA(in []byte) (out PublicKey, rest []byte, err error) {
 	var w struct {
@@ -675,7 +668,7 @@
 		return fmt.Errorf("ssh: signature type %s for key type %s", sig.Format, k.Type())
 	}
 
-	h := ecHash(k.Curve).New()
+	h := hashFuncs[sig.Format].New()
 	h.Write(data)
 	digest := h.Sum(nil)
 
@@ -779,7 +772,7 @@
 		return fmt.Errorf("ssh: signature type %s for key type %s", sig.Format, k.Type())
 	}
 
-	h := ecHash(k.Curve).New()
+	h := hashFuncs[sig.Format].New()
 	h.Write([]byte(k.application))
 	appDigest := h.Sum(nil)
 
@@ -878,7 +871,7 @@
 		return fmt.Errorf("invalid size %d for Ed25519 public key", l)
 	}
 
-	h := sha256.New()
+	h := hashFuncs[sig.Format].New()
 	h.Write([]byte(k.application))
 	appDigest := h.Sum(nil)
 
@@ -943,15 +936,6 @@
 	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
@@ -974,44 +958,20 @@
 }
 
 func (s *wrappedSigner) Sign(rand io.Reader, data []byte) (*Signature, error) {
-	return s.SignWithAlgorithm(rand, data, "")
+	return s.SignWithAlgorithm(rand, data, s.pubKey.Type())
 }
 
 func (s *wrappedSigner) SignWithAlgorithm(rand io.Reader, data []byte, algorithm string) (*Signature, error) {
-	var hashFunc crypto.Hash
-
-	if _, ok := s.pubKey.(*rsaPublicKey); ok {
-		// RSA keys support a few hash functions determined by the requested signature algorithm
-		switch algorithm {
-		case "", KeyAlgoRSA:
-			algorithm = KeyAlgoRSA
-			hashFunc = crypto.SHA1
-		case KeyAlgoRSASHA256:
-			hashFunc = crypto.SHA256
-		case KeyAlgoRSASHA512:
-			hashFunc = crypto.SHA512
-		default:
-			return nil, fmt.Errorf("ssh: unsupported signature algorithm %s", algorithm)
-		}
-	} else {
-		// The only supported algorithm for all other key types is the same as the type of the key
-		if algorithm == "" {
-			algorithm = s.pubKey.Type()
-		} else if algorithm != s.pubKey.Type() {
-			return nil, fmt.Errorf("ssh: unsupported signature algorithm %s", algorithm)
-		}
-
-		switch key := s.pubKey.(type) {
-		case *dsaPublicKey:
-			hashFunc = crypto.SHA1
-		case *ecdsaPublicKey:
-			hashFunc = ecHash(key.Curve)
-		case ed25519PublicKey:
-		default:
-			return nil, fmt.Errorf("ssh: unsupported key type %T", key)
-		}
+	if algorithm == "" {
+		algorithm = s.pubKey.Type()
 	}
 
+	supportedAlgos := algorithmsForKeyFormat(s.pubKey.Type())
+	if !contains(supportedAlgos, algorithm) {
+		return nil, fmt.Errorf("ssh: unsupported signature algorithm %q for key format %q", algorithm, s.pubKey.Type())
+	}
+
+	hashFunc := hashFuncs[algorithm]
 	var digest []byte
 	if hashFunc != 0 {
 		h := hashFunc.New()
diff --git a/ssh/server.go b/ssh/server.go
index e70c592..d28e1ad 100644
--- a/ssh/server.go
+++ b/ssh/server.go
@@ -212,9 +212,10 @@
 }
 
 // signAndMarshal signs the data with the appropriate algorithm,
-// and serializes the result in SSH wire format.
-func signAndMarshal(k Signer, rand io.Reader, data []byte) ([]byte, error) {
-	sig, err := k.Sign(rand, data)
+// and serializes the result in SSH wire format. algo is the negotiate
+// algorithm and may be a certificate type.
+func signAndMarshal(k AlgorithmSigner, rand io.Reader, data []byte, algo string) ([]byte, error) {
+	sig, err := k.SignWithAlgorithm(rand, data, underlyingAlgo(algo))
 	if err != nil {
 		return nil, err
 	}
diff --git a/ssh/testdata/keys.go b/ssh/testdata/keys.go
index 4f2f3a4..ad95a81 100644
--- a/ssh/testdata/keys.go
+++ b/ssh/testdata/keys.go
@@ -61,38 +61,6 @@
 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
@@ -226,7 +194,7 @@
 `),
 	"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
+	"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
 `),
 }
 
diff --git a/ssh/testdata_test.go b/ssh/testdata_test.go
index 26fe248..2da8c79 100644
--- a/ssh/testdata_test.go
+++ b/ssh/testdata_test.go
@@ -34,14 +34,6 @@
 			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, KeyAlgoRSASHA256}
-			case "rsa-sha2-512":
-				testSigners[t] = &rsaSigner{v, KeyAlgoRSASHA512}
-			}
-		}
 		if err != nil {
 			panic(fmt.Sprintf("Unable to create signer for test key %s: %v", t, err))
 		}