Public key authentication works by creating a key pair. One of the keys is public, the other must remain private. Anything encrypted with one key can only be decrypted with the other. Thus, for other to send messages to the owner, they only need to know the public key. After they encrypt their message, only the recipient can reconstruct it. In the same way, only a message encrypted using the private key of a key pair, and therefor by the pair's owner, can be decrypted by the public key. Thus, everyone can verify whether the message really originated from him.

PublicKeyAuthentication exploits this to avoid having to send passwords over a network. Instead, your public key is copied to the machines you want access to. When a machine needs to verify your identity, it sends you a block of random data and asks you to sign it, then it checks whether it can be decrypted with your public key. Because only the person with the matching private key can generate valid encrypted replies, the machine can then be certain of your identity. The machine usually identifies itself the same way. Should the machine be compromised, it is still impossible for an attacker to pretend to be you, because they can grab your public but not your private key, which was never transmitted.

The way this magic works is clever math. In a lot of situations going one way is easy (like multiplying together two large prime numbers a x b = c) but reversing the operation is much harder (finding the two prime factors of the number we just generated). In another class of algorithms, a parameter c is used to mangle data using a function that appears to be one way and doesn't even allow recostructing the original message with knowledge of c. However, there are correlated parameters a and b (that are kept secret) which make it possible to reconstruct the message using a different function.

The maths involved is still complicated, CPU intensive, and not as secure as conventional cryptography. In practice, therefor, PublicKeyAuthentication is used to transfer the key for a conventional symmetric cryptographic algorithm used to encrypt the actual message sent.