GPG, the only system I'm familiar with, makes you find a user's public key, import it, and mark it as trusted (by signing it). You don't have to share the signature if you don't want to.
Encryption with one of the keys public/private key pair is always decrypted with the OTHER key.
So in your example, if the mailserver has everyone's public keys, then anyone can send a message to anyone encrypted with my public key. Only I (the user with both the private key AND the password) can decrypt that message.
Now if I encrypt something with my private key and password, anyone can decrypt that message with my public key. The idea is that only I could encrypt a message with that key, so it's called a "signature." (Usually you send a copy of the message in plaintext but you don't have to.)
EXAMPLE:
So if I want to send you a message that only you can read and want you to be fairly sure only I could have sent it, I would encrypt my message with my private key/password, and then encrypt it with your public key.
You would decrypt it with your private key & password, so that only you could read it, and then you would decrypt it with my public key, so that you were reasonably sure it came from me.
We would also have to arrange one last step - that you and I had talked before so that you were sure my key was mine and your key was yours. Usually a phone call works for that too, depending on your standards.
(I say "reasonably" sure because someone could steal my key and threaten me with jail/beat me with a rubber hose for not sharing my password, but that's another problem for another question.)
My public key is very easily located by my email address (and you will see "Benanov" in the comment field / username field, I forget which). Feel free to send me a message if you want to test this.
3Technical note: When signing, you don't "encrypt" the entire message, but rather a digest (aka hash) of it; usually SHA-1 or similar. – user1686 – 2011-05-26T15:55:36.777
Thanks! I take it if you have an email account at broam@example.com, and I've never written you before, the finding of your public key entails my email client contacting the email server at example.com, requesting, and getting your public key, all unencrypted (since I have no public key yet) and encrypting & sending my email to you after I have it. – mring – 2011-05-26T16:11:38.737
In my specific case, my pubkey is on keyserver.ubuntu.com and has a gmail address listed on it. There's nothing that says you have to store the key on the mailserver. – Broam – 2011-05-26T17:15:18.297
@Pete: At least in the case of PGP (GPG), the location of a public key is not necessarily related to the email addresses attached to it. Usually keys are found by looking up the email address in a well-known "keyserver" -- the SKS Keyservers pool is the most common location. (Some people do have PKA or CERT records in DNS (for example, my key for
grawity@<mydomain>
can be found atgrawity._pka.<mydomain>
in DNS), but this is relatively rare and in no way tied to the "email server", just to the domain name.) – user1686 – 2011-05-27T10:35:00.347