This is a problem, since however good the theories above are they all rely
on us being sure that the 
that we have really is Alice's public key
and not someone else's who we have been given on the pretence that it's
Alice's.
We can get round this problem by using fingerprints .. calculating the message digest of our public keys. It is a pain to quote public keys over the phone or even write them on bits of paper, but the fingerprint is ideal for this since it is much shorter. If we meet then we can give each other a copy of the fingerprint of our public key. We can then check this fingerprint with the copy of the public key we have. If the fingerprints match we can assume we have the person's real public key and we sign it with our own one. If we obtain someones public key from an untrusted source we can see who has signed this key. If someone we know or trust has signed it then we know we can trust the the public key really belongs to the person that it claims it does.
I use `gpg' which is a program that understands how PGP works. You can download it from http://www.gnupg.org. If you run windows you might prefer pgp itself. This is available from http://www.pgpl.org.
Here is my public key.
-----BEGIN PGP PUBLIC KEY BLOCK----- Comment: Key for stephen@earth.li mQGiBDhD7AARBADqXdex1iEqztnftxEEGoCsLE0DEVy0i/s92x8FChiIr993a767 z8QMNXF6tU479ic5RoLEivxzWiw45mmlAsMSqPcj3CICergi0L4GGpoovvcUnMGq 2UjNfyv6fupFgcqb6DRKa44kXOl3edvMOAzqrbZ7roCX0ICsFkJL1im/TwCg+WiK okrsB6kJ90pIz1ifajCeG30EAMzi7DMdGuyjpSCMg6YPCdA9I6QAb9c7k32naZyy Onxlxb9wDWtfr8HJXnmqevZV2o5Cz86LjxkREkVFKRSieg/NY1CCLNuOTzvNX/fO kwFiWc9rgJjXlX7EuieYLxBPuqfK9+DzcYUOJtuFlJ2TirKwQ/FT8O0+NQPWw/we 5gKCA/wLCxTlU+o2MrAptnu6k3hCg6P5jNSaAOP4N0ODWzOLXry1zpZlNvK/jjTk KOOCBXNQWdtXJNNybiepr0wuja2lqZ5R1Lgpu8vX42bbYE1EhwL9nM7Eb+VQL/fG hjVyj4bMEDbjH1s5jLTZpM1k4JVwv5dhOuKzCJDu6IuySuXT37QgU3RlcGhlbiBX aGl0ZSA8c3RlcGhlbkBlYXJ0aC5saT6IVQQTEQIAFQUCOEPsAAMLCgMDFQMCAxYC AQIXgAAKCRA7Ok8Kx55ban78AKCL0oc5kxcECZtSyTfHSLeZdTGJuwCguhLkEJn/ PO6GwvUQj0uAwAcrpXmJARUDBRA4Q/ktHUtPijd4cyMBAYpaCACPrhkGv2fgVSmm 9HEPfgeaR9CTLPVFqK7O+309H2oR/BCNRUc4HapbKtlxfdofYx63Ou/736sNGH2G wstB2oGybOac7taJHkia0lYhJwgpZQiWMwsUcdi2iKOg7DWVV42Leh7elVcr18Ef gGU/m0S5m1XQvKhrIYfStXdxYQRDAoHrZNq2E5E/4ZHlzlI6mlI7GITAOuhLVmJn HBN5IWMxawla/3wV1r4qrAvN+cWnoIiaUFTRHjAMfkSXaExwsvYILdVW6VwALWkq KJFUCvc78Z4/flQImQZGUsTZC+ZeV6yJZAret0Rbd1eQxwZnxpB7mQ2BgJWjIgR9 8DjuKLqjuQINBDhD7WQQCAD4nLAv9Lo+uxKgkiNY2q0ge56xPWMkX+YbCpStLxsI j+B/30DRXohVOjc6O8ic78mhHsT6eajCP0hLJKgjVECE1QKKlB2Q4J1vUwZoOw+t FGqrrQhdHAh+V0mIkwCFufJyf7SOu3aiikMF9iQNmxJW9Moj0lZJHauf+V0U/C3q XRxm9fJygmSeHJ/NH5xrtYTshRyDEM1cYqcUvdHe1Ji6GiUE/QeENQ9a8W09I0PV OV2NHlbDqX+qLYO9chNk3hXJ/XBqFmZ2VU1XjmBfrTDZ/Zkr8szDqqeKhvDvOgc3 B7Kg/GE/2KYgTaF8lE9/hF8tZOl/rvKmox+kcESYbuL3AAMFCACt8Fv/J1sYYihP ouVJfR5osmPBOn2hkohRRNUNlhBwQWgaYdUozGLrEj6bDpIrau1lp7qjLZmZeeNN fNedMnhNkzA5FVrTtIvTrADngfXF1kbd1k6XVleRCH056/fLaNDYEViTDOSdgetm z06+msuR3GpogRJYj4tTJ0C7fZ4Mf9H9YDbjUUhziUUdUMnHDf8tHSrs0d6JPBhW tINPkN8YronHGICBnnE9a+lw2PCmVhdO6meSvw6O6P4CnscRcN73nk9E37y/OxEk DCIQQwckAvjOYUVRhCGyRMcNj8absIqVPwu8Zf/YTgwZvdbF5K6ggY6Z0uxcKjuy VAujKUzZiEYEGBECAAYFAjhD7WQACgkQOzpPCseeW2qkdQCfU5ClIDJAMViROTwt vR+X8xlH1oQAnAumDhSY1WIKWBC34ztjapTCLEZy =5WR3 -----END PGP PUBLIC KEY BLOCK-----
Now suppose you've just downloaded this from a public server .. you wouldn't know whether to trust it or not.
[stephen@eddie encrypt]$ gpg --list-sigs stephen@earth.li pub 1024D/C79E5B6A 1999-11-30 Stephen White <stephen@earth.li> sig C79E5B6A 1999-11-30 Stephen White <stephen@earth.li> sig 37787323 1999-11-30 Stephen White <swhite@ox.compsoc.net> sig 80C83E8E 1999-11-30 Ian Lynagh (wibble) <ian@lynagh.demon.co.uk>
From this you can see that Ian Lynagh has signed my key. If you are happy that this is his signature (maybe because you've previously checked it's fingerprint) then you would know my key was valid.
Alternatively you could ask me directly for my key's fingerprint.
It is 622E 7813 45A9 C65B 4C41 DFD8 3B3A 4F0A C79E 5B6A
Now having written this down and gone back to your computer you type
[stephen@eddie encrypt]$ gpg --fingerprint stephen@earth.li
pub 1024D/C79E5B6A 1999-11-30 Stephen White <stephen@earth.li>
Key fingerprint = 622E 7813 45A9 C65B 4C41 DFD8 3B3A 4F0A C79E 5B6A
sub 2048g/1B77E62B 1999-11-30
The fingerprints match .. so you know that the public keys match and anything that has been signed by that key you know really came from me.