How does SSH public key authentication work (picking up right keys)

Question

As far as I know about SSH authentication and according to many of explanations with Alice and Bob, there is some major steps:

1. Client generates a pair of public/private keys and publishes public key to a server.
2. When server receives a public key authentication request, it generates a random data, encrypts it with client's public key and sends it to client.
3. Client decrypts this data with the private key and sends it back as a proof of authenticity.

I hope some of you help me to understand how then GitHub server knows which public key to pick in step 2 when I clone arbitrary repository over SSH protocol? It has millions of user public keys to choose from. And a user could have installed a number of private keys on his machine.

Answer 1

The protocol is bit a more involved than you think. The manpage describes that the client tells the server which key it wants to use:

The file ~/.ssh/authorized_keys lists the public keys that are permitted for logging in. When the user logs in, the ssh program tells the server which key pair it would like to use for authentication. The client proves that it has access to the private key and the server checks that the corresponding public key is authorized to accept the account.

The relevant SSH rfc details that the client actually sends the whole public key with a SSH_MSG_USERAUTH_REQUEST request.

With the public key github should be able to look the corresponding user in the majority of cases. I don't know what happens when two accounts share a key, though.