diff --git a/org.eclipse.jgit.ssh.apache.test/META-INF/MANIFEST.MF b/org.eclipse.jgit.ssh.apache.test/META-INF/MANIFEST.MF
index 30eb2bf..b035453 100644
--- a/org.eclipse.jgit.ssh.apache.test/META-INF/MANIFEST.MF
+++ b/org.eclipse.jgit.ssh.apache.test/META-INF/MANIFEST.MF
@@ -14,6 +14,7 @@
  org.apache.sshd.common.helpers;version="[2.6.0,2.7.0)",
  org.apache.sshd.common.keyprovider;version="[2.6.0,2.7.0)",
  org.apache.sshd.common.session;version="[2.6.0,2.7.0)",
+ org.apache.sshd.common.signature;version="[2.6.0,2.7.0)",
  org.apache.sshd.common.util.net;version="[2.6.0,2.7.0)",
  org.apache.sshd.common.util.security;version="[2.6.0,2.7.0)",
  org.apache.sshd.core;version="[2.6.0,2.7.0)",
diff --git a/org.eclipse.jgit.ssh.apache.test/build.properties b/org.eclipse.jgit.ssh.apache.test/build.properties
index 9ffa0ca..406c5a7 100644
--- a/org.eclipse.jgit.ssh.apache.test/build.properties
+++ b/org.eclipse.jgit.ssh.apache.test/build.properties
@@ -3,3 +3,5 @@
 bin.includes = META-INF/,\
                .,\
                plugin.properties
+additional.bundles = org.apache.log4j,\
+                     org.slf4j.binding.log4j12
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 97f97f9..09d048b 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
@@ -47,7 +47,9 @@
 import org.eclipse.jgit.api.errors.TransportException;
 import org.eclipse.jgit.junit.ssh.SshTestBase;
 import org.eclipse.jgit.lib.Constants;
+import org.eclipse.jgit.transport.RemoteSession;
 import org.eclipse.jgit.transport.SshSessionFactory;
+import org.eclipse.jgit.transport.URIish;
 import org.eclipse.jgit.util.FS;
 import org.junit.Test;
 import org.junit.experimental.theories.Theories;
@@ -232,6 +234,61 @@
 	}
 
 	/**
+	 * Creates a simple SSH server without git setup.
+	 *
+	 * @param user
+	 *            to accept
+	 * @param userKey
+	 *            public key of that user at this server
+	 * @return the {@link SshServer}, not yet started
+	 * @throws Exception
+	 */
+	private SshServer createServer(String user, File userKey) throws Exception {
+		SshServer srv = SshServer.setUpDefaultServer();
+		// Give the server its own host key
+		KeyPairGenerator generator = KeyPairGenerator.getInstance("RSA");
+		generator.initialize(2048);
+		KeyPair proxyHostKey = generator.generateKeyPair();
+		srv.setKeyPairProvider(
+				session -> Collections.singletonList(proxyHostKey));
+		// Allow (only) publickey authentication
+		srv.setUserAuthFactories(Collections.singletonList(
+				ServerAuthenticationManager.DEFAULT_USER_AUTH_PUBLIC_KEY_FACTORY));
+		// Install the user's public key
+		PublicKey userProxyKey = AuthorizedKeyEntry
+				.readAuthorizedKeys(userKey.toPath()).get(0)
+				.resolvePublicKey(null, PublicKeyEntryResolver.IGNORING);
+		srv.setPublickeyAuthenticator(
+				(userName, publicKey, session) -> user.equals(userName)
+						&& KeyUtils.compareKeys(userProxyKey, publicKey));
+		return srv;
+	}
+
+	/**
+	 * Writes the server's host key to our knownhosts file.
+	 *
+	 * @param srv to register
+	 * @throws Exception
+	 */
+	private void registerServer(SshServer srv) throws Exception {
+		// Add the proxy's host key to knownhosts
+		try (BufferedWriter writer = Files.newBufferedWriter(
+				knownHosts.toPath(), StandardCharsets.US_ASCII,
+				StandardOpenOption.WRITE, StandardOpenOption.APPEND)) {
+			writer.append('\n');
+			KnownHostHashValue.appendHostPattern(writer, "localhost",
+					srv.getPort());
+			writer.append(',');
+			KnownHostHashValue.appendHostPattern(writer, "127.0.0.1",
+					srv.getPort());
+			writer.append(' ');
+			PublicKeyEntry.appendPublicKeyEntry(writer,
+					srv.getKeyPairProvider().loadKeys(null).iterator().next().getPublic());
+			writer.append('\n');
+		}
+	}
+
+	/**
 	 * Creates a simple proxy server. Accepts only publickey authentication from
 	 * the given user with the given key, allows all forwardings. Adds the
 	 * proxy's host key to {@link #knownHosts}.
@@ -247,23 +304,7 @@
 	 */
 	private SshServer createProxy(String user, File userKey,
 			SshdSocketAddress[] report) throws Exception {
-		SshServer proxy = SshServer.setUpDefaultServer();
-		// Give the server its own host key
-		KeyPairGenerator generator = KeyPairGenerator.getInstance("RSA");
-		generator.initialize(2048);
-		KeyPair proxyHostKey = generator.generateKeyPair();
-		proxy.setKeyPairProvider(
-				session -> Collections.singletonList(proxyHostKey));
-		// Allow (only) publickey authentication
-		proxy.setUserAuthFactories(Collections.singletonList(
-				ServerAuthenticationManager.DEFAULT_USER_AUTH_PUBLIC_KEY_FACTORY));
-		// Install the user's public key
-		PublicKey userProxyKey = AuthorizedKeyEntry
-				.readAuthorizedKeys(userKey.toPath()).get(0)
-				.resolvePublicKey(null, PublicKeyEntryResolver.IGNORING);
-		proxy.setPublickeyAuthenticator(
-				(userName, publicKey, session) -> user.equals(userName)
-						&& KeyUtils.compareKeys(userProxyKey, publicKey));
+		SshServer proxy = createServer(user, userKey);
 		// Allow forwarding
 		proxy.setForwardingFilter(new StaticDecisionForwardingFilter(true) {
 
@@ -275,21 +316,7 @@
 			}
 		});
 		proxy.start();
-		// Add the proxy's host key to knownhosts
-		try (BufferedWriter writer = Files.newBufferedWriter(
-				knownHosts.toPath(), StandardCharsets.US_ASCII,
-				StandardOpenOption.WRITE, StandardOpenOption.APPEND)) {
-			writer.append('\n');
-			KnownHostHashValue.appendHostPattern(writer, "localhost",
-					proxy.getPort());
-			writer.append(',');
-			KnownHostHashValue.appendHostPattern(writer, "127.0.0.1",
-					proxy.getPort());
-			writer.append(' ');
-			PublicKeyEntry.appendPublicKeyEntry(writer,
-					proxyHostKey.getPublic());
-			writer.append('\n');
-		}
+		registerServer(proxy);
 		return proxy;
 	}
 
@@ -606,4 +633,35 @@
 			}
 		}
 	}
+
+	/**
+	 * Tests that one can log in to an old server that doesn't handle
+	 * rsa-sha2-512 if one puts ssh-rsa first in the client's list of public key
+	 * signature algorithms.
+	 *
+	 * @see <a href="https://bugs.eclipse.org/bugs/show_bug.cgi?id=572056">bug
+	 *      572056</a>
+	 * @throws Exception
+	 *             on failure
+	 */
+	@Test
+	public void testConnectAuthSshRsaPubkeyAcceptedAlgorithms()
+			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(), //
+					"PubkeyAcceptedAlgorithms ^ssh-rsa");
+			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/resources/org/eclipse/jgit/internal/transport/sshd/SshdText.properties b/org.eclipse.jgit.ssh.apache/resources/org/eclipse/jgit/internal/transport/sshd/SshdText.properties
index f810fd4..16b5738 100644
--- a/org.eclipse.jgit.ssh.apache/resources/org/eclipse/jgit/internal/transport/sshd/SshdText.properties
+++ b/org.eclipse.jgit.ssh.apache/resources/org/eclipse/jgit/internal/transport/sshd/SshdText.properties
@@ -5,8 +5,7 @@
 configInvalidPattern=Invalid pattern in ssh config key {0}: {1}
 configInvalidPositive=Ssh config entry {0} must be a strictly positive number but is ''{1}''
 configInvalidProxyJump=Ssh config, host ''{0}'': Cannot parse ProxyJump ''{1}''
-configNoKnownHostKeyAlgorithms=No implementations for any of the algorithms ''{0}'' given in HostKeyAlgorithms in the ssh config; using the default.
-configNoRemainingHostKeyAlgorithms=Ssh config removed all host key algorithms: HostKeyAlgorithms ''{0}''
+configNoKnownAlgorithms=Ssh config ''{0}'' ''{1}'' resulted in empty list (none known, or all known removed); using default.
 configProxyJumpNotSsh=Non-ssh URI in ProxyJump ssh config
 configProxyJumpWithPath=ProxyJump ssh config: jump host specification must not have a path
 ftpCloseFailed=Closing the SFTP channel failed
diff --git a/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/JGitClientSession.java b/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/JGitClientSession.java
index 66713ba..8183a92 100644
--- a/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/JGitClientSession.java
+++ b/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/JGitClientSession.java
@@ -21,6 +21,7 @@
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
+import java.util.HashSet;
 import java.util.Iterator;
 import java.util.LinkedHashSet;
 import java.util.List;
@@ -45,6 +46,7 @@
 import org.eclipse.jgit.internal.transport.sshd.proxy.StatefulProxyConnector;
 import org.eclipse.jgit.transport.CredentialsProvider;
 import org.eclipse.jgit.transport.SshConstants;
+import org.eclipse.jgit.util.StringUtils;
 
 /**
  * A {@link org.apache.sshd.client.session.ClientSession ClientSession} that can
@@ -201,48 +203,23 @@
 	@Override
 	protected String resolveAvailableSignaturesProposal(
 			FactoryManager manager) {
-		Set<String> defaultSignatures = new LinkedHashSet<>();
-		defaultSignatures.addAll(getSignatureFactoriesNames());
+		List<String> defaultSignatures = getSignatureFactoriesNames();
 		HostConfigEntry config = resolveAttribute(
 				JGitSshClient.HOST_CONFIG_ENTRY);
-		String hostKeyAlgorithms = config
+		String algorithms = config
 				.getProperty(SshConstants.HOST_KEY_ALGORITHMS);
-		if (hostKeyAlgorithms != null && !hostKeyAlgorithms.isEmpty()) {
-			char first = hostKeyAlgorithms.charAt(0);
-			switch (first) {
-			case '+':
-				// Additions make not much sense -- it's either in
-				// defaultSignatures already, or we have no implementation for
-				// it. No point in proposing it.
-				return String.join(",", defaultSignatures); //$NON-NLS-1$
-			case '-':
-				// This takes wildcard patterns!
-				removeFromList(defaultSignatures,
-						SshConstants.HOST_KEY_ALGORITHMS,
-						hostKeyAlgorithms.substring(1));
-				if (defaultSignatures.isEmpty()) {
-					// Too bad: user config error. Warn here, and then fail
-					// later.
-					log.warn(format(
-							SshdText.get().configNoRemainingHostKeyAlgorithms,
-							hostKeyAlgorithms));
+		if (!StringUtils.isEmptyOrNull(algorithms)) {
+			List<String> result = modifyAlgorithmList(defaultSignatures,
+					algorithms, SshConstants.HOST_KEY_ALGORITHMS);
+			if (!result.isEmpty()) {
+				if (log.isDebugEnabled()) {
+					log.debug(SshConstants.HOST_KEY_ALGORITHMS + ' ' + result);
 				}
-				return String.join(",", defaultSignatures); //$NON-NLS-1$
-			default:
-				// Default is overridden -- only accept the ones for which we do
-				// have an implementation.
-				List<String> newNames = filteredList(defaultSignatures,
-						hostKeyAlgorithms);
-				if (newNames.isEmpty()) {
-					log.warn(format(
-							SshdText.get().configNoKnownHostKeyAlgorithms,
-							hostKeyAlgorithms));
-					// Use the default instead.
-				} else {
-					return String.join(",", newNames); //$NON-NLS-1$
-				}
-				break;
+				return String.join(",", result); //$NON-NLS-1$
 			}
+			log.warn(format(SshdText.get().configNoKnownAlgorithms,
+					SshConstants.HOST_KEY_ALGORITHMS,
+					algorithms));
 		}
 		// No HostKeyAlgorithms; using default -- change order to put existing
 		// keys first.
@@ -262,11 +239,67 @@
 				}
 			}
 			reordered.addAll(defaultSignatures);
+			if (log.isDebugEnabled()) {
+				log.debug(SshConstants.HOST_KEY_ALGORITHMS + ' ' + reordered);
+			}
 			return String.join(",", reordered); //$NON-NLS-1$
 		}
+		if (log.isDebugEnabled()) {
+			log.debug(
+					SshConstants.HOST_KEY_ALGORITHMS + ' ' + defaultSignatures);
+		}
 		return String.join(",", defaultSignatures); //$NON-NLS-1$
 	}
 
+	/**
+	 * Modifies a given algorithm list according to a list from the ssh config,
+	 * including remove ('-') and reordering ('^') operators. Addition ('+') is
+	 * not handled since we have no way of adding dynamically implementations,
+	 * and the defaultList is supposed to contain all known implementations
+	 * already.
+	 *
+	 * @param defaultList
+	 *            to modify
+	 * @param fromConfig
+	 *            telling how to modify the {@code defaultList}, must not be
+	 *            {@code null} or empty
+	 * @param overrideKey
+	 *            ssh config key; used for logging
+	 * @return the modified list or {@code null} if {@code overrideKey} is not
+	 *         set
+	 */
+	public List<String> modifyAlgorithmList(List<String> defaultList,
+			String fromConfig, String overrideKey) {
+		Set<String> defaults = new LinkedHashSet<>();
+		defaults.addAll(defaultList);
+		switch (fromConfig.charAt(0)) {
+		case '+':
+			// Additions make not much sense -- it's either in
+			// defaultList already, or we have no implementation for
+			// it. No point in proposing it.
+			return defaultList;
+		case '-':
+			// This takes wildcard patterns!
+			removeFromList(defaults, overrideKey, fromConfig.substring(1));
+			return new ArrayList<>(defaults);
+		case '^':
+			// Specified entries go to the front of the default list
+			List<String> allSignatures = filteredList(defaults,
+					fromConfig.substring(1));
+			Set<String> atFront = new HashSet<>(allSignatures);
+			for (String sig : defaults) {
+				if (!atFront.contains(sig)) {
+					allSignatures.add(sig);
+				}
+			}
+			return allSignatures;
+		default:
+			// Default is overridden -- only accept the ones for which we do
+			// have an implementation.
+			return filteredList(defaults, fromConfig);
+		}
+	}
+
 	private void removeFromList(Set<String> current, String key,
 			String patterns) {
 		for (String toRemove : patterns.split("\\s*,\\s*")) { //$NON-NLS-1$
diff --git a/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/JGitSshClient.java b/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/JGitSshClient.java
index 74455dc..071e197 100644
--- a/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/JGitSshClient.java
+++ b/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/JGitSshClient.java
@@ -267,6 +267,24 @@
 		session.setUsername(username);
 		session.setConnectAddress(address);
 		session.setHostConfigEntry(hostConfig);
+		// Set signature algorithms for public key authentication
+		String pubkeyAlgos = hostConfig
+				.getProperty(SshConstants.PUBKEY_ACCEPTED_ALGORITHMS);
+		if (!StringUtils.isEmptyOrNull(pubkeyAlgos)) {
+			List<String> signatures = getSignatureFactoriesNames();
+			signatures = session.modifyAlgorithmList(signatures, pubkeyAlgos,
+					SshConstants.PUBKEY_ACCEPTED_ALGORITHMS);
+			if (!signatures.isEmpty()) {
+				if (log.isDebugEnabled()) {
+					log.debug(SshConstants.PUBKEY_ACCEPTED_ALGORITHMS + ' '
+							+ signatures);
+				}
+				session.setSignatureFactoriesNames(signatures);
+			} else {
+				log.warn(format(SshdText.get().configNoKnownAlgorithms,
+						SshConstants.PUBKEY_ACCEPTED_ALGORITHMS, pubkeyAlgos));
+			}
+		}
 		if (session.getCredentialsProvider() == null) {
 			session.setCredentialsProvider(getCredentialsProvider());
 		}
diff --git a/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/SshdText.java b/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/SshdText.java
index 13bb3eb..4c4ff59 100644
--- a/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/SshdText.java
+++ b/org.eclipse.jgit.ssh.apache/src/org/eclipse/jgit/internal/transport/sshd/SshdText.java
@@ -25,8 +25,7 @@
 	/***/ public String configInvalidPattern;
 	/***/ public String configInvalidPositive;
 	/***/ public String configInvalidProxyJump;
-	/***/ public String configNoKnownHostKeyAlgorithms;
-	/***/ public String configNoRemainingHostKeyAlgorithms;
+	/***/ public String configNoKnownAlgorithms;
 	/***/ public String configProxyJumpNotSsh;
 	/***/ public String configProxyJumpWithPath;
 	/***/ public String ftpCloseFailed;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/transport/SshConstants.java b/org.eclipse.jgit/src/org/eclipse/jgit/transport/SshConstants.java
index fff2938..be55cd1 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/SshConstants.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/transport/SshConstants.java
@@ -114,6 +114,14 @@
 	/** Key in an ssh config file. */
 	public static final String PREFERRED_AUTHENTICATIONS = "PreferredAuthentications";
 
+	/**
+	 * Key in an ssh config file; defines signature algorithms for public key
+	 * authentication as a comma-separated list.
+	 *
+	 * @since 5.11
+	 */
+	public static final String PUBKEY_ACCEPTED_ALGORITHMS = "PubkeyAcceptedAlgorithms";
+
 	/** Key in an ssh config file. */
 	public static final String PROXY_COMMAND = "ProxyCommand";