The client (Computer 3) does have access to the public key
You are perhaps confusing a private key file with a private key.
When you generate a public/private key pair, most implementations will create a private key file which contains BOTH the private and public key.
Many implementations also write public key to a file separately for convenience.
According RFC 4252 Section 7 the public key is supplied by the client during authentication. Therefore your client MUST have it available.
With openssh's ssh-keygen
you can extract the public key from your private key file:
ssh-keygen -y -f ~/.ssh/id_rsa
The authentication mechanism
https://www.rfc-editor.org/rfc/rfc4252#section-7
Before the client tries to login, it may first check to see what would be acceptable. This check can include sending public keys matching its available private keys and thus allows the server to indicate which public/private key to use.
... the signing operation involves some expensive computation. To
avoid unnecessary processing and user interaction, the following
message is provided for querying whether authentication using the
"publickey" method would be acceptable.
byte SSH_MSG_USERAUTH_REQUEST
string user name in ISO-10646 UTF-8 encoding [RFC3629]
string service name in US-ASCII
string "publickey"
boolean FALSE
string public key algorithm name
string public key blob
Then it attempts to login
To perform actual authentication, the client MAY then send a
signature generated using the private key. The client MAY send the
signature directly without first verifying whether the key is
acceptable. The signature is sent using the following packet:
byte SSH_MSG_USERAUTH_REQUEST
string user name
string service name
string "publickey"
boolean TRUE
string public key algorithm name
string public key to be used for authentication
string signature
Notice that this includes both the public key and a signature generated with the private key. The public key is helpful to the server SSH where it has many "authorized keys"; the server doesn't have to test the signature against each one.
Unlike some similar algorithms, SSH doesn't use a challenge-response. That is it doesn't use a four step (1 client initiate, 2 server challenge, 3 client sign, 4 server verifies) it performs a two step:
- Client signs the session identifier (Ie: a hash produced by the earlier DH Key Exchange)
- The server then verifies that:
- The the specified public key is acceptable (in the user's authorized keys)
- Decrypting the signature with the specified public key, produces the session identifier
Why are some people confused about this?
The technique of public / private key authentication doesn't need the client to hold the public key. The client just needs to write a signature with the private key. The server just needs to check the signature with the matching public key.
However SSH allows a client to have many private keys and the server to have many authorized keys for a user. If a client had 10 keys and the server accepted 10 keys but only one pair of them matched, the client would have to send 10 signatures and the server would have to check each against 10 keys (100 checks in all). This is computationally expensive. SSH instead can handle the same situation with just a single signature check.