How to Set Up and Use SSH
How the SSH Connection Happens

How The Magic Happens

You can observe quite a bit of this by asking SSH to be verbose. For example:

$ ssh -v someserver date

If you are really interested in details, ask for very verbose narration:

$ ssh -vv someserver date

Here's an overview of what you're going to see:

1 — Your client host and the remote server authenticate to each other using public-key cryptography. Each host is certain that it has the other's public key, since the administrator stored all those in /etc/ssh/ssh_authorized_keys. Host #1 picks a random number and sends it to host #2 as a challenge. The host #2 encrypts that challenge with its private key to create the response, and sends it back to host #1. Host #1 decrypts the response using the public key of host #2 (which host #1 is certain that it has). If the result is identical to the challenge, then that must really be host #2 over there!

2 — The client and server negotiate a cipher and a session key. The cipher will be the strongest encryption algorithm that both hosts know. The session key will be generated with the Diffie-Hellman algorithm — see my "Just enough cryptography" page for details.

3 — User authentication happens. Now that the two hosts are certain of each other's identity, and they have negotiated a secure communication channel, the user can be authenticated. Cryptographic challenge-response authentication is tried first, as described above for hosts. Since we disabled password authentication on the server, that method has to work. If the user forgot to run ssh-add, they get mysterious remote authentication failures. So either train your users to always run ssh-add, or else put something in a startup file to force them to do this.