diff --git a/org.eclipse.jgit.ssh.apache.test/tst/org/eclipse/jgit/transport/sshd/ApacheSshTest.java b/org.eclipse.jgit.ssh.apache.test/tst/org/eclipse/jgit/transport/sshd/ApacheSshTest.java
index 09d048b..c56d230 100644
--- a/org.eclipse.jgit.ssh.apache.test/tst/org/eclipse/jgit/transport/sshd/ApacheSshTest.java
+++ b/org.eclipse.jgit.ssh.apache.test/tst/org/eclipse/jgit/transport/sshd/ApacheSshTest.java
@@ -664,4 +664,42 @@
 			session.disconnect();
 		}
 	}
+
+	/**
+	 * Tests that one can log in to an old server that knows only the ssh-rsa
+	 * signature algorithm. The client has by default the list of signature
+	 * algorithms for RSA as "rsa-sha2-512,rsa-sha2-256,ssh-rsa". It should try
+	 * all three with the single key configured, and finally succeed.
+	 * <p>
+	 * The re-ordering mechanism (see
+	 * {@link #testConnectAuthSshRsaPubkeyAcceptedAlgorithms()}) is still
+	 * important; servers may impose a penalty (back-off delay) for subsequent
+	 * attempts with signature algorithms unknown to the server. So a user
+	 * connecting to such a server and noticing delays may still want to put
+	 * ssh-rsa first in the list for that host.
+	 * </p>
+	 *
+	 * @see <a href="https://bugs.eclipse.org/bugs/show_bug.cgi?id=572056">bug
+	 *      572056</a>
+	 * @throws Exception
+	 *             on failure
+	 */
+	@Test
+	public void testConnectAuthSshRsa() throws Exception {
+		try (SshServer oldServer = createServer(TEST_USER, publicKey1)) {
+			oldServer.setSignatureFactoriesNames("ssh-rsa");
+			oldServer.start();
+			registerServer(oldServer);
+			installConfig("Host server", //
+					"HostName localhost", //
+					"Port " + oldServer.getPort(), //
+					"User " + TEST_USER, //
+					"IdentityFile " + privateKey1.getAbsolutePath());
+			RemoteSession session = getSessionFactory().getSession(
+					new URIish("ssh://server/doesntmatter"), null, FS.DETECTED,
+					10000);
+			assertNotNull(session);
+			session.disconnect();
+		}
+	}
 }
diff --git a/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/JGitPublicKeyAuthFactory.java b/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/JGitPublicKeyAuthFactory.java
new file mode 100644
index 0000000..0e3e24d
--- /dev/null
+++ b/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/JGitPublicKeyAuthFactory.java
@@ -0,0 +1,35 @@
+/*
+ * Copyright (C) 2018, 2021 Thomas Wolf <thomas.wolf@paranor.ch> and others
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Distribution License v. 1.0 which is available at
+ * https://www.eclipse.org/org/documents/edl-v10.php.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+package org.eclipse.jgit.internal.transport.sshd;
+
+import java.io.IOException;
+
+import org.apache.sshd.client.auth.pubkey.UserAuthPublicKey;
+import org.apache.sshd.client.auth.pubkey.UserAuthPublicKeyFactory;
+import org.apache.sshd.client.session.ClientSession;
+
+/**
+ * A customized authentication factory for public key user authentication.
+ */
+public class JGitPublicKeyAuthFactory extends UserAuthPublicKeyFactory {
+
+	/** The singleton {@link JGitPublicKeyAuthFactory}. */
+	public static final JGitPublicKeyAuthFactory FACTORY = new JGitPublicKeyAuthFactory();
+
+	private JGitPublicKeyAuthFactory() {
+		super();
+	}
+
+	@Override
+	public UserAuthPublicKey createUserAuth(ClientSession session)
+			throws IOException {
+		return new JGitPublicKeyAuthentication(getSignatureFactories());
+	}
+}
diff --git a/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/JGitPublicKeyAuthentication.java b/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/JGitPublicKeyAuthentication.java
new file mode 100644
index 0000000..297b456
--- /dev/null
+++ b/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/JGitPublicKeyAuthentication.java
@@ -0,0 +1,133 @@
+/*
+ * Copyright (C) 2018, 2021 Thomas Wolf <thomas.wolf@paranor.ch> and others
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Distribution License v. 1.0 which is available at
+ * https://www.eclipse.org/org/documents/edl-v10.php.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+package org.eclipse.jgit.internal.transport.sshd;
+
+import java.io.IOException;
+import java.security.PublicKey;
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Set;
+
+import org.apache.sshd.client.auth.pubkey.UserAuthPublicKey;
+import org.apache.sshd.client.session.ClientSession;
+import org.apache.sshd.common.NamedFactory;
+import org.apache.sshd.common.RuntimeSshException;
+import org.apache.sshd.common.SshConstants;
+import org.apache.sshd.common.config.keys.KeyUtils;
+import org.apache.sshd.common.signature.Signature;
+import org.apache.sshd.common.signature.SignatureFactoriesHolder;
+import org.apache.sshd.common.util.buffer.Buffer;
+
+/**
+ * Custom {@link UserAuthPublicKey} implementation fixing SSHD-1105: if there
+ * are several signature algorithms applicable for a public key type, we must
+ * try them all, in the correct order.
+ *
+ * @see <a href="https://issues.apache.org/jira/browse/SSHD-1105">SSHD-1105</a>
+ * @see <a href="https://bugs.eclipse.org/bugs/show_bug.cgi?id=572056">Bug
+ *      572056</a>
+ */
+public class JGitPublicKeyAuthentication extends UserAuthPublicKey {
+
+	private final List<String> algorithms = new LinkedList<>();
+
+	JGitPublicKeyAuthentication(List<NamedFactory<Signature>> factories) {
+		super(factories);
+	}
+
+	@Override
+	protected boolean sendAuthDataRequest(ClientSession session, String service)
+			throws Exception {
+		if (current == null) {
+			algorithms.clear();
+		}
+		String currentAlgorithm = null;
+		if (current != null && !algorithms.isEmpty()) {
+			currentAlgorithm = algorithms.remove(0);
+		}
+		if (currentAlgorithm == null) {
+			try {
+				if (keys == null || !keys.hasNext()) {
+					if (log.isDebugEnabled()) {
+						log.debug(
+								"sendAuthDataRequest({})[{}] no more keys to send", //$NON-NLS-1$
+								session, service);
+					}
+					return false;
+				}
+				current = keys.next();
+				algorithms.clear();
+			} catch (Error e) { // Copied from superclass
+				warn("sendAuthDataRequest({})[{}] failed ({}) to get next key: {}", //$NON-NLS-1$
+						session, service, e.getClass().getSimpleName(),
+						e.getMessage(), e);
+				throw new RuntimeSshException(e);
+			}
+		}
+		PublicKey key;
+		try {
+			key = current.getPublicKey();
+		} catch (Error e) { // Copied from superclass
+			warn("sendAuthDataRequest({})[{}] failed ({}) to retrieve public key: {}", //$NON-NLS-1$
+					session, service, e.getClass().getSimpleName(),
+					e.getMessage(), e);
+			throw new RuntimeSshException(e);
+		}
+		if (currentAlgorithm == null) {
+			String keyType = KeyUtils.getKeyType(key);
+			Set<String> aliases = new HashSet<>(
+					KeyUtils.getAllEquivalentKeyTypes(keyType));
+			aliases.add(keyType);
+			List<NamedFactory<Signature>> existingFactories;
+			if (current instanceof SignatureFactoriesHolder) {
+				existingFactories = ((SignatureFactoriesHolder) current)
+						.getSignatureFactories();
+			} else {
+				existingFactories = getSignatureFactories();
+			}
+			if (existingFactories != null) {
+				// Select the factories by name and in order
+				existingFactories.forEach(f -> {
+					if (aliases.contains(f.getName())) {
+						algorithms.add(f.getName());
+					}
+				});
+			}
+			currentAlgorithm = algorithms.isEmpty() ? keyType
+					: algorithms.remove(0);
+		}
+		String name = getName();
+		if (log.isDebugEnabled()) {
+			log.debug(
+					"sendAuthDataRequest({})[{}] send SSH_MSG_USERAUTH_REQUEST request {} type={} - fingerprint={}", //$NON-NLS-1$
+					session, service, name, currentAlgorithm,
+					KeyUtils.getFingerPrint(key));
+		}
+
+		Buffer buffer = session
+				.createBuffer(SshConstants.SSH_MSG_USERAUTH_REQUEST);
+		buffer.putString(session.getUsername());
+		buffer.putString(service);
+		buffer.putString(name);
+		buffer.putBoolean(false);
+		buffer.putString(currentAlgorithm);
+		buffer.putPublicKey(key);
+		session.writePacket(buffer);
+		return true;
+	}
+
+	@Override
+	protected void releaseKeys() throws IOException {
+		algorithms.clear();
+		current = null;
+		super.releaseKeys();
+	}
+}
diff --git a/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/transport/sshd/SshdSessionFactory.java b/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/transport/sshd/SshdSessionFactory.java
index 357994d..cad959c 100644
--- a/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/transport/sshd/SshdSessionFactory.java
+++ b/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/transport/sshd/SshdSessionFactory.java
@@ -32,10 +32,9 @@
 import org.apache.sshd.client.SshClient;
 import org.apache.sshd.client.auth.UserAuthFactory;
 import org.apache.sshd.client.auth.keyboard.UserAuthKeyboardInteractiveFactory;
-import org.apache.sshd.client.auth.pubkey.UserAuthPublicKeyFactory;
 import org.apache.sshd.client.config.hosts.HostConfigEntryResolver;
-import org.apache.sshd.common.SshException;
 import org.apache.sshd.common.NamedFactory;
+import org.apache.sshd.common.SshException;
 import org.apache.sshd.common.compression.BuiltinCompressions;
 import org.apache.sshd.common.config.keys.FilePasswordProvider;
 import org.apache.sshd.common.config.keys.loader.openssh.kdf.BCryptKdfOptions;
@@ -49,6 +48,7 @@
 import org.eclipse.jgit.internal.transport.sshd.CachingKeyPairProvider;
 import org.eclipse.jgit.internal.transport.sshd.GssApiWithMicAuthFactory;
 import org.eclipse.jgit.internal.transport.sshd.JGitPasswordAuthFactory;
+import org.eclipse.jgit.internal.transport.sshd.JGitPublicKeyAuthFactory;
 import org.eclipse.jgit.internal.transport.sshd.JGitServerKeyVerifier;
 import org.eclipse.jgit.internal.transport.sshd.JGitSshClient;
 import org.eclipse.jgit.internal.transport.sshd.JGitSshConfig;
@@ -577,7 +577,7 @@
 		// Password auth doesn't have this problem.
 		return Collections.unmodifiableList(
 				Arrays.asList(GssApiWithMicAuthFactory.INSTANCE,
-						UserAuthPublicKeyFactory.INSTANCE,
+						JGitPublicKeyAuthFactory.FACTORY,
 						JGitPasswordAuthFactory.INSTANCE,
 						UserAuthKeyboardInteractiveFactory.INSTANCE));
 	}