Suppose you want to buy something on the Internet. You go to the website Gigafirm.com, select your items, and then proceed to the checkout page. You are asked to enter your credit card number and other information. The website assures you that it is using secure public key encryption, using Gigafirm’s public key, to set up the communications. But how do you know that Eve hasn’t substituted her public key? In other words, when you are using public keys, how can you be sure that they are correct? This is the purpose of Digital Certificates.

One of the most popular types of certificate is the X.509. In this system, every user has a certificate. The validity of the certificates depends on a chain of trust. At the top is a certification authority (CA). These are often commercial companies such as VeriSign, GTE, AT&T, and others. It is assumed that the CA is trustworthy. The CA produces its own certificate and signs it. This certificate is often posted on the CA’s website. In order to ensure that their services are used frequently, various CAs arrange to have their certificates packaged into Internet browsers such as Chrome, Firefox, Safari, Internet Explorer, and Edge.

The CA then (for a fee) produces certificates for various clients, such as Gigafirm. Such a certificate contains Gigafirm’s public key. It is signed by the CA using the CA’s private key. Often, for efficiency, the CA authorizes various registration authorities (RA) to sign certificates. Each RA then has a certificate signed by the CA.

A certificate holder can sometimes then sign certificates for others. We therefore get a certification hierarchy where the validity of each certificate is certified by the user above it, and this continues all the way up to the CA.

If Alice wants to verify that Gigafirm’s public key is correct, she uses her copy of the CA’s certificate (stored in her computer) to get the CA’s public key. She then uses it to verify the signature on Gigafirm’s certificate. If it is valid, she trusts the certificate and thus has a trusted public key for Gigafirm. Of course, she must trust the CA’s public key. This means that she trusts the company that packaged the CA’s certificate into her computer. The computer company of course has a financial incentive to maintain a good reputation, so this trust is reasonable. But if Alice has bought a used computer in which Eve has tampered with the certificates, there might be a problem (in other words, don’t buy used computers from your enemies, except to extract unerased information).

Figure 15.2 A Certification Hierarchy.

Figures 15.3, 15.4, and 15.5 show examples of X.509 certificates. The ones in Figures 15.3 and 15.4 are for a CA, namely VeriSign. The part in Figure 15.3 gives the general information about the certificate, including its possible uses. Figure 15.4 gives the detailed information. The one in Figure 15.5 is an edited version of the Details part of a certificate for the bank Wells Fargo.

Figure 15.3 CA’s Certificate; General.

Figure 15.4 CA’s Certificate; Details.

Figure 15.5 A Client's Certificate.

Some of the fields in Figure 15.4 are as follows:

1. Version: There are three versions, the first being Version 1 (from 1988) and the most recent being Version 3 (from 1997).

2. Serial number: There is a unique serial number for each certificate issued by the CA.

3. Signature algorithm: Various signature algorithms can be used. This one uses RSA to sign the output of the hash function SHA-1.

4. Issuer: The name of the CA that created and signed this certificate. OU is the organizational unit, $O$ is the organization, $C$ is the country.

5. Subject: The name of the holder of this certificate.

6. Public key: Several options are possible. This one uses RSA with a 1024-bit modulus. The key is given in hexadecimal notation. In hexadecimal, the letters $a\text{,}b\text{,}c\text{,}d\text{,}e\text{,}f$ represent the numbers 10, 11, 12, 13, 14, 15. Each pair of symbols is a byte, which is eight bits. For example, b6 represents 11, 6, which is 10110110 in binary.

   The last three bytes of the public key are 01 00 01, which is $65537=2^{16}+1$. This is a very common encryption exponent $e$ for RSA, since raising something to this power by successive squaring (see Section 3.5) is fast. The preceding bytes 02 03 and the bytes 30 81 89 02 81 81 00 at the beginning of the key are control symbols. The remaining 128 bytes aa d0 ba ⋯ 6b e7 75 are the 1024-bit RSA modulus $n$.

7. Signature: The preceding information on the certificate is hashed using the hash algorithm specified – in this case, SHA-1 – and then signed by raising to the CA’s private RSA decryption exponent.

The certificate in Figure 15.5 has a few extra lines. One notable entry is under the heading Certificate Hierarchy. The certificate of Wells Fargo has been signed by the Registration Authority (RA) on the preceding line. In turn, the RA’s certificate has been signed by the root CA. Another entry worth noting is CRL Distribution Points. This is the certificate revocation list. It contains lists of certificates that have been revoked. There are two common methods of distributing the information from these lists to the users. Neither is perfect. One way is to send out announcements whenever a certificate is revoked. This has the disadvantage of sending a lot of irrelevant information to most users (most people don’t need to know if the Point Barrow Sunbathing Club loses its certificate). The second method is to maintain a list (such as the one at the listed URL) that can be accessed whenever needed. The disadvantage here is the delay caused by checking each certificate. Also, such a website could get overcrowded if many people try to access it at once. For example, if everyone tries to trade stocks during their lunch hour, and the computers check each certificate for revocation during each transaction, then a site could be overwhelmed.

When Alice (or, usually, her computer) wants to check the validity of the certificate in Figure 15.5, she sees from the certificate hierarchy that VeriSign’s RA signed Wells Fargo’s certificate and the RA’s certificate was signed by the root CA. She verifies the signature on Wells Fargo’s certificate by using the public key (that is, the RSA pair $(n\text{,}e)$) from the RA’s certificate; namely, she raises the encrypted hash value to the $e$th power mod $n$. If this equals the hash of Wells Fargo’s certificate, then she trusts Wells Fargo’s certificate, as long as she trusts the RA’s certificate. Similarly, she can check the RA’s certificate using the public key on the root CA’s certificate. Since she received the root CA’s certificate from a reliable source (for example, it was packaged in her Internet browser, and the company doing this has a financial incentive to keep a good reputation), she trusts it. In this way, Alice has established the validity of Wells Fargo’s certificate. Therefore, she can confidently do online transactions with Wells Fargo.

There are two levels of certificates. The high assurance certificates are issued by the CA under fairly strict controls. High assurance certificates are typically issued to commercial firms. The low assurance certificates are issued more freely and certify that the communications are from a particular source. Therefore, if Bob obtains such a certificate for his computer, the certificate verifies that it is Bob’s computer but does not tell whether it is Bob or Eve using the computer. The certificates on many personal computers contain the following line:

Subject: Verisign Class 1 CA Individual Subscriber - Persona Not Validated.

This indicates that the certificate is a low assurance certificate. It does not make any claim as to the identity of the user.

If your computer has Edge, for example, click on Tools, then Internet Options, then Content, then Certificates. This will allow you to find the CA’s whose certificates have been packaged with the browser. Usually, the validity of most of them has not been checked. But for the accepted ones, it is possible to look at the certification path, which gives the path (often one step) from the user’s computer’s certificate back to the CA.