Fix publickey authentication with signed RSA key

3 files changed, 22 insertions, 1 deletions

diff --git a/paramiko/auth_handler.py b/paramiko/auth_handler.py
index 41ec4487..e9023673 100644
--- a/paramiko/auth_handler.py
+++ b/paramiko/auth_handler.py
@@ -341,6 +341,8 @@ class AuthHandler(object):
                 DEBUG,
                 "NOTE: you may use the 'disabled_algorithms' SSHClient/Transport init kwarg to disable that or other algorithms if your server does not support them!",  # noqa
             )
+        if key_type.endswith("-cert-v01@openssh.com"):
+            pubkey_algo += "-cert-v01@openssh.com"
         self.transport._agreed_pubkey_algorithm = pubkey_algo
         return pubkey_algo
 
diff --git a/paramiko/rsakey.py b/paramiko/rsakey.py
index 26c5313c..d2dc99e4 100644
--- a/paramiko/rsakey.py
+++ b/paramiko/rsakey.py
@@ -129,7 +129,7 @@ class RSAKey(PKey):
             algorithm=self.HASHES[algorithm](),
         )
         m = Message()
-        m.add_string(algorithm)
+        m.add_string(algorithm.replace("-cert-v01@openssh.com", ""))
         m.add_string(sig)
         return m
 
diff --git a/tests/test_pkey.py b/tests/test_pkey.py
index 0cc20133..e652740c 100644
--- a/tests/test_pkey.py
+++ b/tests/test_pkey.py
@@ -696,3 +696,22 @@ class KeyTest(unittest.TestCase):
             key1.load_certificate,
             _support("test_rsa.key-cert.pub"),
         )
+
+    def test_sign_rsa_with_certificate(self):
+        data = b"ice weasels"
+        key_path = _support(os.path.join("cert_support", "test_rsa.key"))
+        key = RSAKey.from_private_key_file(key_path)
+        msg = key.sign_ssh_data(data, "rsa-sha2-256")
+        msg.rewind()
+        assert "rsa-sha2-256" == msg.get_text()
+        sign = msg.get_binary()
+        cert_path = _support(
+            os.path.join("cert_support", "test_rsa.key-cert.pub")
+        )
+        key.load_certificate(cert_path)
+        msg = key.sign_ssh_data(data, "rsa-sha2-256-cert-v01@openssh.com")
+        msg.rewind()
+        assert "rsa-sha2-256" == msg.get_text()
+        assert sign == msg.get_binary()
+        msg.rewind()
+        assert key.verify_ssh_sig(b"ice weasels", msg)