I'm studying for my LPIC exam and I'm trying to completely understand how SSH and key pairs work. I'm starting to wrap my head around it, but there is one piece which is fuzzy to me..

When a client connects to a server for the first time using SSH, I know that the client will prompt that the authenticity of the host can't be established. If you agree to connect any ways, the server's hostname, encryption type and public key are added to the clients "known_hosts" file. Next time, it won't prompt.

I get that much, but what exactly is happening? That first time I connect, I know that the public key is sent, but when you connect again going forward, does the server simply send the public key again and the client compares it to the data in the known_hosts file everytime, OR does it actually use the server's public key to decrypt a digital signature of sorts sent by the server (which was encrypted using the server's public key) in order to establish the authenticity of the host?

Sorry if this question is a bit confusing. Let me know if I need to clarify.

Thanks.

First read these documents and ask if something is still unclear

http://winscp.net/eng/docs/ssh_keys
http://ubuntuforums.org/showthread.php?t=1689052
https://wiki.archlinux.org/index.php/SSH_keys

Hmm, I think this thread is more to the point for what you are asking.

Especially this part here:
To me this means that yes, the server actually must prove that it owns the private key associated with the public key you are sending to him...