What does it mean for a digital certificate to be "signed"?

Ideally, it means that someone looked at the certificate and decided that it is correct and legitimate. Once they've done that, they want to tell people "Hey, I've verified that this certificate is good. I trust it". To do this, they use their signing key to sign the certificate.

Now when someone gets the certificate they can see who signed the certificate. If they trust one of the signers, they can trust the certificate itself. This is the basis of Web Of Trust in PKI.

The actual signing probably depends on what kind of certificate it is. I think this is a useful read.

A digital certificate consists of three things:

• A public key.
• Certificate information. ("Identity" information about the user, such as name, user ID, and so on.)
• One or more digital signatures.

Typically the "one or more digital signatures" part is done by listing a set of encrypted hashes of the certificate. So when you want to sign a certificate, you would compute the hash of the certificate, encrypt it using your private signing key, and add it to the cumulative list of digital signatures.

Here is the structure of an X.509 certificate:

    Certificate  ::=  SEQUENCE  {
        tbsCertificate       TBSCertificate,
        signatureAlgorithm   AlgorithmIdentifier,
        signatureValue       BIT STRING  }

   TBSCertificate  ::=  SEQUENCE  {
        version         [0]  EXPLICIT Version DEFAULT v1,
        serialNumber         CertificateSerialNumber,
        signature            AlgorithmIdentifier,
        issuer               Name,
        validity             Validity,
        subject              Name,
        subjectPublicKeyInfo SubjectPublicKeyInfo,
        issuerUniqueID  [1]  IMPLICIT UniqueIdentifier OPTIONAL,
                             -- If present, version MUST be v2 or v3
        subjectUniqueID [2]  IMPLICIT UniqueIdentifier OPTIONAL,
                             -- If present, version MUST be v2 or v3
        extensions      [3]  EXPLICIT Extensions OPTIONAL
                             -- If present, version MUST be v3
        }

The data contained in the certificate itself is the TBSCertificate part: it binds the public key (subjectPublicKeyInfo) to an identifier (the subject), and various other attributes extensions).

This is then combined with the signature to form a Certificate structure. The signature algorithm dictates how this should be done.

Essentially, a digest of TBSCertificate (typically SHA-1) is computed and then signed with the private key of the signer (the issuer in X.509 terms). The slightest modification of the TBSCertificate content should make the digest change, which should in turn invalidate the signature.

Using RSA keys, the signing of the digest using the private key is mathematically very similar to what would be done for encryption using the public key. This is not the same conceptually, though, and DSA doesn't have that reciprocity, for example.

The principle is the same for other types of certificates, although the structure may differ. Considering that PGP public keys are in fact certificates, you may be interested in these questions too:

• What does key signing mean?

• What is an SSL certificate intended to prove, and how does it do it?

When someone says that a particular digital certificate (like an SSL cert) has been "signed with a key", what does that imply?

It implies that the entity owning that key has vouched for the accuracy of the information in the certificate and has attached information to the certificate that permits that vouching to be verified.

Does that mean the certificate simply includes a key that should be used for further message exchanges?

No. Certificates only prove identity.

Does that mean that the cert itself is encrypted and can only be decrypted with that key?

No. There's no reason to encrypt certificates, they only contain public information.

Does it imply something else?

It implies that the owner of that key has vouched for the information in the certificate. For a typical SSL certificate, the information in the certificate is a binding between a public key and a common name.

For example, when you point your browser at https://www.amazon.com/ Amazon's server will send you a certificate. This certificate binds a particular public key to the name www.amazon.com. Your browser confirms three things to know it is talking to the real Amazon:

1. The server presented a certificate that was valid and signed by a key it trusts.

2. The certificate binds the identity "www.amazon.com".

3. The server proves it possesses the private key corresponding to the certificate.

So the purpose of the certificate signature is to put the signing agent's credibility behind the information in the certificate which is fundamentally "this guy owns this key".