A Public Key Infrastructure can be used not only to enable parties to exchange confidential messages even when they have no shared secret, but it also makes it possible for them to ensure that those messages are unaltered and authentic. In fact, authentication is actually much more robust using PKI than using techniques based on symmetric cryptography because each person has a secret that only they know (in theory) and we can craft our system to exploit that fact.
Let's say that Alice wants to send Bob a message. For this particular message, she is not concerned whether or not other people can read it (in other words, she is not concerned about message "confidentiality") but she is concerned that someone else might either alter her message (i.e., she is concerned about message "integrity") or send an entirely different message while claiming it is from her (i.e., she is also concerned about message "authenticity"). Let's explore how a Public Key Infrastructure (PKI) and digital signatures help address both of these concerns.
First, let's be sure we understand our starting point. Alice and Bob have never met and have never exchanged any information before. However, we will assume that both Alice and Bob have had some previous interaction with Trent, who is a trusted third party. It's important to note that their interactions with Trent did not involve the other party, by this we mean that Alice's interaction with Trent did not involve any information that was specific to Bob and vice-versa. As we shall see it turns out, for this example, that only Alice has to have had a prior interaction with Trent, Bob's interaction with him could occur later.
Let's walk through a message exchange and identify and fix each problem as it crops up.
Alice transmits her message to Bob as a simple plaintext message.
Q: What could dastardly Mallory do?
A: He could fabricate or modify messages from Alice.
Q: How could we at least make life harder for Mallory?
A: We could prepare and pre-transmit a Message Digest.
A message digest is a string of bits whose values depend on every bit of the message. If even a single bit of the message is altered, the message digest looks completely different in ways that are unpredictable. Ideally, the digest is a random function wherein a random number is assigned to every possible message. The only constraint is that a given message will always produce the same random number. A consequence of using a random function is that, given a message digest, it is impossible to construct a message that will produce that digest (except via brute force trial and error). Keep in mind that terms like "impossible" are referring to the ideal case or the goals of the algorithm - in practice they may or may not be achievable.
Armed with this, Alice could take her message, compute the message digest, and then transmit first the message digest and second the actual message. Assuming that the digest got through, then when the actual message arrives Bob can generate a message digest and compare it to the one he previously received. If it doesn't match exactly, he assumes that the message has been tampered with. Sounds good, but how good is our assumption that the digest was received intact? Pretty tenuous, given that we are already assuming that Mallory has the ability to intercept, alter, replace, or fabricate messages that on the surface appear to come from Alice.
Q: Why couldn't Mallory just fabricate a message digest as well?
A: He could. We need to somehow tie the message digest to Alice's identity.
We can tie the message digest to Alice's identity by involving her private key in the process.
Alice has a public/private key pair and has paid to register her public key with Trent, our trusted third party. As part of the registration process, Trent made Alice prove her identity via a process that is very hard to circumvent. He probably went well beyond just requiring that she show a driver's license. He may have sent someone to interview her employer, her neighbors, her relatives, her high school classmates, etc., before accepting her registration. He probably made her show up in person with multiple forms of I.D. and collected copies of them, photograph, her physical signature, and her fingerprints for his records.
Trent has a vested interest in taking such steps because his entire livelihood is based on trust - if someone comes up to him in the future with Alice's public key, they are going to accept as fact when Trent says, yes, that is Alice's public key. Someone can also go to Trent asking for Alice's public key and they will accept, as fact, that the key they are given is Alice's public key. If it turns out that Mallory managed to trick Trent and posed as Alice in order to register a false public key under Alice's name, then Trent's credibility will be severely damaged and he may never overcome it.
So now Alice takes the message digest and encrypts it with her private key (which only she can do because she is the only one that has ever had access to her private key - even Trent has never seen it). This is known as "signing" the message and the encrypted digest is known as the message's "digital signature". She can now simply append the digital signature to the message and transmit it. When Bob receives it, he will take the digest and decrypt it using Alice's public key. This is known as "unsigning" the message. He also generates a message digest of the received message and compares it to the unsigned digest that was included with the message. If they agree, then Bob knows two things with an extremely high degree of confidence: (1) the message has not been altered, and (2) the message originated from Alice. In other words, it has both integrity and authenticity.
Q: How does Bob get Alice's public key?
A: He could get it from Trent, from a public database, or from Alice herself.
Bob's best course of action is to get it from Trent directly. If that isn't possible, then he could find a public database (or several of them) that list Alice's identity and public key. If he can find several major and well known sites that all have the same information, it is very unlikely that Mallory has corrupted all of them. But if Bob can't go to Trent, it is also very likely he can't access the public databases, either. At least not at the present time. Furthermore, finding a public database that specifically includes Alice may be easier said than done unless Alice is a very famous entity. Knowing this, Alice was considerate enough to include her public key with the message so that Bob doesn't have to look anything up.
Q: Why couldn't Mallory forge a message from Alice by simply including a false public key.
A: He could, unless Alice includes a public-key certificate signed by Trent.
At the same time that Alice registered her public key with Trent, he prepared a document that included Alice's identity information and private key (plus a lot of other things that are not relevant to this basic example) and then he prepared a message digest of that and signed it with his private key. This is known as Alice's public-key certificate. Alice can attach her certificate to any message she has signed. Then Bob can first takes the certificate and unsigns it using Trent's public key to get Alice's public key. Remember that Trent is a trusted third party and so Bob accepts this as Alice's actual public key and then proceeds as before.
Q: How does Bob get Trent's public key?
A: He probably already has it, otherwise he can get it the same way he got Alice's, only better.
If Bob also registered his public key with Trent, then Trent provided him with a public-key certificate of his own and also with Trent's public key. Also, unlike Alice, Trent is a widely known entity and finding his public key is trivially easy because it is in thousands of places. In the real world, the company Verisign is perhaps the largest CA ("certificate authority," i.e., "Trent"), and their public keys are hardwired into most Internet Browsers including Netscape and Internet Explorer (hence the "he probably already has it" claim).
Q: Can this be made less cumbersome for Alice and Bob?
A: Yes. Alice and Bob may not even be aware that all of this is going on.
When someone uses an internet browser such as Internet Explorer to visit a secure web site (https://) the browser requests the Verisign certificate from the website and, using the public keys hardwired into the browser, verifies the identify of the website including that it is using the same Domain Name Server that is indicated in its certificate. A session key exchange then takes place so that the person and the website can communicate confidentially for the remainder of the session.
Organizations can also be certificate authorities for their own members. So when someone is issued a Common Access Credential (CAC) card, their top level organization embeds the person's private key (without saving the private key anyplace else, although the person must take this on faith) in the card and also their public key certificate and the public key of the top level organization. This CAC card can now be used to authenticate traffic between members without the need to check with the CA for every new transaction.
Q: Is it really that simple?
A: No. Of course not. The real world is never that accommodating.
Any real world PKI system has to be able to deal with failures and flaws in the system.
What if someone loses their CAC card? Generally the private key is not stored on the card in the open. It is encrypted and to get access to it the person has to enter a Personal Identification Number (PIN). The PIN numbers are usually pretty short and easy to remember and, hence, not very secure. But the card itself will only permit a limited number of wrong guesses (like three) before it erases the private key and locks up the card. Of course, if Mallory has Alice and a rubber hose in addition to Alice's card, three guesses is probably more than sufficient. The system isn't perfect.
The certificates usually also have lifetimes embedded in them and have to be periodically reissued. The CA generally also maintains a "revocation list" that people are expected to download periodically that is a list of certificates that are to be ignored even though the expirations dates in them haven't expired yet.
Most of this can be made automatic and transparent to the User provided they have reasonably frequent access to the Internet (or whatever network manages their PKI system).