Given an asymmetric encryption algorithm E and accompanying Decryption algorithm D. It uses a key pair (K_e, K_d) to encrypt a plain text message x into a cipher text y.

Suppose Alice and Bob want to exchange encrypted messages with each other, and they also want to sign the messages so that they can be sure the messages they receive are from each other indeed, and not from some malignant third party.

Alice owns two key pairs.

Alice publishes the keys K_A1e and K_A2d.

Bob thas two key pairs as well:

And he publishes K_B1e and K_B2d.

The keys that are published are called public keys, the ones you keep for yourself are called private keys.

Key pairs are kept in a keystore. Trusted public keys, or the certificates thereof (see below), are kept in a truststore.

Bob can now send an encrypted message to Alice using her public encryption key K_A1e with

E(K_A1e, x) = y

Which can only be decrypted by Alice with her private decryption key K_A1d

D(K_A1d, y) = x

And vice versa Alice can send encrypted message to Bob using the public key K_B1e from Bob.

Bob can use his private signing key K_B2e to sign his encrypted messages.

Given a hashing algorithm H

h = H(y) = hash of y

Next define

s = S(y) = E(K_B2e, H(y)) = signature

Bob sends (y, s) to Alice.

Now Alice can verify the cipher text y is from Bob by applying the verify operation V using Bob’s public verification key K_B2d

V(s) = D(K_B2d, s) = h

And she can also calculate h herself from the received y. Both hashes must be equal. Since only the owner of K_B2e could have sent the signature s encrypted in this way she knows this message is from Bob.

NB The same is true if Bob had signed the plain text x instead of the cipher text y. The choice is somewhat arbitrary. Albeit, that signing the cipher text y is a bit safer. Because when signing x and Alice’s private key has somehow been acquired by a malignant third party Mallory, Mallory can decrypt y and reencrypt it with his own private key and reuse the signature. When y is signed, he cannot reuse the signature.

Vice versa Alice can sign her message to Bob using her signing key K_A2e.

What if Alice and Bob have no secure channel to exchange their public keys? Well suppose they do both have a secure channel with a third party CA (Certification Authority) whom they trust, which means they trust the CA’s public verification key K_CAd. They offer their public keys to CA to have them signed.

For example Alice offers her public encryption key to be signed by CA

S_CA(K_A1e) = E(K_CAe, H(K_A1e)) = s_A1e

And Alice publishes

c_A1e = {K_A1e, S_CA(K_A1e)} = {K_A1e, s_A1e} = certificate of K_A1e signed by CA

Bob can now verify the key is from Alice by calculating

V_CA(s_A1e) = D(K_CAd, s_A1e) = h_v

and

H(K_A1e) = h

The following should be true: h_v = h

The same can be done for the other public keys of Alice and Bob. So by publishing certificates of their public keys instead of the keys alone they can safely exchange messages without having a secure channel to exchange their public keys directly.

For convenience CA does not publish its verification key alone, but a self-signed certificate of it

c_CAd = {K_CAd, S_CA(K_CAd)}

Above is an example of a chain of trust. Alice and Bob trust CA. This a chain of length 2. Longer chains are more common. For example when Alice and Bob use a certificate from CA₂, which is signed by CA₁, which is signed by a self-signed certificate of CA₀=CA_root. They both trust CA₀, and Alice has her keys signed by CA₂. For example the chain for her public encryption key:

c_A1e = {K_A1e, s_A1e} = {K_A1e, S_CA2(K_A1e)}

c_CA2d = {K_CA2d, s_CA2d} = {K_CA2d, S_CA1(K_CA2d)}

c_CA1d = {K_CA1d, s_CA1d} = {K_CA1d, S_CA0(K_CA1d)}

c_CA0d = {K_CA0d, s_CA0d} = {K_CA0d, S_CA0(K_CA0d)}

So Bob trusts the public encryption key of Alice, K_A1e, because it is signed by CA₂, which is signed by CA₁, which is signed by CA₀, which he trusts.

It is common practice to send the entire chain upon publishing/sending of one’s certificate. So usually one keeps the entire chain for each certificate in one’s keystore. Since the public key is part of the certificate a keystore usually contains entries with in it a private key and the associated certificate chain.

The certificates one trusts are kept a so called truststore. The sender’s chain of certificates must end at a certificate in one’s truststore.