A autenticação por desafio resposta no ssh deve estar habilitada no ssh server. Por minha experiência, todos os servidores ssh já vem com isto habilitado, mas convém verificar. Apenas verifique se a informação PubkeyAuthentication no /etc/ssh/sshd_config não está em "no". Normalmente ela está comentada no arquivo, o que significa que está ativa (o padrão é permitir):

# grep Pubkey /etc/ssh/sshd_config
#PubkeyAuthentication yes

Se ela estiver comentada ou com "yes", tudo bem. Mas se estiver com "no", comente a regra ou mude para "yes" e reinicie o ssh server.

Com o servidor configurado para aceitar esta forma de autenticação, deve-se ainda realizar os seguintes passos:

1. criar um par de chaves
2. instalar a tua chave pública no servidor

Usarei o usuário fulano como teste neste artigo.

Criação do par de chaves

Usuário fulano tem um login e senha no servidor 10.2.3.4. O cliente é a máquina didaké (nome do meu notebook). Primeiro ele se logou com seu usuário e senha, só para testar:

ssh 10.2.3.4
The authenticity of host '10.2.3.4 (10.2.3.4)' can't be established.
RSA key fingerprint is fb:a9:ac:b6:3d:3f:42:76:11:cc:44:2f:7f:55:49:97.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added '10.2.3.4' (RSA) to the list of known hosts.
Password:
Have a lot of fun...

Voltando a máquina cliente, a didaké, ele cria seu par de chaves com o ssh-keygen. Os parâmetros indicam criar chaves usando o algoritmo dsa e com 1024 bits de tamanho. Se você não especificar o DSA, o algoritmo RSA será usado. O protocolo RSA não é usado por padrão no ssh e não funcionará a menos que você coloque o parâmetro RSAAuthentication yes no /etc/ssh/sshd_config. Este é desabilitado por padrão.

ssh-keygen -b 1024 -t dsa
Generating public/private dsa key pair.
Enter file in which to save the key (/home/fulano/.ssh/id_dsa):
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in /home/fulano/.ssh/id_dsa.
Your public key has been saved in /home/fulano/.ssh/id_dsa.pub.
The key fingerprint is:
4e:e4:ab:5c:5d:06:58:83:95:4a:77:1d:a0:7d:e7:ba fulano@didake
The key's randomart image is:

+--[ DSA 1024]----+ 
|         o+..o.. | 
|        ooo+. .  | 
|       .ooo.. . .| 
|       o.  . . o | 
|        S   o   .| 
|       o o o   . | 
|        + .   .  | 
|     . o       . | 
|      o       E  | 
+-----------------+ 

Quando ele perguntar "Enter file in which to save the key (/home/fulano/.ssh/id_dsa): " simplesmente dê um enter aceitando esta sugestão.

Como frase de passagem eu coloquei "Viva o Linux 2009". Pode ser qualquer coisa, mas tome cuidado pois você deve digitar exatamente a mesma coisa quando solicitado. Se digitar "Viva o LINUX 2009" já não será a mesma frase, pois Linux está tudo em caixa alta. Desaconselha-se deixar sem frase de passagem, mas é uma configuração possível.

Instalação da chave pública no servidor

A instalação da chave pública no servidor consiste em simplesmente colocar ela dentro do arquivo ~/.ssh/authorized_keys. Este arquivo pode ter várias chaves públicas, não apenas uma.

Para realizar esta tarefa o usuário fulano precisará logar-se no servidor, usando ainda sua senha. A chave pública criada está em ~/.ssh/id_dsa.pub no cliente e home do fulano. Ela é texto puro (base64) logo pode-se até dar um cat nela:

cat id_dsa.pub
ssh-dss AAAAB3NzaC1kc3MAAACBAKaOHlNYzozRRr0Ub1kAi/mBap55fQCda0t4T4rZnskdqX /gMnKvLP8B514b3Oq8exNCkTym6nyv1LyxxG1VmhpjKN8N8eDaErp/8qEif/GvH3HaFx4GJBWFed4Z6K9HkxsBy2yFwfcBmkvGFP3ggMwhBnKYFf7DSa9/0QzHDDx3AAAAFQDEb5c3RMsEo8xU6YsvVXnIlJteLQAAAIA+3Oa2X2oW2gprZkCRe7JE +KWvH+O9xjep/7l6iGFww9IDj35VgEHMzAr6LPvw+rAOB1P5qoXZr3hbTU6pzfHiSLy6UD G+LzHLRbyImZOH/p+n7hWtEfZs6mO5ZuJFxO3fStQKWy0r48XUEaduHY5PGQc+sa/fpjyS2BPToM46XgAAAIAzsUHfOZnFhGK5cmMGjEFyjQBIKqYxRo3pR2H0au/ObwrKan6rCEqWropJElI234AeIymOS2h4Hr3lHnbmyXsxxCt14xqE7ZQlq5X7DV2QCl 0PUcgGlbVSLNTGLXapW1KN2tiBv7u8Q0agNgZ3ek3XHTKtZ6jVm0eb/ACsg0D+Sw== fulano@didake

Não faça o mesmo para a chave privada, pois ela não é em formato texto, é binário.

Então, basta pegar esta sequência esquisita de caracteres e copiá-la, assim como está, para o servidor. No Gnome pode-se até mesmo usar o recurso de copiar e colar do sistema, como demonstra a sequência de imagens. Selecionando a chave pública no cliente, arquivo ~/.ssh/id_dsa.pub e usando o "Copy" do próprio Gnome. Após, loga-se no servidor 10.2.3.4 ainda usando sua senha, e coloca-se a chave dentro do arquivo authorized_keys em ~/.ssh. No caso eu usei o simples cat com redirecionamento (cat >> authorized_keys). Ao final, após colar, deve-se pressionar Control+D e o arquivo está com a chave pública. Na imagem, após o término, executei um cat para verificar.

Outras tantas formas podem ser usadas para obter-se o mesmo resultado, como simplesmente editar o arquivo authorized-keys com algum editor qualquer. O fato é que ele deve ter a chave pública.

Por fim, após a instalação, pode-se verificar se está funcionando. fulano sai do servidor e tenta-se logar novamente:

ssh 10.2.3.4
Enter passphrase for key '/home/fulano/.ssh/id_dsa':
Last login: Mon Jul 27 13:40:02 2009 from 10.1.0.10
Have a lot of fun...

Agora ele pediu a frase de passagem que protege a chave pública. No caso eu tive que digitar o "Viva o Linux 2009" para poder me logar.