I have server which I am accessing via SSH. I only allow the authentication to be made with private key. Normally when I login via PuTTY, I am first asked for username and then asked for passphrase for the key. Out of curiosity I have created new private key, which should be invalid for my user and I also have put passphrase on it. To my surprise once I provided the user name the key attempted to login with to my server was refused before I have been asked for the passphrase.
I am wondering how can SSH server know that the private key is incorrect if the passphrase for it haven't been provided yet?