OK, the answer so far are fundamentally on track, but I'm going to try to take your questions as they came in:
A public key is part of a two key pair used in assymetric cryptography. There are many encryption algorithms out there, but boils down to a public key and a private key which are mathematically linked. They can be used this way:
Encrypt(private key, original data) -> encrypted data
Decrypt(public key, encrypted data) -> original data
The nature of the mathematical relationship between private and public key are related to the cryptographic algorithm and quickly become a good topic for Math Overflow. )
The pivotal part is that their is a pair of keys that were generated together.
Next, to deal with a digital signature, the sender sends:
- the original data, the encrypted data, the public key, and information about how to verify the signature (for example, what algorithm is being used)
The verifier performs the Decrypt operation above and compares his output with the original data. If the two are the same, he knows that the message was not tampered with, because only the sender has the private key, and there is no reasonable way to determine the private key from the public key.
taking this a little bit out of order.
Anyone can make a private/public key pair. It's a pretty easy task, given today's toolkits. So giving you my public key, along with the encrypted data and signature as described is just about as trustworthy as giving you a business card that I had printed at Staples for $50. To really trust that I am who I say I am, and am therefore trust worthy, you need someone to sign off on my identity (like checking a driver's license).
That's the Certificate Authority's job (CA for short). The CA has it's own key pair - and it uses it's private key to sign a digital certificate for the key holder. The certificate includes the public key. as well as a bunch of information about the person or thing holding this private key. This is like my government making me a nice looking id with a picture that can't be easily faked without special equipment - you can believe my information because you trust the government. no because you trust me.
Usually when a system verifies a signature, it not only checks that the encrypted data matches the original data, but also that a certificate that vouches for the identity of the public key holder is also properly signed by a trusted source. Usually CA systems are organized in chains
of CAs that originate from a Root. A collection of the more prominent root CAs (which are self-signed, ie, signed by their own private keys), can be found in your browser.
For highly secure systems, additional checks of up to the minute status information can be performed. It all depends on how important it is to be absolutely sure of the sender's status.
Double checking here - do you mean the receiver of the certificate or the holder of the key?
The sender (key holder) can get a key pair and a certificate in a variety of ways. The simplest way is to make them locally, and then apply to the CA for a certificate, submitting the public key data. In other cases, keys may be made centrally and distributed by secure channels to the key holders.
In most signature cases, the key pair are made by the key holder, because it limits the potential that the private key is exposed.
When a signature is created and sent to a recipient, it is typical for the public key to also be attached to the message (for example, a standard for this is XMLDSIG where one optional field in the element is a digital certificate, which includes the public key).
In cases where bandwidth is an issue, the public keys may be held in a central repository - like an employee database, or often an Active Directory or other LDAP server. Then the signature can reference the sender's identity and the verification process can include a request to the repository to retrieve the public key.
Usually through a digital certificate.
When the sender goes to create a digital signature, he typically has rules associated with what key pairs he can use for what purposes. In the X509 certificate standard, certificates identify a Key Usage field that spells out specific purposes for the key pair described by the certificate. One of those uses happens to be Digital Signature, and many software systems won't let you create a signature without that setting in the certificate.
The CA actually determines these settings before it signs the certificate. In many security policies, certain key usage settings cannot be granted without specific authentication processes, so the responsibility for figuring this out rests on the CA and the people in charge of it (typically RAs, Registration Authorities).
If, for some reason, you have a system that does not use digital certificates, there may be other ways to determine what key pair. In the end it comes down to the security policies in place and what is deemed appropriate for the given activity that required the signature.