Update: Rebex SFTP 2012 R1 and higher contain a built-in workaround for this issue.
This exception was thrown because the size of ephemeral Diffie-Hellman key supplied by the server during the SSH key exchange was larger than the maximum key size supported by the cryptographic providers available at the device. This key is only used during key exchange and is not related to RSA and DSA key lengths.
For 512bit keys, "Microsoft Base DSS and Diffie-Hellman Cryptographic Provider" is adequate, but for larger keys (1024-bit and higher), "Microsoft Enhanced DSS and Diffie-Hellman Cryptographic Provider" is needed.
Could you please let us know what cryptographic providers are installed on your device by looking into the following registry key? "HKEY_LOCAL_MACHINE\Comm\Security\Crypto\Defaults\Provider" (Use PHM Registry Editor if the system lacks a registry editor.) It might be possible that the provider is present but we are not detecting it correctly for some reason.
Several customers have encountered several newer devices where the enhanced provider was missing or not installed correctly (causing the same error you got), possibly by a mistaken choice made by the manufacturer (they forgot to include DSS and DH providers). In some of these cases, they were able to fix the problem by installing a fixed OS image on the device (recommended solution) or by recreating the missing or malformed registry structure under "HKEY_LOCAL_MACHINE\Comm\Security\Crypto\Defaults\Provider", so this might be a solution in your case as well.
With the base provider, you should still be able to connect to an SFTP server that supports 512bit DiffieHellmanGroupExchangeSHA1 key exchange algorithm (see Specifying SSH parameters for more info on how to request this), but it seems most SFTP servers only supports 1024bit and larger keys.
