diff --git a/ssl/handshake_server.cc b/ssl/handshake_server.cc
index cffa52d..7c84ef8 100644
--- a/ssl/handshake_server.cc
+++ b/ssl/handshake_server.cc
@@ -303,7 +303,11 @@
   uint32_t mask_a = 0;
 
   if (ssl_has_certificate(hs)) {
-    mask_a |= ssl_cipher_auth_mask_for_key(hs->local_pubkey.get());
+    uint16_t unused;
+    bool sign_ok = tls1_choose_signature_algorithm(hs, &unused);
+    ERR_clear_error();
+
+    mask_a |= ssl_cipher_auth_mask_for_key(hs->local_pubkey.get(), sign_ok);
     if (EVP_PKEY_id(hs->local_pubkey.get()) == EVP_PKEY_RSA) {
       mask_k |= SSL_kRSA;
     }
diff --git a/ssl/internal.h b/ssl/internal.h
index 2896a32..f1d02a0 100644
--- a/ssl/internal.h
+++ b/ssl/internal.h
@@ -542,13 +542,14 @@
 #define SSL_kGENERIC 0x00000008u
 
 // Bits for |algorithm_auth| (server authentication).
-#define SSL_aRSA 0x00000001u
-#define SSL_aECDSA 0x00000002u
+#define SSL_aRSA_SIGN 0x00000001u
+#define SSL_aRSA_DECRYPT 0x00000002u
+#define SSL_aECDSA 0x00000004u
 // SSL_aPSK is set for both PSK and ECDHE_PSK.
-#define SSL_aPSK 0x00000004u
-#define SSL_aGENERIC 0x00000008u
+#define SSL_aPSK 0x00000008u
+#define SSL_aGENERIC 0x00000010u
 
-#define SSL_aCERT (SSL_aRSA | SSL_aECDSA)
+#define SSL_aCERT (SSL_aRSA_SIGN | SSL_aRSA_DECRYPT | SSL_aECDSA)
 
 // Bits for |algorithm_enc| (symmetric encryption).
 #define SSL_3DES 0x00000001u
@@ -649,8 +650,9 @@
                             bool strict);
 
 // ssl_cipher_auth_mask_for_key returns the mask of cipher |algorithm_auth|
-// values suitable for use with |key| in TLS 1.2 and below.
-uint32_t ssl_cipher_auth_mask_for_key(const EVP_PKEY *key);
+// values suitable for use with |key| in TLS 1.2 and below. |sign_ok| indicates
+// whether |key| may be used for signing.
+uint32_t ssl_cipher_auth_mask_for_key(const EVP_PKEY *key, bool sign_ok);
 
 // ssl_cipher_uses_certificate_auth returns whether |cipher| authenticates the
 // server and, optionally, the client with a certificate.
diff --git a/ssl/ssl_cert.cc b/ssl/ssl_cert.cc
index 6c6ae7b..9c40329 100644
--- a/ssl/ssl_cert.cc
+++ b/ssl/ssl_cert.cc
@@ -697,8 +697,12 @@
                                 const CRYPTO_BUFFER *leaf) {
   assert(ssl_protocol_version(hs->ssl) < TLS1_3_VERSION);
 
-  // Check the certificate's type matches the cipher.
-  if (!(hs->new_cipher->algorithm_auth & ssl_cipher_auth_mask_for_key(pkey))) {
+  // Check the certificate's type matches the cipher. This does not check key
+  // usage restrictions, which are handled separately.
+  //
+  // TODO(davidben): Put the key type and key usage checks in one place.
+  if (!(hs->new_cipher->algorithm_auth &
+        ssl_cipher_auth_mask_for_key(pkey, /*sign_ok=*/true))) {
     OPENSSL_PUT_ERROR(SSL, SSL_R_WRONG_CERTIFICATE_TYPE);
     return false;
   }
diff --git a/ssl/ssl_cipher.cc b/ssl/ssl_cipher.cc
index fd8cef9..29e32ce 100644
--- a/ssl/ssl_cipher.cc
+++ b/ssl/ssl_cipher.cc
@@ -164,7 +164,7 @@
      "TLS_RSA_WITH_3DES_EDE_CBC_SHA",
      SSL3_CK_RSA_DES_192_CBC3_SHA,
      SSL_kRSA,
-     SSL_aRSA,
+     SSL_aRSA_DECRYPT,
      SSL_3DES,
      SSL_SHA1,
      SSL_HANDSHAKE_MAC_DEFAULT,
@@ -179,7 +179,7 @@
      "TLS_RSA_WITH_AES_128_CBC_SHA",
      TLS1_CK_RSA_WITH_AES_128_SHA,
      SSL_kRSA,
-     SSL_aRSA,
+     SSL_aRSA_DECRYPT,
      SSL_AES128,
      SSL_SHA1,
      SSL_HANDSHAKE_MAC_DEFAULT,
@@ -191,7 +191,7 @@
      "TLS_RSA_WITH_AES_256_CBC_SHA",
      TLS1_CK_RSA_WITH_AES_256_SHA,
      SSL_kRSA,
-     SSL_aRSA,
+     SSL_aRSA_DECRYPT,
      SSL_AES256,
      SSL_SHA1,
      SSL_HANDSHAKE_MAC_DEFAULT,
@@ -231,7 +231,7 @@
      "TLS_RSA_WITH_AES_128_GCM_SHA256",
      TLS1_CK_RSA_WITH_AES_128_GCM_SHA256,
      SSL_kRSA,
-     SSL_aRSA,
+     SSL_aRSA_DECRYPT,
      SSL_AES128GCM,
      SSL_AEAD,
      SSL_HANDSHAKE_MAC_SHA256,
@@ -243,7 +243,7 @@
      "TLS_RSA_WITH_AES_256_GCM_SHA384",
      TLS1_CK_RSA_WITH_AES_256_GCM_SHA384,
      SSL_kRSA,
-     SSL_aRSA,
+     SSL_aRSA_DECRYPT,
      SSL_AES256GCM,
      SSL_AEAD,
      SSL_HANDSHAKE_MAC_SHA384,
@@ -317,7 +317,7 @@
      "TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA",
      TLS1_CK_ECDHE_RSA_WITH_AES_128_CBC_SHA,
      SSL_kECDHE,
-     SSL_aRSA,
+     SSL_aRSA_SIGN,
      SSL_AES128,
      SSL_SHA1,
      SSL_HANDSHAKE_MAC_DEFAULT,
@@ -329,7 +329,7 @@
      "TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA",
      TLS1_CK_ECDHE_RSA_WITH_AES_256_CBC_SHA,
      SSL_kECDHE,
-     SSL_aRSA,
+     SSL_aRSA_SIGN,
      SSL_AES256,
      SSL_SHA1,
      SSL_HANDSHAKE_MAC_DEFAULT,
@@ -341,7 +341,7 @@
      "TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256",
      TLS1_CK_ECDHE_RSA_WITH_AES_128_CBC_SHA256,
      SSL_kECDHE,
-     SSL_aRSA,
+     SSL_aRSA_SIGN,
      SSL_AES128,
      SSL_SHA256,
      SSL_HANDSHAKE_MAC_SHA256,
@@ -379,7 +379,7 @@
      "TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256",
      TLS1_CK_ECDHE_RSA_WITH_AES_128_GCM_SHA256,
      SSL_kECDHE,
-     SSL_aRSA,
+     SSL_aRSA_SIGN,
      SSL_AES128GCM,
      SSL_AEAD,
      SSL_HANDSHAKE_MAC_SHA256,
@@ -391,7 +391,7 @@
      "TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384",
      TLS1_CK_ECDHE_RSA_WITH_AES_256_GCM_SHA384,
      SSL_kECDHE,
-     SSL_aRSA,
+     SSL_aRSA_SIGN,
      SSL_AES256GCM,
      SSL_AEAD,
      SSL_HANDSHAKE_MAC_SHA384,
@@ -431,7 +431,7 @@
      "TLS_ECDHE_RSA_WITH_CHACHA20_POLY1305_SHA256",
      TLS1_CK_ECDHE_RSA_WITH_CHACHA20_POLY1305_SHA256,
      SSL_kECDHE,
-     SSL_aRSA,
+     SSL_aRSA_SIGN,
      SSL_CHACHA20POLY1305,
      SSL_AEAD,
      SSL_HANDSHAKE_MAC_SHA256,
@@ -528,7 +528,7 @@
     {"kPSK", SSL_kPSK, ~0u, ~0u, ~0u, 0},
 
     // server authentication aliases
-    {"aRSA", ~0u, SSL_aRSA, ~0u, ~0u, 0},
+    {"aRSA", ~0u, SSL_aRSA_SIGN | SSL_aRSA_DECRYPT, ~0u, ~0u, 0},
     {"aECDSA", ~0u, SSL_aECDSA, ~0u, ~0u, 0},
     {"ECDSA", ~0u, SSL_aECDSA, ~0u, ~0u, 0},
     {"aPSK", ~0u, SSL_aPSK, ~0u, ~0u, 0},
@@ -536,7 +536,7 @@
     // aliases combining key exchange and server authentication
     {"ECDHE", SSL_kECDHE, ~0u, ~0u, ~0u, 0},
     {"EECDH", SSL_kECDHE, ~0u, ~0u, ~0u, 0},
-    {"RSA", SSL_kRSA, SSL_aRSA, ~0u, ~0u, 0},
+    {"RSA", SSL_kRSA, SSL_aRSA_SIGN | SSL_aRSA_DECRYPT, ~0u, ~0u, 0},
     {"PSK", SSL_kPSK, SSL_aPSK, ~0u, ~0u, 0},
 
     // symmetric encryption aliases
@@ -1275,14 +1275,14 @@
   return true;
 }
 
-uint32_t ssl_cipher_auth_mask_for_key(const EVP_PKEY *key) {
+uint32_t ssl_cipher_auth_mask_for_key(const EVP_PKEY *key, bool sign_ok) {
   switch (EVP_PKEY_id(key)) {
     case EVP_PKEY_RSA:
-      return SSL_aRSA;
+      return sign_ok ? (SSL_aRSA_SIGN | SSL_aRSA_DECRYPT) : SSL_aRSA_DECRYPT;
     case EVP_PKEY_EC:
     case EVP_PKEY_ED25519:
       // Ed25519 keys in TLS 1.2 repurpose the ECDSA ciphers.
-      return SSL_aECDSA;
+      return sign_ok ? SSL_aECDSA : 0;
     default:
       return 0;
   }
@@ -1423,7 +1423,8 @@
 
 int SSL_CIPHER_get_auth_nid(const SSL_CIPHER *cipher) {
   switch (cipher->algorithm_auth) {
-    case SSL_aRSA:
+    case SSL_aRSA_DECRYPT:
+    case SSL_aRSA_SIGN:
       return NID_auth_rsa;
     case SSL_aECDSA:
       return NID_auth_ecdsa;
@@ -1511,7 +1512,7 @@
       switch (cipher->algorithm_auth) {
         case SSL_aECDSA:
           return "ECDHE_ECDSA";
-        case SSL_aRSA:
+        case SSL_aRSA_SIGN:
           return "ECDHE_RSA";
         case SSL_aPSK:
           return "ECDHE_PSK";
@@ -1603,7 +1604,8 @@
   }
 
   switch (alg_auth) {
-    case SSL_aRSA:
+    case SSL_aRSA_DECRYPT:
+    case SSL_aRSA_SIGN:
       au = "RSA";
       break;
 
diff --git a/ssl/test/runner/runner.go b/ssl/test/runner/runner.go
index cfccdcb..8ddb590 100644
--- a/ssl/test/runner/runner.go
+++ b/ssl/test/runner/runner.go
@@ -10877,7 +10877,7 @@
 			"-key-file", path.Join(*resourceDir, ed25519KeyFile),
 		},
 		shouldFail:    true,
-		expectedError: ":NO_COMMON_SIGNATURE_ALGORITHMS:",
+		expectedError: ":NO_SHARED_CIPHER:",
 	})
 	testCases = append(testCases, testCase{
 		testType: serverTest,
@@ -11015,8 +11015,14 @@
 			}
 
 			prefix := "Client-" + ver.name + "-"
+			noCommonAlgorithmsError := ":NO_COMMON_SIGNATURE_ALGORITHMS:"
 			if testType == serverTest {
 				prefix = "Server-" + ver.name + "-"
+				// In TLS 1.2 servers, cipher selection and algorithm
+				// selection are linked.
+				if ver.version <= VersionTLS12 {
+					noCommonAlgorithmsError = ":NO_SHARED_CIPHER:"
+				}
 			}
 
 			// Test that the shim will not sign MD5/SHA1 with RSA at TLS 1.2,
@@ -11039,7 +11045,7 @@
 					"-signing-prefs", strconv.Itoa(int(signatureRSAPKCS1WithSHA256)),
 				},
 				shouldFail:    true,
-				expectedError: ":NO_COMMON_SIGNATURE_ALGORITHMS:",
+				expectedError: noCommonAlgorithmsError,
 			})
 
 			// Test that the shim will not accept MD5/SHA1 with RSA at TLS 1.2,
@@ -11070,6 +11076,26 @@
 			})
 		}
 	}
+
+	// Test that, when there are no signature algorithms in common in TLS
+	// 1.2, the server will still consider the legacy RSA key exchange.
+	testCases = append(testCases, testCase{
+		testType: serverTest,
+		name:     "NoCommonSignatureAlgorithms-TLS12-Fallback",
+		config: Config{
+			MaxVersion: VersionTLS12,
+			CipherSuites: []uint16{
+				TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256,
+				TLS_RSA_WITH_AES_128_GCM_SHA256,
+			},
+			VerifySignatureAlgorithms: []signatureAlgorithm{
+				signatureECDSAWithP256AndSHA256,
+			},
+		},
+		expectations: connectionExpectations{
+			cipher: TLS_RSA_WITH_AES_128_GCM_SHA256,
+		},
+	})
 }
 
 // timeouts is the retransmit schedule for BoringSSL. It doubles and