Digital Signatures and Public Key Encryption

This document seeks to provide a brief introduction to digital signatures, in particular using public key encryption. This is by no means an in-depth analysis of different digital signature systems.

What is a digital signature?

A digital signature is the electronic equivalent of a handwritten signature, verifying the authenticity of electronic documents. In fact, digital signatures provide even more security than their handwritten counterparts.

Some banks and package delivery companies use a system for electronically recording handwritten signatures. Some even go so far as to use biometric analysis to record the speed with which you write and even how hard you press down, ensuring the authenticity of the signature. However, this is not what is usually meant by digital signatures — a great relief to those of us with limited budgets and resources.

More often than not a digital signature uses a system of public key encryption to verify that a document has not been altered.

What is public key encryption?

Public key encryption (PKE) uses a system of two keys:

• a private key, which only you use (and of course protect with a well-chosen, carefully protected passphrase); and
• a public key, which other people use. Public keys are often stored on public key servers.

A document that is encrypted with one of these keys can be decrypted only with the other key in the pair.

For example, let's say that Alice wants to send a message to Bob using PGP (a popular public key encryption system). She encrypts the message with Bob's public key and sends it using her favorite email program. Once the message is encrypted with Bob's public key, only Bob can decrypt the message using his private key. Even major governments using supercomputers would have to work for a very long time to decrypt this message without the private key.

What does PKE have to do with digital signatures?

Digital signatures often use a public key encryption system. Consider Alice and Bob again: how can Bob be sure that it was really Alice who sent the message, and not the criminally-minded Eve pretending to be Alice?

This is where digital signatures come in. Before encrypting the message to Bob, Alice can sign the message using her private key; when Bob decrypts the message, he can verify the signature using her public key. Here's how it works:

1. Alice creates a digest of the message — a sort of digital fingerprint. If the message changes, so does the digest.
2. Alice then encrypts the digest with her private key. The encrypted digest is the digital signature.
3. The encrypted digest is sent to Bob along with the message.
4. When Bob receives the message, he decrypts the digest using Alice's public key.
5. Bob then creates a digest of the message using the same function that Alice used.
6. Bob compares the digest that he created with the one that Alice encrypted. If the digests match, then Bob can be confident that the signed message is indeed from Alice. If they don't match, then the message has been tampered with — or isn't from Alice at all.

If this sounds complicated, rest assured that the software makes it all very easy.

What if I need to verify a signature from someone I don't know, or be sure that the key is really theirs?

That's where digital certificates and certificate authorities come in.

Let's start with how it works in PGP. Say that someone claiming to be Bob's acquaintance Carol sends a message to Alice. How does Alice know that Carol is who she claims to be? Carol signed the message with her own private key, which has been digitally signed by Bob (essentially saying, "I trust that this key is valid and hope that you will, too"). Because Alice knows and trusts Bob's key (and therefore his signature), Alice can trust that Carol's key is valid — so the person claiming to be Carol almost certainly really is Carol.

Furthermore, once Alice trusts Carol's key, she can sign it. Then someone who has and trusts Alice's key will be able to trust Carol's. This builds a web of trust among PGP users.

However, this informal web of trust may not be rigorous enough for business or goverment purposes. For these cases, third-party entities known as certificate authorities validate identities and issue certificates. These certificates, signed with the CAs' well-known and trusted keys, can be used to verify someone's identity.

What are digital signatures used for?

Digital signatures can be used anywhere that a system for authenticating data is necessary, i.e. anywhere a handwritten signature could be used but can't or shouldn't for some reason — online banking or payroll transactions, for example, or web registration for college courses. A system of digital signatures and encryption is used in e-commerce all the time, to protect confidential information.

Where can I find more information?

There is a substantial amount of information about digital signatures and public key encryption on the Web, including this non-technical introduction to PGP and this detailed (but accessible) introduction to PKE. Those would be a good start, and will lead you some other good places.

You may also be interested in the story of how Swedish researchers cracked one strong encryption scheme in a cipher challenge. Is this cause for concern? Not really; it only reminds us that encryption standards need to be monitored and updated as codebreakers' computing power increases.

---

Comments? Ideas? Let me know! Send email to sam at afongen dot com. Use my PGP key.
Sam Buchanan, March 2002
http://afongen.com/