Generate an ECDSA P521 SSH Host Key

Elliptic curve cryptography provides stronger protection with smaller keys when compared to non-elliptic curve algorithms. Let's start by seeing what key-pairs already exist

$ ls /etc/ssh | grep .pub
ssh_host_dsa_key
ssh_host_dsa_key.pub
ssh_host_ecdsa_key
ssh_host_ecdsa_key.pub
ssh_host_ed25519_key
ssh_host_ed25519_key.pub
ssh_host_rsa_key
ssh_host_rsa_key.pub

There is already one elliptic curve key-pair. Let's see how many bits it is using

$ cat ssh_host_ecdsa_key.pub | cut -d" " -f1
ecdsa-sha2-nistp256

This means the key-pair uses the ECDSA algorithm with a SHA2 hash and the NIST P256 curve. We can do better than that. Start by generating a new key-pair using the P521 curve

# ssh-keygen -b 521 -o -t ecdsa -f /etc/ssh/ssh_host_ecdsa_p521_key

The -b option specifies the number of bits to use for the key and 521 is the highest OpenSSH supports right now. The -o option saves the keys in a newer format that is more resistant to brute-force password attempts, but is not supported on versions of OpenSSH prior to 6.5. The -t option specifies the type of key to create. The -f option is the name and location for the new key-pair. The name specified is for the private key. The corresponding public key will also be generated in the same directory.

Now you are going to have to edit your SSH daemon configuration file in order to use the new key. Before making any changes, backup the original configuration

# cp /etc/ssh/sshd_config /etc/ssh/sshd_config.bak

Now let's take a look at the existing host keys that are configured

$ cat sshd_config | grep HostKey
# HostKeys for protocol version 2
HostKey /etc/ssh/ssh_host_rsa_key
HostKey /etc/ssh/ssh_host_dsa_key
HostKey /etc/ssh/ssh_host_ecdsa_key
HostKey /etc/ssh/ssh_host_ed25519_key

You'll have to add an entry for the newly created key. If you like to keep your config files organized, you can use your text editor of choice to add the new entry with the others. This will add a new line at the bottom of the file for the new key

# echo HostKey /etc/ssh/ssh_host_ecdsa_p521_key >> /etc/ssh/sshd_config

Restart the SSH daemon to make the changes take effect

# /etc/init.d/ssh restart

Now your OpenSSH server is ready to use the newly created key-pair.